Game Development Reference
In a grid where each cell contains all the objects that overlap it, the set of collisions
can be generated very simply. Two objects can only be in collision if they occupy the
same location in the grid. We can simply look at each location containing more than
one object and check each pair for possible collisions.
Unlike tree-based representations, the only way we can tell if a location contains
two or more objects is to check it. Whereas for a tree we stored the number of objects
at each node and could completely miss branches that couldn't generate collisions,
there is no such speed-up here.
To avoid searching thousands of locations for possible collisions (which for a
small number of objects may take longer than if we had not performed coarse col-
lision detection at all), we can create a set of locations in the grid data structure con-
taining more than one object. When we add an object to a cell, if the cell now contains
two objects, it should be added to the occupied list.
Likewise, when we remove an object from a cell, if the cell now contains just one
object, it should be removed from the list. Determining a complete set of collisions is
then just a matter of walking the occupied list and passing all pair-wise combinations
to the fine-grained collision detector.
If objects are larger than the size of a cell, they will need to occupy many cells in
the grid. This can lead to very large memory requirements with lots of wasted space.
For a reasonable-size game level running on a PC this might not be an issue, but for
large levels or memory-constrained consoles, it can be unacceptable.
If we place an object in just one grid cell (the cell in which its center is located,
normally), then the coarse collision detection routine needs to check for collisions
with objects in neighboring cells. For an object that is the same size as the cell, it needs
to check a maximum of three neighbors from a possible set of eight (see figure 12.12).
This rapidly increases, however. For an object four times the size of the cell, 15 from a
possible 24 neighbors need to be considered. It is possible to write code to check the
correct neighbors, but for very large objects it involves lots of wasted effort.
A hybrid data structure can be useful in this situation, using multiple grids of
different sizes. It is normally called a “multi-resolution map.”
M ULTI -R ESOLUTION M APS
A multi-resolution map is a set of grids with increasing cell sizes. Objects are added
into one of the grids only, in the same way as for a single grid. The grid is selected
based on the size of the object: it will be the smallest grid whose cells are bigger than
Often the grids are selected so that each one has cells four times the size of the
previous one (i.e., twice the width and twice the length for each cell). This allows the
multi-resolution map to directly calculate which grid to add an object to.
During coarse collision detection the map uses a modified version of the single-
grid algorithm. For each grid it creates a potential collision between each object and
objects in the same or neighboring cells (there is a maximum of three neighbors to
check now because objects can't be in a grid cell that is smaller than they are). In