Geographic Grid Registration - An alternative to Quadtrees and Octrees

I guess you know what Octrees and Quadtrees are so wont go into too much detail on them here, but they are basically a great way to hold static (none moving) game objects in groups for the use of culling and the like. As stated this is great for game objects that don't move, terrain, buildings and trees etc... So what you could do is only draw the objects that are in your node of the tree and so you don't have to send the every object in the game to the GPU, just the ones in your bit. This is great for none moving object as the tree places the objects in the correct node as they are added, but if it moves position and into an adjacent node you have to re build the tree as it is based on a maximum number of objects in a node and so can result in a rebuild of the tree each time objects move.

Geographic Grid Registration (GGR) I think is a good alternative to this as it will handle both static and dynamic game objects. What it does is split the game world up into a grid, objects then register and un-register in the grid nodes as they move between them. So all I have to do is request all the objects that are in my node (or the nodes I can see) from the GGR system. This reduces the number of objects you need to check against for collision, LOS and even culling.

For example, if you have 10 objects in the game a LOS or collision check will require you to make 10 * 9 checks, 100 would result in 100 * 99 and so on, so not a great way to go. With GGR you may only have 10 of the 100 objects in your node and so you only need to many 90 checks rather than 999000 checks.
So I have decide to have a go at writing one and this is my first version, as ever I don't think it is perfect, but it does the job. I have written 2 types of GGR, a 3D and a 2D version, the principles are exactly the same so I will just describe the 3D version here. The only real difference is naturally the coordinate system; Vector3 as opposed to Vector2, and the bounds checking; BoundingBox rather than Rectangles.

So to the code, first off we need a base class that our game objects can derive from and so be used by the GGR system, the base class for this I have called GridObject3D, this object has all the basics needed, position,scale, and so we know if it has moved or not a last position and a field that gets set if they are not the same HasMoved. In this example it also has methods to draw it's bounds.

GridObject3D

public class GridObject3D
{
BasicEffect shader;

public Color boxColor = Color.Red;

private Vector3 lastPos;
public Vector3 Position;
public Vector3 Scale;
public bool HasMoved;
public Model Mesh;

protected VertexPositionColor[] points;
protected short[] index;

private BoundingBox myDrawBounds;
public List<BoundingBox> Bounds
{
get
{
if (Mesh != null)
{
List<BoundingBox> bounds = (List<BoundingBox>)((object[])Mesh.Tag)[0];
List<BoundingBox> redBounds = new List<BoundingBox>(bounds.Count);
for (int b = 0; b < bounds.Count; b++)
redBounds.Add(new BoundingBox((bounds[b].Min * Scale) + Position, (bounds[b].Max * Scale) + Position));

return redBounds;
}
else
{
List<BoundingBox> bounds = new List<BoundingBox>();
bounds.Add(new BoundingBox(-Vector3.One + Position, Vector3.One + Position));

return bounds;
}
}
}

public void Update(GameTime gameTime)
{
if (lastPos != Position)
HasMoved = true;
else
HasMoved = false;

lastPos = Position;

float ang = (float)gameTime.TotalGameTime.TotalSeconds;
//ang = 10;
float x = ((float)Math.Cos(ang) / 10);
float z = ((float)Math.Sin(ang) / 10);

Position += new Vector3(x, 0, z);
}

public GridObject3D()
{

}
public void DrawBounds(GraphicsDevice myDevice, List<BoundingBox> bounds)
{
if (shader == null)
shader = new BasicEffect(myDevice, null);

for (int b = 0; b < bounds.Count; b++)
{
myDrawBounds = bounds[b];
BuildBoxCorners();

myDevice.VertexDeclaration = new VertexDeclaration(myDevice, VertexPositionColor.VertexElements);

shader.World = Matrix.Identity;
shader.View = Camera.myView;
shader.Projection = Camera.myProjection;
shader.DiffuseColor = bounds[b].Min;
shader.DiffuseColor = boxColor.ToVector3();


shader.Begin(SaveStateMode.SaveState);
for (int pass = 0; pass < shader.CurrentTechnique.Passes.Count; pass++)
{
shader.CurrentTechnique.Passes[pass].Begin();
myDevice.DrawUserIndexedPrimitives<VertexPositionColor>(PrimitiveType.LineList, points, 0, 8, index, 0, 12);
shader.CurrentTechnique.Passes[pass].End();
}
shader.End();
}
}
protected void BuildBoxCorners()
{
points = new VertexPositionColor[8];

Vector3[] corners = myDrawBounds.GetCorners();

points[0] = new VertexPositionColor(corners[1], Color.Green);
points[1] = new VertexPositionColor(corners[0], Color.Green);
points[2] = new VertexPositionColor(corners[2], Color.Green);
points[3] = new VertexPositionColor(corners[3], Color.Green);
points[4] = new VertexPositionColor(corners[5], Color.Green);
points[5] = new VertexPositionColor(corners[4], Color.Green);
points[6] = new VertexPositionColor(corners[6], Color.Green);
points[7] = new VertexPositionColor(corners[7], Color.Green);

short[] inds = {
0, 1, 0, 2, 1, 3, 2, 3,
4, 5, 4, 6, 5, 7, 6, 7,
0, 4, 1, 5, 2, 6, 3, 7
};

index = inds;
}
}

