I n the real world, solid objects are inherently, well. . . solid. They generally avoid doing impossible things, like passing through one another, all by themselves. But in a virtual game world, objects don’t do anything unless we tell them to, and game programmers must make an explicit effort to ensure that objects do not pass through one another. This is the role of one of the central components of any game engine—the collision detection system. A game engine’s collision system is often closely integrated with a physics engine. Of course, the field of physics is vast, and what most of today’s game engines call “physics” is more accurately described as a rigid body dynamics simulation. A rigid body is an idealized, infinitely hard, non-deformable solid object. The term dynamics refers to the process of determining how these rigid bodies move and interact over time under the influence of forces. A rigid body dynamics simulation allows motion to be imparted to objects in the game in a highly interactive and naturally chaotic manner—an effect that is much more difficult to achieve when using canned animation clips to move things about. A dynamics simulation makes heavy use of the collision detection system in order to properly simulate various physical behaviors of the objects in the simulation, including bouncing off one another, sliding under friction, rolling and coming to rest. Of course, a collision detection system can be used standalone, without a dynamics simulation—many games do not have a “physics” 647 648 12. Collision and Rigid Body Dynamics system at all. But all games that involve objects moving about in two- or three-dimensional space have some form of collision detection. In this chapter, we’ll investigate the architecture of both a typical collision detection system and a typical physics (rigid body dynamics) system. As we investigate the components of these two closely interrelated systems, we’ll take a look at the mathematics and the theory that underlie them. 12.1 Do You Want Physics in Your Game? Nowadays, most game engines have some kind of physical simulation capabilities. Some physical effects, like rag doll deaths, are simply expected by gamers. Other effects, like ropes, cloth, hair or complex physically driven machinery can add that je ne sais quoi that sets a game apart from its competitors. In recent years, some game studios have started experimenting with advanced physical simulations, including approximate real-time fluid mechanics effects and simulations of deformable bodies. But adding physics to a game is not without costs, and before we commit ourselves to implementing an exhaustive list of physics-driven features in our game, we should (at the very least) understand the trade-offs involved. 12.1.1 Things You Can Do with a Physics System Here are just a few of the things you can do or have with a game physics system. • Detect collisions between dynamic objects and static world geometry. • Simulate free rigid bodies under the influence of gravity and other forces. • Spring-mass systems. • Destructible buildings and structures. • Ray and shape casts (to determine line of sight, bullet impacts, etc.). • Trigger volumes (determine when objects enter, leave or are inside predefined regions in the game world). • Complex machines (cranes, moving platform puzzles and so on). • Traps (such as an avalanche of boulders). • Drivable vehicles with realistic suspensions. • Rag doll character deaths. • Powered rag doll: a realistic blend between traditional animation and rag doll physics. 12.1. Do You Want Physics in Your Game? 649 • Dangling props (canteens, necklaces, swords), semi-realistic hair, clothing movements. • Cloth simulations. • Water surface simulations and buoyancy. • Audio propagation. And the list goes on. We should note here that in addition to running a physics simulation at runtime in our game, we can also run a simulation as part of an offline preprocessing step in order to generate an animation clip. A number of physics plug-ins are available for animation tools like Maya. This is also the approach taken by the Endorphin1 package by NaturalMotion, Inc. (http://www. naturalmotion.com/endorphin.htm). In this chapter, we’ll restrict our discussion to runtime rigid body dynamics simulations, but offline tools are a powerful option, of which we should always remain aware as we plan our game projects.