Physics Engine in your Game, or on the way to the Moon (and Monte Carlo!)

This paper contains some complex-looking maths. Don’t worry. Everything gets much easier at the end!

Introduction

If there is one technique that is inevitably connected with computer games, this is animation. To animate means to move various gaming objects in frame by frame basis. Motion is a physical phenomenon. Any motion. Physicists describe motion using the velocity vector that unambiguously determine its direction and speed. Even if you just do a simple animation, drawing an image at coordinates differing by a fixed number of pixels in each frame, without any sophisticated physical formulas behind, it is actually a simple physical simulation of a uniform motion (motion with constant velocity). The number of pixels the image is moved in each frame is the speed, measured in pixels per frame (ppf) or, if multiplied by frame rate, in pixels per second (pps). When you determine new coordinates for the current frame you actually apply a physical formula for Displacement with Constant Velocity: D = vt, where your velocity, v, expressed in ppf, is multiplied by time, t, which is 1 frame. Uniform motion, especially if it is started and stopped abruptly, rarely look natural. In most cases you should try to apply smooth acceleration at the start and gradual delaying (deceleration) when the motion is about to be stopped. Both cases are well described with Newton's second law: if any force is applied, whether it is engine pull or resistance of the brakes, the motion becomes accelerated (or decelerated): a = F/m (a - acceleration, F - force, m - mass).

The real world is ruled by physics. If we want the virtual world of a computer game to mimic the real one, what we need is to implement the physics. This part of the game software is often referred to as a physics engine. Nowadays, no self-respecting action game can get by without a good physics engine. Gravity, falling down, throwing, hitting, colliding, bouncing, reflecting, breaking, exploding - all these is essential for the game quality and player's experience.

The main task of the physics engine is the physics-based simulation. As in the whole physics, a good mathematical model is inevitable. Mathematics itself has few applications in games industry, however as the backstage for the physics engine - it's ubiquitous. During your Games Fundamentals course you could have a feeling that it is mostly about the physics, but mathematics was all the time used to solve physical problems.

To solve typical problems within your physics engine you could follow this recipe:

1. First, identify the forces acting on your objects. Some of them may be obvious: a missile is launched, an enemy kicks a character, a ball is thrown. There may be also less obvious forces, like gravity, friction, air resistance.
2. Using the Newton's second law, calculate the acceleration.
3. Determine velocity.
   You can iterate through 1..3 to add-up all the forces. It is a good idea to leave all resistance forces and to process them at the very end as they usually act against the actual motion (velocity).
4. Determine the new position.

These guidelines can be adequately enhanced if rotational motion is to be considered.

Derivative Approach to Motion

Assume a rocket is flying somewhere in outer space (gravity may be postponed). The propulsion force is constant. According to Newton’s second law, the acceleration is:

(where: a - acceleration, F – propulsion force, ­m – mass of the rocket). The velocity after a time t is given as:

Using a typical school formula for velocity:

where s is the displacement, we get:

Warning! This result is totally wrong! Our formula is only good for a uniform motion (with constant speed), or in case of average speed is known. If the velocity varies over the time, it can be applied only on a very short distance, so short that the change of velocity may be postponed. Physics is a precise science, so whatever short distance you could imagine, it should be even shorter - just next to the "infinitely small". Instead of s we will rather use ds and instead of time t we will rather use dt (infinitely short time", and therefore the physicists use the following universal formula for velocity, which replaces the formula (3):

which means, that the velocity is a change in displacement measured over a very short time. In other words, velocity is a derivative of the displacement function.

To get the distance traveled over the given time, we have to integrate:

The formula (6) is relatively easy to find out without differential and integral calculus (it has a simple geometrical interpretation). Consider a far more complex example: the rocket is traveling to the Moon, with a common propulsion force. While it is flying, the fuel is consumed and therefore it is getting lighter. The force is constant, but the acceleration depends on the total mass, which changes with time:

where m is the rate in which the fuel is consumed. The velocity is therefore given by:

and, finally, displacement is now given by:

Quite complex? Exactly so. I’ve used the Mathematica package to calculate it!

Now, let’s make the thing even more complex. Assume we are near a massive planet. According to Newton’s universal gravitation, the gravity force is:

where G is gravity constant (G=6.67428 × 10^-11m³·kg^-1·s^-2), M is the planet mass, m is the rocket mass and r is the distance between centres of both masses. Acceleration due to gravity is:

The problem is that the formula above contains the distance from the planet which depends on the displacement, while the rocket moves:

Combining both formulas, we get:

This is a non-linear differential equation of the second level. I did not even try to solve it.

Frame by Frame Simulation – and All Gets Simpler!

The MoonRocket game, also known as Fly to the Moon, contains even slightly more complex system then described in the previous section, as it contains two gravitational forces: from the Earth and from the Moon. The fuel is burnt while the engines are on.

The simulation is done on frame-by-frame basis. In each frame (around 80 times per second), the following update sequence is executed:

// modify fuel
1: decreaseFuel(Math.abs(getPropulsion()) / 20);
// mass of the rocket (incl. fuel)
2: double mass = 120 + getFuel();

// distance from Earth & Moon
3: double rEarth = getX() + 100;
4: double rMoon = 900 - getX();
// gravity forces
5: double G = 500; // gravity constant
6: double gEarth = G * mass / (rEarth * rEarth);
7: double gMoon = G * mass / (rMoon * rMoon) / 4;
// propulsion
8: double gProp = getPropulsion();
// net force
9: double force = gProp + gMoon - gEarth;

// acceleration
10: double acc = force / mass / 40;
// velocity
11: double v = getVelocity() + acc * getMyTime(t);
// set engine's velocity
12: setVelocity(newV);

First, the fuel is modified in accordance with the engines power (the more power the more fuel consumed), and the total mass of the rocket is calculated (lines 1 - 2). Then, the distance from both the Earth and the Moon is determined (lines 3-4) and the Newton's universal gravity formula is used to calculate the current value of the gravity force (lines 5-7). Together with the propulsion force (line 8), they are all used to calculate the net force acting onto the rocket (line 9).

In the next step, acceleration is calculated using a well known Newton's second law (line 10). 40 is a scaling factor, introduced to slow down the animation. In the line 11 we calculate velocity and then apply it to the engine (line 12).

The calculation of the actual position of the rocket is done internally by the standard Sprite class, but it looks similar to this:

setPosition(getX() + getXVelocity() * dt, getY() - getYVelocity() * dt);

Where all the complexity is gone? Where are the integrals, where are the differential equations of the second level? Where all this is gone?

The complexity is indeed gone. It's a good news - the gaming physics engine does not need to be SO complex. And, well, the integrals and differential equations are still there... In the next section I will reveal where the calculus is hidden.

Numerical methods, Integral Calculus, Simulation and Computer Games

The Fly to the Moon game can afford using simplified formulas because the updates are done on the basis of very short amounts of time. In a typical game updates are done every 10 or 12 milliseconds. The rocket travels no more than a few pixels; the forces therefore change so insignificantly that we can ignore these changes and treat them as constant over this short period. This allows to apply simple, well known forms of formulas for acceleration and velocity, and also displacement (position):

The delta symbol tells that we take very small, almost-constant slices, but not infinitely small, so they are not dx and dt. And that's the essential difference between the mathematically precise but complex calculation that involved integrating, and something we call a numerical approach.

The picture below shows some function. The y coordinate may here represent velocity, or displacement, while the x coordinate is usually time. The value of integral represents the area of the surface below the curve. Mathematically precise methods based on analytical integrating supply the exact formula for that surface.

A numerical method known as Monte Carlo integration uses a number of uniformly (sometimes randomly) distributed points within the integration range, that are depicted with vertical lines. For each point x_i we can calculate the value of the function, which is the height of the vertical line. This, multiplied by the distance between the consecutive points Dx, results in the area of surface of a small stripe - between two neighbouring lines. One of such stripes is shown in the picture (white). Summing up the surfaces of all the stripes within the integration range gives an estimation of the value of the integral. The result is an approximation: for example, area painted red in the picture will not be calculated. Fortunately, over wider ranges, the approximation tends to converge with the exact value - we say that the method is "stable".

Here is a mathematical formula for the Monte Carlo integration:

In our game, each frame update calculates the area of a single stripe. The line 11, repeated below, sums up the partial values of velocity, and therefore is the place where the numerical integration (of the acceleration function) actually occurs:

11: double v = getVelocity() + acc * getMyTime(t);

Similarly the calculation of the new position is nothing else but the numerical integration of the velocity function.

Conclusion

The complexity of analytical integration has been replaced in numerical integration with computational complexity - instead of complex algorithm it is rather a number of iterations what decides about the precision of results.

The precision of numerical integration may be increased in a number of ways. One of the most common is to take into account the value of the first derivative of the function at each point, which allows for estimating the area of a more-or-less triangular area of numerical error (shown red in the picture). Another is to increase the number of points for which the value function is calculated; there are adaptive methods in which the number of points depends on how quickly the function value changes (once again, this may be measured using the first derivative).

In majority of cases the simplest version of Monte Carlo is pretty enough for gaming solutions and you will rarely or never require anything more precise.