Understanding the Game Loop
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:
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.
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.
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.
felixters
Good stuff!
April 21st, 2008 at 2:00 pmlschiedel
I have approached this problem a different way. I don’t know if it what you are calling CCD.
What i do is check my movement value and convert it into a bunch of movements of amount <= 1 pixel. Thus i find COUNT=FLOOR(movement+0.5) and loop that many times by a movement of original/count. Since the graphics are repainted only at the end of my game loop, this guarrantees that my moving object will bounce only on contact and i do not have to calculate when it contacted, how much movement is left, where on its new movement vector it ended up, and if it collided with another object in the rest of its movement. My test app is a pinball simulation with horiz, vertical, angled, and curved (quarter or semi-circles) walls. Trying to bounce a ball off the inside of a semi-circle without this algorythm was beyond me since the ball could bounce and end up hitting another part of the wall. Now my ball smoothly moves along the edge of the semi-circle and exits straight out the other end.
What do you think? Is this a good method or overkill?
April 21st, 2008 at 2:45 pmPanayoti
@felixters: Thanks! Glad it is helpful!
@Ishiedel: That isn’t exactly CCD, but it is an approximation of it. CCD works by creating a new shape for your moving object based on the interval, with a start and end point and all possible locations in between for any possible time on the interval. For example, a moving point becomes a line, a moving circle becomes a capped cylinder, etc. What it then calculates is a time of collision, by modeling a continuous simulation, rather than a traditional discrete simulation which is more like a flip-book.
The method you describe is pretty computationally expensive. Ideally you could use that in conjuction with a fixed time interval and optimize it on the fly so that you only drop down to the pixel stepping when your object gets too fast and you need to worry about tunneling.
That being said, I hate math, so I’d just use a fixed interval time based system and Box2d which has CCD capabilities when you need it (that’ll come as a separate article).
April 21st, 2008 at 3:12 pmlschiedel
I understand the concept of checking for collisions all along the path based on the movement of all points in the shape. My problem is that of multiple collisions in the timespan as the object bounces, especially against multiple surfaces or multiple moving objects. The problem is calculating the first collision time, then the new vector, then the remaining movement. This involves solving a quadratic equation to determine the time/position of impact. And if you have multiple moving objects, you need to find the first collision in time, handle it while moving all moving objects that time amount, then check for the next collision, etc. Plus if you have multiple moving objects you risk them “sticking” and moving as clumps. And i assume in a 2d game, the amount of math to move a small number of objects times the max vector length of all moving objects movement, still consumes a small amount of time compared to that required to redraw all of the graphic objects on the screen.
April 21st, 2008 at 4:19 pmPanayoti
Most physics engines let you specify how many iterations to use when trying to solve those types of problems (ie: solving a constraint disrupts other constraints forcing additional computation). I’m not going to presume to be able to present a solution that does it better than them, so I’d recommend that if your custom physics solution is not working, it’s probably worth exploring the open source options as they have already solved all these problems for you (and by and large they are each solid offering).
Regarding speed, Flash is still pretty slow. Even a basic simulation can quickly become computationally expensive, so for the foreseeable future, you will need to worry about accuracy versus performance trade offs.
April 21st, 2008 at 4:33 pmCrash1hd
Hello This is a very good article, but I was wondering if it would be possible to get a hold of the Physics Example Source Code Files at all?
August 18th, 2008 at 1:22 amPanayoti
Um.. Yeah.. Soon? I expect to be doing a Box2D tutorial in the next month or two.
August 18th, 2008 at 1:39 amCBridgman
Hi, cool article, but it seems to stop a bit short of the ideal situation. In the ‘Fix your timestep’ article you reference, a visual problem with this implementation is described. It’s to do with your accumulator’s remainder slowly growing or shrinking in such a way that when a frame is rendered, one extra step, or one less step is executed than normal.
This results in a fairly regular visual ‘jarring’ effect (which is more apparent on faster moving objects) on object movement, which doesn’t occur if you process the full accumulated amount per frame. Even with frame based, this is less of an issue as your FPS generally hovers around the same amount (assuming you cap it at a reasonable value, like 30fps).
The description on how to address this in the ‘Fix your timestep’ article is a bit cryptic, so I am still unsure as to how one solves this problem. Processing the remainder after all full intervals have been processed will solve the problem, but breaks the determinism. One could try and ‘temporarily’ apply the remainder of movement, then roll it back and process it in a full interval the next frame, but that sounds very messy to me, since you’d need to run all game logic just like a full interval, and you may have collisions which occur and set off a whole chain of events in the game. Do you have any suggestions on how to tackle this problem?
September 4th, 2008 at 6:42 amPanayoti
I need to go back and tear the Fix Your Timestep article apart, but I believe he’s basically presenting interpolation for that partial over step as a means to correct the visual jarring. As I recall he’s interpolating only the visual render state, and not actually trying to do a partial physics step (because that would most certainly break the determinism). I’ve never bothered going as far as doing an interpolation step, because Flash is slow enough as is and I haven’t really experienced the visual jarring effect. Have you tried some level of display-only interpolation? My concern is that it might result in some other visual artifacts that would be worse than any barely noticeable stuttering.
September 4th, 2008 at 12:52 pmCBridgman
Hi. In order to illustrate the issue, I modified your code from the ‘Frame Based Code Sucks!’ article. The sample shows what Accumulator based timing looks like versus Delta based timing: http://www.retrotoast.com/downloads/flash/DeltaVsAccumulatorTiming.html Code is at: http://www.retrotoast.com/downloads/flash/DeltaVsAccumulatorTiming.zip
I’ve reread the last bit of that ‘Fix your timestep’ a few times, and it seems like you make the game intentionally lag by the percentage of a frame that’s in the accumulator by interpolating between the previous frame and the current one. I can understand interpolating a simple straight vector movement from A to B, but it seems like such an approach would have a large number of special cases, which increase with the complexity of your physics. For example, an object is orbiting a point, if you just find the point half way between the previous and current position, that won’t be correct. You’d need to know that in that case, you’re finding half way between a certain amount of movement around a circle. And consider a case where you need to interpolate for an object’s frame based animation, movement vector and rotation of its graphic. I can’t think of a way to do that sort of thing in a generic manner.
September 4th, 2008 at 7:49 pmPanayoti
Nice work. Something tangible to play with. I’m looking at the code now and will get back to you with my thoughts soon.
September 4th, 2008 at 8:34 pmPanayoti
CBridgman, I sent you an e-mail. I noticed one thing in particular about the code: the interval doesn’t match the FPS – if you have them match, the difference is far less severe, though I will concede there is a noticeable stutter.
As for the interpolation, you don’t want to do a partial physics step. You want to interpolate between the last two complete physics steps. Essentially you want to render your physics one frame in the past, at a delay of up to the size of the interval. I’ve never actually done it before, but I imagine it will not be accomplished without some amount of sweating.
September 4th, 2008 at 10:05 pmNick Wiggill
@ CBridgman,
Did you by any chance get anywhere with a solution to this? Could you clarify what the end result was, if so? Was it worth it?
Rgds,
-Nick
February 18th, 2009 at 4:29 am