c++ - Quad tree vs Grid based collision detection

I'm making a 4 player co-op r-type game, and I'm about to implement the collision detection code. I've read a lot of articles and stuff about how to handle collision detection, but I'm having a hard time figuring out what to go with. It seems the quad tree is the most common way to go, but in some resources they mention the grid based solution. For having used a grid for detections in a previous game, I'm comfortable with that, but is it actually better than a quad tree ? I'm not sure which offers best performance, and I've also ran a little benchmark, there is not much difference between both solutions.

Is one better than the other ? or more elegant ? I'm really not sure which one I should use.

Any advice is welcome. Thanks.

Answer

The right answer depends a little bit on the actual game you're designing, and choosing one over the other is really going to require implementing both and doing profiling to find out which one is more time or space efficient on your specific game.

Grid detection seems to only apply to detecting collisions between moving objects and a static background. The biggest advantage to this is that the static background is represented as a contiguous memory array, and each collision lookup is O(1) with good locality if you need to do multiple reads (because entities cover more than one cell in the grid). The disadvantage, if the static background is large, is that the grid can be rather wasteful of space.

If instead you represent the static background as quadtree, then the cost of individual lookups goes up, but because large blocks of the background take up a small amount of space, the memory requirements go down, and so more of the background can sit in the cache. even if it takes 10 times as many reads to do a lookup in such a structure, if it's all in the cache, it'll still be 10 times faster than a single lookup with a cache miss.

If I were faced with the choice? I'd go with the grid implementation, because it's stupid simple to do, better spend my time on other, more interesting problems. If I notice that my game is running a little slow, I'll do some profiling and see what could use some help. If it looks like the game is spending a lot of time doing collision detection, I'd try another implementation, like a quadtree (after exhausting all easy fixes first), and find out if that helped.

Edit: I haven't got a clue how grid collision detection relates to detecting collisions of multiple, mobile entities, but instead, i'll answer how a spatial index (Quadtree) improves detection performance over the iterative solution. The naive (and typically perfectly fine) solution looks sort of like this:

foreach actor in actorList:
    foreach target in actorList:
        if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

This obviously has performance around O(n^2), with n the number of actors that are currently alive in the game, including bullets and spaceships and aliens. It can also include small static obstacles.

This works fantastically well so long as the number of such items is reasonably small, but starts to look a little poor when there's more than a few hundred objects to check against. 10 objects results in just 100 collision checks, 100 results in 10,000 checks. 1000 results in one million checks.

A spatial index (like quadtrees) can efficiently enumerate the items it collects according to geometric relationships. this would change the collision algorithm to something like this:

foreach actor in actorList:
    foreach target in actorIndex.neighbors(actor.boundingbox):
       if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

The efficiency of this (assuming a uniform distribution of entities): is usually O(n^1.5 log(n)), since the index takes about log(n) comparisons to traverse, there will be about sqrt(n) neighbors to compare, and there are n actors to check. Realistically, though, the number of neighbors is always quite limited, since if a collision does occur, most of the time one of the objects is deleted, or moved away from the collision. thus you get just O(n log(n)). For 10 entities, you do (about) 10 comparisons, for 100, you do 200, for 1000 you do 3000.

A really clever index can even combine the neighbor search with the bulk iteration, and perform a callback on each intersecting entity. This will give a performance of about O(n), since the index is being scanned once rather than queried n times.