Linux DevCenter    
 Published on Linux DevCenter (http://www.linuxdevcenter.com/)
 See this if you're having trouble printing code examples


Physics for Game Developers

Five Steps to Adding Physics-Based Realism to Your Games

by David M. Bourg, author of Physics for Game Developers
11/01/2001

As a game developer, and very likely as a gamer yourself, you've probably seen products being advertised as "ultrarealistic," or as "using real-world physics." At the same time you are wondering how you can spice up your own games with such realism. Or perhaps you want to try something completely new that requires you to explore real physics.

Say, for example, you're writing a baseball video game and you want to model the various pitches, such as curve balls, knuckle balls, and fast balls, based on real-world parameters such as release speed, spin, the altitude of the playing field, and so on. Considering all these factors would allow you to distinguish between different pitchers and even between different playing fields. This would offer greater challenges to your gamer, and perhaps more importantly, greater intrigue and variety.

Related Reading

Physics for Game DevelopersPhysics for Game Developers
By David M. Bourg
Table of Contents
Index
Sample Chapter
Full Description

Now, I can't explain how to write such a physics simulation in this short article; instead I've written a book, Physics for Game Developers, which explains the physical and computational principles you will need to know to write such a simulation. In this article, I'll give you a general overview of the five major steps you must take when developing physics-based simulations for your games.

Step 1: What to Model?

The first thing you have to do is decide what it is you'd like to model physically. This may seem obvious, but it's not trivial. You could decide that you'll just model everything in your game physically. While this makes your decision easy, you just significantly increased your development workload. Further, your game's performance will suffer unnecessarily. It's important to remember why you're adding physics to your games in the first place. Presumably, it's because you want to enhance the immersive experience for your players. You've already created a gaming environment that looks realistic, and now you want it to behave realistically as well. What you must do is determine which elements of your game will benefit the most from using real physics and which elements won't make a difference at all in terms of the overall gaming experience.

Generally, your game environment will be full of visual detail so as to create a visually immersive experience. However, it isn't necessary for every little visual element to be modeled physically to achieve this.

Consider this example: You're working on the next blockbuster hunting game complete with first-person 3-D, beautiful textures, and an awesome soundtrack to set the mood, but something is missing. That something is realism. Specifically, you want the game to "feel" more real by challenging the gamer's marksmanship, and you want to do this by adding considerations such as distance to target, wind speed and direction, and muzzle velocity. Moreover, you don't want to fake these elements, but rather you'd like to realistically model them based on the principles of physics.

So now you're faced with deciding what exactly to model physically. Well, for this example, you'd want to model the flight dynamics of the bullet fairly realistically. Do you have to model the gun, too? Probably not, unless you want to use a force-feedback mechanism to simulate the kick of the gun when it's fired. What about the target? Say your gamer is shooting at some tin cans for target practice. You could include the tin cans in your simulator and model the collision between the bullet and tin can so that when struck the can goes tumbling through the air. That would be neat.

On the other hand, what about the stand that the tin can is set upon? Do you really need to model that to yield an immersive shooting experience? Probably not. The point is that you should carefully select what game elements are most important for immersion and focus your attention on those. Leave everything else out of your physical model so you don't waste CPU time.

Step 2: Physical Models

Now that you've decided what it is you want to model, you have to decide how to actually model it. Recall from your physics lessons that rigid body motion is governed by Newton's second law of motion, which states that the acceleration of a body is proportional to the resultant force acting on the body and this acceleration is in the same direction as the resultant force. In equation form this is simply the familiar equation, F = ma; where "F" is the resultant force vector, "m" is the mass of the body, and "a" is its acceleration. You can write an analogous formula relating applied torque to a body's moment of inertia and angular acceleration. Don't worry if you've forgotten these fundamental principles of rigid body dynamics, I've devoted several chapters in my book to this subject as a refresher course.

The formulas for Newton's second law form the equations of motion for the objects in your simulation. Given some externally applied forces and torques (moments), your objects of known mass and inertia will accelerate. While accelerating, their speeds and positions will change; for example, they'll move around under the influence of the external loads. This last statement is critical. It's true that you must solve the equations of motion in a manner such that your simulation is stable. It's also true that you must incorporate accurate collision detection and response in order to capture the interaction of the objects if they run into each other. I'll talk more about this in step 3 later in this article. What ultimately determines the behavior of your objects, however, are the forces and moments that act on them, so it is important to get them right.

While the concept put forth by Newton's second law is easy to grasp, the simplicity of the governing formulas are deceptive because these forces and moments acting on your object are not always easy to calculate. This presents you with a dilemma: It's crucial that you model the forces and moments accurately, but you must trade absolute accuracy with ease of implementation and computational speed. This requires a practical understanding of the object you are trying to model. For example, if you are writing a flight simulator and you want to accurately model the flight dynamics of your plane, then you need to understand how wings generate lift, how tail rudders cause a plane to yaw, how flaps cause a plane to bank, and so on. All these elements effectively apply forces and moments to your plane in order to get it to fly, yaw, bank, and so forth.

What ultimately determines the behavior of your objects are the forces and moments that act on them, so it is important to get them right.

Here's another example: if you want to model the flight of a baseball in your game, then you must consider aerodynamic drag, Magnus Lift forces, and gravity. If you don't get these right, your baseball won't behave like it should. If you leave out Magnus Lift forces, for example, you'll never get a curve ball in your simulation (unless you fake it, but that defeats the purpose of implementing accurate physics in the first place).

Many game physics references that I've come across spend little time discussing the physical nature of forces and moments. Instead, you often see simple, generalized formulas for forces such as viscous drag (commonly called damping in the literature) and spring forces. Generalized formulas are great for modeling generic objects, but they won't cut it if you're going to accurately distinguish the behavior between, say, airplanes and cars, baseballs and cricket balls, or hovercrafts and boats. That's why I've included several chapters in my book that discuss the nature of a variety of forces acting on common objects, including practical formulas and data.

While there are an infinite number of things you may try to simulate in your games, there are a handful of different types of forces that are common across a wide variety of situations. The first type is field forces. These are also known as forces-at-a-distance since the forces are generated between objects that are not in contact, but which are separated by some distance. The best example of this type of force is the force due to gravity. If you are simulating any sort of projectile in your game, then it's safe to assume that you'll have to include gravity in your force calculations.

Another common force is friction. Friction acts between objects in contact and always resists motion. If your hero has to push barrels or crates around in order to navigate a level, then you'll have to model the friction between the barrel or crate and the ground in order to simulate its motion as it is being pushed.

Any time you have an object moving through a fluid, which could be air, water, or any other gas or liquid, the object will experience drag forces opposing its motion. Whether your object is a plane, a bullet, or a person jumping through the air, fluid dynamic drag is a factor that you should consider. In addition to contributing to physical realism, drag, or damping, is always good to help stabilize your simulation.

Many objects moving through fluids also generate lift forces. The best example of this is an airplane wing that generates the lift that allows an airplane to fly. Most people normally associate lift with wing-like, or airfoil shapes; however, even completely round objects can generate lift, if they are spinning. This is the so-called Magnus Lift force that is created when an object rotates as it moves through a fluid. As I mentioned earlier, this is the physical mechanism behind a curve ball in baseball. It's also a significant factor governing the flight of golf balls as well as many other types of sports balls.

One means of connecting objects in a simulation is through the use of springs. A spring applies a force between two connection points, which is proportional to the elongation or compression of the spring. Springs are often used in particle-spring assemblies to simulate the motion of flexible objects, such as cloth. The last chapter of Physics for Game Developers goes through an example of how to use a spring-particle system to simulate a cloth flag waving in the wind while suspended from a flagpole.

Step 3: Collision Detection and Response

It is important to make the distinction between collision detection and collision response. Collision detection is a computational geometry problem involving the determination of whether and where two or more objects have collided. Collision response is a physics problem involving the motion of two or more objects after they have collided.

Related Reading

Physics for Game DevelopersPhysics for Game Developers
By David M. Bourg
Table of Contents
Index
Sample Chapter
Full Description

Collision detection is a crucial aspect of any real-time simulation where objects are not supposed to be able to pass through each other. Your collision-response algorithms rely on the results of your collision-detection algorithms in order to accurately determine the appropriate response to any collision. Therefore, you should take care in making sure your collision-detection schemes are accurate and reliable. That said, collision detection is no easy task. I personally find it much more difficult to implement robustly than it is to implement the physics aspects of rigid body simulations. For game applications, as I'm sure you are aware, speed is also a major issue, and accurate collision detection can be slow. Generally, you'll want to use a two-phase approach to collision detection. First, you can use a bounding sphere or box check to test whether there are possible collisions between objects. If this check indicates possible collisions, then you'll want to do a more detailed check on the candidate objects to see if they are indeed intersecting.

There are many approaches you can take for this detailed collision check. The thing you have to keep in mind is the trade-off between accuracy and performance. Kevin Kaiser addresses triangle-to-triangle level collision detection in detail in Chapter 4.5 of Game Programming Gems. Nick Bobic also treats polygonal collision detection in his Gamasutra article Advanced Collision Detection Techniques. Brian Mertich has also written several useful papers on collision detection for real-time simulations.

Whatever collision-detection scheme you use, there are certain pieces of information that it must provide to you in order for you to simulate physically accurate collision responses. Your collision-detection routine must tell you:

If you're writing a 3-D game complete with detailed polygon models for high-quality rendering, you might be tempted to use those same models in your collision-detection checks for your physics simulation. However, you may not want to do this since it will take more CPU time to do the collision check and may be unnecessary in terms of physical realism. Don't confuse the requirements for visual realism with physical realism. You may find that you need highly detailed polygon models for quality renderings, but your collision model for that object may only need a fraction of the number of polygons. Granted, this approach means you'll have to keep track of two models for each object in your simulation, but the payoff in terms of performance may be well worth it.

It is important to make the distinction between collision detection and collision response.

My treatment of rigid body collision response in my book is based on classical Newtonian impact principles. Bodies that are colliding are treated as rigid regardless of their construction and material. Rigid bodies discussed here do not change shape even upon impact. This, of course, is an idealization. You know from your everyday experience that when objects collide they dent, bend, compress, or crumple. For example, when a baseball strikes a bat, it may compress as much as three quarters of an inch during the millisecond of impact. Notwithstanding this reality, you can rely on the well-established impulse method to approximate rigid body collisions. In this method, an impulsive force is applied to each colliding object at the point or points of impact. This force is calculated such that it changes the velocity of each object instantly, not allowing them to penetrate one another. The method is semi-empirical in that it uses so-called coefficients of restitution to simulate the hardness or softness of various objects. For example, different coefficients of restitution can be used to simulate a rubber ball bouncing off of a hard surface, or a lump of clay that sticks to a surface after a collision.

This classical approach is widely used in engineering machine design, analysis, and simulations. However, for rigid body simulations there is another class of methods known as penalty methods at your disposal. In penalty methods, the force at impact is represented by a temporary spring that gets compressed between the objects at the point of impact. This spring compresses over a very short time and applies equal and opposite forces to the colliding bodies to simulate collision response. Proponents of this method say it has the advantage of ease of implementation. However, one of the difficulties encountered in its implementation is numerical instability. David Baraff reviews several aspects of penalty methods (as well as other methods) in his paper Nonpenetrating Rigid Body Simulation.

Step 4: Numerical Integration

The next aspect of implementing your physics simulator deals with actually solving the equations of motion. The equations of motion can be classified as ordinary differential equations. In some simple cases you can solve these differential equations analytically. However, this won't be the case for general rigid body simulations. Force and moment calculations for your system can get pretty complicated and may even rely on tabulated empirical data, which will prevent you from writing simple mathematical functions that can be easily integrated. This means you have to use numerical-integration techniques to approximately integrate the equations of motion. I say approximately because solutions based on numerical integration won't be exact and will have a certain amount of error depending on the chosen method. I discuss several integration methods, along with sample code, in Chapter 11 of my book.

By far, the easiest integration method to implement is Euler's method. In this method you first calculate the forces and moments on each object in order to determine acceleration. Recalling the equation for Newton's second law, you can obtain acceleration by dividing the resultant force acting on an object by the object's mass (for angular acceleration you need to divide torques by inertias). Once you have acceleration you can obtain the change in velocity by simply multiplying the acceleration by a small change in time called a time step. The object's new velocity is simply its old velocity plus the change in velocity for the current time step. To obtain the object's new position, you first multiply its velocity by the time step to obtain a change in displacement (position) and then add this change to the object's last position. To minimize numerical errors you must step through your simulation at very small time steps with this method.

A major drawback of Euler's method is instability. If your time steps are too large, then your solution may diverge from the exact solution, and your simulation may blow up.

A major drawback of Euler's method is instability. If your time steps are too large, then your solution may diverge from the exact solution, and your simulation may blow up. For example, I was recently implementing a simulation of water flowing over a dam using a method called Smoothed Particle Hydrodynamics. Initially, I was using Euler's method just so I could get the simulation up and running quickly, with the idea of implementing a better method later. While running the simulation for the first time, the water started flowing over the dam in a fairly realistic manner. However, after a few steps all the particles representing the water took to the air and flew out of my computational domain like meteors. Obviously this is wrong, and is a good example of a solution becoming numerically unstable. To solve the problem I was forced to implement an alternative method sooner than I had anticipated.

One such method is known as the Improved Euler method. For ill-conditioned problems, this method is far more stable than Euler's method. However, it requires two force calculations for each object in the simulation. Thus, improved accuracy and stability come at a price in terms of CPU time. Other methods, including the Runge-Kutta and Leap-frog methods, also improve accuracy and stability but again at the cost of CPU time, and in some cases increased memory requirements. Sometimes you can offset the increased CPU burden with these improved methods since they allow you to take larger time steps while still maintaining accuracy. The bottom line is that, here again, you're faced with trading off ease of implementation and speed with accuracy and more importantly, stability.

Step 5: Tuning

The final and arguably the most time-consuming aspect of implementing your physics simulator is tuning (also known as parameter tuning). Many times I've gone through the steps outlined above only to run my simulation to watch it fail. Either the simulation blew up or the behavior of the objects I was trying to simulate was less than accurate.

When writing any simulation you'll find that there are many empirical coefficients and parameters that you have to estimate, for example, collision tolerances, coefficients of restitution, mass properties, and drag coefficients, among others. In many cases your initial estimates for such parameters may be off, resulting in instability or unrealistic behavior. This means that you'll have to tune such parameters until you get the results you want. By tuning I mean the trial-and-error process of changing certain parameters to see what effect they have on your simulation until you get it to work right. In some cases it may mean implementing new algorithms, as I had to do with the integration scheme in my water simulation, for example.

There are a couple of things you can do to make this job easier on yourself. First, research the physics behind what it is you are simulating. Try to obtain an understanding of how the system you are simulating actually behaves in the real world. Find out what factors are important: for example, what forces govern the system's behavior, and try to find some real-world empirical data for things such as drag coefficients, coefficients of restitution, friction coefficients, and so on. This will help take some of the guesswork out of setting initial values for such parameters, and help to identify unrealistic behavior.

Second, don't bury (or spread out) all this data in your source code. Set up a bunch of defines for such data in one file so you can quickly find and change the data as you go through the tuning process. Something you might consider is implementing a mechanism that allows you to change specific data on the fly so you can tune certain aspects of the simulation in real time. I've found this helpful in specific simulations where, for example, I wanted to see the effects of changing viscous drag as the simulation ran. I found it difficult to observe subtle changes in behavior if I had to stop one simulation, change some data, and then rerun the simulation again; especially if the behavior I wanted to observe didn't occur at the start of the simulation but only after many hundreds of time steps.

David M. Bourg performs computer simulations and develops analysis tools that measure such things as hovercraft performance and the effect of waves on the motion of ships and boats.

O'Reilly & Associates will soon release (November 2001) Physics for Game Developers.


Return to the Linux DevCenter.

Copyright © 2009 O'Reilly Media, Inc.