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.
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).
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
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...