Deterministic Delta-tee in JS Games

Games are generally driven by a timer or loop, where a “tick” function is called as often as the screen repaints, or, failing that, as often as possible given CPU constraints. The classic game loop looks something like this:

The core idea here is to normalize the simulation speed to actual real-world time rather than however many times the runtime can call tick for a given time interval.  Your computer might be faster than mine and call tick many more times each second, but our game speed should be identical.  Each iteration the tick function will advance the game simulation forward by however many milliseconds have passed since the last time the loop was executed.  For example, actors in the simulation will move further in a tick when the dt is higher. The frame rate is then determined by how quickly the loop can execute, which is in turn determined by the complexity of the tick and render functions, as well as the speed of the cpu. But the simulation is ultimately driven by wall time, not CPU time, so even at lower frame rates, the game advances time in accordance with the way that we experience it.

In JavaScript, of course, the timer is generally not powered by a simple loop, but by a callback attached to setTimeout. This allows the browser to update native UI, dispatch input events, and handle interactions with the network between steps.

Keep in mind that there is a new way to do this, requestAnimationFrame (and Mozilla docs) which allows the step function to be driven by the screen refresh rate rather than an arbitrary timer.

Complications

While this game loop is easy to understand and generally works, it is very easy to make mistakes. For instance, a typical collision detection formula will update the position of each actor, then check for collisions. But if the frame rate drops and the dt is high, then it might be that an actor has entirely skipped over a wall. There are many physics engines that have various mathematical models for dealing with these issues, but many simple game libraries don’t have a solution.

A more serious problem with this kind of game loop is that of deterministic simulations. I’ve played many tower defense games in flash and html5 that run slightly differently every time I play. Flash Element Tower Defense, for instance, was the first popular tower defense game on the web, and it played slightly differently every time. There was a particular tower you needed to build in a particular spot on the first level in order to get one of the top scores, but sometimes it just didn’t work — a creep or two would get by and you’d have to start over. The reason for this was that the frame rate would drop, and one of the creeps would jump just past the edge of your tower’s range in a single step. No one really thought much of this, except for notes of caution in various game walkthroughs that getting a high score was essentially random depending on how well your cpu performed on that first level.

This is even more of a serious problem in multiplayer games when the simulation needs to run exactly the same on two remote clients.

A Solution

One solution we use at Game Closure is to normalize the simulation step size by running it independently of the render call. We choose a “fixed dt”, such as 10ms, and we only ever call tick with that 10ms. You can imagine that the dt each iteration will usually be much higher than that, so the game loop may need to call the tick function multiple times.

The code above should allow for a normalized simulation every single time the game is played, independent of the frame rate. If we get 2 frames a second, then the two calls to step with 500 ms dt will each result in a total of 100 calls to tick(10) with the above code, just as 50 frames a second will result in 50 calls to step with 20 ms each, and still 100 calls to tick(10).

A Caution

The bottleneck in games is generally on the render() call, not the tick() call, and it’s fine to have multiple tick calls each frame. However, when calls to tick(STEP_SIZE) start taking more time to complete than STEP_SIZE itself, the simulation will fall hopelessly behind. It’s important to benchmark the average time it takes to complete a tick call on entry-level hardware so that you can properly adjust your STEP_SIZE to fit. Generally speaking you should keep the STEP_SIZE at 15ms or below, as this can allow you to still run at 60+ fps. If you were to choose a STEP_SIZE of 50ms you would only ever be able to change the simulation state a maximum of 20 times a second, and so you’d only be able to draw 20 unique frames of animation a second.