Game Development Reference
A better solution would be to resolve the contacts in groups. Contacts A, B, and
C can be sent to the resolver first; then D and E and then F. Used in this way the
contact resolver would have no way of altering contacts D and E based on the results
of resolving A, B, and C. But this is okay, since we know those contacts can't possibly
This batching is typically done in one of two places. It can be the job of the colli-
sion detector to return groups of contacts. Or the whole list of contacts can be sepa-
rated by the collision resolution system and processed in batches.
The first approach is the best, if it can be implemented. Typically the collision
detector can determine if objects are a long way from one another and batch them.
If it is using a coarse collision detection system, for example, it can produce contact
batches for each distinct area of the game level. For sets of nearby objects that aren't
touching, however, the collision detector will typically return batches that are too
large (i.e., batches that contain contacts that can't affect one another). If the game
level has many such situations, it can improve performance further to add a batching
processor to the resolver as well as the collision detection batching.
A batching processor separates the whole list of contacts into batches. It does this
by starting at one contact and following the combination of contacts and rigid bod-
ies to find all contacts in one batch. This is then sent for processing. It then finds
another contact that has not yet been placed in a batch and follows the contacts to
build another batch. This repeats for as long as there are contacts that have not been
Implementing a batching processor involves being able to quickly find the rigid
bodies involved in each contact (we have that data already, since the contact data
structure stores the rigid bodies involved) and being able to find the contacts on each
rigid body. This is difficult with the current state of the engine, since rigid bodies don't
keep track of the contacts that affect them. Searching through all possible contacts to
find those belonging to a rigid body would take too long and defeat the object of the
In chapter 14 we looked at a set of modifications to contact processing that
allowed a sorted list of contacts to be retained so they didn't need to be sorted
each time. In the update part of this algorithm the effect of one resolution step is
propagated through the contacts. This uses the same data structure we would need
to efficiently implement batching: a linked list of contacts belonging to each rigid
C ODE O PTIMIZATIONS
The final optimization phase I want to consider is code optimization. Code optimiza-
tions are tweaks that don't change the algorithm but make processing it more efficient.
3. In fact, while this is true of our engine, it is not necessarily true of engines with much more complex
resolution algorithms. In either case, however, there is a better way.