GridObject 2D

public class GridObject2D
{
private static int ID = 0;
private string myID;
public Color boxColor = Color.Red;
private int size = 50;

private Vector2 lastPos;
public Vector2 Position;
public Vector2 Scale;
public bool HasMoved;
public Texture2D Texture;

private Vector2 origin;

public Rectangle Bounds
{
get
{
Vector2 pos = Position - origin;

if (Texture != null)
return new Rectangle((int)pos.X, (int)pos.Y, (int)Texture.Width, (int)Texture.Height);
else
return new Rectangle((int)pos.X, (int)pos.Y, 1, 1);
}
}

public void Update(GameTime gameTime)
{
if (lastPos != Position)
HasMoved = true;
else
HasMoved = false;

lastPos = Position;

float ang = (float)gameTime.TotalGameTime.TotalSeconds;

float x = ((float)Math.Cos(ang) / 1);
float y = ((float)Math.Sin(ang) / 1);

if (myID != "[1]")
Position += new Vector2(x, y);

}

public GridObject2D()
{
ID++;
myID = string.Format("[{0}]", ID);
}

public void LoadContent(GraphicsDevice myDevice)
{
if (Texture == null)
{
boxColor = new Color(boxColor.R, boxColor.G, boxColor.B, (byte)127);
Texture = new Texture2D(myDevice, size, size, 1, TextureUsage.None, SurfaceFormat.Color);
Color[] data = new Color[size * size];

for (int x = 0; x < size * size; x++)
data[x] = boxColor;

Texture.SetData<Color>(data);

origin = new Vector2(Texture.Width / 2, Texture.Height / 2);
}
}

public void DrawBounds(GraphicsDevice myDevice, SpriteBatch spriteBatch, SpriteFont font)
{
// Draw objects texture.
spriteBatch.Draw(Texture, new Rectangle((int)Position.X, (int)Position.Y, size, size), new Rectangle(0, 0, Texture.Width, Texture.Height), Color.Blue, 0, origin, SpriteEffects.None, 0);

// Draw objects bounds.
spriteBatch.Draw(Texture, Bounds, new Rectangle(0, 0, Texture.Width, Texture.Height), Color.White, 0, Vector2.Zero, SpriteEffects.None, 0);

// Draw ovjects ID.
spriteBatch.DrawString(font, myID, new Vector2((int)Bounds.X + (25 - font.MeasureString(myID).X / 2), (int)Bounds.Y + (25 - font.MeasureString(myID).Y / 2)), Color.White);
}
}

Now we need a manager to look after the grid an keep our object in line. I have it derived from DrawableGameComponent, but should just be GameComponent as there is no need to have the draw methods, they are here as a guide so you can see the grid in the world. By the way, with all the bounds drawing on it slows the thing down a fair bit (well on my crappy lappy it does). Also you will see in here a lump of code commented out, I was going to have it so an object could be registered in more than one zone/node, but when you have a lot of objects it gives the FPS a bit of a kicking, so removed it...for now.


Grid3DManager

