ISBN-10:
0123819768
ISBN-13:
9780123819765
Pub. Date:
08/29/2010
Publisher:
Taylor & Francis
Game Physics Engine Development: How to Build a Robust Commercial-Grade Physics Engine for your Game / Edition 2

Game Physics Engine Development: How to Build a Robust Commercial-Grade Physics Engine for your Game / Edition 2

by Ian Millington
Current price is , Original price is $63.95. You

Temporarily Out of Stock Online

Please check back later for updated availability.

Product Details

ISBN-13: 9780123819765
Publisher: Taylor & Francis
Publication date: 08/29/2010
Pages: 552
Sales rank: 606,101
Product dimensions: 7.50(w) x 9.10(h) x 0.80(d)

About the Author

Ian Millington is a partner of IPR Ventures, a consulting company developing next-generation AI technologies for entertainment, modeling, and simulation. Previously he founded Mindlathe Ltd, the largest specialist AI middleware company in computer games, working with on a huge range of game genres and technologies. He has a long background in AI, including PhD research in complexity theory and natural computing. He has published academic and professional papers and articles on topics ranging from paleontology to hypertext.

Read an Excerpt

GAME PHYSICS ENGINE DEVELOPMENT

How to Build a Robust Commercial-Grade Physics Engine for your Game
By IAN MILLINGTON

Morgan Kaufmann Publishers

Copyright © 2010 Elsevier Inc.
All right reserved.

ISBN: 978-0-12-381977-2


Chapter One

Introduction

Physics is a hot topic in computer games. No self-respecting action game can get by without a good physics engine, and the trend has recently spread through other genres, including strategy games and puzzles. This growth has been largely fueled by middleware companies offering high-powered physics simulation. Most high-profile games now feature commercial physics engines.

But commercial packages come at a high price, and for a huge range of developers building a custom physics solution can be better, as it can be cheaper, provide more control, and be more flexible. Unfortunately, physics is a topic shrouded in mystery, mathematics, and horror stories.

When I came to build a general physics engine in 2000, I found that there was almost no good information available, almost no code to work from, and lots of contradictory advice. I struggled through and built a commercial engine, and learned a huge amount in the process. Over the last 10 years I've applied my own engine and other commercial physics systems to a range of real games. Almost a decade of effort and experience is contained in this book.

There are other books, websites, and articles on game physics, much of it quite excellent. But there is still almost no reliable information on building a physics engine from scratch—a complete simulation technology that can be used in game after game. This book aims to step you through the creation of a physics engine. It goes through a sample physics engine (provided on the CD), as well as giving you insight into the design decisions that were made in its construction. You can use the engine as is, use it as a base for further experimentation, or make various design decisions and create your own system under the guidance that this book provides.

1.1 What Is Game Physics?

Physics is a huge discipline, and academic physics has hundreds of subfields. Each describes some aspect of the physical world, from the way light works to the nuclear reactions inside a star.

Lots of these areas of physics might be useful in games. We could use optics, for example, to simulate the way light travels and bounces, and use to make great-looking graphics. This is the way ray tracing works, and (although it is still very slow compared to other approaches) it has been used in several game titles. Although these areas are part of academic physics, they are not part of what we mean by game physics and I won't consider them in this book.

Other bits of physics have a more tenuous connection with games. I cannot think of a use for nuclear physics simulation in a game, unless the nuclear reactions were the whole point of the game play.

When we talk about physics in a game, we really mean classical mechanics, that is, the laws that govern how large objects move under the influence of gravity and other forces. In academic physics these laws have largely been superceded by relativity and quantum mechanics. Almost all of the physics described in this book has long since stopped being an active area of research; all the results we'll be relying on were settled before the turn of the twentieth century.

In games, classical mechanics is used to give game objects the feel of being solid things, with mass, inertia, bounce, and buoyancy.

Game physics has been around almost since the first games were written. It was first seen in the way particles move: the ballistics of bullets, sparks, fireworks, smoke, and explosions. Physics simulation has also been used to create flight simulators for nearly three decades. Next came automotive physics, with ever-increasing sophistication of tire, suspension, and engine models.

