Euler's Method In Game Design

Physics in games are a massive factor in providing realism, from racing in a car around the Laguna Seca to sniping unsuspecting enemies on Battlefield, you can find physics almost everywhere! However, there is no silver bullet when it comes to simulating real world physics. There are several methods to choose from and each method has its pros and cons therefore developers need to determine when and where these methods should be used in certain situations. These methods are usually broken down into several different categories depending on the level of accuracy that each one gives (this is due to the number of steps that it takes to calculate the derivative):

First Order Integration
Second Order Integration
Higher Order Integration

Before we delve into any integration techniques, it is important to recap some basic Newtonian equations of motion:

Force = Mass * Acceleration
Acceleration = Force / Mass

Next to understand that acceleration is the derivative of velocity and position is the derivative of acceleration. In calculus terms this can be represented like so:

dv/dt = a
dx/dt = v

First Order Integrators

Explicit Euler

This is one of the simplest methods of numerical integration that games developers use however it is not the most accurate. This method works by taking an initial position and velocity and calculating the next position and velocity after a given time, this would be repeated using a time step value for example, 0.5 seconds (this will be represented by 'dt' throughout the article). Once the first values are calculated we then use them to calculate the next values and so on and so forth. Here is a simple equation to demonstrate:

Velocity_n+1= Velocity_n + (Acceleration_n * dt)

Using the equation above to find the velocity, we now find the position by the following:

Position_n+1= Position_n + (Velocity_n * dt)

However, like I previously mentioned, this method isn't one of the most accurate methods to use. We will always get an error value, which is dependent on the step size value (in this case 0.5s). The error value is the difference between the actual solution and the estimation, the further in time we get, the general rule is that the error value builds up therefore meaning that there is a practical limit for when we can use this method, especially with smaller time steps. We can make the time step value smaller, this will make the estimations closer to the actual solution however this is impractical, if we take a step size of 0.01 for a duration of 10 seconds, this means that there would be thousands of calculations that the computer would have to process, thus slowing down the computational speed. It is important to note that no matter how much you reduce the time step value, the error value will still increase over time.

To summarise, this Euler method is great to build a conceptual understanding from for other integration techniques however, it isn't very accurate unless we decrease the step sizes, which as we now know, causes the problem of increasing the number of calculations and increases error value build up. Euler is mainly used when the impacts of the error value won't have a deciding impact on what happens next e.g. a sprinting character jumping then as the character lands it continues to sprint.

There are other different types of Euler integration that can be used to improve the accuracy, in this article I will discuss implicit and semi-implicit Euler integration.

Implicit Euler (Backwards Euler)

This method is different to the previous Euler techniques because it calculates the derivative and then jumps back to use that derivative to calculate the next estimation, it is not surprising that the other name this Euler method has is 'backwards Euler'. Here is how the velocity would be calculated:

Velocity_n+1= Velocity_n + (Acceleration_n+1 * dt)

Once the velocity has been calculated the next step is to calculate the position:

Position_n+1 = Position_n + (Velocity_n+1* dt)

Even though this is another first order integration method, meaning that there will still be that error, it is extremely stable, even with the larger time steps however one of the trade-offs with this is that it is more complex because you would have to calculate the updated acceleration and velocity because you wouldn't have these values. This means that it is a slower method to integrate.

This method however isn't ideal for any rigid body movements, although this method is extremely accurate and despite being quicker than higher order integration methods, it still takes too long computational wise for it to be worthwhile to be used in this way. This method is used for a variety of things within games such as springs, calculating friction, drag and changes in acceleration.

Semi-Implicit Euler (Symplectic Euler)

This method of Euler is the middle ground between explicit Euler and implicit Euler, hence the name is it given 'semi-implicit'. The reason why it is the middle ground between these two types of Euler integration is due to how it calculates both the velocity and position at a specific time. This method calculates the velocity by using the explicit Euler technique where we calculate the velocity using the acceleration from the previous time step:

Velocity_n+1= Velocity_n + (Acceleration_n * dt)

The next step in the process is to calculate the position, and this is done by using the implicit method where we calculate the position using the newly updated velocity value:

Position_n+1 = Position_n + (Velocity_n+1 * dt)

One of the advantages with the semi-implicit method is that it is a lot more stable than the explicit. This means that it provides an estimation that is closer to the actual solution however, it is still just an estimation so it still suffers the error value. Another advantage of this method of numerical integration is that, although it is more accurate than the explicit Euler method, it is still fairly easy to integrate thus making it faster to implement than higher order techniques.

To summarise, this method is extremely popular amongst game developers due to its simplicity and its improved stability over the explicit Euler. This method is mainly used to calculate 'rigid body movement'

An example of physics in madden, a sudden burst of velocity, once the Dolphins player is in the air, apply gravity!

Second Order Integration

Verlet Integration

One of the most popular methods of numerical integration in games development is the Verlet method and its partner velocity Verlet (see next heading). One of the reasons for this is due to it being a higher order integration method, meaning that it is a lot more accurate (low error value percentages) and still maintains a simplicity for implementation. In addition to this is also very efficient because it doesn't take as much time to calculate as higher order integrators.

This method is different to many different methods of integration because it calculates the position from acceleration, where as other methods such as Euler calculates the velocity from acceleration then position from velocity, so it is not surprising that another name for the Verlet method is 'Position Verlet'. Here is how we calculate the position using this method:

Position_n+1 = 2*Position_n– Position_n-1+ Acceleration*dt ²

If needed we can calculate the velocity by doing the following:

Velocity_n+1 = (Position_n – Position_n-1)/dt

Although this method has its advantages, it does have its drawbacks. One disadvantage of this method is that it assumes that the time step will be constant therefore this method won't be as accurate when the time step value varies.

The next drawback of this method is that the velocity calculation isn't very accurate because it would only be an approximation, therefore if we wanted to implement anything where the velocity changes a lot such as a car racing round a track it would not be very accurate. This also would be a problem if we needed to calculate instantaneous velocity changes that may happen after collisions

So to summarise, this method is pretty accurate whilst maintaining efficiency and simplicity however the trade-offs are that we can only find an approximation for the velocity. Like I previously stated, this method is one of the most popular methods used by game developers, especially interactive games. So with that being said, what is this method used for? Mainly for Verlet integration systems which are then used to simulate projectile trajectories such as bullets fired from a gun and particle systems e.g. smoke, waterfalls etc.

Other uses for this method include, simulating cloth and ragdoll effects such as a character model falling down a flight of stairs.

Velocity Verlet

As mentioned in the standard/position Verlet method above, one of the problems with this type of integration method is that, because we are approximating the velocity, the velocity isn't very accurate. One way of increasing the velocity accuracy is by using this method, the velocity Verlet method. What this method does is split the process into four steps were we calculate the velocity twice, once at a half time step and again after we calculate the next acceleration (We will insert a simple equation to calculate this):

Step 1)

Velocity_n+1/2 = Velocity_n + Acceleration_n*dt/2

Step 2)

Position_n+1 = Position_n + Velocity_n+1/2 *dt

Step 3)

Acceleration_n+1 = Force/Mass

Step 4)

Velocity_n+1 = Velocity_n+1/2 +Acceleration_n+1*dt/2

However by doing this the method loses some of its efficiency although, this does mean that we can use Verlet in situations where we would need to simulate physics with a velocity that increases and decreases rapidly e.g. car racing game. In addition to this, this method can be used in all of the same situations as the standard Verlet but with more accuracy. This method is one of the more common of the two Verlet techniques discussed. On a final note about this integration technique, the first three steps are a second order integration however the final step is first order integration.

Dani Pedrosa (Repsol Honda) will be affected by several physics elements in this lean!

Dani Pedrosa (Repsol Honda) will be affected by several physics elements in this lean from the MotoGP14 Game!