public class Grid3DManager : DrawableGameComponent
{
BasicEffect shader;
private Vector3 gridDimensions = Vector3.Zero;
private BoundingBox gridElementSize = new BoundingBox();

public Dictionary<Vector3, BoundingBox> theGrid;
public Dictionary<Vector3, List<GridObject3D>> gridObjects;
public List<GridObject3D> listObjects;
public Dictionary<GridObject3D, List<Vector3>> objectRegisteredZones;
public List<BoundingBox> bounds = new List<BoundingBox>();

public Grid3DManager(Game game, Vector3 dimensions, BoundingBox ElementSize)
: base(game)
{
gridDimensions = dimensions;
gridElementSize = ElementSize;

buildGrid();
}


private void buildGrid()
{
// Build the grid.
gridObjects = new Dictionary<Vector3, List<GridObject3D>>();
theGrid = new Dictionary<Vector3, BoundingBox>();
listObjects = new List<GridObject3D>();
bounds = new List<BoundingBox>();
objectRegisteredZones = new Dictionary<GridObject3D, List<Vector3>>();

Vector3 width = ((-gridElementSize.Min + gridElementSize.Max));

for (int x = 0; x < gridDimensions.X; x++)
{
for (int y = 0; y < gridDimensions.Y; y++)
{
for (int z = 0; z < gridDimensions.Z; z++)
{
Vector3 gridRef = new Vector3(x, y, z);
Vector3 pos = gridRef * width;
pos -= (width * gridDimensions) / 2 - (width / 2);
BoundingBox locBounds = new BoundingBox(gridElementSize.Min + pos, gridElementSize.Max + pos);
theGrid.Add(gridRef, locBounds);
gridObjects.Add(gridRef, new List<GridObject3D>());
bounds.Add(locBounds);
}
}
}
}
protected override void LoadContent()
{

shader = new BasicEffect(Game.GraphicsDevice, null);
base.LoadContent();
}

public override void Update(GameTime gameTime)
{
// Check if object has moved. If it has, re register.
for (int i = 0; i < listObjects.Count; i++)
{
if (listObjects[i].HasMoved)
RegisterObject(listObjects[i]);
}

base.Update(gameTime);
}

public void AddObject(GridObject3D obj)
{
listObjects.Add(obj);
objectRegisteredZones.Add(obj, new List<Vector3>());
RegisterObject(obj);
}

private Vector3 GetGridRef(GridObject3D obj)
{
Vector3 gridRef = Vector3.Zero;

for (int x = 0; x < gridDimensions.X; x++)
{
for (int y = 0; y < gridDimensions.Y; y++)
{
for (int z = 0; z < gridDimensions.Z; z++)
{
Vector3 checkRef = new Vector3(x, y, z);
ContainmentType ctp = theGrid[checkRef].Contains(obj.Bounds[0]);
if (ctp == ContainmentType.Contains || ctp == ContainmentType.Intersects)
return checkRef;
}
}
}
return gridRef;
}

private void RegisterObject(GridObject3D obj)
{
bool registered = false;
Vector3 gridRef = Vector3.Zero;
List<GridObject3D> objList;

// Get my zones.
List<Vector3> registeredZones = new List<Vector3>();

if (objectRegisteredZones.ContainsKey(obj))
registeredZones = objectRegisteredZones[obj];

// Am I already registered?
if (registeredZones.Count == 0)
{
gridRef = GetGridRef(obj);
registered = false;
}
else
registered = true;

// If not then find my initial place in the grid..
if (!registered)
{
// Register with this grid ref.
objList = gridObjects[gridRef];
objList.Add(obj);
gridObjects[gridRef] = objList;
registeredZones.Add(gridRef);
objectRegisteredZones[obj] = registeredZones;
}
else // If so, then am I still in these zones?
{
for (int r = 0; r < registeredZones.Count; r++)
{
for (int b = 0; b < obj.Bounds.Count; b++)
{
if (!theGrid[registeredZones[r]].Intersects(obj.Bounds[b]))
{
// Remove from this ref
// Remove me from the object list in the ref.
objList = gridObjects[registeredZones[r]];
objList.Remove(obj);
gridObjects[registeredZones[r]] = objList;

// Remove my registration with this ref.
registeredZones.Remove(registeredZones[r]);
objectRegisteredZones[obj] = registeredZones;
}
}
}
}
// Am I also in neigbouring zones?
for (int r = 0; r < registeredZones.Count; r++)
{
Vector3 thisGridRef = registeredZones[r];
for (int x = (int)thisGridRef.X - 1; x <= thisGridRef.X + 1; x++)
{
for (int y = (int)thisGridRef.Y - 1; y <= thisGridRef.Y + 1; y++)
{
for (int z = (int)thisGridRef.Z - 1; z <= thisGridRef.X + 1; z++)
{
if (x >= 0 && x < gridDimensions.X && y >= 0 && y < gridDimensions.Y && z >= 0 && z < gridDimensions.Z)
{
Vector3 checkingGridRef = new Vector3(x, y, z);
if (!registeredZones.Contains(checkingGridRef))
{
for (int b = 0; b < obj.Bounds.Count; b++)
{
if (theGrid[checkingGridRef].Intersects(obj.Bounds[b]))
{
// Register with this grid ref.
objList = gridObjects[checkingGridRef];
objList.Add(obj);
gridObjects[checkingGridRef] = objList;
registeredZones.Add(checkingGridRef);
objectRegisteredZones[obj] = registeredZones;
}
}
}
}
}
}
}
}
}

public List<GridObject3D> GetObjectsInMyZone(GridObject3D obj)
{
List<Vector3> registeredZones = new List<Vector3>();
List<GridObject3D> objList = new List<GridObject3D>();

if (objectRegisteredZones.ContainsKey(obj))
registeredZones = objectRegisteredZones[obj];

if (registeredZones.Count > 0)
{

for (int z = 0; z < registeredZones.Count; z++)
{
for (int o = 0; o < gridObjects[registeredZones[z]].Count; o++)
{
if (gridObjects[registeredZones[z]][o] != obj)
objList.Add(gridObjects[registeredZones[z]][o]);
}
}
}
return objList;
}

public override void Draw(GameTime gameTime)
{
DrawBounds(base.Game.GraphicsDevice, bounds);
base.Draw(gameTime);
}

BoundingBox myDrawBounds;
protected VertexPositionColor[] points;
protected short[] index;
private void DrawBounds(GraphicsDevice myDevice, List<BoundingBox> bounds)
{
for (int b = 0; b < bounds.Count; b++)
{
myDrawBounds = bounds[b];
BuildBoxCorners();

base.Game.GraphicsDevice.VertexDeclaration = new VertexDeclaration(base.Game.GraphicsDevice, VertexPositionColor.VertexElements);

shader.World = Matrix.Identity;
shader.View = Camera.myView;
shader.Projection = Camera.myProjection;
shader.DiffuseColor = bounds[b].Min;
shader.DiffuseColor = Color.Gold.ToVector3();


shader.Begin(SaveStateMode.SaveState);
for (int pass = 0; pass < shader.CurrentTechnique.Passes.Count; pass++)
{
shader.CurrentTechnique.Passes[pass].Begin();
myDevice.DrawUserIndexedPrimitives<VertexPositionColor>(PrimitiveType.LineList, points, 0, 8, index, 0, 12);
shader.CurrentTechnique.Passes[pass].End();
}
shader.End();
}
}
protected void BuildBoxCorners()
{
points = new VertexPositionColor[8];

Vector3[] corners = myDrawBounds.GetCorners();

points[0] = new VertexPositionColor(corners[1], Color.Green);
points[1] = new VertexPositionColor(corners[0], Color.Green);
points[2] = new VertexPositionColor(corners[2], Color.Green);
points[3] = new VertexPositionColor(corners[3], Color.Green);
points[4] = new VertexPositionColor(corners[5], Color.Green);
points[5] = new VertexPositionColor(corners[4], Color.Green);
points[6] = new VertexPositionColor(corners[6], Color.Green);
points[7] = new VertexPositionColor(corners[7], Color.Green);

short[] inds = {
0, 1, 0, 2, 1, 3, 2, 3,
4, 5, 4, 6, 5, 7, 6, 7,
0, 4, 1, 5, 2, 6, 3, 7
};

index = inds;
}
}

