The Game Loop

Context

Doom, Tetris, Minecraft and Counter-Strike look nothing alike. Underneath, they all repeat the same small program many times a second: read the player's input, move the world forward a little, then draw it. Before any of the interesting algorithms arrive, that loop is what makes the game run.

The chapters ahead assume this vocabulary: the game loop, frames and their time budget, fixed simulation steps, smooth drawing, and the world represented as data. Pathfinding runs inside the update, rendering is the draw, and online games are one long argument about whose copy of the world is right. First, a note on the interactive boxes used throughout the volume.

How the boxes work

Almost every section in this volume has a live program. The picture on top is drawn from whatever the program underneath prints, and you can change the program yourself:

• Press Run to start an example. Nothing runs until you do.
• Edit the program, then use Run or Ctrl+Enter to run it again.
• A slider changes a number and reruns the program.
• New seed creates a different random world when the example supports it.
• In the grid chapters, click or drag to add and remove walls. You can also drag the S and G markers.

Animations play once. Run starts them over, and the bar under the picture lets you scrub through them. Everything runs in your browser, so nothing is sent anywhere.

The loop

Here is a whole game, if not a good one. Each frame it reads which key is held down, updates the world, and draws it:

Loading canvas playground...

The inputs text supplies one key per frame, so the run is the same every time. Add more ^ characters for more jumps, then run it again.

Loop is the game loop. Every game has one somewhere, and it repeats three steps:

1. Read input. Here that means one character; in a real game it means the state of the keyboard, mouse and gamepad.
2. Update. Update takes the current world and the input, then returns the world one frame later. The box moves, gravity pulls, and the ground stops it.
3. Draw. Draw turns the world into a picture without changing it.

The loop never waits for the player. A word processor can sleep until you press a key, while a game must keep running because enemies walk, timers tick and gravity pulls.

Games therefore poll input once per frame: "is the jump button down right now?" A press that starts and ends between two polls would be missed, so engines also keep a queue of events, such as a key press or menu click, and read it at the start of the frame. Both forms of input enter the world at the top of the loop.

Frames and the budget

One trip around the loop draws one picture: a frame. Run it 60 times a second and you have 60 frames per second, which leaves

$$\frac{1000 \text{ ms}}{60} \approx 16.7 \text{ ms}$$

for everything: reading input, running every enemy's AI, moving every physics object, and drawing the whole screen. This is the frame budget, and much of game programming is about staying inside it. A console game targeting 30 frames per second gets 33.3 ms. A competitive shooter on a 144 Hz monitor gets under 7.

Exceeding the budget usually makes each picture appear late, which the player feels as stutter. Many algorithms in this volume reduce that work. A* explores fewer cells than Dijkstra, a flow field serves a thousand units with one search, and a spatial hash avoids checking every pair of objects for collisions.

Average frame rate can hide uneven delivery. A game that alternates between short and long frames can still average 60 frames per second. Movement looks jerky because the pictures arrive at an uneven pace, so engines track individual frame times and frame pacing too.

Time steps

Update above moves the world by dt, a thirtieth of a second, because the box assumes 30 frames a second. Real frames are less tidy: one takes 14 ms, the next 22 because the screen was busy, and the next 16. A variable time step measures how long the last frame took and moves the world by that amount.

The result depends on the frame rate. Here is the same jump simulated at 15, 30, 60 and 144 frames per second, shown in red, blue, green and black. Each dot is a frame. On the left, each frame advances the simulation by however long that frame took:

Loading canvas playground...

The jumps on the left disagree. At 15 frames per second the jump peaks at 60 pixels and clears the ledge; at 144 it peaks at 51 and does not. Step moves the body with its velocity before gravity changes it, so the error depends on the size of the step. Smaller steps produce smaller errors. The figures under the box give each rate's peak, first for the variable step and then for the fixed step.

Real games have shipped with this problem. In Quake III Arena, the movement code ran once per rendered frame and rounded the player's velocity each time, so jump height depended on frame rate. Players capped the game at 125 frames per second, the rate that happened to jump highest, and could reach ledges that other players could not. Letting hardware change the physics gave some players access to the rocket launcher and made the game difficult to test consistently.

The simulation on the right uses a fixed time step of exactly 1/60 s. Each frame adds its duration to an accumulator, runs as many whole steps as fit, and carries the remainder over:

1  def Catch = fn(body: Body, budget: Float, best: Float) -> (Body, Float, Float) =>
2      if budget < tick then (body, budget, best) else {
3          def next = Step(body, tick);
4          Catch(next, budget - tick, Math::Max(best, ground - next.y))
5      };

A slow frame runs several steps; a fast one may run none. All four jumps now trace the same arc and peak at the same height. The world behaves the same on every machine, and the same input produces the same result each time.

In a real game, Catch also needs a limit. After a half-second pause, the accumulator holds 30 steps at 60 Hz. Running all of them can make the next frame late too, adding still more work. This feedback loop is called the spiral of death. Engines usually cap the number of catch-up steps or clamp the elapsed time so the game can recover, even if the simulation loses a little time.

Doom runs its game logic at a fixed 35 steps a second, called tics, regardless of what the screen is doing. Equal-length tics make the game deterministic, so a recording only needs to store the player's input for each tic: about 4 bytes per tic, or 140 bytes per second of play. Play those inputs back and the game unfolds exactly as it did. The chapters on replays, undo and lockstep networking build on the same idea.

Drawing between steps

A fixed step introduces another problem. If the simulation steps 60 times a second while the screen refreshes 144 times, most frames fall between two steps. The picture changes only on some refreshes, producing visible stutter even though the game is running quickly.

To draw an interpolation, keep the last two simulation states. At draw time, divide the accumulator's leftover by the step to find how far the clock lies between those states, then blend them. The picture stays smooth but shows the world up to one step late.

Here the simulation steps 8 times a second and the screen draws 60. Drag the slider to change the step rate:

Loading canvas playground...

On the left the ball jumps from step to step. On the right it glides, one step behind. At very low rates the interpolated ball visibly cuts the corners because it moves in a straight line between two steps; blending positions knows nothing about circles. At 30 or 60 steps a second both versions look the same, and the simulation can run independently of the screen's refresh rate.

Glenn Fiedler explains the accumulator and interpolation together in "Fix Your Timestep!" Most engines use this arrangement. Unity's FixedUpdate runs physics on a fixed step, while Update runs once per drawn frame.

The world as data

Update in the first box is a function from one World to the next. The drawing and input remain separate from that state. This separation makes several other systems easier to build.

• The world is data: positions, velocities, health and the map. A real game has many entities, including the player, enemies, bullets and doors, each carrying the data it needs.
• Update reads the world and the input, then produces the next world.
• Draw reads the world and produces a picture.

With those jobs separated, the simulation and drawing can run at different rates. Saving writes the world's data to disk and loading reads it back. A replay stores a starting world and a list of inputs. A network game sends world data or inputs between machines, and a test can run Update a thousand times without drawing anything. Later chapters return to each of these uses.

Double buffering

If a game drew directly into the picture currently on the monitor, the screen would sometimes show a half-finished frame: the background might be visible before the characters had been drawn.

Games instead draw into a hidden back buffer. When the frame is complete, they swap it with the front buffer that the monitor is reading. This process, called double buffering, keeps unfinished pictures off the screen.

The swap must also be timed. A monitor redraws the screen from top to bottom 60 or more times a second. If the buffers swap midway through a redraw, the top of the screen shows one frame and the bottom shows the next, split by a visible seam called tearing. Vertical sync, or vsync, waits for the gap between redraws before swapping. It removes the tear but can make the game wait, adding another constraint to the frame budget.

Putting the loop together

Here is the full loop in one place. The elapsed-time clamp keeps a long pause from building an unlimited backlog. After the fixed updates, the remaining fraction of a step becomes alpha, which places the drawing between the two latest states.

world = initial_world
previous = world
accumulator = 0
last = clock()

while running:
    now = clock()
    elapsed = min(now - last, 0.25)
    last = now

    input = read_input()
    accumulator += elapsed

    while accumulator >= tick:
        previous = world
        world = update(world, input, tick)
        accumulator -= tick

    alpha = accumulator / tick
    draw(interpolate(previous, world, alpha))
    swap_buffers()

What's Coming

The rest of the volume follows the loop. It starts where every frame starts, with input: what a controller actually reports, and how a game turns that into movement that feels right. The programs throughout import a small shared toolkit, described in the appendix for anyone who wants to look inside.