Collision Detection Efficiency

Question

I've just written my first successful collision detection code, and it works great for a small scene of actors (player + 4-5 obstacles).

However, I realize that since it checks every possible collision for each actor in the scene, it checks each possible collision in the scene twice (Does A collide with B? Does B collide with A?).

With a small number of objects that may be colliding, this is not a problem, but it seems to me that it could slow things down in a very busy scene if every collision is checked twice.

Should I go ahead and rewrite it to check each collision once, or would that be a premature optimization?

Answer 1

First of all, try it. If your game makes use of a large number of objects in the scene and you find that the game is slowing down because of it, that's when you need to worry about it.

To answer the question though, games tend to optimize this by using spatial partitioning (Graphics tends to use techniques to cull objects from rendering, and the same techniques can be used to aid with collision detection).

Havok physics, for example, makes use of two phases in their collision detection. A broadphase and a narrow phase.

The broadphase check is usually a much less computationally expensive test to determine whether two objects are near each other. The narrowphase check then checks the objects that pass the broadphase for actual collisions.

Quadtrees (or octrees) are a good and simple to understand data structure for carrying this out. The broadphase check would determine whether two objects in your list of objects are in the same quadrant. If not, then we can safely ignore collisions between them, otherwise carry out the more expensive check between the two to see whether they are colliding.

There are a number of other data structures you could look into (cell space partitioning, BSP trees, etc), but my first suggestion would be to actually try it out.

Hope that helps!