Grid2DManager

public class Grid2DManager : DrawableGameComponent
{
BasicEffect shader;
private Vector2 gridDimensions = Vector2.Zero;
private Rectangle gridElementSize = new Rectangle();

public Dictionary<Vector2, Rectangle> theGrid;
public Dictionary<Vector2, List<GridObject2D>> gridObjects;
public List<GridObject2D> listObjects;
public Dictionary<GridObject2D, List<Vector2>> objectRegisteredZones;
public List<Rectangle> bounds = new List<Rectangle>();

SpriteBatch spriteBatch;
Texture2D pixel;

public Grid2DManager(Game game, Vector2 dimensions, Rectangle ElementSize)
: base(game)
{
gridDimensions = dimensions;
gridElementSize = ElementSize;

buildGrid();
}


private void buildGrid()
{
// Build the grid.
gridObjects = new Dictionary<Vector2, List<GridObject2D>>();
theGrid = new Dictionary<Vector2, Rectangle>();
listObjects = new List<GridObject2D>();
bounds = new List<Rectangle>();
objectRegisteredZones = new Dictionary<GridObject2D, List<Vector2>>();

Vector2 width = new Vector2(gridElementSize.Width, gridElementSize.Height);

for (int x = 0; x < gridDimensions.X; x++)
{
for (int y = 0; y < gridDimensions.Y; y++)
{
Vector2 gridRef = new Vector2(x, y);
Vector2 pos = gridRef * width;
Rectangle locBounds = new Rectangle((int)(gridElementSize.Left + pos.X), (int)(gridElementSize.Top + pos.Y), (int)gridElementSize.Width, (int)gridElementSize.Height);
theGrid.Add(gridRef, locBounds);
gridObjects.Add(gridRef, new List<GridObject2D>());
bounds.Add(locBounds);
}
}
}
protected override void LoadContent()
{
shader = new BasicEffect(Game.GraphicsDevice, null);
pixel = new Texture2D(Game.GraphicsDevice, 1, 1, 0, TextureUsage.None, SurfaceFormat.Color);
Color[] data = new Color[1];
data[0] = Color.White;

pixel.SetData<Color>(data);

spriteBatch = new SpriteBatch(Game.GraphicsDevice);

base.LoadContent();
}

public override void Update(GameTime gameTime)
{
// Check if object has moved. If it has, re register.
for (int i = 0; i < listObjects.Count; i++)
{
if (listObjects[i].HasMoved)
RegisterObject(listObjects[i]);
}

base.Update(gameTime);
}

public void AddObject(GridObject2D obj)
{
listObjects.Add(obj);
objectRegisteredZones.Add(obj, new List<Vector2>());
RegisterObject(obj);
}

private Vector2 GetGridRef(GridObject2D obj)
{
Vector2 gridRef = Vector2.Zero;

for (int x = 0; x < gridDimensions.X; x++)
{
for (int y = 0; y < gridDimensions.Y; y++)
{
Vector2 checkRef = new Vector2(x, y);
if (theGrid[checkRef].Intersects(obj.Bounds))
return checkRef;
}
}
return gridRef;
}

private void RegisterObject(GridObject2D obj)
{
bool registered = false;
Vector2 gridRef = Vector2.Zero;
List<GridObject2D> objList;

// Get my zones.
List<Vector2> registeredZones = new List<Vector2>();

if (objectRegisteredZones.ContainsKey(obj))
registeredZones = objectRegisteredZones[obj];

// Am I already registered?
if (registeredZones.Count == 0)
{
gridRef = GetGridRef(obj);
registered = false;
}
else
registered = true;

// If not then find my initial place in the grid..
if (!registered)
{
// Register with this grid ref.
objList = gridObjects[gridRef];
objList.Add(obj);
gridObjects[gridRef] = objList;
registeredZones.Add(gridRef);
objectRegisteredZones[obj] = registeredZones;
}
else // If so, then am I still in these zones?
{
for (int r = 0; r < registeredZones.Count; r++)
{
if (!theGrid[registeredZones[r]].Intersects(obj.Bounds))
{
// Remove from this ref
// Remove me from the object list in the ref.
objList = gridObjects[registeredZones[r]];
objList.Remove(obj);
gridObjects[registeredZones[r]] = objList;

// Remove my registration with this ref.
registeredZones.Remove(registeredZones[r]);
objectRegisteredZones[obj] = registeredZones;
}
}
}
// Am I also in neigbouring zones?
for (int r = 0; r < objectRegisteredZones[obj].Count; r++)
{
gridRef = objectRegisteredZones[obj][r];
for (int x = (int)gridRef.X - 1; x < gridRef.X + 2; x++)
{
for (int y = (int)gridRef.Y - 1; y < gridRef.Y + 2; y++)
{
if (x >= 0 && x < gridDimensions.X && y >= 0 && y < gridDimensions.Y)
{
Vector2 thisRef = new Vector2(x, y);
if (!registeredZones.Contains(thisRef))
{
if (theGrid[thisRef].Intersects(obj.Bounds))
{
// Register with this grid ref.
objList = gridObjects[thisRef];
objList.Add(obj);
gridObjects[thisRef] = objList;
registeredZones.Add(thisRef);
objectRegisteredZones[obj] = registeredZones;
}
}
}
}
}
}
}

public List<GridObject2D> GetObjectsInMyZone(GridObject2D obj)
{
List<Vector2> registeredZones = new List<Vector2>();
List<GridObject2D> objList = new List<GridObject2D>();

if (objectRegisteredZones.ContainsKey(obj))
registeredZones = objectRegisteredZones[obj];

if (registeredZones.Count > 0)
{
for (int z = 0; z < registeredZones.Count; z++)
{
for (int o = 0; o < gridObjects[registeredZones[z]].Count; o++)
{
if (gridObjects[registeredZones[z]][o] != obj)
{
if (!objList.Contains(gridObjects[registeredZones[z]][o]))
objList.Add(gridObjects[registeredZones[z]][o]);
}
}
}
}

return objList;
}

public override void Draw(GameTime gameTime)
{
DrawBounds(base.Game.GraphicsDevice, bounds);
base.Draw(gameTime);
}

protected VertexPositionColor[] points;
protected short[] index;
private void DrawBounds(GraphicsDevice myDevice, List<Rectangle> bounds)
{
spriteBatch.Begin(SpriteBlendMode.AlphaBlend, SpriteSortMode.Immediate, SaveStateMode.SaveState);
// Draw squares...
for (int b = 0; b < bounds.Count; b++)
{
spriteBatch.Draw(pixel, bounds[b], Color.SkyBlue);
// Draw top hriz
spriteBatch.Draw(pixel, new Rectangle(bounds[b].X, bounds[b].Y, bounds[b].Width, 1), Color.White);
// Draw left vert
spriteBatch.Draw(pixel, new Rectangle(bounds[b].X, bounds[b].Y, 1, bounds[b].Height), Color.White);
// Draw right vert
spriteBatch.Draw(pixel, new Rectangle(bounds[b].X + bounds[b].Width, bounds[b].Y, 1, bounds[b].Height), Color.White);
// Draw bottom hriz
spriteBatch.Draw(pixel, new Rectangle(bounds[b].X, bounds[b].Y + bounds[b].Height, bounds[b].Width, 1), Color.White);

}
spriteBatch.End();
}
}

