Monthly Archives: March 2004

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.

Heppa

Well I have Hepatitis. Yeah, ouch. It’s Hepatitis A, the nice one, but it’s still no walk in the park. My mom gave it to me; she picked it up from Peru somewhere. I’m most contagious …… now! But people around me probably don’t have to worry, because I wash my hands often and I don’t prepare food.

On a related note, I’m hosting Poker tomorrow because Drew can’t. And if they beat me, well, I hear Hepatitis is going around :-).

I get the impression it won’t be that bad. I just noticed my urine getting a little orange a day or two ago, and I’ve started taking really good care of my liver now. Just eating salad, eggs, asparagus, etc. Plus, before I was born, I purchaced the best immune system money could buy, so I imagine I’ll fight this off relatively quickly.

Poker Winnings

I won two of the four tournaments tonight at the poker club (I guess it’s a club now). A $1 and a $5 (while losing a $1 and a $5). That puts me, let’s see, $18 up. Both times I went heads up with Drew, formerly the only one who could play me without luck (that is, I consider Namaste, Metz, and Clif to be about on my level—though with vastly differing styles).

Drew plays looser than I do, when I’m in the right state of mind. Not much looser though. He bluffs me out a lot pre-flop, and occasionally when I’ve made it clear through my tells that I’ll fold. But he won’t bluff me out of the bigger hands. On the other hand, he seems quite ready to give me the pot when I go over the top.

He’s a very smart player though. I suspect next week he’ll have a new surprise for me that I’ll have to figure out to win. For instance, he’ll take his reads on me to another level (that’s what he’s got on me: he can read me much better than I can read him, but I killed him mostly with complex mechanics).

On a related note, I accepted a $50 buy-in tournament that Namaste told me about. The host expects 16 people, probably amounting to a $400 payoff for first. In order to win this, I’m going to have to step back and concentrate on my strengths: pure tight agressive play with the occasional well placed bluff (that could be advertizing: I’m good at advertizing). If I start bluffing too much, say, 5 times per tournament :-), I lose because I’m an aggressive bluffer. I should play online and work on winning every sit-and-go tournament I play.

IPC is picking up

Incredible Physics Contraptions, our Incredible Machine clone, is picking up. We have a mailing list, an IRC channel (freenode#ipc), a team of five. Now all we need is some code :-)

Seriously, the code is coming along nicely. I mean, I’ve only got 400 lines or so, but it’s enough to get started. There’s some lean, mean archetectural stuff in there, which was fun to finish. The Widget traversal system uses functors to separate the order and number of passes from the code that does each pass. Very nifty.

Bored and Tired

Sitting here at school, having been up for 17 hours already, and have yet a class at 7:30 (Don’t feel like using the personal nominative pronoun today). Also, on a fast, so can only drink water (for a particular health reason—not because think am fat). This makes me even more tired than should be.

Have to work on The Incredible Machine (renamed “Incredible Physics Contraptions” by Namaste). But am too tired. Decided to blog to waste time instead of working. That’s why you’re reading this drivel. Shaving Yaks as they say.

Perhaps can take a nap. Hope feel better. Hope use that one letter word again.