Enjoy this tutorial on Quadtrees, explaining how they work and why they’re useful for collision detection. Includes pictures and source code. Comments are highly appreciated.
A Quadtree’s Purpose
Your collision detection solution should operate at successively more accurate levels to be effective. Since each successive level is more accurate, deeper levels require more processing time. Therefore, the rule at each level is to perform as few collision detections as possible. We do this by eliminating unnecessary checks at higher levels. Let me explain with an example.
Imagine a game like Pong, except with a rotating triangular ball. This ball needs to have perfect collision detection with the paddles, which means if any part of the triangle intersects with the paddle, there is a collision. You can’t just do simple radial collision detection, nor can you do rectangle collision detection, because the triangle might not actually be colliding for some collisions detected in those cases. However, performing the triangle-to-paddle collision detection can be expensive to do every frame (I know, not that expensive – but imagine 200 balls with 30 players around a big field with balls also colliding with each other, or something like that). So what are you to do?
The solution is to do several levels of collision detection. First, you’re going to check if the ball is even on the paddle’s side of the line. If it’s not, then obviously it doesn’t need to be checked for a collision. Then, if it is on the paddle’s side, you’ll check if the ball is in the same vertical half of the screen as the paddle. Again, if it’s not, you’re done. You might do this a couple more times, and if you could still be colliding, that’s when you actually perform the expensive detection. With just the two checks, you’ve just reduced 75% of the expensive collision detections to a simple positional check (e.g. Position.X < ScreenMiddle.X).
How a Quadtree Divides Space
The Quadtree is your first line of defense in the two-dimensional collision detection battle. It lets you know with pretty decent accuracy which objects could be colliding. It does this with rectangular bounds checks, which are simple to perform. Once you’ve found out which objects could be colliding, you can then pass those on to a more complex algorithm, like the Separating Axis Theorem, or a pixel-based collision detection algorithm.
A Quadtree works by dividing space into rectangles as objects enter that space. It does this by following a simple rule, which is:
For any node in the Quadtree, the node will be divided further if more than n objects are contained within the node at any time.
With n being a pretty low number, like 1 or 2. When a node divides, it divides into four different rectangles by splitting the node in half horizontally and vertically. Any objects that can fit entirely within one of these new nodes are pushed down (with objects that are on node edges remaining in the higher-level node). These pictures should explain the process.
One object in a Quadtree. The object is at level 2 of the tree (with level 1 being the entire box).
Note: Duncan points out in the comments that this image couldn’t exist unless there had previously been two objects in the Quadtree (since the level 1 box would never have been partitioned). The image is like this to demonstrate an object moving across nodes – which you’ll see in the next image. Look in the comments for further discussion.
Now the object is at level 1, because it can’t fit entirely within a lower-level node.
Two objects in a QuadTree. Note that they are in different nodes, so the space doesn’t need to be divided further.
Now three objects are in the QuadTree. Two objects were in the level 2 node at the top-left, so the node had to be split (since this is a tree with a maximum of one object per node). The objects fit entirely within the new level 3 nodes now.
This image shows the nodes created by an object moving across the space. Notice that as the object passes through the first level 3 node, it divides the space again. Then, as it passes through a level 2 node, it has to divide it twice to be able to satisfy the “only one object per node” rule. Also notice that the object actually passes through every level of Quadtree node in this image – try to figure out how.
So How Does This Help Me?
Well, when it comes time to figure out if some object is colliding with anything else, you’ll want to check the Quadtree to see what items it might be colliding with, so you can then perform a more complicated collision detection check later. You do this by querying the Quadtree with a query box. The Quadtree will then figure out which nodes contain any part of the box, and return a collection of all items within those nodes. So for a query box like this:
The following would happen:
- The box collides with the level 1 node – but there are no objects in level 1.
- The box collides with two level 2 nodes – but there are no objects in them either. However, their child nodes need to be checked now.
- The box collides with four level 3 nodes, and there is one object in them, which is added to the return list. Note that there are no level 3 nodes in the top-right level 2 node, so it is not queried any further.
- Finally, the box is colliding with six level 4 nodes, one of which contains another object. Note that the object we just returned was on an edge, so it was contained within the level 3 node instead of a level 4 node.
So, for this query, two objects would be returned. In this example, all of the returned objects are colliding with the box. However, if there was an object on the middle line on the left (at level 1), it would also be returned, though it clearly does not collide. However, in a world with hundreds of objects, this would be acceptable (as long as everything wasn’t on the line).
If you query the tree with all n objects in the tree, with each query returning log n results, you have reduced the number of expensive collision detections from n-squared (checking every object against every other object) to n log n (the average number of objects returned from this sort of tree query). Sound like big-O notation?
Some Code?! Oh boy!
I updated the QuadTree used in my WSUXNA engine to work with the newest version of XNA, to be generic, and to be a little more efficient than its previous incarnation. It comes in two files – one containing the QuadTree and all related classes, and one containing a floating-point rectangle class, which I needed for this implementation. I’ve tried to comment it as fully as possible, so hopefully you shouldn’t have any problems reading through it – if you do, please, ask questions!
In my Quadtree, I’ve made the query methods take a List by reference, to cut down on the garbage generated by throwing new Lists around every frame. I also perform a simple box collision detection method on every object that might be returned, to reduce the edge-crossing objects problem.
There are three classes in the QuadTree file, two of which you will use. I’ll explain the useful ones:
- QuadTree – The Quadtree. Create a Quadtree with the generic type being the type of object you want to place in the Quadtree. You’ll need to specify your initial world size, which can be at whatever scale you’d like.
- QuadTreePositionItem – A long name for a position class. You’ll need to instantiate and store these in your objects and then add then to the QuadTree by using the QuadTree.Insert method. You can also just store the position item returned by the QuadTree.Insert overload method. To move an object in the QuadTree, just update the Position property in the position item class. The position item also contains a link to its Parent, which is the object that it’s being used by (yah yah, I can see you OO people cringing…but it’s easy to use and understand this way, and isn’t really that horrid). Finally, remember to Delete() the position item when you’re done with it and set your references to it to null – that’ll remove it from the Quadtree and make sure it gets picked up by the garbage collector.
Now, if you need to get a list of items that might be colliding with some item, just query the QuadTree class by using its GetItem methods.
Note: I may update this code later…I’ve tested it a bit, but I haven’t subjected it to really rigorous testing since I removed it from the engine, so it might have a couple bugs. There’s also a few things I’d like to do, like make the node class internal, and possibly extend the QuadTree to return a list of parents when you query it. Go ahead and explore that yourself though Also, comments are highly appreciated, as I’d like this article to be as helpful as possible to everyone who runs across it.