Runge Kutta 4th Order

Up until now I have discussed first and second order integration methods, now it's time to go into one of the more complex integration methods.

The Runge Kutta 4^th Order (RK4) method is the more commonly known method of the Runge Kutta integration methods that are used in physics. One of the main advantages of this method is that it is extremely accurate when compared the all of the previous integration methods that have been mentioned so far in this report. The reason why RK4 is accurate is because it calculates the estimation in 4 steps, hence why it is a 4^th order integrator. RK4 calculates x_n+1by the following calculation, it also needs and Ordinary Differential Equation (this is an equation that all derivatives are with respect to a single independent variable):

x_n+1= x_n + 1/6(K1 + 2 * K2 + 2 * K3 +K4) * h

To calculate K1, K2, K3 and K4 the following calculations are needed, please note that the time step in this equation is represented as 'h':

K1 = ODE (t + x)

K2 = ODE (t + 1/2* h, x + 1/2 * K1 * h)

K3 = ODE (t + 1/2 * h, x + 1/2 * K2 * h)

K4 = ODE (t + h, x + K3 * h)

Understandably this can be a lot to take in at first, for this reason here is an example of a rocket that is flying through the Earth's atmosphere. First of all we have the ODE to calculate the acceleration:

acceleration = (rocket force + force drag) / mass

We know that acceleration is the derivative of velocity (as mentioned earlier) so using RK4 to calculate this should be relatively straight forward:

K1 = ODE (time + velocity)

K2 = ODE (time + 1/2 * timeElapsed, x + 1/2 * K1 * timeElapsed)

K3 = ODE (time + 1/2 * timeElapsed, x + 1/2 * K2 * timeElapsed)

K4 = ODE (time + timeElapsed, x + K3 * timeElapsed)

And finally, to calculate the acceleration:

acceleration_n+1= acceleration_n + 1/6 (K1 + 2 * K2 + 2 * K3 +K4) * timeElapsed

However one of the trade-offs for the improved accuracy is that there are more computations needed to calculate the result than other integrator techniques. This means that it is not ideal for calculating all types of physics in games and therefore should be used for simulations or when accuracy is critical to what would happen next, for example, a sniper shot fired in Battlefield 4.

An example of a type of simulation that this method could be used for is a moon orbiting a planet, it also has uses in games such as flight simulators where the accuracy is extremely important to simulate realistic flying.

Conclusion

In conclusion there are many different types of integration methods that can be used to simulate physics in game worlds, however each one has its pros and cons for example, Explicit Euler is quick and easy to implement and uses less computations to calculate the physics, the drawback to this is that is isn't as accurate as other methods. On the other hand we have RK4 which takes longer and is more complex in its implementation, however we are rewarded with an extremely accurate estimation. With that being said, it is up to the game developer to decide which method is best suited for which situation by taking into account several variables such as; computational expense, accuracy and simplicity. On a final note, it is important to note that there are many more different integration techniques that can be used, Runge Kutta for example doesn't end at 4, it can go even further!

I hope this article has been useful and has at least helped develop a basic understanding of each integration method, at the bottom of this post I am including a list of references I found extremely useful (I highly recommend taking a look at Glenn Fiedler's website Gaffer on Games). Finally, if I am wrong about anything in the blog please do let me know and I shall make the necessary amendments.

Resources

Bourg, D. M. (2002). Physics for Game Developers. California: O'Reilly.

Catto, E. (2011). Soft Constraints.

Dobre, D. R. (2014). Physics for JavaScript Games, Animation. and Simulations: with HTML5 Canvas. Apress.

Fieldler, G. (2006). Integration Basics. Retrieved from GafferonGames: http://gafferongames.com/game-physics/integration-basics/

Gregory, J. (2009). Game Engine Architecture. Wellesley, Mass.: A K Peters Ltd.

Images

http://www.igameresponsibly.com/

http://www.familyfriendlygaming.com/