Fix Your Timestep!

Introduction

Hello, I’m Glenn Fiedler and welcome to the second article in my series on Game Physics.

In the previous article we discussed how to integrate the equations of motion using an RK4 integrator.

Now that we have a working physics simulation the next thing we want to do is to display it animating on the screen.

The basic idea is this: each frame we advance the simulation forward by some small amount of time then draw it to the screen. By repeating this over and over the objects animate following the laws of physics.

This sounds so simple, but there are many different ways to do it – so read on!

Fixed delta time

One way to step forward is with a fixed delta time value, like 1/60th of a second:

    double t = 0.0;
    double dt = 1.0 / 60.0;

    while ( !quit )
    {
         integrate( state, t, dt );
         render( state );
         t += dt;
    }

This code is absolutely perfect – provided that VSYNC is on, the display refresh rate is 60HZ and your simulation and rendering code always takes less than 1/60th of a second per-frame.

Problem is if your code is unable to make frame, or if the display rate is different – your game runs faster or slower than the speed you intended.

Variable delta time

This this easy to fix. Just measure how much time spent each frame using a high resolution timer, then feed this value back in as the delta time to use next frame:

    double t = 0.0;

    double currentTime = hires_time_in_seconds();

    while ( !quit )
    {
         double newTime = hires_time_in_seconds();
         double dt = newTime - currentTime;
         currentTime = newTime;

         integrate( state, t, dt );
         t += dt;

         render( state );
    }

And this does work. No matter how fast or slow your game is rendering the simulation keeps up and runs at the correct speed. But there is a huge problem with this which I will now explain!

Fix your timestep or explode

Consider this situation: you are working on a physics-based game. You code and tune the simulation on a fast computer. You are easily able to run at 60fps in your test level and everything looks great: your simulation is stable, your collision detection works perfectly and you have the max speed of the objects tuned just right so that they cannot tunnel through walls.

Then you put your game into QA and in less than 10 minutes you get back the following bug report: At low frame rates collision detection stops working, objects are bouncing all over the place and your vehicle suspension code causes the car to bounce halfway across the map and sometimes fall through the terrain.

What the hell is going on?

The problem is that the behavior of your simulation depends on the size of the timestep you take.

There are two main reasons for this. First, numerical integration is only an approximation. Even advanced integrators like RK4 have some error per-frame and each frame you take this slightly incorrect result from the previous frame and feed it back in to the integrator to predict the next step in the simulation and so on. Now, consider what happens when you pass in larger delta time values? It’s less accurate and eventually at some point, depending on the simulation and the integrator you are using, you may actually be able make the simulation explode. Anybody who’s modeled spring physics knows exactly what I’m talking about here.

Second, collision detection is usually discrete in that it relies on the objects actually penetrating at the beginning of the frame to detect collision. But what if your object moves so quickly that it passes entirely through a wall and out the other side in a single frame? Lets say you tuned your collision detection at 100fps then QA tested your game at 10fps – now each object moves 10 times the distance per-frame at the same speed, and if you’re unlucky this might just be far enough to pass completely through something they’d normally collide with.

It should be pretty clear by now that variable delta time can be problematic. So what is the alternative?

Free the physics

What we want is the best of both worlds. A fixed delta time value for the simulation plus the ability to render at different framerates. These two things seem completely at odds, and they are – unless we can find a way to decouple the simulation and rendering framerates.

Here’s what to do. Advance the physics simulation ahead in fixed dt time steps while also making sure that it keeps up with the timer values coming from the renderer so that the simulation appears to run at the correct speed. For example, if the display framerate is 50fps and the simulation runs at 100fps then we need to take two physics steps every display update.

What if the display framerate is 200fps? Well in this case it would seem that we need to take half a physics step each display update, or alternatively, one physics step every two display updates. Even trickier, what if the display framerate is 60fps, but we want our simulation to run at 100fps? There is no easy multiple here. What if VSYNC is disabled and the display frame rate fluctuates from frame to frame?

The trick is to use a time accumulator. Each render update you add the frame time into an accumulator then while there are whole increments of dt remaining you subtract dt and run a physics step.

Effectively the renderer produces time and the physics update consumes it in discrete dt sized chunks.

    double t = 0.0;
    const double dt = 0.01;

    double currentTime = hires_time_in_seconds();
    double accumulator = 0.0;

    while ( !quit )
    {
         double newTime = hires_time_in_seconds();
         double frameTime = newTime - currentTime;
         currentTime = newTime;

         accumulator += frameTime;

         while ( accumulator >= dt )
         {
              integrate( state, t, dt );
              t += dt;
              accumulator -= dt;
         }

         render(state);
    }

If you read the code above carefully you’ll notice that there can be small amounts of frame time left over in the accumulator from one render frame to the next. What is this and what should we do about it?

The final touch

Consider a situation where the display framerate is 60fps and the physics is running at 50fps. There is no easy multiple so the time accumulator causes the simulation to alternate between taking one and two physics steps each frame. This irregular amount of physics steps taken each update causes a subtle but visually unpleasant stuttering of the physics simulation on the screen known as temporal aliasing.

The solution to this is to interpolate between the previous and current physics state based on how much time is left in the accumulator:

    double t = 0.0;
    const double dt = 0.01;

    double currentTime = hires_time_in_seconds();
    double accumulator = 0.0;

    State previous;
    State current;

    while ( !quit )
    {
         double newTime = time();
         double frameTime = newTime - currentTime;
         if ( frameTime > 0.25 )
              frameTime = 0.25;
         currentTime = newTime;

         accumulator += deltaTime;

         while ( accumulator >= dt )
         {
              previousState = currentState;
              integrate( currentState, t, dt );
              t += dt;
              accumulator -= dt;
         }

         const float alpha = accumulator / dt;

         State state = currentState*alpha + previousState * ( 1.0f - alpha );

         render( state );
    }

This looks pretty complicated but here is a simple way to think about it. Any remainder in the accumulator is effectively a measure of just how much more time is required before another whole physics step can be taken. For example, a remainder of dt/2 means that we are currently halfway between the current physics step and the next one. A remainder of dt*0.1 means that the update is 1/10th of the way between the current and the next state.

We can use this remainder value to get a blending factor between the current physics state and the previous state simply by dividing by dt. This gives an alpha value in the range [0,1] which is used to perform a linear interpolation between the two physics states to get the current state to render. This interpolation is easy to do for single values and for vector state values. You can even use it with full 3D rigid body dynamics if you store your orientation as a quaternion and use a spherical linear interpolation (slerp) to blend between the previous and current orientations.

Click here to download the source code for this article.

Further reading

Integration Basics

Integration is used to determine the motion of an object over time. In this article I show how to correctly integrate the equations of motion using an RK4 integrator instead of starting off on the wrong foot with a stupid Euler integrator.

Physics in 3D

Leap ahead from integrating single values to integrating the entire physics state for a cube in three dimensions. Introduces rotational physics concepts including orientation in 3D, angular velocity and momentum, inertia and torque.

Spring Physics

Explains the physics of springs and how to apply them to control physics simulations. Learn how to implement joints, constraints, motors and basic collision response.

Networked Physics

How do network games synchronize physics over the network? This article explains the core techniques used in today’s first person shooters and shows how you can apply these techniques to network your own physics simulations.