Continuous Collision Detection

November 18, 2013

Collision detection in game development is something that I've thought about a lot. I remember reading the wikipedia page about collision detection, and they mentioned the difference between "a posteriori" (discrete) and "a priori" (continuous) collision detection. Discrete collision detection is the kind most people use: update positions periodically and check for overlaps. Back when I first saw this, I didn't know exactly what they meant by "continuous collision detection" or how to implement such a thing, so I ignored it.

When I published my first Android game, I learned that using a fixed time-step may not be the best way to make a game. Frame rates fluctuate, so it is better to have a method that can update the game state to any given time. This suggests using a priority queue of timed events that are resolved in chronological order. Some of these events will be invalidated before they can be resolved due to the unforeseen effects of other events. At this point, the appeal of continuous collision detection became clear to me. Collisions would be timed events in a priority queue. The effects of a collision are resolved at the precise moment of collision, which can avoid many problems.

As an example, suppose an arrow is flying towards a wall. With discrete collision detection, if the arrow is moving very quickly, there is a chance that the arrow will bypass the wall altogether and skip to the other side. Even if we use a small enough time-step so that the arrow does not skip the wall, the arrow will be partway through the wall when the collision is detected, so a post-correction step is needed to push the arrow back outside of the wall. If the wall is thin and an enemy is on the other side of the wall, the enemy may be hurt by the arrow if the enemy-arrow collision is tested before the wall-arrow collision, so we need to devise careful rules about the order in which collisions are tested. Continuous collision detection avoids all of these problems, because the two shapes never interpenetrate.

Collider is a library for continuous 2-D collision detection that I developed. I made this for use with a game I'm making named Resplendent Bell, but I thought I would make it an open-source project so that anyone who wants to can use it. It uses some classes in LibGDX, a Java game library I found a few months ago that looks very promising. Currently, Collider only allows circles and axis-aligned rectangles as shapes (no arbitrary polygons), since I think that is all I will need for my game.

There are a lot of other collision detection libraries out there, but I find they are usually in 3-D and coupled with physics engines. In my opinion, realistic physics engines are fairly useless and sometimes detrimental for most games, especially 2-D games. Also, continuous collision detection doesn't seem to be used very often. I wonder if people think it takes up too much computation time. I haven't noticed any performance problems with my code so far. My software has a pretty simple interface and is not intrusive on the user's game design choices. So if you are a game developer and think Collider sounds interesting, give it a try.