As processing power became available, we saw crates that could be moved around or stacked, and walls that could be destroyed and crumble into their constituent blocks. This is rigid-body physics, which rapidly expanded to include softer objects: clothes, flags, and rope. Then came the rise of the ragdoll: a physical simulation of the human skeleton that allows more realistic trips, falls, and death throes. And recently we've seen a lot of effort focused on simulating fluid flow: water, fire, and smoke.

In this book we'll cover a representative sample of physics tasks. With a gradually more comprehensive technology suite, our physics engine will support particle effects, flight simulation, car physics, crates, destructible objects, cloth, and ragdolls, along with many other effects.

1.2 What Is a Physics Engine?

Although physics in games is more than 30 years old, there has been a distinct change in recent years in the way that physics is implemented. Originally, each effect was programmed for its own sake, creating a game with only the physics needed for that title. If a game needed arrows to follow trajectories, then the equation of the trajectory could be programmed into the game. It would be useless for simulating anything but the trajectory of arrows, but it would be perfect for that.

This is fine for simple simulations, where the amount of code is small and the scope of the physics is quite limited. As we'll see, a basic particle system can be programmed in only a hundred lines or so of code. But directly implementing phyical behavior becomes a difficult task as the complexity increases.

In the original Half-Life game, for example, you can push crates around, but the physics code isn't quite right, and the way crates move looks odd. The difficulty of getting physics to look good, combined with the need for almost the same effects in game after game encouraged developers to look for general solutions that could be reused.

Resuable technology needs to be quite general: a ballistics simulator that will only deal with arrows can have the behavior of arrows hard coded into it. If the same code needs to cope with bullets too, then the software needs to abstract away from particular projectiles and simulate the general physics that they all have in common. This is what we call a physics engine: a common piece of code that knows about physics in general, but isn't programmed with the specifics of each game.

This leaves us with a gap. If we have special code for simulating an arrow, then we need nothing else in order to simulate an arrow. If we have a general physics engine for simulating any projectile, and we want to simulate an arrow, we also need to tell the engine the characteristics of the thing we are simulating. We need the physical properties of arrows, or bullets, or crates, and so on.

This is an important distinction. The physics engine is basically a big calculator: it does the mathematics needed to simulate physics. But it doesn't know what needs to be simulated. In addition to the engine we also need game-specific data that represents the objects in our level.

Although we'll look at the kind of data we need throughout this book, I won't focus on how the data gets into the game. In a commercial game, there will likely be some kind of level-editing tool that allows level designers to place crates, flags, ragdolls, or aeroplanes to set their weight, the way they move through the air, their buoyancy, and so on. For a physics engine drivinga flight simulator, the data may have to be acquired from real aircraft capabilities. For simpler games, it may be hardcoded somewhere in the source code.

The physics engine we'll be developing throughout this book needs gradually more and more datato drive it. I'll cover in depth what kind of data this is, and reasonable values it can take, but for our purposes we will assume this data can be provided to the engine. It is beyond the scope of the book to consider the tool chain that you will use to author these properties for the specific objects in your game.

1.2.1 Advantages of a Physics Engine

