Y-Depth Sorting

Picture a street in a side-on beat ’em up. The pavement runs up the screen into the distance, so a thug standing near the top is further away than one at the bottom. When the two overlap, the nearer one, the one lower on the screen, should hide the other. Get that wrong and a character who walks behind a barrel appears to stand on top of it. The cheapest rule that gets it right is to sort the objects by their Y position on the screen and draw them from the top down, so that each new object covers the ones behind it.

Commodore built exactly that rule into the Amiga’s animation system, which draws software sprites called Bobs with the blitter. Its manual explains that if the program does not set any priorities, “Bobs that are higher on the display will appear behind the lower ones, and Bobs that are more to the left on the display will appear behind Bobs on the right”, and warns that “as Bobs are moved about the display, their priorities will change.”

Sorting on the feet

The key is where an object touches the ground, not where its picture starts. The Amiga system sorts on each object’s x and y position, and that position is the upper left corner of its image. Two characters standing side by side have their feet on the same line, but if one is taller, its corner is higher, so it is drawn first and ends up behind. That is why the manual also gives each Bob a pair of pointers, Before and After, to set the drawing order by hand, and recommends using them for objects built from several Bobs, because otherwise “you may have an object drawn with half of its Bobs in front of another object!” A game that sorts on its own usually keeps a separate value for each object’s foot position and sorts on that.

The same idea answers the awkward cases:

The last row is where Y sorting stops working. One number cannot say whether a long wall is in front of a character who stands beside one end of it. Ultimate’s Filmation engine compared objects two at a time on all three axes instead (see isometric projection).

Drawing order: software sprites

On a machine that draws its moving objects into screen memory, such as the ZX Spectrum, the drawing order is the priority. Drawing from back to front so that nearer things paint over further ones is what graphics textbooks call the painter’s algorithm, after a painter who does the background first and the foreground last. Each object has to be drawn with a mask so that the ones behind show through its gaps (see sprites).

The sort does not have to be exact. Dean Belfield’s open-source Spectrum library, written in 2020, files each masked sprite by the top four bits of its Y coordinate, so by the 16-line band of the screen it is in, and then draws the bands from the top down. Sprites in different bands come out in the right order, and the routine never compares one sprite with another.

Priority slots: hardware sprites

Hardware sprites do not have a drawing order the program controls frame by frame. The video chip decides which sprite wins where two overlap, and on most machines it decides by number:

• Commodore 64. The Programmer’s Reference Guide gives the rule as “first come, first served”: “sprite 0 will appear to be IN FRONT OF sprite 1”, and sprite 7 is behind all the others.
• TMS9918 (the MSX and ColecoVision chip). Texas Instruments numbers its 32 sprite planes so that 0 is “the highest priority or outermost”.
• NES. “Priority between sprites is determined by their address inside OAM”, the sprite memory, so the sprite listed first is in front.
• Game Boy. On the original Game Boy, the object with the smaller X coordinate wins an overlap; equal X coordinates are resolved by object-memory order. Native Game Boy Color mode normally uses object-memory order instead. The public Pan Docs reference explains both rules; Nintendo’s Game Boy Programming Manual, version 1.1 (1999), describes the distinction. On the original machine, sorting by Y cannot override different X positions.
• Super NES. Object-memory order determines priority between the 128 objects, with a rotation option that changes where that order starts. The public Fullsnes hardware reference describes the priority rotation register.
• Mega Drive. Sprites form a linked list, and earlier entries take priority over later ones. A program can change the order by rewriting the links without moving the sprite records. The public Plutiedev sprite reference explains the links; Sega’s Genesis Software Manual (revised February 1992) describes the same mechanism.

So on most systems Y sorting means moving each object’s picture into the right slot: the nearest object into the slot that wins. The bits that set a sprite in front of or behind the background are a different matter. On the NES and the C64 they decide whether a sprite covers the scenery, not other sprites (see sprites).

This can clash with the other jobs the slots do. A multiplexer on the Commodore 64 hands out sprites in order down the screen, and an NES game that shuffles its sprite list each frame to share out flicker shuffles the priorities along with it. Robert A. Peck described the problem in his 1987 Programmer’s Guide to the Amiga, writing about the system’s virtual sprites: because hardware sprites are reassigned as they move, “a sprite that just one moment ago was behind another sprite will now be in front of that sprite.”

In the arcade

Arcade hardware drew the scenery in layers as well as the sprites, which gave designers a second tool. In Capcom’s Final Fight (1989), as Fabien Sanglard’s study of the CP System hardware shows, the characters, tyres and barrels all share one sprite layer, so which of them hides which is a matter of sprite order. To let the fighters pass behind part of the scenery, as they do on the stairs near the end of the first round, the hardware let individual background tiles mark some of their colours as drawn in front of the sprites.

Doing the sort every frame

Objects move every frame, so the list has to be sorted every frame. But they rarely overtake each other up and down the screen, so last frame’s order is almost right. An insertion sort that starts from that order does little work: it checks each object against the one before it and only moves the few that have changed places. Commodore 64 programmers used the same idea for their multiplexers, which also sort on Y. Lasse Öörni called it “Ocean” sorting after the games he found it in, and Falco Paul’s tests found that it was very fast on game-like data and performed poorly on random data, while a bucket sort was steadier.

This 6502 routine sorts a list of object numbers so that their foot positions rise down the list. Drawing the objects in list order, or giving the first entry the lowest-priority sprite slot, puts the nearest one in front.

; ORDER  holds COUNT object numbers, furthest (smallest Y) first.
;        It is kept from frame to frame, so it is nearly sorted.
; FOOTY  holds each object's foot Y on the screen.
; POS, OBJ, KEY are one-byte work variables.

sort:   ldx #1           ; start with the second entry
next:   cpx count
        bcs done         ; all entries placed
        stx pos          ; next entry to insert
        lda order,x
        sta obj
        tay
        lda footy,y
        sta key          ; its foot Y
        ldy pos          ; Y = the gap, starting at its old place
shift:  ldx order-1,y    ; object just in front of the gap
        lda footy,x
        cmp key
        beq place        ; same Y: leave it where it was
        bcc place        ; further up the screen: stop here
        txa
        sta order,y      ; move it one place along
        dey
        bne shift
place:  lda obj
        sta order,y      ; drop the new entry into the gap
        ldx pos
        inx
        bne next         ; always taken (COUNT is under 256)
done:   rts

The beq makes the sort stable: an object with the same foot Y as the one before it stays where it was, so two characters standing on the same line do not swap from frame to frame. With sixteen objects already in order, the routine takes about 1,000 cycles, roughly 65 per object. Each place an object has to move costs about 25 cycles more, so a list in completely reversed order takes about 4,000. A 6502 running at 1 MHz has 20,000 cycles in a fiftieth of a second.

In modern engines

Game engines still offer the rule as a setting. Godot’s y_sort_enabled property makes child nodes “with a higher Y position” render “in front of nodes with a lower Y position”. Unity’s 2D renderer lets a game set its transparency sort axis to (0, 1, 0), “so the higher the GameObject in the scene, the further away it is”, which its manual recommends for top-down games, and a diagonal axis for isometric ones.

See also

• Sprites
• Sprite Multiplexing
• Sprite Flicker
• BOBs: Blitter Objects
• Isometric Projection
• Filmation Engine
• Final Fight