Sprite Multiplexing

The Commodore 64’s video chip has eight sprites. Commodore’s own Programmer’s Reference Guide admitted in 1982 that this was not the real limit: “Up to 8 sprites at a time can be maintained by the VIC-II chip automatically. More sprites can be displayed using RASTER INTERRUPT techniques.” It added a warning that held for the rest of the decade: “Unfortunately BASIC isn’t fast enough to do this very well.”

The trick works because a sprite is not an object the chip keeps track of. It is a set of registers the chip reads as the picture is drawn. Once the beam has drawn a sprite, the program can give it a new position lower down, with a new shape and colour, and the chip will draw it again there. Do that for all eight, several times a frame, and eight sprites become twenty or thirty. By 1991 ZZAP!64 could promise that Chris Butler’s Turbo Charge had, “for the technically minded”, “22 multiplexed hardware sprites on screen”. Making it work took a sort, a chain of raster interrupts, careful timing and a fair share of every frame. Martin Walker, planning his next game in his ZZAP!64 diary after Hunter’s Moon, noted the other catch: “simply having 32 sprites whizzing about does not a game make.”

The rules on the C64

The VIC-II sets the terms:

• No more than eight sprites on one line. Each sprite has one shift register, filled from memory once per line. A ninth object on the same line needs a ninth sprite, and there is none.
• A sprite can be reused only below itself. A sprite is 21 lines tall, so the next object that shares its hardware must start at least 21 lines further down.
• The new Y position must be written before the beam reaches it. Lasse Öörni, who writes as Cadaver, calls this “the most important hardware feature to take into account”: if the Y coordinate is late, “the re-used sprite won’t display at all!” It is not as tight as it sounds. The Y register can be rewritten as soon as the previous use has started drawing, since changing it in the middle “won’t ‘cut’ it or anything”.
• Shape and colour are the harder part. “It will take at least one rasterline to rewrite the frame & color registers,” Öörni wrote, so a badly timed write shows the next object’s graphics on the last line of the previous one.

Reusing sprites in rows

The simplest multiplexer does not sort anything. It shows the eight sprites in one row, and when the beam has passed the row, a raster interrupt moves all eight down to the next. Öörni calls this the “zone split” and dissects an example from Turrican, where the first boss, a giant fist, is “5 sprites per row and 4 rows (20 sprites total)”. An interrupt before each row rewrites the Y positions, shapes and colours of five sprites; the X positions stay the same, so they are set once.

This program does the same with all eight sprites, four rows of them, 32 boxes in four colours. One handler serves every row, taking the next row’s Y position, colour and interrupt line from small tables.

; eight hardware sprites shown four times each: 32 objects (ACME syntax)
; start it from a BASIC SYS line
start   sei
        ldx #62             ; sprite shape: a hollow box in block 13 ($0340)
-       lda shape,x
        sta $0340,x
        dex
        bpl -
        ldx #7
-       lda #13
        sta $07f8,x         ; all eight sprites use block 13
        lda xpos,x
        pha
        txa
        asl
        tay                 ; Y = 2 * sprite number
        pla
        sta $d000,y         ; X position
        lda #60
        sta $d001,y         ; first row at Y = 60
        lda #1
        sta $d027,x         ; white
        dex
        bpl -
        lda #$ff
        sta $d015           ; all eight sprites on
        lda #$7f
        sta $dc0d           ; switch off CIA 1's interrupts
        lda $dc0d
        lda #<irq
        sta $0314
        lda #>irq
        sta $0315
        lda #84
        sta $d012           ; first interrupt: row 0 has been drawn
        lda $d011
        and #$7f
        sta $d011
        lda #$01
        sta $d01a
        sta $d019
        cli
        rts

irq     lda #$01
        sta $d019           ; acknowledge
        ldx zone
        lda newy,x          ; move all eight sprites down to the next row
        sta $d001
        sta $d003
        sta $d005
        sta $d007
        sta $d009
        sta $d00b
        sta $d00d
        sta $d00f
        lda newcol,x        ; and give that row its own colour
        sta $d027
        sta $d028
        sta $d029
        sta $d02a
        sta $d02b
        sta $d02c
        sta $d02d
        sta $d02e
        lda nextline,x
        sta $d012           ; where the next interrupt happens
        inx
        cpx #4
        bne +
        ldx #0
        stx zone
        jmp $ea31           ; once a frame, let the KERNAL run
+       stx zone
        jmp $ea81

zone     !byte 0
newy     !byte 100, 140, 180, 60   ; row each interrupt sets up
newcol   !byte 7, 5, 3, 1          ; yellow, green, cyan, white
nextline !byte 124, 164, 212, 84   ; each just below the row now showing
xpos     !byte 30, 62, 94, 126, 158, 190, 222, 254
shape    !byte $ff,$ff,$ff         ; top edge
         !for r, 1, 19 {
         !byte $80,$00,$01         ; left and right edges
         }
         !byte $ff,$ff,$ff         ; bottom edge

Each interrupt comes a few lines below a row that has finished drawing and well above the next, so the timing has plenty of slack. Move the interrupt for the second row to line 105, after that row should have started, and the whole second row vanishes: the Y positions arrive too late, exactly as Öörni warned. The last interrupt of the frame, at line 212, puts the sprites back at the top ready for the next frame.

Rows are easy because the program decides where everything goes. In a game, objects move where they like.

A general multiplexer

Games such as Green Beret and Ghosts’n Goblins, in Öörni’s words, “allow free usage of over 8 sprites anywhere on the screen, any colors and frames”. To do that, a multiplexer treats the game’s objects as virtual sprites and does four jobs every frame:

1. Sort the virtual sprites by Y position, top of the screen first.
2. Map them onto the eight real sprites in turn: the first eight sorted objects go to sprites 0 to 7, the ninth to sprite 0 again, the tenth to sprite 1, and so on round.
3. Reject any object that would be a ninth sprite on a line. With round-robin mapping, object n shares a sprite with object n − 8, so the test is whether they are less than 21 lines apart. Öörni gives it as if (spry[next_sprite] - sortspry[sorted_sprites - 8] < 21) then reject(). The first eight never need the test.
4. Display them with a chain of raster interrupts down the screen, each writing the registers for the next few objects, Y positions first because they are the ones that must not be late.

The sort is where the time goes. Öörni named the one he preferred “Ocean” sorting, “because it can be found from many Ocean/Imagine games, like Green Beret or Midnight Resistance”. It keeps the sorted order from the previous frame and repairs it, swapping neighbours that have changed places. Objects in a game rarely overtake each other vertically, so most frames need almost no work, but “on some frame it’ll eat a lot of time, when there’s a lot of changes in the sprite order”. Falco Paul later tested the candidates in Java over random, extreme and game-like data. On the game-like pattern the Ocean sort “performs very fast”; on random data it “performs lousy (bubbesort like)”. A bucket sort, grouping objects by Y, was steadier, and in his tests “only 18% slower than the Ocean sort” on game-like data.

What it cost the programmer

Programmers learned this from each other and by taking games apart. Andrew Braybrook’s diary of Morpheus in ZZAP!64 shows the process from the inside. In January 1987 he saw Gary Liddon’s multiplexer and could not “understand why his runs faster”, so he borrowed Liddon’s method of “building a table in the system stack so I can use faster instructions to read the table”. The multiplexer then set its own traps. In April the sprites vanished between the title screen and the game, because “the sprite multiplexor clears out the sprite table ready for the next position”, and no new positions arrived while the program was busy setting up the screen; he asked readers what to do about the pause mode. In August, arranging the enemy line-up on the title screen, he found “the sprite positioning had to be pixel perfect to actually work properly, there’s no room for any play in the vertical positioning at all”.

Öörni, writing years later, had found no better written guide. Full multiplexing was “a subject seldom discussed in magazines”, and the Braybrook diary was “referring to some of the issues involved quite cryptically”, so he reverse-engineered “the sprite sorting/multiplexing routines of games like Green Beret, Midnight Resistance etc.” himself.

Game design had to live with the eight-per-line rule. Walker put it plainly in his Citadel diary in November 1988: “the main problem with any multiplexor is making sure that it is never possible for more than eight sprites to attempt to occupy the same horizontal ‘strip’”. Fixing some of Citadel’s sprites in position on the landscape would help. “If all the sprites may be moving, the alternatives are a lot of effort to ensure that the wrong combination can never occur (Armalyte) or nasty flickers and lurchers (Zynaps, for one).”

Flicker and the late interrupt

Some of the flicker in C64 games came not from too many sprites on a line but from interrupts that arrived late. A raster interrupt fires only when the beam reaches its line exactly. If a handler runs long and then sets the next interrupt for a line the beam has already passed, that interrupt does not come until the next frame, and the sprites it should have moved are missing or wrong. Öörni describes the result as “flicker & slowdown (caused by the new raster interrupt being higher or at same position than the current $d012 value)”.

His fix checks before returning. If the next interrupt’s line is already close, the handler jumps straight to the next handler’s code instead:

        sta $d012           ; A = line of the next interrupt
        sec
        sbc #$03
        cmp $d012           ; late from next IRQ?
        bcc go_to_irq_directly

The margin of three lines is from experience: “3 lines feel like paranoidically much ‘safety’ for the interrupt but in fact I got flicker in some rare cases if I was subtracting only 2.” He also advises keeping objects that are off the visible screen out of the list, and keeping sprites a couple of lines clear of the top of a score panel, so that the panel’s own interrupt is not pushed late.

On the Amiga

The Amiga’s Denise chip also has eight sprites, but Amiga sprites are fetched by DMA from a list in memory, and the list can describe several uses of the same sprite down the screen. Commodore’s Hardware Reference Manual says so plainly: “Sprite DMA channels can be reused several times within the same display field. Thus, you are not limited to having only eight sprites on the screen at the same time.” The only restriction is a gap: “the bottom line of one usage of a sprite must be separated from the top line of the next usage by at least one horizontal scan line”, because the channel uses that line to fetch the next position. No interrupt is needed. The one thing the list cannot change is colour; for that the manual has the copper wait for the last line of one use and rewrite the sprite’s colour registers before the next.

Amiga games still needed sorting, because the list must run top to bottom. Braybrook, writing his Uridium 2 diary for The One in 1992, explained the term for its readers: “Multi-plexor’s a fancy name for a routine which sorts the objects to be displayed into vertical position sequence and re-uses hardware sprites to show them”.

On the NES

The NES works the other way round. Its PPU holds 64 sprites, but draws only the first eight it finds on each line, in the order they sit in sprite memory. The rest on that line are not drawn. Reusing sprites down the screen is not the problem; too many on one line is. The usual answer was to change the order of sprite memory from frame to frame, so that a different sprite drops out each time and every object is visible some of the time. That trades missing objects for sprite flicker, the shimmer familiar from busy NES games.

See also

• VIC-II
• Raster interrupts
• Stable raster
• Sprite flicker
• Denise
• PPU
• Andrew Braybrook