The problem

In a game, you run a simulation, which you step by some amount of elapsed time to update the simulation. Then you render a frame to show the user what the simulation looks like. Then you repeat.

Many simulation systems ("physics") work best when you step them by the same amount everytime; they'll go unstable if the step size fluctuates. Thus, measuring the elapsed time and stepping physics by that amount each frame will not work well. It's also useful to have a fixed step size when supporting replay, as you can just save user input to a file, rather than the full state of the simulation.

When you do this, however, you will find that different PCs have different speeds; some will be able to run grahpics frames faster than your step size; others will not be able to keep up. It would be nice if someone with a ForceRadeon 400,000 Deluxe can get a grahpics rate that's faster than your fixed step size; it's also necessary for someone with an Intel Extreme 3D Graphics built-in chipset to still be able to play your game.

The solution

To achieve this, structure your game loop something like this:

oldstate = initstate();
newstate = initstate();
now = seconds();
oldstatetime = now-STEPSIZE;
newstatetime = now;
while( running ) {
  while( get uievent ) {
    handle uievent
  cur = seconds();
  if( cur-now > MAX_ALLOWED_FRAMETIME ) {
    // pause, load time, etc -- reset progress
    newnow = cur-STEPSIZE;
    oldstatetime += newnow - now;
    newstatetime += newnow - now;
    now = newnow;
  while( cur-now >= STEPSIZE ) {
    copystate to oldstate from newstate
    newstate = step newstate by STEPSIZE
    now += STEPSIZE;
    oldstatetime = newstatetime;
    newstatetime = now;
  render extrapolated state from oldstate to newstate extrapolate by 
    STEPSIZE + (cur - newstatetime);
  render interpolated state from oldstate to newstate interpolate by 
    (cur - oldstatetime);


If you don't want to keep two state copies around to extrapolate (or interpolate) then you can render iff you actually stepped, else snooze for a few milliseconds. Although snoozing on 16-bit based versions of Windows (98, ME) is likely to be very jittery.

If you use EXTRAPOLATE, then the graphics display will be "current" (or as current as you can make it) but it'll always be slightly non-physical, with small overshoots etc.

If you use INTERPOLATE, then the graphics display will be physically based (no penetration right before a collision, etc) but there will be a graphics lag of about one step/frametime. If you can keep the frame time high (> 50 fps) this is not a problem, and is recommended.

The MAX_ALLOWED_FRAMETIME check is there to avoid the spiral of death that might happen if physics suddenly runs slightly slower than real time -- if that happens, we want to limit the amount of updating we do to some fixed time-step, such that the real time speed of the game will slow down, but at least it won't spiral out of control with ever-longer frame times trying to catch up. It's worth noting, though, that if you run a distributed simulation (networked game), falling behind for any longer period of time will lead to de-synch of the game. This is why networked games are often more serious about their PC minimum spec requirements than traditional first-person games.

So what are reasonable values for these constants? Of course, it depends on your game. For a rigid body simulation, you probably want the physics update rate to be 100 Hz, so STEPSIZE is 0.01 seconds. In that case, you probably want to set MAX_ALLOWED_FRAMETIME to something like 0.05 or 0.1 seconds.

For an interpolator class, see the article on this web page.