How’s your relationship with your game loop? Is it a relationship based on mutual love and respect? Do you recognize each other’s strengths and weaknesses? Understanding the Game Loop is a critical element in programming interactive entertainment and utilizing it effectively can undermine or help support your development goals. In Frame Based Code Sucks!, I discussed some of the pitfalls of a game loop that is frame-rate driven. I presented a simple time based alternative in order to prevent some of the issues that we encounter in a frame-rate locked solution. This implementation was actually flawed because it was incomplete. Today, I will go over some of the pitfalls of time-based code, and how to deal with them effectively.

Time-based engines must deal with one particular concern otherwise our code may end up being just as unreliable as a frame-rate based solution. A simple delta time implementation, as discussed in last week’s article, introduces non-deterministic behavior into our simulation. Non-deterministic behavior is very very bad for effective development as it is inconsistent at best, or unpredictably difficult to debug at worst. It is introduced by the fact that the deltaTime with which we do our per-tick calculations is unpredictable in size.

In a game running at 100fps, we might expect the deltaTime to be in the region of 10-20ms, depending on the speed of the rest of your code. Hitting spikes in execution (a massive colliding stack of boxes, for example, or another process hogging the CPU), can potentially introduce deltaTimes that are 50-100ms in size (or more), which can cause some really unpredictable results (noticeable as things start popping outside of the level boundaries - we’ve all played games like this!). This side-effect is known as tunneling.

Case Study: Tunneling

Tunneling is the term used to describe the unwanted occurrence of a fast (usually small) moving object passing through what should be solid a barrier, such that it seems like the object magically teleported through the boundary. The following diagram illustrates the conditions under which this can occur:

In Hunky Dory we have 7 ticks coming in at 20 ms per tick, and we’re moving our object along in lots of little jumps. We detect the partial penetration in tick #7 and respond to the penetration by doing some sort of physical response (maybe we deflect the rocket, maybe it explodes.. whatever your gameplay dictates).

In Buggalicious, we have 3 ticks coming in at 60 ms per tick. Maybe the game player is encoding a DVD in the background, or has World of Warcraft minimized while they’re playing your awesome Flash game. In this case, somewhere between tick #2 and tick #3, the rocket passed completely through the barrier. There was never any penetration, in tick #2 it was on one side of the barrier, and in tick #3 it was on the other side. Our collision detection code never fires, so our game thinks everything is fine, but now the player is trapped outside the level.

This is clearly a Bad Thing. There are numerous ways to address the problem, like Continuous Collision Detection (CCD - also called sweeping), which is very expensive, or throwing out deltaTimes that are too big to simulate is another. Most of these “solutions” deal with the symptoms, rather than the cause of the issue, the variable deltaTime, which is creating a non-deterministic game loop. We need to fix our deltaTime interval to make our game loop deterministic, and then we can safely avoid the conditions that cause tunneling, ease development, and provide some interesting new capabilities to our game engine.

Creating a deterministic game loop

In the above example, if we could guarantee that each tick of the game engine occurred at a pre-determined tick interval, then we can establish guidelines to ensure that it is impossible to cause tunneling. Rather than dispatching a game tick every frame based on the deltaTime since the last frame, we need to examine the time that has passed since the last game tick and determine if it is time yet to dispatch the next game tick, or if we missed some ticks and we need to catch up.

There are three cases that occur when we’re trying to figure out if its time to run another game tick:

Case 1: Less Than

The deltaTime since our last tick is less than the interval that must pass before we can fire the next tick. Store how much time this is and use it in our calculation next time the frame updates (in a process known as accumulation).

Case 2: Equal To

The deltaTime since our last tick is equal to our interval. Dispatch the game tick, we’re good to go.

Case 3: Greater Than

The deltaTime since our last tick is greater than our interval. It means that enough time has passed that at least one tick should have occurred, and the chances are we’re already half the way through the time until the next tick would fire. It is precisely in this case that tunneling would occur, given a large enough deltaTime, if we simply dispatched a single game tick with the entire deltaTime. Instead of firing a single large deltaTime, we break up the deltaTime into interval-sized blocks, and dispatch each game tick with the appropriately sized interval. Any left over deltaTime that is not used up in the process is accumulated as if we were in Case #1 again, so that our game ticks are firing as accurately as possible.

Mathematical Example

If our interval size is 30ms and the frame rate is 100fps, we should be getting deltaTimes of 10ms every frame. We will accrue 3 frames, at 10ms each, until we hit 30ms, at which point we dispatch a game tick with an interval of 30ms.

If we get t-boned by a sudden deltaTime of 65ms, it means we missed 2 intervals (at time 30ms and time 60ms), and we are already 5ms into the next interval. To maintain our deterministic fixed-interval game loop, instead of firing a single game tick with an interval of 65ms, we need to fire two game ticks this frame, with 30ms each, and then we need to store the left over 5ms and apply it to the next possible update.

Thus we have ensured that no matter what, our code is both time-based, but also fixed-interval, and is therefore deterministic. So long as we’re careful about the size and speed of our in-game objects, it’s possible to guarantee that we will never have to deal with an object popping out of a level.

Determinism is the true prize!

We solved tunneling by creating a deterministic game loop. We insured that our game loop will generate the same results given the same input. We did this so we could make sure our inputs don’t create in-game objects that move too fast for collision detection. But, in doing so, we’ve actually opened up massive opportunities for expanding the capabilities of our game engine.

“Our game loop will generate the same results given the same input.”

This is true for everything, not simply the interactions between a fast moving object and a wall. If we record the player’s input and the time in which it occurred, we have all we need to create a replay of the player’s performance. The possibilities introduced by this are bounded only by your imagination. Some obvious examples are:

1. Debugging. You can track the input generated by the player and automatically submit it with a bug report. You can now recreate the scenario on your development machine and figure out what caused the bug without needing to muddle for hours trying to recreate the same exact engine scenario.

2. Replays. Using an input log, you can show players replays of their levels that they can share with their friends (Halo3’s Theater, anyone?). Because you only need to record the input, the “size” of these replay files is minute compared to video capture.

3. Gameplay mechanics. You can give players the ability to go back in time with special power ups (for example Prince of Persia: Sands of Time) and other cool time-based effects.

A Physics Example

Use the “Prev” and “Next” buttons to cycle through the 2 test examples in this Physics Example. You’ll notice that the deterministic example executes the same every time. All objects always come to rest in the exact same spot. In the non-deterministic example, you’ll notice that it is different every time, because the game loop is not firing on a fixed interval and is instead using a variable deltaTime.

Ticker Implementation

Here’s the good news, I’ve done all the hard work for you! I have implemented a Ticker class whose API is identical to the built in AS3 Timer class that takes care of all the work for you (a choice that was made based on my Coding Conventions). Use it like you would Timer, and your game can benefit from all of the advantages of a deterministic game loop.

Download the Ticker source code.