Game Loops

IPC is getting so nice that we have to start tackling the hard problems like user interaction and the Canonical Game Loop.

Don’t know what the Canonical Game Loop is? Well you’re in the right place. I’ll start by talking about integrator step, then I’ll contrast variable with fixed step, and finally I’ll introduce the happy medium that is the Canonical Game Loop.

Integrator Step

Say you have a ball (in a one-dimensional space) with mass 1 kg, going at speed +3 m/s, at position 0 m, with a force acting on it of -1 N, at time 0 s. You want the integrator to find its position at time 1 s.

The way you’d do this in Physics class is to take ∫01(3-1t)dt, giving the result 2.5 m. But the typical game simulation is far too complex to solve analytically, so the integrator has to do it numerically.

With a timestep of 0.25 each time, it steps the simulation Newtonianly by 0.25 s, recomputes the forces, steps again, until it has covered a whole second. This gives:

Time Position Velocity
0.0 0.0 3.0
0.25 0.75 2.75
0.5 1.44 2.5
0.75 2.06 2.25
1.0 2.63 2.0

Not quite 2.5 m, but close. If, on the other hand, an integrator step of 1 s is used, then it computes the final position as 3 m. That’s pretty bad. In summary, bigger integrator step ⇒ bigger error. Most of you probably already knew that.

Fixed & Variable step

There are two obvious ways your game can integrate, using a variable and using a fixed time step. A variable time step measures the time that it took to draw the last frame and uses that as the time step for the next frame. This way your simulation always runs in real time, no matter what your frame rate. A fixed time step uses the same step no matter how long it took to draw the frame. In order to keep this in real time, a sleep can be issued if the drawing time was shorter than the time step.

At first glance, variable time step seems like a big win. You’re always maximizing the potential of the computer, getting the most accurate results that are possible to calculate in real time. There are big problems with that, though. First, since the computer doesn’t run at the same speed all the time (background processes, temperature, etc. play in), your simulation doesn’t come out the same if run two different times with the exact same input. This is obviously something that we don’t want to happen for a game like the incredible machine. Another problem is that if you move the window, suspend the process, do anything that takes more than a small amount of time in which the program doesn’t get to run, you get a huge time step, and thus big error and instability in the system. This latter issue is correctable, though.

On the other hand, a fixed time step will always give you the same result for the same input. Many games want this, IPC in particular. But, not surprisingly, it too has issues. If your computer’s faster than the pre-chosen time step, your frame rate suffers. You might only get 24 frames per second when your machine is capable of hundreds, because of the sleeping involved. If your computer is too slow, the game’s time slows down and you’re no longer running in real time. Although if you want a stable system, this latter problem is uncorrectable. Thus “minimum system requirements.”

Enter The Canonical Game Loop

The Canonical Game Loop is a way of using a fixed time step while not making fast computers’ frame rates suffer. The first thing you have to do is separate the drawing pass from the integration/computation pass. Fortunately, this is something that IPC has done from the beginning (yay design choices!). The game loop looks something like this:

    num time = 0;
    loop {
        time += timer.tick();     // Get the time since the last tick()
        while (time > TIME_STEP) {
            Integrate();
            time -= TIME_STEP;
        }
        TIME_ERROR = time;
        Draw();
    }

Not surprisingly, this is almost the exact code used in game.cpp from IPC.

When you’re drawing your objects, you fetch the position and rotation first, right? So when you fetch the position, add the velocity times TIME_ERROR. Likewise when you fetch the rotation, add the rotational velocity times TIME_ERROR. This is extrapolating, so your results will be slightly non-physical. But if you have your TIME_STEP sufficiently low, this isn’t a problem, as nobody will notice.

The way I did it in IPC is made a wrapper around the ODE dBodyID, and added the velocity time TIME_ERROR in the pos() method. That’s all there is to it, but to do it right, you kind of have to know that you’re going to do this from the beginning, as it effects your design.

You can also interpolate, so that your results will never be non-physical (no penetrating bodies, etc.), but that is more computationally expensive, and requires one timestep of visual lag. For IPC that’s fine, but for a more real time game, that might take away from the responsiveness too much. I encourage extrapolating, because of its algorithmic simplicity.

Now the next time you write a game, you’ll know what to do so that you can implement the canonical game loop.

About these ads

3 thoughts on “Game Loops

  1. Thanks! I’ve been searching for available timing concepts that can be used in a game loop. This post covers the two I’d run across so far, but it’s nice to find you’ve put them here in one place. I’m also wondering if using threads would propose a third alternative, or does that basically utilize either of these concepts? Are there any other approaches out there?

  2. Threads would be a pretty terrible idea for something like this without some extreme magic. If you want one thread for integrating and one thread for drawing, you’d have to copy all your structures into a “to be integrated” pool so that your drawing thread doesn’t get half $step objects and half $step+1 objects (and maybe one object that’s half-and-half of each). Ultimately, that may end up being slower than doing it synchronously. Maybe you had something else in mind for threads (there are a lot of uses, where the terrible idea is just one)? I’d be happy to cover it.

  3. Ah, good thoughts. You addressed much of what I was pondering (I’m still trying to organize all these ideas in my head). Perhaps a separate thread could be used just to blit a pre-rendered screen to the monitor (which may only be useful if waiting for vertical retrace). But you’re right that trying to use separate thread(s) to render a screen would be a nightmare. Thanks for responding :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s