Game Development Reference
5. For each collision work out the exact time of the first collision.
6. Choose the first collision to have occurred.
7. If the first collision occurs after the end time, then we're done: exit the algorithm.
8. Remove the complete update from step 2, and perform an update from the start
time to the first collision time.
9. Process the collision, applying the appropriate impulses (no interpenetration res-
olution is needed, because at the instant of collision the objects are only just
10. Set the start time to be the first collision time, keep the end time unchanged, and
return to step 1.
This gives an accurate result and avoids the problems with interpenetration res-
olution. It is a commonly used algorithm in engineering physics applications where
accuracy is critical. Unfortunately it is very time consuming.
For each collision we run the collision detector again and rerun the regular physics
update each time. We still need to have special-case code to cope with resting contacts;
otherwise, the resting contacts will be returned as the first collision at every iteration.
Even without resting contacts, numerical errors in the collision detection calculations
can cause a never-ending cycle—a constant stream of collisions occurring at the same
time, which causes the algorithm to loop endlessly.
For almost all game projects this approach isn't practical. A once-per-frame up-
date is a better solution, where all the contacts are resolved for velocity and interpen-
The “almost” case I am thinking of is pool, snooker, or billiards games. In these
cases the sequence of collisions and the position of balls when they collide is criti-
cal. A pool game using once-per-frame physics might be believable when two balls
collide, but strange effects can appear when the cue ball hits a tightly packed (but
not touching) bunch of balls. For a serious simulation it is almost essential to follow
the preceding algorithm, with the advantage that if you are writing from scratch, it is
easier to implement without the interpenetration code (not to mention the simplifi-
cations you can get because all the balls have the same mass).
You can see this in pool simulation games running on older PCs. When you break
off, there is a fraction of a second pause when the cue ball hits the pack, as the thou-
sands of internal collisions are detected and handled sequentially.
For a simple arcade pool game, if you already have a once-per-frame physics en-
gine available, it is worth a try: it may be good enough to do the job.
C OLLISIONLIKE T HINGS
Just as for springs, we will look at several types of connections that can be modeled
using the techniques in this chapter.
You can think of a collision as acting to keep two objects at least some minimum
distance apart. A contact is generated between two objects if they ever get too close.
By the same token, we can use contacts to keep objects together.