There are two compelling advantages for using a physics engine in your games. First, there is the time savings. If you intend to use physics effects in more than one game (and you'll probably be using them in most of your games from now on), then putting the effort into creating a physics engine now pays off when you can simply import it into each new project. A lightweight, general-purpose physics system, of the kind we develop in this book, doesn't have to be difficult to program either. A couple of thousand lines of code will set you up for most of the game effects you need.

The second reason is quality. You will most likely be including more and more physical effects in your game as time goes on. You could implement each of these as you need it, such as building a cloth simulator for capes and flags, and a water simulator for floating boxes, and a separate particle engine. Each might work perfectly, but you would have a very hard time combining their effects. When the character with a flowing cloak comes to stand in the water, how will her clothes behave? If they keep blowing in the wind even when underwater, then the illusion is spoiled.

A physics engine provides you with the ability to have effects interact in believable ways. Remember the moveable crates in Half-Life 1? They formed the basis of only one or two puzzles in the game. When it came to Half-Life 2, crate physics was replaced by a full physics engine. This opens up all kinds of new opportunities. The pieces of a shattered crate float on water, objects can be stacked and used as moveable shields, and so on.

It's not easy to create a physics engine to cope with water, wind, and clothes, but it's much easier than trying to take three separate ad-hoc chunks of code and make them look good together in all situations.

1.2.2 Weaknesses of a Physics Engine

This isn't to say that a physics engine is a panacea. There are reasons that you might not want to use a full physics engine in your game.

The most common reason is speed. A general-purpose physics engine is quite processor-intensive. Because it has to be general, it can make no assumptions about the kinds of objects it is simulating. When you are working with a very simple game environment, this generality can mean wasted processing power. This isn't an issue on modern consoles or the PC, but on handheld devices such as phones and PDAs, it can be significant. You could create a pool game using a full physics engine on a PC, but the same game on a mobile phone would run faster with some specialized pool physics.

The need to provide the engine with data can also be a serious issue. In a game that I worked on we needed no physics other than flags waving in the wind. We could have used a commercial physics engine (one was available to the developer), but the developer would need to have calculated the properties of each flag, its mass, springiness, and so on. This data would then need to be fed into the physics engine to get it to simulate the flags.

There was no suitable level-design tool that could be easily extended to provide this data, so instead we created a special bit of code just for flag simulation, the characteristics of flags were hardcoded in the software, and the designer needed to do nothing special to support it. We avoided using a physics engine because special-case code was more convenient.

A final reason to avoid physics engines is scope. If you are a one-person hobbyist working on your game in the evenings, then developing a complete physics solution might take your time away from improving other aspects of your game, such as the graphics or game play. Or worse, it might distract you from finishing, releasing, and promoting your game. On the other hand, even amateur games need to compete with commercial titles for attention, and top-quality physics is a must for a top-quality title of any kind.

1.3 Approaches to Physics Engines

There are several different approaches to building a physics engine. From the very simple (and wrong) to the cutting-edge physics engines of top middleware companies. Creating a usable engine means balancing the complexity of the programming task with the sophistication of the effects you need to simulate.

There are a few broad distinctions we can make to categorize different approaches.

1.3.1 Types of Objects

The first distinction is between engines that simulate full rigid bodies or so-called "mass aggregate" engines. Rigid-body engines treat objects as a whole, and work out the way they move and rotate. A crate is a single object, and can be simulated as a whole. Mass aggregate engines treat objects as if they were made up of lots of little masses. A box might be simulated as if it were made up of eight masses, one at each corner, connected by rods.

Mass aggregate engines are easier to program because they don't need to understand rotations. A large amount of effort is needed to support rotations, and it forms a sizable chunk of this book. Mass aggregate engines treat each mass as if it were located at a single point, and the equations of motion can be expressed purely in terms of linear motion. The whole object rotates naturally as a result of the connections between masses.

Because it is very difficult to make things truly rigid in a physics engine, it is difficult to make really firm objects in a mass aggregate system. Our eight-mass crate will have a certain degree of flex in it. To avoid this being visible to the player, extra code is needed to reconstruct the rigid box from the slightly springy set of masses. While the basic mass aggregate system is very simple to program, these extra checks and corrections are more hit and miss, and very quickly the engine becomes a mess of fixes and ugly code.

Fortunately, we can extend a mass aggregate engine into a full rigid-body system, simply by adding rotations. In this book, we will develop a mass aggregate physics engine on the way to a full rigid-body physics engine. Because we are heading for a more robust engine, I won't spend the time creating the correction code for springy aggregates.

1.3.2 Contact Resolution

The second distinction involves the way in which touching objects are processed. As we'll see in this book, a lot of the difficulty in writing a rigid-body physics engine is simulating contacts—locations where two objects touch or are connected. This includes objects resting on the floor, objects connected together, and, to some extent, collisions.

One approach is to handle these contacts one by one, making sure each works well on its own. This is called the "iterative" approach and it has the advantage of speed. Each contact is fast to resolve, and with only a few tens of contacts, the whole set can be resolved quickly. It has the downside that one contact can affect another, and sometimes these interactions can be significant. This is the easiest approach to implement, and can form the basics of more complex methods. It is the technique we will use in the engine in this book.

A more physically realistic way is to calculate the exact interaction between different contacts and calculate an overall set of effects to apply to all objects at the same time. This is called a "Jacobian-based" approach, but it is very time consuming. The mathematics needed to process the Jacobian is very complex, and solving the equations can involve millions of calculations. In some cases there is simply no valid answer and the developer needs to add special code to fall back on when the equations can't be solved. Most physics middleware packages andseveral open-source physics engines use this approach, and each has its own techniques for solving the equations and dealing with inconsistencies.

A third option is to calculate a set of equations based on the contacts and constraints between objects. Rather than use Newton's laws of motion, we can create our own set of laws for the specific configuration of objects we are dealing with. These equations will change from frame to frame, and most of the effort for the physics engine goes into creating them (even though solving them is no picnic either). This is called a "reduced coordinate" approach. Some physics systems have been created with this approach, and it is the most common one used in engineering software to achieve really accurate simulation. Unfortunately, it is very slow, and isn't very useful in games, where speed and believability are more important than accuracy.

We'll return to the Jacobian and reduced coordinate approaches in Chapter 20, after we've looked at the physics involved in the first approach.

(Continues...)



Excerpted from GAME PHYSICS ENGINE DEVELOPMENT by IAN MILLINGTON Copyright © 2010 by Elsevier Inc.. Excerpted by permission of Morgan Kaufmann Publishers. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Table of Contents

Introduction
What is Game Physics?
What is a Physics Engine?
Approaches to Physics Engines
The Mathematics of Physics Engines
The Source Code in the Book
How the Book is Structured

PART I Particle Physics
The Mathematics of Particles

Vectors
Calculus
Summary
Exercises
The Laws of Motion
The Particle
The First Two Laws
The Integrator
Summary
Exercises
The Particle Physics Engine
Ballistics
Fireworks
Summary
Projects

PART II Mass Aggregate Physics
Adding General Forces

D’Alembert’s Principle
Force Generators
Built-In Gravity and Damping
Summary
Exercises
Springs and Spring-Like Things
Hook’s Law
Spring-Like Force Generators
Stiff Springs
Summary
Exercises
Hard Constraints
Simple Collision Resolution
Collision Processing
The Contact Resolver Algorithm
Collision-Like Things
Summary
Exercises
The Mass Aggregate Physics Engine
Overview of the Engine
Using the Physics Engine
Summary
Projects

PART III Rigid-Body Physics
The Mathematics of Rotations

Rotating Objects in 2D
Orientation in 3D
Angular Velocity and Acceleration
Implementing the Mathematics
Summary
Exercises
Laws of Motion for Rigid Bodies
The Rigid Body
Newton-2 for Rotation
D’Alembert for Rotation
The Rigid-Body Integration
Summary
Exercises
The Rigid-Body Physics Engine
Overview of the Engine
Using the Physics Engine
Summary
Projects

PART IV Collision Detection
Collision Detection

The Collision Detection Pipeline
Broad-Phase Collision Detection
Bounding Volume Hierarchies
Spatial Partitioning
Summary
Exercises
Generating Contacts
Collision Geometry
Contact Generation
Simple Collision Algorithms
Separating Axis Tests
Coherence
Summary
Exercises

PART V Contact Physics
Collision Resolution

Impulse and Impulsive Torque
Collision Impulses
Resolving Interpenetration
The Collision Resolution Process
Summary
Exercises
Resting Contacts and Friction
Resting Forces
Microcollisions
Types of Friction
Implementing Friction
Friction and Sequential Contact Resolution
Summary
Exercises
Stability and Optimization
Stability
Optimizations
Summary
Putting It All Together
Overview of the Engine
Using the Physics Engine
Limitations of the Engine
Summary
Projects

PART VI Further Topics in Physics
Physics in Two Dimensions

2D or 3D?
Vector Mathematics
Particle and Mass Aggregate Physics
The Mathematics of Rotation
Rigid-Body Dynamics
Collision Detection
Collision Response
Summary
Projects
Other Programming Languages
ActionScript 3
C
Java
C#
Other Scripting Languages
Other Types of Physics
Simultaneous Contact Resolution
Reduced Coordinate Approaches
Summary
Appendix A Useful Inertia Tensors
Discrete Masses
Continuous Masses
Common Shapes
Cuboid
Sphere
Cylinder
Cone
Hemisphere
Moments of Inertia in 2D
Common 2D Shapes
Appendix B Useful Friction Coefficients

Appendix C Mathematics Summary
Vectors
Quaternions
Matrices
Integration
Physics
Other Forumlas

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews