Frameskipping and Interpolation

A C64 action game traditionally does everything once a frame: read the joystick, move every character, run the enemies’ thinking, scroll the screen and set up the sprites, fifty times a second on a PAL machine. When there is too much to do, a well-built game does not tear or flicker. It slows down, and the player slows down with it. Lasse Öörni, who wrote games as Cadaver, set out in his ninth “rant” on Codebase64 what a game can do instead. “No approach can magically give you more clock cycles,” he wrote, “but there are ways to sort of ‘cheat’, while keeping the internal logic of the program uncompromised.”

Both of his cheats rest on one condition. The code that advances the game world, which he calls movement and logic (moving the characters, the AI, collision detection), has to be separate from the code that shows it (scrolling, sorting sprites for multiplexing, putting them on screen). “If they can’t be separated in your project, the rest of this rant will not be of much use to you.”

Fast facts

• Frameskipping: draw less often than the logic runs. Count the frames since the last drawing and run the logic that many times before drawing again. Motion gets jerkier; speed stays right.
• Interpolation: run the logic every second or fourth frame, and on the frames in between move each sprite along a straight line from its old position to its new one. The screen still scrolls at 50 Hz.
• Cost: the game reacts to the joystick only when the logic runs, so the longer the interval, the laggier the controls feel.
• Uses named by Cadaver: his own Metal Warrior 4. He noted that Gauntlet III and Myth scroll at 50 Hz while moving their sprites less often, without the in-between frames, and he thought Last Ninja 2 probably frameskipped.

Frameskipping

Frameskipping is the approach “many know from PC games/demos”, where the machine could afford the logic every frame but not the drawing. The game notes when it last drew the screen. If that was three frames ago, it runs the logic three times, then draws once. The characters jump further between pictures, but they cover the ground at the right speed.

Cadaver thought it could help a C64 game whose drawing is expensive: 3D games, isometric games drawn into a bitmap, and games like The Last Ninja, where sprites have to be masked against the background. He could not say whether the Last Ninja games did it, but remembered the characters taking “bigger steps in some CPU-intense scenes, like the maintenance areas in LN2:Office level, so likely at least LN2 frameskipped”. Frameskipping cannot help when the logic itself is the slow part.

Interpolation

Interpolation turns the ratio round. The full movement and logic pass runs on every second or fourth frame. On the frames between, each sprite is moved part of the way along the line from where it was to where the logic has put it, which costs far less than moving it properly. Scrolling, sprite sorting and the raster interrupts keep running every frame, so the screen stays smooth.

Cadaver dated the idea, for himself, to the end of 2001, and did not know of an earlier C64 game that showed the in-between frames. Gauntlet III and Myth, he wrote, scroll at 50 Hz and update their sprites less often, but do not draw the steps in between.

The simple form keeps everything in the main program and alternates two kinds of frame. On the first it stores every sprite’s old position, runs the full logic, scrolls if needed, sorts the sprites and tells the raster interrupts what to show next. On the second it interpolates, scrolls, sorts and hands over again. Then the cycle repeats. The weak point is the logic frame: if it overruns, the whole cycle slips and the game slows down.

Re-entrant interrupts

The stronger form splits the program into three layers that can interrupt each other:

1. Movement and logic, in the main program, triggered every two or four frames. It touches no VIC-II registers and does no scrolling.
2. The frame update, run from the interrupts: interpolation, scrolling and sprite sorting.
3. The low-level raster interrupts: screen splits, putting the multiplexed sprites on screen, and music and sound.

Cadaver’s game screen had one raster interrupt at the top and one at the bottom, for the score panel and the music. Each finishes its own work and then, instead of returning, turns itself into the frame update:

        dec $d019            ; acknowledge the raster interrupt
        cli                  ; allow further interrupts
        jmp frameupdate      ; carry on as the frame update

frameupdate:
        inc exec_count
        lda exec_count       ; already running? then skip the update
        cmp #$02
        bcs skip
        ; ... the frame update itself goes here ...
skip:   dec exec_count
        pla                  ; restore Y, X and A and leave the interrupt
        tay
        pla
        tax
        pla
        rti

Because cli comes before the jump, the next raster interrupt can arrive in the middle of the frame update, do its own urgent work on time and then try to start the frame update again. The counter turns it away: the first entry sets exec_count to 1, a nested entry raises it to 2 and goes straight to skip. The exit pulls Y, X and A in that order, so each interrupt must push A, X and Y on the stack when it starts, as the C64’s KERNAL interrupt entry already does. Cadaver insisted on the stack for this: “Using fixed zeropage addresses instead would corrupt the regs in case of nested IRQs (that will occur with this approach!)”

Because the frame update can be entered from either interrupt, it has to keep its own record of what to do next, and leave when nothing useful can be done. A colour RAM update, for instance, only makes sense after the bottom interrupt, where it cannot be seen. And because the logic, the frame update and the raster interrupts now run at overlapping times, each needs its own copy of the sprite information, so that one layer does not change what another is halfway through using.

What it felt like

The second preview of Metal Warrior 4 ran the logic every fourth frame and scrolled at 50 Hz, unlike the first preview. Cadaver worried that the controls would feel “too lagged” and asked two testers, CreaMD and Pixman, who told him it did not. He carried on, but his conclusion to the rant admits that “4-frame interpolation feels indeed quite lagged, just compare the preview to the full game”. The finished game used only the simpler interpolation, because it needed nothing more and the re-entrant version would have used too much memory.

See also

• The Game Loop
• VSync
• Raster Interrupts
• Sprite Multiplexing
• Multidirectional Scrolling
• The Last Ninja