collision detection - When is a quadtree preferable over spatial hashing?

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? http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

Answer

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!