The typical way to improve collision-detection time is to adopt a space partitioning scheme.

http://en.wikipedia.org/wiki/Space_partitioning
This is not always a simple thing to do, although the concept behind it is simple.

Basically, you divide the space into two (or more) parts. For example, in a 2D space, you can draw a vertical line down the middle. Now, in order to check for collisions, you only need to check the objects in the left half against other objects in the left half. Same for the right half. This works because there is no possible way for one object to be in the left half and the right half at the same time. In short, nothing in the left half can possibly collide with anything in the right half, and vice versa, so checking for possible collisions is unnecessary: the answer will always be No.

The basic concept can be applied recursively. That is, each half-space can itself be divided in half. And so on, until you reach some practical limit, such as having more sub-spaces than pixels.

While simple in concept, however, the practical aspects get complicated quickly.

First, moving objects can move between subspaces. So an object that started in the left half can end up in the right half. This can happen at any point in time, if the velocity and trajectory of an object are sufficient.

Second, any object that isn't a particle of zero size can overlap a boundary, residing partly in one half and partly in the other half.

Third, any object (even infinitesimal particles) can lie exactly on the boundary between partitions. Objects exactly on the boundary can be adjacent to objects in either space, which means you have to check both subspaces for collisions or other object interactions.

Fourth, if all (or most) objects end up in only one of the halves, then you haven't gained anything. So keeping the subspaces balanced is part of what must be done to manage performance, given the dynamics of the moving objects.

Click to expand...