QuadTree (Source Included)
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 Purpouse
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).
The Moral
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.
Enjoy!
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.
May 6th, 2007 at 4:00 pm
Very nice article. I’ll have to check out the implementation
Thanks,
Ziggy
http://www.ziggyware.com
May 7th, 2007 at 8:01 am
“Very nice article”.
Indeed.
May 8th, 2007 at 2:14 pm
Sweet tutorial. Helpful for me since I never really got quadtrees.
May 9th, 2007 at 11:55 am
[quote]
4. 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.
[/quote]
I thought the box was colliding with 12 level 4 nodes in the South-East Quadrant? And another 6 in the North-East Quadrant.
Don’t get me wrong, I think this is a good article. Just checking if I understood this correctly.
May 9th, 2007 at 12:26 pm
Close - if all of the nodes had been partitioned fully (down to level 4), then you would be correct. However, a Quadtree (at least the way I’ve designed mine) only partitions a node when it needs to. You can see in the fourth picture that the north-east quadrant hasn’t been divided below level 2, and some nodes of the south-east quadrant have only been divided to level 3.
This happens because a node divides itself if it has too many objects when an item enters the node (provided it hasn’t already been partitioned). The node will partition itself, and then try to push down every object it can to its children nodes. The “tree” object doesn’t handle any of this interaction between nodes (except for a few special cases) - it pretty much just acts as a wrapper for the head node.
In fact, in two dimensions, the structure would be pretty much like a simple binary tree without any leaf-depth restriction. So, if you inserted 5 3 1 4 6 into a binary tree (in that order), you’d end up with 5 at depth 1, 3 and 6 at depth 2, and 1 and 4 at depth 3. However, the right-side of the tree would have a maximum depth of 1 (since the 6 is the only number greater than 5 to have been inserted).
Now, that’s not a perfect example, since a Quadtree is a spatially-dependent structure - but I think it helps explain how a Quadtree partitions itself.
Note: There’s nothing stopping you from enforcing equal depth on all leaf nodes of a Quadtree. However, it’s probably not the best idea. You’re going to have to spend a lot of processor cycles and memory to allocate and set up every new node if you have to partition a low-level node, and your Quadtree will grow huge before you know it (which could result in a lot of cache misses when processing the Quadtree, and would give you worse performance). It just depends on your situation.
May 9th, 2007 at 12:45 pm
Thanks for the explanation. That is indeed much more efficient than I thought it worked.
I’m definitely going to use this design in my game and I’ll be sure to put your name in the credits
May 9th, 2007 at 12:59 pm
Let me see your game when it’s finished (or finished enough to play) - I’d like to see how you put this to use. =)
May 9th, 2007 at 3:56 pm
I’m a bit confused by this bit - “One object in a Quadtree. The object is at level 2 of the tree (with level 1 being the entire box).” - how come it’s in level 2? Shouldn’t it be level 1 until a second object comes along to push it down?
May 9th, 2007 at 4:26 pm
Duncan:
Good point - I’ll add a note about that to the article. I prepared the image to demonstrate what happens when an object crosses node boundaries, but didn’t mention that if there had been no other objects in the Quadtree beforehand, then the object would be in level 1, which would be the only level.
You could also be asking about how the objects move around when the tree has already been divided. For example, if the tree had been divided to level 2, all objects were removed, and then a new object was added, what would happen? In my examples, I automatically push the object to the lowest possible level when entering a node. You could also place objects at the top-level when they move, and then move them down as top-level nodes become too full.
Again, I think which route you take depends on what you’re using the Quadtree for. With a relatively full Quadtree, it might be best to automatically push items down to the lowest level so you don’t run into full nodes whenever something moves - which would require you to keep jumping around between different functions. However, for an emptier Quadtree or one in which you expect fewer full nodes to occur (e.g. a landscape stored in a Quadtree, where you just want the query functions), you might be better off just pushing objects to the highest-level node and letting the nodes decide when they need to push objects down.
I chose to push items to the lowest level when they enter a node, but different scenarios might require different solutions.
May 9th, 2007 at 5:18 pm
Yeah, it took me a while to realize it seems like everywhere has a slightly different idea about the reality of implementing quadtrees, which really doesn’t help when you’re struggling to understand the basics of the concept - I was expecting to find a sort of definite groundrock general-case and then look at deviations out from it, but it doesn’t look like there really is one. This is a great article and your source code is highly appreciated, but even with them I’m far from confident I could implement one on my own yet. I’ll try to persevere though, it’s a very cool idea.
May 9th, 2007 at 6:12 pm
I think I’ll make a post about actually coding a Quadtree as soon as I finish some finals (and get some more job-hunting stuff together - I’m graduating in a week and looking for a job). If you haven’t done it before, I’d suggest coding a binary search tree with just C# and the Console. If you can make a good BST, you should be able to expand that experience to a Quadtree. It’s the same basic pattern - a main class containing a headNode and an interface to some methods, a node class with some child nodes, insert, remove and search methods, and then the actual data you’re storing in the tree.
To be fair, I coded this in a day during XNA Beta 1 - but then spent a month or so fixing the problems that cropped up, so it’s seen lots of battles. Then I fixed it up for Beta 2, and just now for the current release, while also adding in some performance improvements and separating it from my engine into a generic class. It’s far from perfect, and it’s not the best Quadtree for every use, but it demonstrates the concepts pretty well.
But yah, if you understand the code behind building a good tree data structure, then you should be able to build a Quadtree with a bit of work. Wikipedia has the basic algorithms: < http://en.wikipedia.org/wiki/Binary_search_tree >. You don’t need to worry too much about traversal either, but you should understand it.
(I have no intention of patronizing you if you know all of this already, but I thought the information might be helpful for beginning coders. A good foundation in data structures is really essential for building this sort of thing.)
June 25th, 2007 at 8:36 am
Hi Kyle,
big thanks for this article.
i wrote a small test app:
[code]
Random _rand = new Random(DateTime.Now.Second);
QuadTree m_qt = new QuadTree(new Point(100, 100), 500);
//populate quadtree
for (int i= 0; i (Guid.NewGuid().ToString(),
new Point(_rand.Next(0, 100), _rand.Next(0, 100)),
new Point(10, 10)));
}
List> _resultList = new List>();
Point _point;
//get rectangle for 20 randomly generated points
for (int i= 0; i item in _resultList)
{
Trace.WriteLine(”rect: ” + item.Position);
}
}
[/code]
but thiis app crashed with StackOverflowException.
what’s wrong with this code?
June 25th, 2007 at 8:40 am
sorry, similary chars was deleted…
Random _rand = new Random(DateTime.Now.Second);
QuadTree<string> m_qt = new QuadTree<string>(new Point(100, 100), 500);
//populate quadtree
for (int i= 0; i < 500; i++)
{
m_qt.Insert(new QuadTreePositionItem<string>(Guid.NewGuid().ToString(),
new Point(_rand.Next(0, 100), _rand.Next(0, 100)),
new Point(10, 10)));
}
List<QuadTreePositionItem<string>> _resultList = new List<QuadTreePositionItem<string>>();
Point _point;
//get rectangle for 20 randomly generated points
for (int i= 0; i < 20; i++)
{
_point = new Point(_rand.Next(0, 100), _rand.Next(0, 100));
m_qt.GetItems(_point, ref _resultList);
Trace.WriteLine(”———————–”);
Trace.WriteLine(”Point: ” + _point);
foreach (QuadTreePositionItem<string> item in _resultList)
{
Trace.WriteLine(”rect: ” + item.Position);
}
}
August 30th, 2007 at 4:29 pm
Hello,
I want to thank you for the explaination of the quadtrees - it helped me out very much. I still have a performance question:
I want to add about 3000 objects to the tree and it gets stuck, it seems to do nothing anymore, could there be an error? I thought it would be no problem to handle this amount of objects (=parents, right?).
Well, I think it is a problem that many nodes get pushed down during time and this is costly. Is there a good way to optimize this?
Thanks in advance,
Bye, Tom
September 10th, 2007 at 2:54 am
Tom:
Sorry I didn’t respond earlier - I’ve been busying myself so much and haven’t looked at my website lately!
As to your question: you’re most likely experiencing an issue with allocating nodes in the tree…especially if you’re moving that many things around at once, and ESPECIALLY if you’re running this on the Xbox. While a Quadtree can handle that many objects, mine isn’t optimized enough to do so gracefully.
The easy method would be to pre-divide all Quadtree nodes so you don’t have to allocate anything while inserting / moving items (for any real-life situation I’d actually recommend this) - but you still end up with really deep leaves, which can take time to traverse, especially in the event that you resize your world (since my Quadtree uses a very naive resizing algorithm where it just rebuilds the whole thing).
Alternatively, you can increase the leaf size, so you can put more items in a node before it divides. You still end up with the same problem though.
I’d suggest making markers at every 100 objects or so and see how the Quadtree is dividing. Quadtrees handle distributed data really well - but when objects clump up is when Quadtrees have problems…especially on object boundaries.
I dunno - I’d need to know more about what you’re doing to really help you come up with a better solution.
October 23rd, 2007 at 2:55 am
Thanks a lot for this article; it really gave me the boost I needed to finally start implementing a quad tree class. Just a couple questions:
1) You said: “However, if there was an object on the middle line on the left (at level 1)”. I’m not sure which “middle line on the left” you’re referring to. Could you clarify this a bit?
2) Just to be clear, as object positions change, the quad tree will have to update their place in the tree, right? If you have a ton of objects moving around (as in the hypothetical massively-multiplayer Pong game), wouldn’t this cause a lot of churn inside the quad tree? It seems as though the quad tree would become stale with every game update, and would essentially need to be re-examined every frame. Is this true?
October 23rd, 2007 at 9:23 pm
Mike:
1) Basically, when an object is on a boundary, it will be returned as if it were in the level above (e.g. a box on a boundary of two level-2 areas will be returned for the encompassing level 1 area above it). In this case, it may be that when querying for an object in the bottom-right box, you get some object that’s on the top-middle, since it’s on the level above it. A pretty simple IsNear check can help you cull those, though.
2) Well, lets see. If you mean you’ll have to find all objects in all nodes every time and move them around, then no. If you set up a two-way relationship, objects can notify the tree-node they’re in when they need to be moved, and that tree node can communicate with its parent and children to help move the object. You’re switching data around a lot, yes, but if you program it cleverly, it shouldn’t be a huge issue (my example is programmed for understanding, not best practices!)
If you’re talking about the tree being restructured and items moving around a lot, then yes, and this is the biggest problem with quadtrees (at least with mine!). The QuadTree is constantly updating its structure as objects move through it, creating lots of nodes that will most of the time be empty (i.e. wasted space). If you don’t remove nodes (or remove them only after they’ve been stale for a while - like garbage collecting) you won’t have as much of a problem with QuadTree nodes. However, dynamic data structures can be a mess on the Xbox, because of the garbage collection, so if you’re implementing a QuadTree for the Xbox, I suggest you:
a) Use structs for anything that’s going to change a lot, since they don’t allocate on the heap.
b) Use arrays instead of lists, so you don’t have the problem of dynamic list garbage.
Basically, how you implement the QuadTree depends on your needs. I mentioned in the comments here that you could also just pre-allocate the entire tree structure so you don’t have the tree changing at all during execution.
So basically, there’s no silver bullet for Quadtrees - you’re going to have to make it suit your needs, and make sure you really need a Quadtree.
November 5th, 2007 at 8:09 am
I’ve only seen quad tree examples for games and collision detection, i’m more of an application developer, and am developing an app with a large canvas (think huge excel document or 100 page word document), and need to virtualize the UI because the canvas is so big. Obviously i’ll need some kind of function that, given the current viewport’s location and size, will return all the objects that should be visible at this time. Would quad trees be a good fit for this application, or would other algorithms be more appropriate? The objects wouldn’t move very often, but the four corners of the viewport would move A LOT.
Thanks!
Todd Wilder
November 7th, 2007 at 5:53 pm
Todd:
Some sort of tree structure would probably work well, especially if things aren’t moving a lot (meaning you can optimize the tree for querying).
You could also keep the objects in a list sorted on X, and then grab all objects between the left and right side of the viewport, and then prune out objects above the top or below the bottom of the viewport. Whenever your viewport moved, you could add items in the new area (newViewport - oldViewport) to the visible list, and prune items from the list that aren’t visible anymore. That might be faster than a QuadTree for your purposes (Though some combination of the two methods might be even faster).
May 28th, 2008 at 8:29 pm
Hey Kyle!
Thanks for the excellent article with very readable code to boot! I am curious about a few things at the moment…
I am planning to use a quad tree for collision detection and and considering pre-partitioning the tree as to not require many objects to be created during run-time. That being said, would all objects have to be in leaf nodes of the tree for this to be feasible, or could the larger sized objects remain in higher level nodes, while smaller ones exist in leaf nodes? I am not sure if the question actually makes sense, but it is something that I am trying to work through semantically at the moment. Thanks again!
-Josh
June 1st, 2008 at 6:12 pm
Yah, you can have the objects in any level of the tree - it’s just best if they’re in the leaf nodes, since you can eliminate the most collision checks if they are (in fact, the closer to the leaves the better).
December 16th, 2008 at 12:31 pm
[...] More info about quadtrees, including source: http://www.kyleschouviller.com/wsuxna/quadtree-source-included/ [...]
June 8th, 2009 at 3:37 pm
What happens to a tiny square which spans the centre of the quadtree?
it will always be allocated to level 0 ??
and that means it will be returned even for your query above
and that is true for all objects spanning dividing lines in the quadtree
it does not work
plus it is no good for dynamic objects as it takes too long to shuffle everything about when things move
the classic quadtree you describe is almost no use in real life
why not think up a variation that works properly and then write a good article about a good spatial index
instead of a good article about a bad spatial index
June 16th, 2009 at 12:18 pm
Jack,
Thanks for the “good article” comments.
You’re correct that items spanning dividing lines will be allocated in the level above the dividing line, which may be as high as level 0. If this isn’t optimal for the type of objects in the scene, then a quadtree probably isn’t a good solution.
My implementation is pretty old, and doesn’t implement a lot of performance considerations you’d want to make for XNA and especially the Xbox.
However, that’s not the purpose of the implementation, or this article. A quadtree is a good introduction to spatial trees, and can in fact be fairly useful in certain situations. The tree I’ve described isn’t optimal for most situations, but it’s not meant to explore those - just the basic concepts of a quadtree. I leave the specific variation as an exercise to the reader.
September 14th, 2009 at 4:58 pm
Nice tutorial it helped me alot! but i still got a question.
Just like your example above I have a quadtree with nodes that hold 1 object each, what happen if i add 2 objects to the tree and both of them cannot fit entirely into the lower level, and both of them got to stay in level.
September 26th, 2009 at 3:15 am
[...] en el caso en el que dos objetos se encuentren en el mismo voxel. ¿Parecido con el Quadtree? Bastante, la diferencia está en que aquí no hay voxels [...]
October 20th, 2009 at 10:03 am
thank you so much, it helps me how to make store my world game. Thanks,
October 25th, 2009 at 12:12 am
Just wondering, but you mentioned changing the passing of Lists to use the ref keyword. Isn’t that unnecessary, since List is a reference type? As far as I understand it, adding the keyword is only necessary when dealing with value types, which are copied by default.
Otherwise, great post. Probably the best run-down and tutorial on Quadtrees I have ever read. I implemented your system awhile back on a game project for class that had several hundred moving particles of different scales all doing collision, and with modifications to handle position changing it worked amazingly well. There was a point where having lots of empty nodes was a problem, but running a quick cull on all empty nodes each frame solved the issue.
December 24th, 2009 at 5:31 am
gg dude