Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
32 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

how to know what is in octree space?

Started by
4 comments, last by Bombshell93 12 years, 5 months ago
I'm making a 3D co-op survival game for XBLIG using XNA.
naturally I need a way to tell player from ground. This game will have a level editor based around placing blocks and chunks, so naturally I need to also know ground from ground.
because of this I can't just make an octree that checks if there is ground I need to also get the type of ground it is and in some cases the individual identity of that block.
But this is what has always puzzled me about octrees. How do I keep track of what is inside octree elements dynamically?

EDIT: Here is the octree system I have at the moment, the creation and destruction will be a bit harsh, but its only meant to be created and destroyed once per game so I think it should do. Please comment on it, I've not worked with octree's that much.
public class Octree
{
ushort MaxLevel;
OCtreeElement[] Elements;
BoundingBox Box;

public Octree(ushort MaxLevel, BoundingBox Box)
{
Elements = new OCtreeElement[8];
this.Box = Box;
ushort Level = 1;
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
//0,0,0
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
//1,0,0
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
//0,1,0
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
//0,0,1
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,1,0
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
//0,1,1
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,0,1
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,1,1
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
}

public class OCtreeElement
{
public ushort Level;
public BoundingBox Box;
public OCtreeElement[] Elements;
public bool isEnd;
public List<ulong> IDs; //ID's of the entity list

public OCtreeElement(ushort Level, ushort MaxLevel, bool isEnd, BoundingBox Box)
{
this.Level = Level;
this.isEnd = isEnd;
this.Box = Box;
if (isEnd)
{
IDs = new List<ulong>();
}
else
{
Elements = new OCtreeElement[8];
if (Level + 1 == MaxLevel)
{
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
//same as before except isEnd is set true
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
else
{
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
} }

Any and all help is appreciated,
Thanks in advanced,
Bombshell
Advertisement
The same way you would know about the type of object in any other setting.
A virtual function that returns a bitwise flag that tells you what type of object it is.
It only tells you what type of class it is, so all of your terrain chunks will still just be “terrain chunks”, unless they are not the same class.
Once you know a class is a terrain chunk, cast it into that type and call its GetChunkType() (for example) function to get more detail on the type of chunk.


L. Spiro

I restore Nintendo 64 video-game OST’s into HD! https://www.youtube.com/channel/UCCtX_wedtZ5BoyQBXEhnVZw/playlists?view=1&sort=lad&flow=grid

I'm confused,
How would I know what octree elements the block is in?
Consider the block able to move outside of a grid alignment. Able to move in and out of octree elements (moving platforms, doors, etc.)
Having a virtual function is fair enough for getting the type but my main problem is keeping track of things moving between the octree elements.
I'm not sure how I would let the octree know the entity just entered its element without storing a library of pointers in the elements. But I can't use pointers as I plan to release on XBLIG and the xbox does not support unsafe code.

A virtual function that returns a bitwise flag that tells you what type of object it is.

*gurgles* *splutter* *choking*

Back in the good old days of C, one would emulate classes like that: give each struct an integer member at offset 0 that encoded the type, and then process unknown objects with a giant switch statement. A very great deal of the motivation behind the inheritance/virtual method system in C++ is to get away from such a fragile paradigm. There's no excuse for resurrecting that sort of thing, when we have modern, type-safe alternatives to hand - the visitor pattern is your friend.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

okay I've got past my "coders block" I've thought of a not very elegant but get the job done system.
I have an object manager controlling the creation, destruction and recycling of objects. With lists for each object type (World blocks, items, npc's, w/e)
I have an enumeration of each object type and each individual object is given as an ID its own position in the relevant list.

The octree is built around this with lowest level elements containing lists of a struct containing object type (via the enum) and the ID's.
Looking up the objects would be as simple as (just a quick example)
foreach struct S in octreeElements E
{
switch S.enum
{
case block
{
CollisionCheck(ObjectManager.BlockList[ID].boundingbox);
}
case tree
{
CollisionCheck(ObjectManager.TreeList[ID].boundingbox);
}
}

}

I know its nothing amazing, please if you have a better method , let me know :)
Here is the octree system I have at the moment, the creation and destruction will be a bit harsh, but its only meant to be created and destroyed once per game so I think it should do. Please comment on it, I've not worked with octree's that much.
public class Octree
{
ushort MaxLevel;
OCtreeElement[] Elements;
BoundingBox Box;

public Octree(ushort MaxLevel, BoundingBox Box)
{
Elements = new OCtreeElement[8];
this.Box = Box;
ushort Level = 1;
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
//0,0,0
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
//1,0,0
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
//0,1,0
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
//0,0,1
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,1,0
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
//0,1,1
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,0,1
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
//1,1,1
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
}

public class OCtreeElement
{
public ushort Level;
public BoundingBox Box;
public OCtreeElement[] Elements;
public bool isEnd;
public List<ulong> IDs; //ID's of the entity list

public OCtreeElement(ushort Level, ushort MaxLevel, bool isEnd, BoundingBox Box)
{
this.Level = Level;
this.isEnd = isEnd;
this.Box = Box;
if (isEnd)
{
IDs = new List<ulong>();
}
else
{
Elements = new OCtreeElement[8];
if (Level + 1 == MaxLevel)
{
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
//same as before except isEnd is set true
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, true,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
else
{
Vector3 i = Box.Max - Box.Min;
i /= 2 * Level;
Elements[0] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[1] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z)));
Elements[2] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[3] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[4] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z)));
Elements[5] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[6] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
Elements[7] = new OCtreeElement((ushort)(Level + 1), MaxLevel, false,
new BoundingBox(new Vector3(Box.Min.X + i.X, Box.Min.Y + i.Y, Box.Min.Z + i.Z), new Vector3(Box.Min.X + i.X + i.X, Box.Min.Y + i.Y + i.Y, Box.Min.Z + i.Z + i.Z)));
}
} }

This topic is closed to new replies.

Advertisement

Popular Topics

Calin
Avoiding other units without using pathfinding General and Gameplay Programming
black4
Quake 1 source code triangle rasterization General and Gameplay Programming
coulomb
D3D12 Alpha blending not working both ways Graphics and GPU Programming
taby
Post-Newtonian general relativity Math and Physics
gjl
ARM64 Native Calling Convention Return Issue on Apple Silicon AngelCode
timanov
How to build race game For Beginners
Advertisement

Recommended Tutorials

lwm
Generating 2D Navmeshes Artificial Intelligence
agentcox
Why I'll Never Work on First-Person Shooters Again Game Design and Theory
Myopic Rhino
A Practical Guide to Building a Complete Game AI: Volume I Artificial Intelligence
All8Up
Cross Platform Test Driven Development Environment Using CMake (Part 2) General and Gameplay Programming
Jetpeks
From Game Prototype to Release in 2 Months Production and Management

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top