Digit 7

Your source for XNA tutorials and 3D programming ideas.
Home     Shader Tutorials     XNA/C# Downloads     Links      
Blackjack Simulation
Heightmap Generator
Physics Simulator
Procedural Tree Generator
QuadTree
Swarm Intelligence
Matrix Solver
Massive Battle
Quad Tree Space Partitioning



Introduction

     While working on porting over the StarlingSwarm to XNA, I was disappointed with the performance. Not so much for XNA, but because I always wanted it to run faster. I ran some profiling applications on it to find out that the biggest chunk of time was spent avoiding collisions between neighboring starlings. This is because for each starling, I had to check against every other starling and see if it was in range. I couldn't just tell it "Only look at the closest birds because those are the only ones that matter." You can't just tell your computer which ones are close when all you have is a one-dimensional array of starlings. With a quad-tree, however, you are able to do this.
     A quad tree is pretty simple: it takes an area and divides it up into a grid of squares. You start with one big square covering the whole area. Then you divide that into 4 quadrants. You divide each of those quadrants up into smaller quadrants and so on. Once you've broken your grid down into the smallest quadrants, you place your objects inside of them (only the smallest ones though). You're probably asking what the benefit of all this is. With everything partitioned into small bite size chunks like that, I can now tell me computer "Okay, I know I'm in this quadrant, so only check the objects in the same quadrant." Every frame I recalculate which little box each starling is in (since they fly around and can move between boxes). This may seem like a lot of work, but it's much less work than checking N birds against N other birds. With the quad-tree implemented, I was able to put twice as many starlings in the scene at the same frame-rate.

How to Use It

     The QuadTree class I've provided is very simple to use. All you have to do is instantiate it, inherit your objects from the IRenderable class (or use your own. All the QuadTree needs is a class that has a position) and use these three methods.
  1. placeObject( IRenderable o ) - This is how you put an object in the quad tree. You just pass in the object and it will determine which quadrant it needs to be placed into.
  2. clearObjects() - Clears all of the objects from the quad tree. Since every object in my scene is moving, I clear everything. You might want to add some functionality if you have static objects so it doesn't erase them.
  3. getObjectsInQuad( Vector2 pos )  - You pass in a Vector2, it finds the quadrant that vector is in and returns the objects in that quadrant.

Why Use It

     Space partioning is extremely important if you want to maximize the performance of your application. In scenarios where you're doing collision detection, you want to avoid checking as many objects as possible. Space partitioning structures are a fantastic way of reducing the number of checks by a great amount. Like I said before, I was able to double the number of objects on the screen just by using a quad tree.


DOWNLOAD QuadTree.zip HERE
Last Update: 10/14/09