17
\$\begingroup\$

I'm making a 2d platformer with lots of objects at the same time. They're all AABB collision detected. I first tried a quadtree to decrease the number of of objects to check, tried a few different configurations, but it didn't prove as effective as I needed. I implemented a spatial hash and it's way more efficient, the number of objects to check for each collision went down drastically.

Is there a case when doing 2d collision detection using a quadtree is preferable over spatial hashing? According to my tests, it seems spatial hashing always ends up with less objects to be tested for collision?

I haven't done timing over the algorithms, but is hashing simply very expensive or difficult to implement when you're, for example, coding in C? Worth noting is that I'm writing the game in javascript, where you have hashing "for free".

Here's the comparison, did I overlook something?

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
12
\$\begingroup\$

The major advantage of a quad tree is that it allows you to discard whole groups of buckets from consideration very quickly.

For example, let's assume that I have a quad tree with six levels. At its lowest level, that's 32x32 boxes; 1024 boxes comprising that bottom, most-detailed level. For comparison, we'll also consider a "spatial hash" -- a flat grid which also contains 32x32 boxes, 1024 boxes in total. (the quad tree has more than 1024 boxes in total, since it also contains larger boxes at its higher levels)

Let's assume that there are no collidable objects in the system -- all the boxes of our quad tree and our flat grid are completely empty.

If you're testing the collisions of something which is large enough that its bounding box intersects all of those boxes, and you're using a flat grid, you have to check every single one of those 1024 boxes to see if there's even anything in them.

But if you're using a nested quad tree, the very topmost level can tell you that there are no other objects in the system, and so you only have to look at that single box to know that you're not going to find collisions deeper in the tree -- you can stop testing immediately.

Similarly, if the objects only exist in certain regions of the quad tree, the quad tree will naturally guide your search through only potentially relevant boxes, whereas the grid requires you to check every single intersected box, because you have no way to know in advance which grid squares will have objects in them. If much of your quad tree is empty and you're doing large, complicated queries (say, huge camera frustums instead of small, simple rectangles), then you may find that you're iterating over far fewer boxes in total if you do your tests against something using a tree structure, rather than a flat grid. And that can make a big difference.

All of which isn't to imply that a tree structure is always the right choice, of course. Flat grids are ideal for the situation you have in your example -- dense clouds of objects pretty much evenly spread everywhere in the world, and we're doing simple, inexpensive collision tests. Absolutely a grid is likely to be the optimal approach in that case!

Improve this answer
\$\endgroup\$
5
  • 7
    \$\begingroup\$ Laconic summary, for the extremely lazy: Quadtrees handle differently sized objects faster. \$\endgroup\$
    – Anko
    Feb 3, 2014 at 13:42
  • \$\begingroup\$ Thanks, this is an excellent answer! The uniform size of objects was something that I suspected. \$\endgroup\$
    – Chris
    Feb 3, 2014 at 13:57
  • \$\begingroup\$ Actually, you typically will have to search through all levels of the quad tree to check if there are no objects since generally, a level only holds information about objects that both fit entirely inside that level's bounds and does not fit in a lower level. \$\endgroup\$
    – malthe
    May 29, 2019 at 7:11
  • 1
    \$\begingroup\$ @malthe If you insist on using a quad tree implementation which can't early out in this kind of query, then absolutely use a spatial hash instead; you'll save 33% of the memory cost, and you'd have been getting no benefit from it anyhow. Or alternatively, you can loosen up your idealogical purity just a smidge and use a quad tree that can early-out, either by having each node track the number of entities in its children, or else by using a sparse quadtree such that empty nodes are unlinked from the tree until they're needed. Actually. More than five years later. \$\endgroup\$
    – Trevor Powell
    May 30, 2019 at 1:03
  • \$\begingroup\$ @TrevorPowell of course, you're right. I just fell over your guarantee that you only had to look at a single box. This just isn't true because you'll have to pursue those counts. You can find collisions higher up and further down the tree as far as I can tell. \$\endgroup\$
    – malthe
    May 31, 2019 at 6:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .