Collision Detection and Response For Real-Time Strategy Games

Lecture Notes

CS 480

Matthew H. Jones

UAF 2009

Collision detection and response are involved in any video game attempting to portray a “realistic” (at least where physical barriers are concerned) environment. In real-time strategy games, the problem often boils down to either keeping units from passing through each other (some games opt to allow this behavior anyway for simplicity's sake) or making units react realistically to terrain variations. Depending on the design of maps and areas, the latter problem can be drastically reduced in complexity.

For a game with as many interacting objects as a typical real-time strategy game, culling collision tests down to a simple list of potentially intersecting pairs is important. This process is called “sweep and prune”, and is often done by tracking an interval along each primary axis for all objects, and flagging a pair for detailed collision detection only if the object bounding intervals overlap on all three axes.

Such a method typically relies on a bounding sphere or an axis-aligned bounding box for the bounding volume (a volume within which all vertices of the object lie). Bounding spheres are incredibly simple to perform calculations with, and the interval length for any object will be the same on all three axes, but typically do not provide as close a fit as an axis-aligned bounding box (AABB). An AABB is convenient in that the intervals are already part of its definition. As with spheres, intersection of bounding boxes is not too difficult to test for.

Where collision detection gets a little trickier is when refinement of the collision to a convex hull becomes necessary. For the vast majority of RTS games, convex hull collision will be sufficient to maintain the illusion of realism (no need for polygon perfect collision detection). Two commonly used methods are the Gilbert-Johnson-Keerthi distance algorithm (collisions are distance 0), and the Minkowski Portal Refinement method employed by Xenocollide. Both require support mapping for convex hulls, and seem pretty slick and not too hard to follow from the annotated illustrations.

After collision detection, a game programmer must consider collision response. How will units react when they run into each other or steep terrain?

Three options for this discussed in the presentation are sliding, bouncing, and impulse. Sliding generally looks okay in a real-time strategy game, and can be accomplished with general rules (either always sliding to the object's right or left, or communication between objects to establish opposite sliding directions or make one object stand still until collision is resolved). Bouncing looks horrible in most situations, though it could conceivably make sense for naval battle in which ships collide broadside and such. Impulse is a variation on bouncing with actual physics calculations involved, and would look better in nearly any situation where bouncing is applicable.

Another option brought up in class is to have damage involved with collision, which will eventually result and units destroying each other as they collide (larger ones winning).

One alternative to all of this is a variation on sliding that never relies on anything finer than a bounding sphere. By using a tiered system of bounding spheres with associated sliding “weights,” units can be made to deflect from each other (as if intelligently steering around each other) without coming into contact. This is less costly than running one of the convex hull collision detection algorithms, and can produce pretty good looking results (might actually appear there is a driver in that tank, after all). Simply weight each successively smaller bounding sphere higher as far as how much deflection from its original path intersection with that sphere will cause, and the units should divert from their paths and then return to something approximating the path as they pass the diverting object.