Jump to content
  • Advertisement
Sign in to follow this  
Bombshell93

how to know what is in octree space?

This topic is 2571 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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)));
}
} }

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!