Sprite Multiplexing

The VIC-II has 8 sprites. The NES has 64 sprites but only 8 per scanline. The Amiga has 8 sprites. Yet games routinely displayed dozens of moving objects. The trick: reposition sprites after the raster beam has drawn them, allowing the same hardware sprite to appear multiple times per frame.

The principle

Frame start:
  Sprite 0 at Y=50
  Raster draws sprite at line 50

Raster reaches line 71 (sprite done):
  Move sprite 0 to Y=150
  Raster draws "second" sprite at line 150

Result: One hardware sprite appears twice

Commodore 64 implementation

Simple approach

; Wait for raster to pass sprite's bottom
    lda #71             ; line after first sprite
.wait:
    cmp $d012
    bcs .wait

; Reposition sprite for second appearance
    lda #150
    sta $d001           ; sprite 0 Y position
    lda new_x
    sta $d000           ; sprite 0 X position

Full multiplexer

A proper multiplexer:

Sorts all virtual sprites by Y position
Assigns hardware sprites to the nearest virtual sprites
Uses raster interrupts to reposition at exact moments

; Simplified multiplexer structure
virtual_sprites:        ; array of Y,X,pointer for each object
    .res MAX_SPRITES * 4

sorted_indices:         ; Y-sorted order
    .res MAX_SPRITES

; IRQ chain repositions sprites as raster descends

Sorting requirement

Sprites must be Y-sorted because the raster moves top to bottom and a sprite can only be reused after it has been drawn. Two hardware facts set the constraints:

The Y-coordinate must be written before the beam reaches it, or the reused sprite does not appear at all. This is less tight than it sounds — writing Y mid-display “won’t ‘cut’ it or anything”, so the value can be set as soon as the previous row starts drawing. Frames and colours are the harder problem: rewriting those registers takes at least a raster line.
Sprites less than 21 pixels apart cannot share a physical sprite. Cadaver gives the rejection test exactly: if (spry[next_sprite] - sortspry[sorted_sprites - 8] < 21) then reject(). The first eight sprites need no test, because there is nothing yet to collide with.

Which sort

The sort is the multiplexer’s real cost, and the scene benchmarked the options rather than arguing about them. The one that carries a name carries a publisher’s:

“Ocean” sorting. Named this way because it can be found from many Ocean/Imagine games, like Green Beret or Midnight Resistance. A similar algorithm is also in Dragon Breed.

It keeps the order array between frames instead of resetting it, so a frame where little has moved costs almost nothing — at the price of an occasional frame that costs a great deal.

Falco Paul later built a test framework and ran the candidates over a million random frames plus deliberately hostile patterns:

Pattern	Ocean sort	Bucket sort
Typical in-game	“performs very fast”	18% slower than Ocean
Pure random	“performs lousy (bubbesort like)”	“pretty stable most of the time”
Extreme values	“extremly bad”	stable

Which is the case for choosing by measurement: the fast sort is fast only on the input that games produce.

NES sprite considerations

The NES has different constraints:

64 sprites in OAM (Object Attribute Memory)
Only 8 sprites per scanline (hardware limit)
Excess sprites on a line become invisible
Sprite 0 is always evaluated first — never flickered, and used for sprite-0-hit timing

NES solution: cycling priority

The PPU evaluates OAM in order, keeping the first 8 sprites it finds on each scanline. Rotating the OAM start offset each frame distributes the flicker:

; Rotate which sprites get priority each frame
; Spreads flicker across all objects instead of
; always hiding the same ones

    inc frame_count
    lda frame_count
    and #$1C            ; 0, 4, 8, 12, 16, 20, 24, 28
    tay                 ; OAM start index
    ; Build OAM buffer starting at offset Y, wrapping at 256

The mask #$1C gives 8 different start offsets cycling every 32 frames, so each sprite spends roughly 1/8 of its time at low priority. This is the standard Super Mario Bros. / Contra idiom.

Amiga sprite multiplexing

The Copper makes Amiga multiplexing elegant:

copper_list:
    ; Sprite 0 first appearance
    dc.w    $0120, sprite0_hi
    dc.w    $0122, sprite0_lo
    dc.w    $0140, $5050        ; position 1

    ; Wait for sprite to pass
    dc.w    $6007, $fffe

    ; Sprite 0 second appearance
    dc.w    $0140, $a070        ; position 2
    dc.w    $0144, new_data

No CPU interrupts needed — the Copper handles repositioning. The Copper can also reposition sprites mid-scanline by writing to SPRxPOS at the right horizontal position; the constraint is the Copper DMA budget, not “after the sprite has finished drawing” as on the C64.

Limitations

Constraint	Cause	Mitigation
Vertical only	Can’t reuse until raster passes	Sort by Y, design levels accordingly
Flicker	Too many sprites at same Y	Spread objects vertically
CPU cost	Sorting, repositioning	Pre-sort static objects
Per-line limits	Hardware constraint	Design around it

Games that used multiplexing

These are the C64 games named in Cadaver’s article, which reverse-engineered them because no published account existed:

Game	What it shows
Turrican	Zone split, dissected sprite by sprite: 3 sprites for the player, 20 for the first boss in 4 rows of 5
Green Beret (Ocean)	The “Ocean” sort, and one of two games named for “free usage of over 8 sprites anywhere on the screen”
Midnight Resistance (Ocean)	The “Ocean” sort
Dragon Breed	“A similar algorithm”
Ghosts’n Goblins	Full multiplexing, “any colors and frames”

Andrew Braybrook’s published Morpheus development diary was the only prior written source Cadaver could find, and it “was referring to some of the issues involved quite cryptically.”

Flicker management

On the C64 the usual cause of flicker is not overlap but a missed interrupt — “the new raster interrupt being higher or at same position than the current $d012 value.” The fix is to check before returning, and to jump straight into the next handler if you are already late:

    sta $d012
    sec
    sbc #$03
    cmp $d012        ; Late from next IRQ?
    bcc go_to_irq_directly

Three lines of margin is empirical, not theoretical: “3 lines feel like paranoidically much ‘safety’ for the interrupt but in fact I got flicker in some rare cases if I was subtracting less.”

Two design measures help before any of that: do not display sprites outside the visible screen, and keep sprites clear of the last couple of lines above a score panel.

For platforms without a raster interrupt to miss, the mitigations are different — see sprite flicker.

More sprites than hardware allows