I mentioned in the last post that checking for pairs of colliding objects was O(N^2), and a stress test on the system shows that up very plainly with only a few hundred objects. What I really want is O(N active objects), where an active object is one that is potentially doing something during the frame. And it’s possible to code it that way.
There are a few options:

  • Sweep and prune.
  • Hierarchical structures (quad tree etc).
  • A regular grid.

Sweep and prune is, I think, the best for minimising the number of collision tests performed. It is also pretty good at using frame-to-frame coherence, i.e. if the objects don’t move, they don’t cost anything. On the other hand, it’s a pain to implement and not so good for fast moving objects. A hierarchy might be good for a static world with a wide range of object sizes; in my opinion, it’s good for visibility culling but just wrong for collision detection, which rarely has those properties. A regular grid though, is going to be pretty good all round, only needing a bit of tweaking to get the grid spacing right. So, in pseudocode, here it is.

for each active object
  update object position, velocity

Clearly, O(N active objects). So far so good. The objects start out active, by the way.

for each active object
  for each cell covered
    add to the cell
    wake up the cell

I don’t keep a list of active objects in each cell from frame to frame. This is because they can move, so the test has to be performed anyway. I do keep a list of sleeping objects (in a hash table with the cell ID as the key). If an active object enters the cell, they all wake up (the list can then be deleted). This step is also O(N active objects), although N is now larger because some objects woke up. Adding an object to a cell is a constant time operation. Note that objects can be in more than one cell. To avoid duplicate collisions, I store the cell IDs on the object and only allow collisions to be registered from the lowest cell ID present for both objects.

for each active cell
  check for object collisions

for each active object
  check collisions with the world

The number of objects in each cell is roughly constant, but the number of active cells is proportional to the number of active objects. So both these loops are O(N active objects).

for each active cell
  if cell should sleep
    put cell to sleep

If nothing is moving in a cell, it can go to sleep. The objects are all added to the sleeping list for that cell.

resolve collisions

Finally, resolve all the collisions we found previously. I won’t go into the details of this stage here.

Now I can even run the stress test in debug mode. Excellent.