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. Integration sounds complicated but really it’s just a way to advance the your physics simulation forward by some small amount of time called “delta time” (or dt for short).

But how to choose this delta time value? This may seem like a trivial subject but in fact there are many different ways to do it, each with their own strengths and weaknesses – so read on!

Fixed delta time

The simplest way to step forward is with a fixed delta time, 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;
}

In many ways this code is ideal. If you are lucky enough to have your physics delta time match the display rate and you can ensure that your update loop takes less than one frame then you have the perfect solution for updating your physics simulation.

But in the real world you may not know the display refresh rate ahead of time, VSYNC could be turned off, or perhaps you could be running on a slow computer which cannot update and render your frame fast enough to present it at 60fps.

In these cases your simulation will run faster or slower than you intended.

Variable delta time

Fixing this seems simple. Just measure how long the previous frame takes, then feed that value back in as the delta time for the next frame. This makes sense because of course, because if the computer is too slow to update at 60HZ and has to drop down to 30fps, you’ll automatically pass in 1/30 as delta time. Same thing for a display refresh rate of 75HZ instead of 60HZ or even the case where VSYNC is turned off on a fast computer:

double t = 0.0;

double currentTime = hires_time_in_seconds();

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

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

    render( state );
}

But there is a huge problem with this approach which I will now explain. The problem is that the behavior of your physics simulation depends on the delta time you pass in. The effect could be subtle as your game having a slightly different “feel” depending on framerate or it could be as extreme as your spring simulation exploding to infinity, fast moving objects tunneling through walls and the player falling through the floor!

One thing is for certain though and that is that it’s utterly unrealistic to just expect your simulation to correctly handle any delta time passed into it. To understand why, consider what would happen if you passed in 1/10th of a second as delta time? How about one second? 10 seconds? 100? Eventually you’ll find a breaking point.

Semi-fixed timestep

It’s much more realistic to say that your simulation is well behaved only if delta time is less than or equal to some maximum value. You can use mathematics to find this exact delta time value given your simulation (there is a whole field on it called numerical analysis, try researching “interval arithmetic” as well if you are keen), or you can arrive at it using a process of experimentation, or by simply tuning your simulation at some ideal framerate that you determine ahead of time. This is usually significantly easier in practice than attempting to make your simulation bulletproof at a wide range of delta time values.

With this knowledge at hand, here is a simple trick to ensure that you never pass in a delta time greater than the maximum value, while still running at the correct speed on different machines:

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

double currentTime = hires_time_in_seconds();

while ( !quit )
{
    double newTime = hires_time_in_seconds();
    double frameTime = newTime - currentTime;
    currentTime = newTime;
          
    while ( frameTime > 0.0 )
    {
        float deltaTime = min( frameTime, dt );
        integrate( state, t, deltaTime );
        frameTime -= deltaTime;
        t += deltaTime;
    }

    render( state );
}

The benefit of this approach is of course that we now have an upper bound on delta time. It’s never larger than this value because if it is we subdivide the timestep. The disadvantage is that we’re now taking multiple steps per-display update including one additional step to consume any the remainder of frame time not divisible by dt. This is no problem if you are render bound, but if your simulation is the most expensive part of your frame you could run into problems including the so called “spiral of death”.

What exactly is this spiral of death? It’s what happens when your physics simulation cannot keep up with the steps it’s asked to take. For example, if your simulation is told: “OK, please simulate X seconds worth of physics” and if it takes Y seconds of real time to do so where Y > X, then it doesn’t take Einstein to realize that over time your simulation falls behind. It’s called the spiral of death because ironically being behind causes your update to simulate more steps, which causes you to fall further behind, which makes you simulate more steps…

So how do we avoid this? In order to ensure a stable update I recommend leaving some headroom. You really need to ensure that it takes significantly less than X seconds of real time to update X seconds worth of physics simulation. If you can do this then your physics engine can “catch up” from any temporary spike by simulating more frames. Alternatively you can clamp at a maximum # of steps per-frame and the simulation will appear to slow down under heavy load. Arguably this is better than spiraling to death, assuming of course that the heavy load is just a temporary spike.

Free the physics

Now lets take it one step further. What if you want exact reproducibility from one run to the next given the same inputs? This comes in handy when trying to network your physics simulation using deterministic lockstep, but it’s also generally a nice thing to know that your simulation behaves exactly the same from one run to the next without any potential for different behavior depending on the render framerate.

But you ask why is it necessary to have fully fixed delta time to do this? Surely the semi-fixed delta time with the small remainder step is “good enough”? And yes, you are right. It is good enough in most cases but it is not exactly the same. It takes only a basic understanding of floating point numbers to realize that (vdt) + (vdt) is not necessarily equal to v2dt due to to the limited precision of floating point arithmetic, so it follows that in order to get exactly the same result (and I mean exact down to the floating point bits) it is necessary to use a fixed delta time value.

So 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 how to do it. 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 advances at the correct rate. 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, but we can’t do that, we must advance with constant dt; So instead we must take 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. Finally, what if VSYNC is disabled and the display frame rate fluctuates from frame to frame?

If you head just exploded don’t worry, all that is needed to solve this is to change your point of view. Instead of thinking that you have a certain amount of frame time you must simulate before rendering, flip your viewpoint upside down and think of it like this: The renderer produces time and the simulation consumes it in discrete dt sized chunks.

Again:

The renderer produces time and the simulation 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 );
        accumulator -= dt;
        t += dt;
    }

    render( state );
}

Notice that unlike the semi-fixed timestep we only ever integrate with steps sized dt so it follows that in the common case we have some unsimulated time left over at the end of each frame. This is important! This left over time is passed on to the next frame via the accumulator variable and is not thrown away.

The final touch

But what do to with this remaining time? It seems incorrect somehow doesn’t it?

To understand what is going on consider a situation where the display framerate is 60fps and the physics is running at 50fps. There is no nice multiple so the accumulator causes the simulation to alternate between mostly taking one and occasionally two physics steps per-frame when the remainders “accumulate” above dt.

Now consider that in general all render frames will have some small remainder of frame time left in the accumulator that cannot be simulated because it is less than dt. What this means is that we’re displaying the state of the physics simulation at a time value slightly different from the render time. This causes a subtle but visually unpleasant stuttering of the physics simulation on the screen known as temporal aliasing.

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

double t = 0.0;
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 += frameTime;

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

    const double alpha = accumulator / dt;

    State state = currentState * alpha + 
        previousState * ( 1.0 - 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. 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 previous and current physics 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.

Next: Physics in 3D

If you enjoyed this article please consider making a small donation. Donations encourage me to write more articles!

243 comments on “Fix Your Timestep!
  1. Очень полезная статья! Кроме того, у вас отличная способность правильно и понятно объяснять! Огромное спасибо!

  2. I have a question in regards to interpolation. Say you have a ball that moves from one end of the screen and stops at the other end.

    Let’s say that the previous x,y coordinates are 4,4 and the current coordinates are 5,5

    and the interpolation delta is 0.5. So the interpolated value is 4.5, 4.5

    So now the ball is at rest and is no longer animating and it is being displayed at 4.5, 4.5. How do you resolve the issue that the ball NEVER really comes to its actual resting place of 5, 5?

    • I don’t understand. As soon as time moves past the time of the object coming to rest the interpolation will be between 5,5 and 5,5 -> 5,5.

      • Thanks you just solved my problem! lol!

        In my fixed time step tick function when the object came to rest I was NOT setting the previous and current position to 5,5 and 5,5 respectively. This is why in my example the ball remained at 4.5, 4.5.

        I had forgotten to set the previous and current positions to the final destination position when the ball came to rest in the tick function.

        Thanks so much for the help!

  3. I don’t understand the part about interpolating using the accumulator. If the point is that there is effectively unsimulated time, surely interpolating between the current and past states is actually going backwards in time? So it may get rid of temporal aliasing but it’s going to be like a frame out of time?

    • You’re actually delaying the simulation by one frame and then doing the interpolation to ensure smoothness. That is all. Otherwise you get jitter because the simulation rate and the render rate don’t match — eg. 1,1,1,2,0,1,1,1,2,0, etc… That doesn’t look good. The eye notices. The interpolation with accumulator fixes that, but costs you one frame of added latency. — cheers

      • This is why the best possible situation is VSYNC with your game running at a fixed timestep matching that. That’s not always possible though, but if it is possible, you should always do that.

        • Thanks for the super fast reply. I already felt that there is no absolute answer and all implementations have their own pros and cons. It’s difficult to decide what to use.

          • Agreed. Like most things there is no silver bullet here. For some applications adding one frame of latency is bad and it’s better to run at native render rate (eg. FPS). For others, eg. deterministic lockstep it’s super important that everybody runs at the same fixed timestep. You have to look at exactly you want to achieve, consider all the options and think! — cheers

            • If in doubt, just lock to VSYNC on your computer. 99% sure it’ll be 60, and that’s a nice fixed timestep for development. Alternatively, you could determine what the refresh rate is and then just force fixed timestep for 1/display_framerate to run on a wider range of computers. — cheers

              • For now i’m going to go with the timestep matching the vsync hz, mainly because it’s simpler and a good default. It would be easy to allow multiples of that timestep as an advanced option. My game isn’t using a deterministic lockstep either.

                I thought that there’s something nice about how if you have an unlocked fixed timestep your game will always behave exactly how you expected, but i’m wondering whether that is really so important above other things. I think i’m right in saying that as long as the timestep is stable increasing it can only get better results.

                Anyway you’ve been really helpful so thank you.

  4. Thanks for the answer, but I’m still confused. How can it be that the code works even if there is no syncing to the display refresh rate? What is restricting the loop in the first example from running at a much higher number of iterations per second than the intended 60? (For instance, integrate() and render() might be so low-effort that the computer is able to run the loop at 6000 iterations per second, in which case the simulation will appear fast-forwarded by a factor of 100.)

    • The answer is contained in the article. Each time it runs through the main loop it accumulates time. Only when that accumulator enough time to perform one or more frame updates does the simulation run. This is how the game updates at 60fps even though it make go through the render loop (non-zero time btw…) at a much higher rate, in effect decoupling rendering and physics.

      • I understand that this is the case for the last two examples shown, but I was referring to the first example, in which the while-loop only does three things: integrates, renders and advances the time variable. Is it true to say that a fast computer is free to run through this loop at a much much higher rate than 60 iterations per second? If not, where in the code is the iteration rate restricted?

  5. There seems to be some piece of information about what the render() function represents that is only implied in this article. For instance, what is it that is preventing the loop in the first piece of code from running as fast as the computer possibly can manage, rather than at the intended 60 iterations per second?

    Does render() in fact contain not only instructions for rendering, but also an instruction to “sleep” until the next monitor refresh cycle begins, before returning?

    • The render does the rendering. It is implied that the display refresh rate is up to you — you can choose to sync to retrace or not. The code works in both cases.

  6. Hi Glenn,

    I’ve attempted to implement the most complex version of your timestep (i.e. the bottom one!), but i have a question regarding it. Should the timestep be a constant value, as my implementation has it counting down ever so slightly, i.e. it begins at around the 12th decimal place and as the program runs it gradually effects the preceding decimal places! Or, it there a bug in my implementation? I should note that i have no state manipulation currently, just trying to get an accurate delta time for the time being! Thanks

    • I have no idea what is going on there. If you are using the most complicated version then you should be stepping forward with constant delta time, subtracting this constant delta time from the time accumulator (where real time passing is added), and interpolating between before render. Please refer to the sample code.

  7. So, the line:
    State state = currentState * alpha + previousState * ( 1.0 – alpha );
    render( state );
    renders ahead the left over interpolated delta?
    How do you do this easily with the whole physics world and many objects?
    Do you have to clone your world, then step that to be rendered? That seems like a lot of overhead every frame.

    • Yes, you clone your entire world state, eg. visible quantities such as position/orientation, and you have to specially handle attached objects hierarchically.

      A much easier solution is to just always lock to 60HZ or so, if you can get away with that, it’s the best and simplest option.

  8. Congrats! One thing I think would make it even more clear is say: “In any situation, even if the real interval is bigger or less than the fixed value, it keeps being incremented and considered in the next frame”. Anyway… congrats one more time!

    • You should never use that because of two reasons: 1. Your simulation may jump to light speed or grind to a halt if your FPS fluctuates, potentially causing tunneling and other side effects and 2. It will run at different speeds on different devices, making game play lighting fast or painfully slow.

  9. Cool article! Interestingly, I encountered the issue of the physics exploding when the update time wasn’t fast enough (things moving through boundaries) but didn’t question the update logic too much.

    I have a question, though. Can you think of any ramifications for having separate time deltas for different components? For example, if you have fast moving objects, you could have them update at say 100 updates per second, but for slower moving objects or more static objects you could have only say 50 or 30 UPS. This way you can have a fixed time step (and thus deterministic calculations), without interpolation, but minimize temporal aliasing since all highly dynamic objects are frequently updated so your renderer more closely matches your simulation. Of course, you’d have to know which objects are high activity and what a good enough UPS for them is…(maybe there is a good way to figure this out dynamically?)

    So what are your thoughts?

    • There are ramifications. If the objects can interact then it will affect that, but it can often be OK.

      For example, in 2002 I worked on Freedom Force and that had high quality physics for important objects (60) low quality for others (20) as an optimization, and the AI ticks such as decision making and A* at much lower rates (eg: make decisions 4 times a second)

      But you wouldn’t want to do different update rates for objects that needed to form a stable stack.

  10. First off a big thank you for providing these concise explanations. I’ve referenced your site countless times in conversations since I first discovered it years ago.

    I’ve implemented interpolation for my physics engine, but I was wondering if I could circumvent the interpolation step for my particle emitter. Looping through hundreds of particles to interpolate seems unnecessary because a variable timestep for particles is efficient.

    I was thinking about adding an additional update call before the interpolation, and passing in accumulator, which updates my particles .

    • Yes that is a good plan. For particles and other visual effects it is typical to not fix time step for those, interpolation and the double copy of state is a waste

  11. Great article! Thanks.
    One thing I do not understand. In the while loop you step the physics engine until there is no whole step to catch up with the current render time. In other words if the accumulator is still positive after the while loop it means your physics simulation is still behind the render time. And then you interpolate between two past times. In my understanding you should go one step further where your simulation time is already in the future and the former simulation time is in the past, so you can interpolate to the current render time.

  12. Many thanks for the great article.
    I just implemented the loop like you suggested and it works seemingly flawless.
    However, I had to switch the weighting for the lerp to make it work:

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

    instead of:

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

    The bigger the remainder of “accumulator” (and therefore alpha) is the bigger the weighting of the previousState has to be. ;)

  13. I’m just getting started with programming and I’m looking this up to help with writing my first game loop so I may be wrong, but with the interpolation at the end does this mean every changing value of every object has to have a current and old value stored?
    This seems like it could be a huge amount of extra data and also a lot more code as at each step every value that changes has to be first ‘backed up’ for the old value. Is this right?
    If this is the case do you make a custom data type or custom object to store these temporally linked pairs of values and back them up or is this a bad idea?

    Thanks for the article and sorry it’s a lot of questions, this has been a very informative read for me and obviously it’s left me thinking about things I’ve not had to think about before. Haha.

    Cheers,
    Zack

    • Yes you have to store current and previous value per-object. It’s not a huge amount of data. It’s exactly double. eg. vec3f oldPosition; vec3f newPosition;

      • I guess, doubling does seem kind of huge to me though. :P I guess it depends a fair bit on the size of the project and capabilities of the target platform though.

        Looks like you just manually take care of all the backing up of variables then? Well it doesn’t look to complicated so I think I will have a go at implementing my own version soon. :)

        Thank you for replying so fast and clearing all that up for me (especially as I’ve now seen how long ago you wrote this! :O) and writing such a great article in the first place. :)

        Cheers,
        Zack

        • It’s not huge, unless you have hundreds of thousands of particles. Each vector takes 12 bytes, or 16 bytes if you are SIMD, so in a typical case with a few hundred objects you increase from 16*100 = ~1.6k -> 2*16*100 = 3.2k. It’s really not a big deal.

          If you want to keep it simple just lock to display refresh and assume constant dt = 1/60.

          • Also I think you are confused, you don’t need a duplicate of all objects variables, only immediately displayed ones, eg. position/orientation need this duplication. Basically, you just keep track of the previous and current transform for the object and that’s all. It’s easy.

    • That’s another option. The idea with this one however is that you’ll never have a timestep *larger* than your ideal dt. If you don’t care about that, then your alternate idea is fine.

      • Sure, I meant choosing the minimum number of steps that would let you have a dt below that max value. Something like

        steps = ceiling(frameTime/maxdt);
        dt = frameTime/steps;

        That way your median dt should be smaller. Naively I’d think that would produce more stable physics, but I’m not very familiar with this sort of thing!

        (Oh, and thanks again for the great article!)

  14. Hey Glenn, thank you for this awesome article!

    But I’m curious if the physics and the render would desync in case ‘frametime > 0.25′ because currentTime is increased by ‘newTime-currentTime’ instead of frametime. There is no way for the physics to ever catchup again, is there? What do you think about:

    if ( frameTime > 0.25 ) {
    frameTime = 0.25; // note: max frame time to avoid spiral of death
    currentTime += frameTime;
    } else {
    currentTime = newTime;
    }

    And I’m also wondering if it really limits the frametime to 0.25 (4fps). The time needed for one loop is dominated by ‘0.25/dt * time_needed_to_process_integrate_function’ what can still be greater than 0.25

    • Yes the time would desync. That’s the point, the computer cannot keep up with real time so time slows down.

  15. I have fixed the Problem now ;) The Problem was the rasterization on .5 float-positions
    in combination with using sub-textures in openGL. Adding one extra pixel-Line arround each sub-texture fixes the flickering problem. Now my 2D-Tile-engine (With interpolated cam) scrolls NEARLY perfectly smooth. But now I have a last problem. I render on ca. 300 FPS, but my Refreshrate is only 60 HZ. So only If I turn vsync on, then absolutly no flickering is there.
    Is it a good idia to combine vsync with fixed timesteps? Maybe 50 Logic Ticks and 60 Renderings per Second? I thought the cool thing on interpolation is the fact, that u can render unbraked on full speed? :(

    • If you do vsync and you know the refresh rate (typically 60) you can just cut through all the crap and use fixed time steps with dt=1/ 60

  16. Yes, I render already on float coordinates :(. The root problem is, that one target-pixel could change beetween the calcualtion of two equal positons ? :( Or maybe I have an other problem?
    Maybe I could write a little Test-Program, which reproduces this errors and post it here?

  17. U mean in addition to the linear interpolation or as a replacement? OpenGL always uses floats
    to draw the sprites (Quad-Vertices from two triangles) and I have never seen, that someone
    uses there interpolation for the drawing routine. Do u have a hint for me ? :)

  18. Hi,
    I have a big problem using the Frame-Interpolation with the Alpha-Values.
    I am drawing a tile grid all over the screen. If I scroll the tiles, sometimes I can see
    some really short flickering. After some tests, I decided to cast my tile-positions (float) to full
    integers before drawing them (OpenGL) and let the tiles stay on one fix positon. So actual positions (float) and previous positions (float) were always exact the same, only the alpha-values (float) changes in dependence from the delta-time. The flickering was still there! So I think, sometimes some tiles changes their position in the distance of one pixel, If their position is near the next pixel. My int-cast should always be the same, cause it “cuts” the float to an int! So there must be an full integer overflow in dependence of the Delta-Time?

    Maybe a Scenario like this:
    ActPos = 1,9999999 (Castet to int = 1)
    Prevpos = 1,9999999
    AlphaValue: 1,9999999 * 0,9999999 + 1,9999999 * 0,0000001 ~~ 2,0 (Castet to int = 2!)

    Does anyone have some trick for me….to solve the problem of the bad flickering :(
    Or maybe it is a complete other problem?

  19. Hi Glenn,

    I’ve been reading through your RK4 implementation and thinking of adding it as an option for more accuracy over my current use of velocity-corrected Verlet. This of course had me looking at your time-step implementation. As far as i see the ‘t’ value continually increments. Is this correct? If so, not that it would come up under most circumstances, is there a solution once it reaches max double?

    • I would recommend against using floating point values for time, but in reality a double value should be sufficient for any reasonable game session length. cheers

      • So is my understanding correct that you’re using ‘t’ effectively as the life of each object? Your example shows one object, but if there were objects being dynamically added / removed they’d each need their own ‘t’ so that they all updated on their own timestep.

        I.e. with a fixed physics deltaT = 0.1s
        create one object at realtime = 0s, then another at realtime = 0.05s.
        By keeping their own ‘t’ value this would ensure that the second object doesn’t update it’s physics until realtime = 0.15s.

          • If ‘t’ is the overall time for the simulation then, in the example i gave, both objects would be updated at overall time of 0.1s. Wouldn’t this mean that the second object is being updated before it should be?

  20. Ah okay, so i would have to put in multiple asteroids, but just add them to the state struct? Maybe an array world work there.

  21. Hi Glenn,

    First off, thanks for the awesome article, really useful, although I do have a few questions.

    1. When I’m using this, the actual alpha for say all my objects in one frame should be the same, so they get the same amount of physics blending correct?

    2. Also, what exactly is the part about render(state); supposed to do, what is the render function?

    3. What is a State? I understand it’s from the struct, where it is a position in terms of x and y. But say I have a game like asteroids, do I have hundreds of states, or what?

    4. Is the accumulator and dt universal, so I only need it once per game loop?

    • Yes the alpha is the same for all objects

      State is the position and orientation for all objects in your game

      Render draws your game on the screen.

      Hope this helps, cheers

      • It does for the most part, although can you be more clear on what state is? For example if I have tons of asteroids, do I need a different state created for each of them? and can you answer #4? Thanks again!

  22. Hi,
    In your opinion Glenn, what approach would you suggest for a 2D platformer, where, IMO, responsiveness and input latency are core factors to take into account? Not full physics based, but hard coded on the characters movement (think like genesis sonic and snes super mario world).
    Id like to know your opinion about both game loop and integration methods considering that kind of game.

    I also noticed you mentioning an article about input latency somewhere… >.< do it!
    Thanks a lot for all precious information.

  23. Not sure if people are going to see this with so many comments, but it’s worth noting that:

    State state = previousState * ( 1.0 – alpha ) + currentState * alpha
    [ or State state = currentState * alpha + previousState * ( 1.0 – alpha ) as you have it in the code in this post ]

    is the same as saying:

    State state = previousState + alpha * (currentState – previousState)

    which is how you might intuitively think of interpolating. To take position as an example:

    state.position = a.position * (1 – alpha) + b.position * alpha

    is the same as saying:

    state.position = a.position + alpha * (b.position – a.position)

    In English this is “advance position A toward position B by a certain percentage ‘alpha'”. (well, except alpha isn’t a percentage, it’s a decimal, but anyway)

    I assume you choose the shorter way, though, because there’s slightly less vector math involved.

  24. This may seem like a very poor question, but what exactly does your “hires” stand for in your “hires_time_in_seconds” function?

  25. I have a question to you Glenn. Is it better to check input (mouse, keyboard and packets) in fixed step loop or in render loop?

    I mean #1:
    while (true) //main loop
    {
    while(fixed step loop) //ie 50/100 times a second
    {
    check input
    do logic
    }
    render
    }

    or rather #2:

    while (true) //main loop
    {
    check input
    while(fixed step loop) //ie 50/100 times a second
    {
    do logic
    }
    render
    }

    I think the approach #1 is better especially for lower framerates (you check input whenever you need for logic, and in case #2 @5fps you could press a key for a short moment and it could be processed 20 times by logic loop).

    Could you advice me what’s better?

    Thanks

  26. I cannot seem to understand your last bit of code about interpolating.
    ‘Space’ left a comment about the same thing, saying:

    “To do the interpolation for the correct position, you should use the current position and the NEXT position, meaning you would have to always calculate the next step, a frame before you actually render it.”

    Then Glenn replied with:

    “yes thats exactly what i’m doing, interpolating between the previous frame and the current – effectively adding one frame of latency”

    Which I still dont get.. Why interpolate between current and previous, if you are looking for a “future” frame?

    If we take a look at the code and let ‘State’ represent a number which is incrementing.
    Lets say that after the simulations, we are left with an alpha of 0.75, the current State is a number of 10 and the previous State is a number of 5.

    The way that I understand it, we would want a number higher than 10, but when we interpolate between 5 and 10, with 0.75, we would get 8,75, which is “older” than the current State.

    What have I misunderstood?

    • But I’m not looking for a future frame. I’m interpolating between two frames.

      If you want a future frame then you would be extrapolating.

      That’s fine, and you can choose to do that – guess where it will be in the future – if you want, but that’s not what I’m doing

      I’m interpolating between the current and the previous state, and yes in the common case the interpolated state will be “behind” the current

      cheers

      • I think what’s a little confusing is – in a way you are calculating a future frame, as the frame will not get fully rendered until alpha reaches 1 (at which point the future frame becomes the current and we calculate another frame). I guess I don’t really get what the difference between interpolation and extrapolation is, the way you’ve defined them in code, it just seems like difference in semantics to me (“interpolation” is spelled current/previous, “extrapolation” is spelled next/current). Unless the difference has to do with responding to collision detection. I suspect it might, but can you expound on this a little bit? (or point me to some resources)

        • Perhaps a better question is, how would you change your example above to implement extrapolation rather than interpolation. I’m just curious so I know what to watch out for.

  27. Hello! I just wanted to congratulate you for such a great article. It’s a very important subject to consider when writing games and interestingly enough not many people write about it.

  28. I know this is late – but great article. It’s really a wonder how an article written 6 or so years back is still valid and correct. Math never gets old.

    Anyway – I had forgotten what linear interpolation is so the last calculation indeed threw me for a loop. en.wikipedia.org/wiki/Linear_interpolation and http://en.wikipedia.org/wiki/Extrapolation#Linear_extrapolation helped me fix that – It would be helpful indeed if you can add a note pointing to this for people who are lagging on their math. They can probably derive the equation and convince themselves that what you are doing is correct.

    Question here though: do correct me if I am wrong. I see that you have a previousState, currentState and a delta that has value in the future that you have not computed into your equation. This means two things to me:

    1. you are extrapolating, not interpolating, since the point lies outside your known points. This is unless you calculate one frame extra all the time – which I don’t see happening here.
    2. Since you have a while (accumulator >= dt), you will infact move the data one step behind to previousState in case accumulator is an exact multiple, because of your equation.

    is #2 intentional? See below for my reasoning:

    Regarding #1 above, from http://en.wikipedia.org/wiki/Extrapolation#Linear_extrapolation

    Equation for linear Extrapolation (and interpolation if Xk-1 < X* = 0 ) // might need to do with with FP tolerance.
    {
    previousState = currentState;
    integrate( currentState, t, dt );
    t += dt;
    accumulator -= dt;
    }

    //at this point, pS contains this step. cS contains next step. accumulator contains (delta – dt) = ((X – Xk-1) – (Xk – Xk-1)) = (X – Xk). Remember, we want (X – Xk-1) in numerator to interpolate between pS and cS. So add dt to this value. It will make it (X – Xk + (Xk – Xk-1)) = (X – Xk-1).

    accumulator += dt; //Make accumulator contain only delta. This is also needed for future iterations to be correct.

    const double alpha = accumulator / dt;
    State state = currentState*alpha + previousState * ( 1.0 – alpha );

    What am I missing here?

  29. First, thanks for amazing article Glenn!

    I have one question because there is one thing that I don’t understand. Let’s say, we have the fixed step physics simulation being done 25 times per second. And my question is about interpolation – how can I deal with getting into walls etc (basically – physics is calculated only 25 times per seconds while render with movement interpolation gets done 60 times per second). So not only you can get into the wall, but later when it’s time to calculate physics you will be teleported some distance behind, which is for sure noticeable on high fps, 120 hz screen etc. How to deal with it? Because as I see calculating physics for the second time in loop at the moment of interpolation with variable delta time is just stupid as it fucks up the whole idea (no fixed step).
    I hope that you understand what I mean because I’m not native english speaker – if you don’t understand fully please tell me it and I will try to tell it another way!

    Thanks in advance!

  30. Hi Glenn,
    I have implemented the fixed timestep system you have described in this article, using the RK4 integrator you described previously. For the most part it seems to be working nicely, but I’ve run into a small issue. My player movement works on a ‘target speed’ system, so if I want to walk left then the target speed on the X axis is, for example, -250. I have tried to implement the acceleration() function something like this:
    return (target_v – current_v) * acceleration_constant;
    This doesn’t seem to be framerate independent, however. When I limit my game to run at 20 frames per second to test it, the current_v value never manages to reach the value of target_v. When I allow the simulation to run as fast as possible, it does.
    How can I implement this behaviour in a framerate independent manner?

    Thanks in advance.

  31. Yes you are right. And the good thing is, that if I use collision-detection and small deltas, I cannot run in trouble (Skipping some walls etc.). I think this is the best solution at the moment for me :) Thanx so much for this article! Maybe you want to write some game-programming-book some day?!

  32. This article is great! I really want to use it for my game (Jump’n Run), but I cannot figure out how
    to implement it correct to be able to handle alle my objects with this game-loop. I have a player-object, many enemy-objects and some camera-positions (tile-engine) and much more.

    Should I save for all of the objects the states and the previous states and also do the interpolate-calculations for all of them? Maybe this is some overkill? Maybe I need something like a state-container with all positions in there? I looked into the source code of some jump’n runs (Hurrican for example) ..it is super smooth..but no one uses fixed time steps. For fixed time steps I must do a complete rework of my game-engine…is it that worth or only from interest when dealing with more complex physics?

    • it’s not that hard, but if you don’t feel that you need fixed timesteps why not just go with the semi-fixed timestep instead.

  33. I have a question about the final touch example, when you ‘blend the states’.
    How do you solve the issue when a game character Dies, or anything is removed from one state to the next? How can you blend between the 2 states of an object, where the object doesnt exist in the next state?

  34. By the way: In the last block of code, you have a couple of minor typo errors.

    Your `State` variables are called `previous` and `current`. Below that (inside the while loop), they are used as `previousState` and `currentState`.

  35. I’m seeing a jitter effect which is most noticeable during small oscillations of a spring.

    It’s only noticeable during subtle movements, but I’m wondering if that’s something that you’ve dealt with?

  36. I currently use variable timestep in my WP7 2D game “Air Soccer Tour”, and havent seen any issues besides the fact that if a frame takes a long time (physics+rendering+AI) the next frame naturally shows a jump in positions of objects. So I have reduced the frequency of AI updates (not computing AI every frame – but physics and render happens every frame) and the game stays between 50FPS to 60FPS and the results are satisfactory.
    But maybe thats because I have very less objects in my game for physics simulation. i.e. 10 dynamic objects with continuous physics (TOI stuff) and 10 static objects. and the game coordinates are 6 meter by 10 meter. small world.
    I thought Fixed timestep was a bad idea cause since the game will run fast on good hardware and slow on bad hardware. But you discussion on floating type precision, fixed physics timestep and accumulator logic makes sense.
    I do have a question on networked physics. In my game there is no authoritative server, its a casual game so not worried about cheating :). I did a very basic implementation where two phones/players have their own physics + rendering happening and the server is only relaying messages like player1 took this action/moved or player 2 moved. Now obviously the issue is that the physics simulation needs to be absolutely synchronized otherwise the two phones show different world state. And with latency of 100 ms to 200 ms over the internet, the physics go off on both ends with different results. So the next thing I did was use teleportation in the sense that when player 1 moves, it not sends its “action” info but also the whole world state. player 2 receives it and all objects teleport to the received positions before the player 1 action is executed. This of course looks completely un-acceptable to the players :) So my next try is to somehow synchronize the simulation time i.e. instead of just sending the player moved message (which happens every 2-4 seconds I might add and its sort of turn based game) I was thinking the player who is active at the moment (meaning he can take his turn) will fire off simulation time messages to the inactive player (who is waiting on the turn) the inactive player will try to slow down the simulation step time to stay in sync with the time.. so when finally the player moved message arrives, the teleportation wont loook to bad.. but now the issue is that the first player will have to double slow his simulation and it wil become a mess soon :) So, any ideas on a non-authoritative server based two player game?

    • Obviously if you have continuous collision the need for fixed timestep to avoid tunneling is greatly reduced or eliminated entirely.

      • And yes, your approach of sending state seems good. You can either run the sim on both sides and have each player broadcast the state for the object they control, or attempt to interpolate between the two last samples received from the other machine, and run the simulation only for “real” physics objects. I recommend the first approach, but first try it without any fancy time synchronization. Just apply the most recent state received over the network and do a visual smoothing (eg. reduce linear/angular error over time). You may find this is good enough. cheers

        • I tried a few things, but still have issues:

          1. I have fixed simulation timestep (20 milliseconds) and a simulation step counter on both sides.
          2. Every 300 milliseconds the “Active team” is sending positions/velocities for all objects alongwith the currentSimulationStep number e.g. 8. The “Inactive team” receives the state message after lets say 400 milliseconds when he is already at simulation step 12. I apply the received state positions/velocities, set simulation step at receving end to 8 and then re-run simulation steps in a loop to to get back to step 12 (so basically adjusting and catching up).
          3. When the active team finally takes its turn within 4 seconds, (lets say at step 16) I dont apply that move right away I schedule it on the local system 20 simulation steps in future (i.e step 36) and send that info right away to the “inactive team”. This way both systems will apply the “move” command at simulation step 36.

          Even with all this in place the game still gets out of sync. One reason I believe is that while the inactive team is re-applying state and catching up on simulation steps, it keeps falling behind in wall clock time as compared to the active team.

          Then when the active team makes its move done at step 36. The other team becomes active – and its lets say 500 milliseconds behind the previously active team now. So, now it starts doing teh same routine as an active team.. but this time the inactive team is far ahead in simulation steps. Kind of a mess :)

          I cant really assign object ownership to the teams. The two teams have 3 players each.. but then there is the ball which belongs to no one.

          i wish a simple 2d physics engine was deterministic and wouldnt use floats :) the issue is that in my game teh playing field is so small that .001 makes a difference since everything is in motiong and players are flying at the ball trying to deflect it into the goal.. so after a while the ball is completely in different positins. I took care of this with the state sync every 300 milliseconds. but now one phone is so far behind the other one – sometimes by over a second.

  37. Hi,

    There’s something I’ve always been curious about interpolating between the two different states. If say sprite animations were based off specific update states, how is that handle when the states are interpolated? For example, a player is at rest at the last state but now moving in the current state. When the player moves in the current frame, an animation is triggered. If alpha = 0.5, what do you do with the animation? If it is played, then the time passed for the animation will be a negative number. If I had to guess, I’d say to start the animation and if the time elapsed for the anim is less than 0, just display the first frame and if the time is positive, then the animation time is the actual program time minus a fixed step time. Can you clarify if this makes any sense? Thanks!

  38. Hi Glenn,

    great article! I find your interpolation technique interesting. Is this something that is commonly done in games? Somewhere above, you say that it does not create (visual) penetration. I don’t see why not. Every inexpensive (relative to the actual physics computation) interpolation technique can create state that is physically not valid. If you take your example of a V-shaped bounce, interpolation could create a position that lies somewhere in white space, e.g., between the top corners of the “V”. If there is another small object at that location that won’t actually be hit, you will get visual penetration, don’t you? Or am I missing something?

    Cheers

    • yes it has been used in many shipped games. of course there are inaccuracies with interpolation, but typically if the game runs acceptably at the simulation framerate — the interpolation errors are too small to notice. if you choose to extrapolate instead these errors are usually more noticeable. cheers

  39. Excellent post. Very insightful and well said. Continuing on your “Final Touch” approach, many people mentioned what I am about to state but I’m surprised this solution didn’t show up…

    My concern is that rendering is always rendering (0,1] timestep behind. It will never be up-to-date.

    My proposed solution follows the change from “previous/current” state mindset to one of “current/next”. We always solve up to the “nextState” and then interpolate from current to next. This shouldn’t be an issue under the concept that a single-simulation-iteration should take far less time than rendering. We also end out loop with a negative value accumulator (meaning how much time we must “wait” before we arrive at the “nextState”).

    Code changes:

    Current state = Next state (Purely for readability)
    Previous state = Current state (Purely for readability)
    Inner while-loop would read: “while (accumulator >= 0)”
    Assigning of alpha value would read: “const double alpha = – accumulator / dt;”

    Any reasoning that this wouldn’t work that you can see, and if not, then any reason that it would not work better? (Takes away the concept of always being 1 step behind.)

    The only thing that comes to mind would be interactions (or any event) that would alter the way the state will integrate from the rendered state to the “next state” that has been stored. Easy work around here is to define that such non-determinstic events are to be applied after the time has been spent to reach the “next state”… which should be hardly noticeable I would think.

    Looking forward to your response, and I apologize if someone else mentioned this and I misread.

    • Measure the time between the player input and the frame incorporating that input to be displayed. Does your method actually reduce this, or are you just renaming prev/current to current/next?

      • I’ve gone over it again, with fresh eyes, and I see what you mean. Since alpha is never going to be 1, it is in sense equivalent. Although the way I said it seems more intuitive (to me, obviously), in terms of effect your version is the same… and arguably less likely to catch people up on the details than the derivative version I submitted.

        As others said, you have a knack for teaching – explaining what needs to be said in a manner that is easy to understand quickly. I’m looking forward to reading the rest of your posts.

  40. hello glenn fiedler:
    i spend almost whole day to get a fully perspective about your article,however ,i have to say thank you ,after i followed your method ,all but my confusions had been settled ,the only one left is that my project has been building with box2d,so when the world->step within every deltatime , there are some remainder left over ,by your advice ,i should put the interpolation between two frames,but how i can do that ? do you have any advice further particular or there are not at all needed the interpolation?because in my observation ,my game character now running smoothly in the world.

    my code here is:

    static double TIMEINTEVERAL = 1.0f/60.0f;
    static double MAX_CYCLE_NUM = 5;
    static double timeAccumulator = 0;

    timeAccumulator += timeStep;
    if (timeAccumulator > MAX_CYCLE_NUM * TIMEINTEVERAL) {
    timeAccumulator = TIMEINTEVERAL;
    }
    while (timeAccumulator > TIMEINTEVERAL) {

    timeAccumulator -= TIMEINTEVERAL;
    world ->Step(TIMEINTEVERAL,
    velocityIterations,
    positionIterations);

    }

    if (timeAccumulator > 0) {
    const double alpha = timeAccumulator / TIMEINTEVERAL;

    world -> Step(timeAccumulator, velocityIterations, ); // here i dont know how to do ???
    }

    hopefully ,my expression is clearly

    • Hi. When you interpolate you want to linearly combine the previous and the current frame positions and orientations according to the alpha factor. You only need to do this if you completely fix the timestep and have the accumulator left over. Perhaps you could just try the partially fixed timestep instead, where you just simulate the remainder of time.

      cheers

    • Hi brighthead,

      did you solve this with box2d?
      i am very interested in your solution.
      please give me a hint to: its.just4phil at googlemail com

      thanks
      phil

  41. Should this method of fixed time step only apply to physics updates and have separate update for other things?

    ie:

    while ( accumulator >= dt ) { … OnFixedUpdate(); … }
    OnUpdate();
    OnRender(alpha);

    OnFixedUpdate() { updatePhysics(..); }
    OnUpdate() { updateScene(); updateGUI(); etc }

  42. Very nice read. I was just wondering, when you are talking about interpolation, are you talking about linear interpolation, like this?

    interpolated_x = alpha * previous_x + (1 – alpha) * current_x

  43. Hi Glenn

    Thanks for such a nice article.

    In “the final touch” paragraph, for your example:

    – Can I assume that the following code
    const double dt = 0.01;
    equates to a maximum frame cap of 100FPS? (10millisecs per frame)

    – And could you then please confirm that the following code equates to a minimum frame cap of 4 FPS? (that is 250millisecs per frame)
    if (frameTime > 0.25)
    frameTime = 0.25; // note: max frame time to avoid spiral of death

    Many thanks for your great effort.

    Kind regards,
    Jean

  44. Hi Glenn, thanks for the excellent infos.

    If separate threads are used, then when to base alpha on? In my case the physics will run at 60Hz, and render will have forced v-sync usually at 30Hz. I’m hoping to interpolate and avoid stuttering. But now the render thread doesn’t care about the physics threads’ accumulator remainder or ?

    Cheers!

    • one thread produces state, the other one consumes it — you’ll have to come up with a technique to work out the minimum delay is required to ensure that the render thread always has simulation state to consume. this is a closed form equation you can work out assuming you have min/max bounds on render time and the sim thread is constant (and sim thread does not skip frames…)

      cheers

  45. To avoid the 1 frame lag,
    Instead of interpolating between the previous state and current state, is it possible to step the physics one extra time to get a “future” state and then interpolate between the current state and the “future” state?

  46. Why are you setting the

    deltaTime to 0.01; in the “The final touch” example,
    and to 0 in the “Free the physics”?

  47. I have already used this great article many times for different projects I am working on. For timing, I always return here. This never gets obsolete. Well done!

  48. Hi Glenn,
    Thanks for the reply. I do understand that the curve would flatten out if we interpolate. I only suspected it at first and I’m glad to have it confirmed. If I guessed ahead before calling the collision response code, wouldn’t the trajectory be corrected? I do realize that I would have to call the collision detection and response code twice, but would this strategy work?

    • Possibly, but then you are no longer really doing a decoupled rendering and physics. You’d be basically doing continuous collision detection and collision response with variable dt. This could work well for bouncing points against infinite planes but generally, it’s better to just fix the timestep at least and just stick with interpolation. Consider the extrapolation more of a “guess” … you could attempt to say, bound that guess via collision detection, if it will help. It’s an interesting idea. cheers

      • Hi Glenn, I’m sorry I haven’t replied to your comment for a year. I somehow missed the comment notification and I haven’t been back on the site or doing physics simulation for a while now. Thank you so much for your reply and your article. I have more questions, but I need to get my head sorted first.

        Thanks again!

  49. If you interpolate you’ll see no penetration, but on bounces you’ll see the curve flatten out strangely. consider a bounce like a “V” but the bottom point of the V is not a sample point, now the bounce is flattened out.

    If you interpolate instead of extrapolate, you are “guessing” ahead, and in the V case you’ll actually guess a bit into the surface before bouncing out, at this point you’ll see discontinuity due to extrapolation. So don’t extrapolate.

    cheers

  50. Hi Glenn,

    You’ve already discussed why interpolation works better for this case. However, I don’t quite understand why you’d see jerks/snap-to-place stuff happening if you follow the following scheme:
    1. Integrate
    2. Test for collisions
    3. Respond to collisions
    within the (accumulator >= dt) loop. Except that you modify it to (accumulator > 0)
    Now, you’d be interpolating between the current and the next state. But if there was an object bouncing off at 45 degrees (i.e. a sudden change in velocity) then we’d have the correct result irrespective of interpolation or extrapolation, wouldn’t we?

    I’m very confused by this issue and would appreciate your walking me through the problem, if you have the time to do it.

  51. aha

    currentstate*alpha + previousState*(1.0-alpha)

    cs*alpha + ps*1 – ps*alpha
    -> (cs-ps)*alpha + ps which imho much more comprehensible…

    • Sure. But from my friend Fabian Giesen (@rygorous)

      “lerp(t,a,b) = (1-t)*a + t*b eval’d as a + t*(b-a) is well known but has precision issues: lerp(1,a,b) != b generally.”

      also,

      “Less well known+also 2 ops with FMA/FNMS: lerp(t,a,b) = b*t + (a – t*a) – and exact for t=0, t=1.”

  52. Hi Glenn!

    I personally enjoy simulating time-scaling, such speeding up, slowing down or even reversing time. Your method is great, but the while-routine simply stops when the elapsed time is negative. This could be solved e.g.

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

    I wrapped the whole time-functionality in a Timer-Class, which makes things easier, but I think you got the idea.

    Great articles though, all of them! Looking forward for new ones :)
    Sincerely,

    Gurki

  53. The code in the “Final Touch” section calculates the frameTime but does not use it.
    Is this right or should the line:
    accumulator += deltaTime;

    instead read
    accumulator += frameTime;

    Thanks

  54. Wouldn’t it be a lot simpler to just have a max time delta, so a physics step is never bigger than that maximum? Like this, keeping with your pseudocode:

    double currentTime = hires_time_in_seconds();
    State state;
    double maxdt = 1.0 / 60.0;

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

    while (dt > maxdt) {
    state.physicsStep(maxdt);
    dt -= maxdt;
    }
    state.physicsStep(dt);

    render(state);
    }

    • It’s a lot simpler but it does not step forward with fixed delta time. If you don’t care about completely fixed delta time then it’s a perfectly good technique. I have a reworked version of this article which includes this as one of the options discussed.

        • There is more to come… an analysis of input latency and multithreaded approaches etc. but these will have to wait for a bit later. I felt the old article was getting a bit stale and I’m a bit happier with it now! cheers

  55. Great tutorials, thanks for taking the time to write them!

    What if the update frequency was dynamic as in per computer or per scene change or even per fps drop. Take for example a simple game which fps will vary a lot (from 30-400fps on different computers). Would changing the physics update step help the game at all and when should it be done if its not in the physics initialization (after updates were done on the objects).

    • if your game physics is mostly simple linear motion, you’ll probably get no real benefit. if you have more complex physics you’ll benefit from more consistent behavior with fixed timesteps.

      so, work out how differently your game sim code behaves depending on framerate and if it’s significant or problematic then fixing the timestep is a good idea. some examples of where this is good, tunneling at low framerates if you don’t raycast, different behavior of springs at different delta time due to integrator errors etc.

  56. you can interpolate, you can extrapolate — if you interpolate you’ll add *up to* one frame of latency depending on how much accumulator you have left. the alternative is to extrapolate forward networking style and trade latency for misprediction

    cheers

    • With your code you’re interpolating between the states that happened the current state (which happened some accumulator time ago, and previousStep which happened 1 dt + accumulator time ago. So by interpolating the state at previousTime + accumulator you’re rendering the interpolated state at exactly 1 dt behind rendertime, not up to 1 dt.

      With my proposed method I would interpolate like you, but on a predicted state rather than the two previous states. What I’d like to know is why one method would be preferable to the other, or if you’d think the way I propose would be feasible/reasonable.

      • either way is good and it depends on the error you consider most acceptable during a sharp change in velocity – consider a particle moving very quickly and bouncing @ 45 degrees, cheers

  57. Hi ! I find these articles on physics very useful.
    I wanted to ask Glenn a question:
    If I had to buy a game’s physics book which one would you recommend ?
    I am looking for something that covers the basics and provides solid tools such as the ones presented in your articles.

    Thank !

    • I recommend:

      “Essential Mathematics for Games and Interactive Applications, Second Edition: A Programmer’s Guide” by James M. Van Verth and Lars M. Bishop

      “Real Time Collision Detection” by Christer Ericson

      Also, the siggraph course notes by Baraff are a great introduction to physics simulation.

  58. You are fantastic! I was having a really hard time getting a Javascript physics animation to work smoothly and accurately on all browsers/all systems, and your solution fixes everything and required minimal coding to implement! The interpolation kicks ass, I can now do super slow smooth motion just by changing a variable! It’s great for replays etc. and keep everything consistent among browsers and their crappy timings. Thank you!

  59. @David
    Don’t use time(), it will be wrong on multicore processors: if available, use monotonic time.
    On *nix systems you can use “clock_gettime( CLOCK_MONOTONIC, …” and linking with -lrt

  60. Great article.

    Only problem I encountered was instances of negative deltaTime (which made the dot animation vibrate as it moved). Apparently this can sometimes happen on duel-core CPUs. Easy way around this was to simply add another loop to update deltaTime until it is positive again (ignoring it basically).


    float newTime = time();
    float deltaTime = newTime – currentTime;
    while(deltaTime < 0){
    newTime = time();
    deltaTime = newTime – currentTime;
    }
    currentTime = newTime;

  61. also for what its worth, using a float value to accumulate time t from dt is also craziness, please consider that you should have some 64bit fixed point representation of time if you use this technique, otherwise the precision of your time t gets worse the longer your program runs. i only use float here for clarity because i use it for the dt and accumulator only. if you have a truly fixed timestep, then you can use your integer frame count as time

  62. i agree that checking if two floats are equal is very bad, but as far as I can tell conditionals you presented are exactly equivalent:

    bool a = accumulator >= dt;
    bool b = ! ( accumulator < dt );
    assert( a == b );

    (try this and let me know)

    of course, bool c = accumulator == dt;

    is craziness…

  63. Hi,
    Thank you for great article!

    I have on remark, though.
    I think that it would be better, if instead of following condition:

    while (accumulator>=dt)

    you’ve used:

    while ( !( accumulator < dt ) )

    Comparing if two floats are equal can get you into trouble.

  64. Thanks for the article I get my timestep fixed !

    But for those you think it’s a bit complex to use a coefficient to calculate the exact position of all their physic objects and than it complicate the calculate and codes, I found a simple solution costing only some part of 1 frame and doing the same exact result.

    In fact you just have to to wait some milliseconds to have a round count of frames, for example, your render function took 88ms and your physics frame is fixed to 10ms then you wait 2ms and calculate the number of physics frame to do (88+2)/10 -> 9 you proceed and render again, so simple!

  65. this is actually very hard, i remember a paper about something pixar did for Monster’s Inc where they ran a solver to solve motion for rigid bodies to pass through various points and end up at a specific configuration (e.g. one side up)

    i would say that you should try to find this paper and read about how they do it

  66. Hello.
    Can you help me, please? I need to solve a simple problem.
    I created a cube (JBox or Cube). The cube fly from same top point and then rolling on the plane. How can I make, that cube always stopped the same one side up?

    Sorry for my bad English.

  67. Nice article. I have developed a game for the iPhone, and the game renders and it is played beatifuly on an iPhone 3GS or 3rd generation iPod touch, but on older hardware it starts fine, but at some point on the game, especially when loading textures, and because of memory constraints, I need to start clearing the image cache, and that eventually lowers my fps, after a few seconds everything comes back to normal. But the thing is, that under those few seconds, some objects that were falling, suddenly they appear on the ground, and the point of the game is to kill this objects in mid air. So my question is, do you think that implementing the rendering interpolation and/or having the calculations and rendering algorithm on different threads might eliminate this problem? I have implemented the fixed time step, but not the rendering interpolation. Here is the link of the game to give you an idea: http://www.softwarefactoryllc.com/airassault

    Thanks.

    • you could move the texture loading and other stuff onto a separate thread so they don’t hitch up the simulation – this is the best way to get around your problem. interpolation as described in this article won’t help you. moving the sim off to a separate thread is another way to look at it, but i’d first try getting the loading async – cheers

      • Thanks for your response. I tried all the solutions, but what really did the trick was clamping the dt values to 0.1. Now the game is super responsive in any situation on all devices, and even if it gets slow, at least the physics and rendering engines are in sync always.

        Thanks for a great article, and for taking the time to clear my doubts.

    • Thanks! Ironically, it’s the very first article I wrote waaaaaay back in 2004… and it’s still the most popular. Despite many attempts to improve my writing style. I should just give up. This article is always 2x more hits each day than any other =)

  68. at this point, when running the integrate function in the physics loop, is this call completely CPU independant ? I understand we are independant from rendering, but are we independant from cpu speed for simulation ?

    • I’m not really sure what you mean. Yes it’s CPU independent, to a degree assuming you can simulate one physics step of dt in less than dt/2 in real-time, you should be fine. Otherwise you may get spiral of death given that you may have to simulate 1-1-2-1-1-2 etc. to speed up occasionally when the sim rate is lower than the render rate. Alternatively, you could move the sim into it’s own thread or process to be completely asynchronous to render.

  69. I forgot to mention in your sample code you are also interpolating the velocity, not only the screen position: obviously you intended to interpolate the screen state with properties like position, rotations and scaling, but this may lead other people to think they need to do the same with other forces, as well as trying to inject these lerp’ed values back in their physics engine.
    I was reading Box2D forums and some code around and, sadly, most of them seem to misunderstand this very important point: too bad since it’s a very well-written article on a too much often undervalued subject.

    • You are correct in that the velocity does not need to be interpolated. The code interpolates the entire physics state for the object but in fact the only interpolated quantity which is actually used is the position.

  70. Glenn Fiedler :
    to take it even further, you can run the main physics loop entirely on a separate thread which actually runs (in real time) at the number of frames per second the physics should run (say 100hz) and the render thread just reads latest physics state and interpolates, completely independent of physics
    this way you are never doing two or more physics updates per-update, so processing is more evenly distributed
    in addition, if you gather the input for you simulation on the physics thread, you sample the joystick or keyboard at regular 100hz intervals, which leads to better behavior of your physics
    consider this, “fix your timestep version 2.0″

    Hi Glenn, thank you for such a beautiful article, nicely done!
    I implemented a testbed with box2d and i have the renderer running in the main thread, while the physics and input are running on another one: i’m experimenting the better way of doing things and at this point i can say from my tests that a strict producer/consumer model (that is, a frameNeeded semaphore and a frameReady semaphore) make the physics thread fluctuate since it’s need to wait for the render thread to signal a frameNeeded.
    However, implementing it with a mutex protecting the “onRender” call (main thread) and the same mutex protecting the “onUpdate” call (in the other thread), adding “usleep” to avoid both threads concurring much for the lock seems to work flawlessly.
    The thing i can’t get to work is the render thread to do subframe interpolation: i mean, everything is fine if the update thread do the subframe interpolation/time aliasing lerp, but if it would work in the render thread as you said it may need less cpu time if vsync is on.
    Anyway, let me know if i can send you my code for your own tests: i see you are planning a “fix your timestep v2″ so i’m willing to help you out, although i’m running Ubuntu it shouldn’t be a problem to make v2 cross-platform!

    • In general, physics simulation is too complicated to solve analytically so it is solved via numerical integration. Numerical integration is an approximation to the exact solution in which the accuracy of the result depends on the size of time-step. Typically numerical integration gives more accurate results for smaller time-steps. It follows that one step of n*dt is not the same as n steps of dt.

    • state is the current attributes of a body in the simulation

      for example for a rigid body state is position, velocity, orientation and angular velocity

      for a car, state could have all of that information but also include the RPM of the engine, the current gear, the suspension lengths for each wheel, the speed of each wheel rotating and so on

      basically, state is the thing which you step forward by delta time (dt) each step of your simulation

      cheers

  71. Great article, thank you very much.

    Just to be sure ( i am new in game development ), if I understand, any code writen inside the ‘while( accumulator >= dt )’ is totally independant from framerate, is that right ?
    So is this the good section to implement any game mechanics that have nothing to do with rendering ?

    • precisely, the game simulation update goes inside the while loop – anything which is per-render frame goes outside – eg. perhaps you have some visual only particle effects, these could be updated at render frequency if you wish

  72. Sorry, but I’m having a bit of trouble implementing this in obj-c
    I ported the code from the download example you provided and my version compiles and returns results, but the values seem way off.

    One method in particular has me wondering….

    float acceleration(const State &state, float t)
    {
    const float k = 10;
    const float b = 1;
    return – k*state.x – b*state.v;
    }

    Why isn’t the value of “t” used in this function?

    Thanks

    • the value t is not used in that function, it is just passed in in case you want an acceleration that is a function of time, eg. sin(t) – in this case, acceleration is just a function of distance from the center point and velocity (it is a simple damped spring)

      cheers

  73. Ah, works perfectly!
    Also, thank you for your advice on fast forwarding, makes sense too. :)

    Thank you very much for your help~!

    Cheers~!

  74. I am curious: how does one handle interpolation of objects that do not exist in one frame or the other? for instance, a bullet only exists in the frames between being fired and hitting its target. Does one simply not display these objects? Or would something more involved be preferable?

    • if an object is created, you just set its previous position same as the current, eg. dont interpolate

      if the object is deleted, then obviously you dont need to interpolate it because its no longer there

      of course, to be smooth about it fade-in fade-out works fine, during which time you’d interpolate normally

      cheers

  75. in this case there is no need to extrapolate, since the rendering is performed synchronously with the simulation in one process – of course, if you had a server process running the simulation and a client process viewing it, then yeah it would make sense to have support for extrapolation

  76. Hi,

    nice article! Although I’ve been using these techniques for a while, I never thought of it this way. Rather, these are classic client/server game design (client doing rendering, server doing physics and stuff). The interesting part however, that one that threw me a bit off, you interpolate between last and current frame (effectively adding a frame of latency). Wouldn’t make more sense to extrapolate (sometimes called prediction) from the current frame onto the next, and compensate when the frame is finished? The reason for this is two-fold, one, as you describe, to smooth the animation, and two (which is more important if you’re a network jock like me) to compensate for packet loss.

  77. I see now, that the spiral I mentioned can be avoided by making sure the timestep is big enough. Of course there will be a lower limit of how slow the computer can be then, but you can’t expect your games to work on a 286 anyway :)

    I also wondered about the interpolation.

    I understand the reason to interpolate and not extrapolate, but it doesn’t make sense though, since the position you are getting is a previous one.

    To do the interpolation for the correct position, you should use the current position and the NEXT position, meaning you would have to always calculate the next step, a frame before you actually render it.

    Maybe that is what you are already doing, and I just didn’t catch that in your code. I don’t know.

    I was also thinking, that your clamp the deltaTime to some max, it would mean that you couldn’t use it for realtime multiplayer games, since one computer could get behind. But I guess it could under all circumstances, since the timers might not run the same on both. I guess in such cases you would need some time signal from the server to keep it accurate. But maybe these differences would be so small that it wouldn’t be important.

    By the way, thanks for the article, it was useful for me.

  78. yes i actually prefer the separate thread approach myself, and it has better CPU patterns than the approach in this article, avoiding having to simulate 2 or more sim frames per render frame in the common case, spreading it out properly with frame sleeps — it also avoids the “input aliasing” that you get with this approach, which is subtle, but there

    or even better — put the simulation in a different process and connect a “view client” to it, using a simple network model with interpolation/extrapolation

    ps. the reason i interpolate previous two frames is to always be accurate, you could extrapolate from the current frame if you want, but this causes discontinuities if the velocity changes abruptly (eg. a bounce…)

    cheers

  79. Hehe, well if it takes longer than your time step to simulate that amount of time, you’re in a bit of trouble! You probably need to increase the size of your step..

    These are some very good articles!

    Though I’m slightly baffled by the interpolation used.. You’re dropping back one step then interpolating by alpha towards the most recent known data.. Is that really the best way to handle it? I guess it’s the only accurate data..

    Any way I was thinking that having the rendering done in a separate thread would be the best solution, but it adds complexity and makes things harder to debug.. So I was considering going with the single threaded approach for initial revisions and then moving the rendering to another thread.. But do you think this would just cause more pain in the long run than just starting with that approach?

  80. if you’ve already got code that can interpolotate a timestamp… if your simulation can’t keep up, you’ll atleast know how much it isn’t keeping up by the accumulator being > than 1/60th (or whatever rate you are intending to get)… and can get a rough interpolotation since the last time.

    maybe that didn’t make much sense, but it worked decently enough for me.

  81. sure thats actually correct, but the premise of this article is that you can actually afford to simulate one timestep in <= the actual time it is simulating

    so in your case, you should simply use a variable framerate, or optimize your code down so it fits in budget

    cheers

  82. I’ve discovered a problem with this method.

    If the computer cannot keep up, meaning it’s been longer since last frame, then you have to calculate several physics states for that frame.

    This will mean that this frame will take even longer to calculate for the computer, and thus when you get to the next frame, even more time has passed, and you will have to do even more calculations for that frame, which will take even longer.

    It’s an evil spiral, that means once it just gets slow enough once, for the computer to not be able to keep up, then the accumulation will just keep growing bigger every frame.

  83. It seems to me that with this method there will always be a remainder. It’s unlikely that the time would happen to fit with a multiple of your dt, so you will always be doing interpolation.

    You write: “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”

    If you want to interpolate the next point, you should be getting the the blending factor between the current and the next state, not the previous. So to do this interpolation, you have to also calculate the next step, even though you are not yet taking it.

  84. Exactly, I am getting this exact problem right now.
    What was hard for me to “get” was the part that, on the last code snippet, we’re not rendering something that is the latest physics step we know of, we’re rendering 1 dt BEFORE that!

    That was kinda weird for me at first, but it makes a little more sense now. As soon as I can figure out how to get/set all of the “state” of the simulation (I am using a framework, Box2D, so it encapsulates the state), I’ll try that and see how it goes. Thanks again!

    Cheers,
    Marcelo.

  85. yes, you are stepping forward at nice physics intervals like 1/60th of a second, but rendering at another rate – since you have no way to get the exact position at the real time of render, you just interpolate between the two nearest physics steps to get the approximate position at the render time t, so that your rendering is smooth

    if you don’t do this, you get temporal aliasing – eg. jittery movement

    cheers

  86. I am a programmer and wannabe-game-developer, and am currently trying to tackle a project that is much larger than my skills. Just ’cause. :)

    Being that so, I have to thank you very much on this article, it’s been really helpful. It’s also taken me several hours to wrap my head around the “final touch”. I’ve been able to “free the physics” and, of course, experienced the problem you mentioned.

    So here’s how I understand it: In “free the physics”, we are always rendering the latest physics step we have, even though we’re a bit ahead of it in time. On transitioning to “the final touch”, though, we decide to render something that is between the latest physics step and the step BEFORE it. That would mean, as I understand, we’re further away from “the truth” (the state as it would be in current time) than we were before deciding to interpolate, but that means better animation.

    Do I understand it correctly?

    Thank you again for this,
    Marcelo.

  87. damian, yes i agree the absolutely correct pattern is a producer/consumer model with the simulation running in another thread or process from the renderer – i’ll be writing a new article about this at some point i hope

  88. For the Windows alt-tab issue, the other solution is to run the physics code even when the renderering code isn’t happening. This should free up the CPU time being used for graphics, and given the technique in the article wouldn’t need to run perfectly smoothly anyway.

    This is especially important in multiplayer games where you can’t just automatically pause the game.

  89. I was reading your article and tough it was perfect, but I just though “integrate” meant the physics update/game logic/input pooling and I though it was working this this, but after checking the source code, integrate is really a mathematical integration, and I don’t quite understand what it is doing there. I also don’t quite understand the constants used in the function, and what are x and b are supposed to mean in your State structure..

    • Basically integrate just means to advance the simulation state forward. You can try it with something simpler like euler integration, eg. x += dxdt * dt if you like. cheers

  90. Hi Glenn,

    Thank you for this article, as a beginner in game development this is a great help and I will definitely make my game loop like this.

    I also like the way you separate your window code from your game code, it makes everything so much more clean.

    I got a question though, when I run your example I can still see the dot stuttering from the moment it goes left for the second time and the stuttering stays until it slows down in the middle.
    Is that normal? Am I being too picky? Do you have the same effect when you run it or your computer?

    Anyway, again, thanks a lot for this.

    Regards

    David

  91. Thanks for the great article. You have the optimal solution here that I really wish I had known about when I was screwing around with physics simulation Java applets back in high school. The animation was just never quite right.

  92. Hi cheers

    I cannot make him to work still, but I think that I am very close.

    At the moment, I don’t use QueryPerformanceCounter .
    I wanted to ask to you.
    How much can this affect in the problem?.

    At the moment I has a undersampling problem.
    My fps fluctuates between 29 and 35.

    Advance thank you

    KIKO

  93. What confused me is that the actual current time is currentTime + acumulator, so it’s outside the (previousTime, currentTime) interval. But after thinking it trough I realised that what you’re doing is shift the fraction alpha back one inteval. This is complelty legal, as the game loop uses a fixed time step. So CurrentState could be vweyt well named NextState and PreviousState could be named CurrentStep.

    Thank you for your time, reading your article and replies was very informative. One other question though (feel free to ignore it): why do you initialize currentTime to 0? Isn’t that going to give a wrong deltaTime the first time the game loop is entered?

    Best Regards, Cazy.

  94. interpolation is between two known values, so its “perfect” – just lagged by up to one frame

    extrapolation is jerky and is predicting ahead, thus gets it wrong, and has to snap and pop to correct

    trust me you want interpolation

    take the example source code and change it to extrapolation, and let me know how it goes! – maybe it’ll be good for you, i’m conservative so i prefer interpolation

    cheers

  95. I am very impressed by the quality of the article too. I’ve read a few more on the subject but none was this clean and eloquent.

    One comment though. The interpolation function in your code looks like this:

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

    My calculations (and intuition) say it should be:

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

    Am I wrong? Can you double-check your math?

    Best regards, Cazy.

  96. i think you should try a simple example first, and get your head around it — its not hard! but becomes complex when introducing middleware and “its way of doing things”

    here is what i think you need to do with newton, always update it at 60fps (~16.7 ms per frame), but interpolate between according to render rate, as described in the article above

    so newton is always creating state for you on integer frame numbers, exactly 1/60th of a second apart, while your renderer is not always doing this, it is working on arbitrary dt, — so you interpolate between the two nearest integer frame samples to find the position/orientation of your body at the render time

    cheers

  97. Hi Glenn

    Thank you for their attention.
    I have a question more.
    Suppose you, that I update the physics with a dt=0.016 that is the minimum that NewtonGD requires.
    The range is of (1/60.. 1/1000) for NewtonGD.
    I would update the physics X times before the render, you suppose 16 times.
    With a smaller dt=0.01 I would be update the physics more times, you suppose 25 times.

    My question is:

    Should I have a buffer the position/orientation coming out of newton’s callbacks of variable size?
    For example: 16 for dt=0.016 or 25 for dt=0.01.
    Is this correct?.
    if it is this way.
    How I do make to manage after the update of the physics the render?

    I implement the solution with 2 variables (currentMatrix previousMatrix), but I have the problem of the stuttering

    I am really confused

    Advance thank

  98. Very nice article. I was using this method for a game and it actually caused a very subtle bug. When playing very large in game cut scenes, the audio would become out of sync with the animations. I tracked the problem down to delta time accumulating error. The solution instead was to keep a simulation time and a real time. Then the loop is something like:

    while ( (time() – simTime)>=dt )
    {
    simTime += dt
    }

    You still get error but it’s less. It also works with a crappy timer :)

    Leigh

    • This is a suitable implementation if you don’t need a fixed delta time, but for general 100% repeatability and same results each time run, I generally prefer the full fixed dt myself. cheers

  99. Hello, great article! I’v implemented your technique but I’d like your advice about (mega)oversampling.

    My project doesn’t do much things so the framerate is insanely high with my PC (3000fps), and the timer of my engine (Ogre) gives me a deltaTime of 0, because it’s has a precision of 1 milisecond, so 1/3000 = 0.00033s = 0.33ms (that’s why I got 0).

    I already had this problem with the SDL timer and I guess a QueryPerformanceCounter or any other high precision timer have the same limitation. So I thought putting some ugly Sleep() in the code to obtain a valid deltaTime. How do you think it’s possible to do something about this ?

    And even I if want to fix the display framerate, the problem is the same (adding 0 to any accumulator, so it’s never time to update).

    Thank you !

  100. I thought I could get by without fixed timestep, however some testers were having issues with the game I’m working on – which were fixed by a fixed timestep. Thanks for writing the article, it saved me tons of time messing around.

  101. Excellent article and very helpful to my current situation. Thanks for taking the time to explain this in terms that non-mathematician games programmers can have a half chance of understanding.

  102. Given the last interpolation trick with ‘alpha’ blending between states, you’d think that for physics-intensive programs it may be important to really catch up with realtime. I.e. after the while(accumulator>=dt) loop finishes, do a new deltaTime calculation with a new time() call and re-enter the while loop if deltaTime is bigger than some threshold.
    I’ve noticed with my car simulator that the physics can take up quite a bit of CPU time, making the last alpha blending call a bit useless if you’re already straying away from the actual time.

  103. Thanks so much for posting this! After trying to figure this out after many hours, I was able to quickly come up to speed thanks to this article. Excellent work!

  104. Excellent articles on game physics. I’m starting to do some research on network-based state machines/physics and they were quite helpful.

  105. Great article! Best article I’ve read on this important subject. Very nice and clean implementation too.

    Do not worry about your difficulties in Mathematics. I can assure you mine are still greater
    -Albert Einstein

Leave a Reply to Glenn Fiedler Cancel reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>