The Developer’s Cry

a blog about computer programming

Recording Pac-Man

Back in 2013 (grandpa tells stories) I wrote a little clone of the mighty Pac-Man game. It was written on a 32-bit intel Mac using OpenGL. This stuff doesn’t run anymore, as I’ve written about before on this blog, but even worse, when I tried porting it to SDL3 I noticed something funny about it. Funny as in code smell. When resizing the window, the code messes around with the coordinate system, apparently for maintaining the correct aspect ratio. While the code succeeds, it is basically a sin to mess around with the coordinate system in an OpenGL program, because everything breaks when you touch it. Even with help of AI it was beyond repair, so … I sat down and hand-coded a whole new game (no AI!) that gets it right. Basically it’s a modern clone of Jr. Pac-Man in gorgeous 4k high-res widescreen. Jr. Pac-Man is a faster version of the game with bigger maps, and in its best moments it plays as the frantic, crazy chase that Pac-Man is known for.

The mechanics of Pac-Man are pretty interesting by themselves, but I’m not going into that here. Let me say however that it still takes considerable effort to deliver a game that is complete and polished from A to Z. (Most notably, sound is still lacking). It features vector graphics, seven maps (copied from Jr. Pac-Man), a builtin map editor that does auto-tiling, and it has an attract mode. Attract mode is where an arcade cabinet shows a demo playthough, where the game plays itself, in order to attract players.

Rather than adding an AI player (I said, NO AI…!), the easiest way to add an attract mode is to make a short demo recording and play it back. Now, we’re not doing a screen recording; that’s way too heavy for what we want. A builtin game recorder saves the input keystrokes and plays them back later, using the same update() and render() functions to run the game logic and presentation during playback.

One caveat: the pseudo-random number generator (PRNG) should be seeded so that all random decisions taken while the game runs, turn out the same when playback happens.

typedef enum {
    R_NONE = 0,
    R_KEYUP,
    R_KEYDOWN,
} RecordEventType;

typedef struct {
    RecordEventType event_type;
    SDL_Scancode key;
} RecordEvent;

So, the idea is pretty simple. Record all keystrokes plus a timestamp so that we know the exact timings, and we should be able to play it back accurately. It didn’t work.

I think describing it doesn’t hit nearly as hard as seeing the bug visually happen: during recording Pac-Man eats a power pill, takes a turn, and eats the ghost that was just trying to escape. When played back it would sometimes eat the ghost, while at other times the ghost would make the turn and get away! How?? The problem stems from slight varations in timing:

It is an unsolved problem in computer science to have a stable frame rate.

Let that sink in for a moment. Quote from Jonathan Blow, by the way.

If the duration of a frame is not constant, then as a solution we can record the frame time frame-by-frame, and recreate the exact delay between frames for playback. That works, but is also incredibly convoluted. So actually, rather than recording each frame time, we can simply fix the timestep (ie. “Fix Your Timestep!”) to e.g. 1 / 60th of a second.

Fixing the timestep basically takes the frame time out of the equation. Thus what we can do now, is only record the current frame counter with the keydown (or keyup) event as it happens.

typedef struct {
    RecordEvent event;
    uint64 frame_number;
} RecordSample;

A recording is just a collection of samples, stored in an array.

In the keyboard input routine we write:

if (we_are_recording) {
    record_sample((RecordEvent){
        .event_type = R_KEYDOWN,
        .key = key,
    });
}

Upon playback we simply look at the current frame counter and inject the key events again.

// mind that multiple events may occur in a single frame
while ((playback_index < num_samples) &&
    (recording[playback_index].frame_number == playback_current_frame)
) {
    playback_event(recording[playback_index].event);
    playback_index++;
}
playback_current_frame++;

My sloppy hand-coded implementation experiences the variant frame times but runs the game simulation using the fixed timestep. In theory that causes jitter, but I don’t see it.

Watching the game play itself is pure joy, even if it is just a recording. Games are quantized time step simulations. In principle this recording technique works for any type of game. Note that since time is not a factor in the recording data, you can easily play it back at twice the speed, or even frame-by-frame. For a turn-based game you would record the turn rather than the frame number, allowing playback turn-by-turn at any speed you like.