So when object are added to the manager they are registered on the grid, in the update call, if an object has moved then it is re-registered with the grid, if it has moved out of it's current node/zone it un-registers with that zone and then the surrounding zones are checked and if intersected, are registered next time through is registered in the new node/zone. You can then use the GetObjectsInMyZone method to return all the other object in your zone so you can check for collision etc..

An issue I have just spotted here is that as objects come to rest, if they have just left the zone and are seen as not having moved by the time it comes round to the update then they could "fall" off the grid, I imagine the chances of this are slim, but will have a think on how I will resolve this, maybe have a flag in the object saying it is registered and it not then it get's registered giving me an extension to the if condition in the Update call, just spotted this while writing this post, so will be fixed in the next version :P


Now fixed as code now checks surrounding grids.

Think I will take a look at BSP (Binary Space Partition) next see if I can come up with a version for that...
Well I hope you find this post useful or at the very least, it gives you ideas on how to create/implement your own GGR for XNA. I have not put this code into a game yet so I guess it will evolve as I use it, I will post any changes and/or improvements I make on it as I go.

Sample code can be downloaded here

Comments welcome as ever...

I should mentioned that I got the idea for this from (Just found a link to the paper) Game Programming Gems 6, the chapter contributed by Roger Smith of Modelbenders. Thanks Roger :)

Blimey, there must be something wrong with me, there is no YouTube link with this post or pretty pictures!!

Well one now...