Game Development Reference
F IGURE 12.12
An object may occupy up to four same-sized grid cells.
addition, the object is checked against all objects in all cells in larger-celled grids that
overlap. We don't need to check against objects in smaller-celled grids because the
small objects are responsible for checking against larger objects.
For each grid in the map we can use the grid data structure with the same set
of occupied cells. However, we need to add a cell to the active list if it contains any
objects at all (because they may be in contact with neighbors).
Collision detection is a complex and time-consuming process. To do it exhaustively
takes too long for real-time physics, so some optimization is needed.
We can split collision detection into two phases: a coarse phase that finds possible
contacts (some may turn out not to be collisions, but it should never miss a collision);
and a fine-grained phase that checks potential collisions in detail and works out the
Coarse collision detection works by wrapping objects in a simple bounding vol-
ume, such as a sphere or box, and performing checks on each collision volume. The
collision volumes can be arranged in a hierarchy, which allows whole branches to be
excluded, or in a spatial data structure, which allows nearby objects to be accessed