How was sprite Z sorting done in games?

Discussion of development of software for any "obsolete" computer or video game system. See the WSdev wiki and ObscureDev wiki for more information on certain platforms.
Post Reply
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

How was sprite Z sorting done in games?

Post by psycopathicteen »

Like in Panorama Cotton on the Sega Genesis. My guess is that they sorted it out by object memory slot, and used the previous frame's Z order as the initial order.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: How was sprite Z sorting done in games?

Post by calima »

Sorting by the desired Y (Z) value is fast enough on Genesis. Coffee Crisis had >20 sprites to sort at times, and it took about 1/6th of a frame. There's no need for hand-tuned asm or any smart reuse.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Truncated bubble sort for approximate sorting

Post by tepples »

When objects are nearly sorted based on their positions in the previous frame, and an occasional 1- or 2-frame missort isn't critical, you can use cocktail sort, which is one pass of bubble sort with direction alternating per frame.

Even frames:
Scan front to back, swapping sprites x and x+1 if they're out of order
Odd frames:
Scan back to front, swapping sprites x and x+1 if they're out of order

The worst case of cocktail sort happens when you spawn a bunch of things into one screen at once, as shown in this animation. It settles out over the course of several frames, and even then, not all objects will be horizontally aligned to where Z order matters anyway.

Image
Cocktail sort from a cold start finishing in 14 passes, by Simpsons contributor, CC BY-SA 3.0


To make some cases settle out sooner, you could borrow a concept from comb sort, comparing at a larger distance.

Odd frames:
Scan back to front, swapping sprites x and x+2 if they're out of order
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How was sprite Z sorting done in games?

Post by rainwarrior »

For Lizard I had sprites draw in random order, except for the player, and the object in slot 0, which drew first. For the River Zone I wanted effective Z sorting, though, so I did a few things to work around this:

1. For the majority of cases, the various objects do not overlap each other, so I only have to manage overlap with the player. If the player is within a hitbox around the object I do a Z test between them, and set a flag that decides whether to draw the player before objects or after.

2. For waves, I had a series of overlapping wave objects, but it was always in one direction or the other. In this case I had the first wave to draw them all in the correct order, and then set a flag indicating not to draw any more waves this frame.

So... not robust sorting, but in practice I reduced it to these couple of special of cases. Other cases of overlap in the game were handled with use of object slot 0.


I haven't needed the full Z sorting on an NES game, but I have done it more or less like you're saying in 3D games to sort for transparency layering. Keep the previous sorted list and insertion sort it each frame to touch it up, generally doesn't take that long. If you get significant spikes when there's a lot of changes at once, you can flag it for a heap sort or something. Like calima was suggesting, how hard you need to think about this depends a lot on just how many objects you've got.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How was sprite Z sorting done in games?

Post by psycopathicteen »

I've been looking at many algorithms and I think I'll use Shell-sort. I think it's roughly as fast as merge sort, but doesn't require extra memory space.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: How was sprite Z sorting done in games?

Post by Oziphantom »

Basically this is Y sorting on a multiplexer just on the Z ;) Same principals, relies upon things not shifting in Z to much, but you might have the case of having a lot more things on the same value.

Generic Sorts are here http://codebase64.org/doku.php?id=base:6502_6510_maths
Optimised for the Mulitplex case is here http://codebase64.org/doku.php?id=base:sprites

There is also a fancy "abuse the stack" sort that Ocean is famous for, not sure of a public reference for it though.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: How was sprite Z sorting done in games?

Post by tepples »

What the "multiplex" pages (particularly rant3) call "Ocean sort" is insertion sort. Like bubble sort, insertion sort is fast on already-sorted data. Shell sort is insertion sort with decreasing gap size.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How was sprite Z sorting done in games?

Post by psycopathicteen »

I made a 65816 routine (not 100% optimized yet though) for shell sort. I got the gap sequence (1, 4, 10, 23, 57) from several places that say it's the fastest gap sequence on average, but I'm curious about it's worst case scenario because 20 is divisible by both 4 and 10, so some sequences of numbers such as (0,x,x,x,1,x,x,x,2,x,3,x,4,x,x,x,5,x,x,x,6) would slow it down quite a bit, but that probably rarely happen.

Code: Select all

shell_sort:
sep #$30
ldx.b #57
jsr +
ldx.b #23
jsr +
ldx.b #10
jsr +
ldx.b #4
jsr +
ldx.b #1

+;
stx {temp}
ldy #$00

-;
lda {z},x
cmp {z},y
bcs ++
phy
phx
sta {temp2}
lda {entry},x
pha
-;
lda {entry},y
sta {entry},x
lda {z},y
sta {z},x
tyx
tya
cmp {temp}
bcc +
sbc {temp}
tay
lda {temp2}
cmp {z},y
bcc -
+;
lda {temp2}
sta {z},x
pla
sta {entry},x
plx
ply
+;
iny
inx
cpx #$80
bne --
rts
The above code looks at 8-bit numbers. If 8-bit is only 256 values, and my own homebrew game already uses 8 levels of sprite priorities using a linked list system, I can probably just expand it to 256 levels of priorities. Do you think 8-bit is enough precision for Z layering? Because if it is, I don't think I need any sorting algorithm.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: How was sprite Z sorting done in games?

Post by Oziphantom »

It depends on what you are doing...

Muttant Muds/Donkey Kong Returns/LittleBigPlanet you only need 3 levels

Afterburner yeah 256

3D game 16bits Zbuffer with logarithmic scale ;)

you only need as many things as you have "planes", or if you want to ensure no fighting then you need as many as items you have on screen.
Stef
Posts: 263
Joined: Mon Jul 01, 2013 11:25 am

Re: How was sprite Z sorting done in games?

Post by Stef »

In SGDK i'm using insertion sort and i'm doing it only when Z (depth) value of a sprite is changed so i only sort this sprite :
https://github.com/Stephane-D/SGDK/blob ... rite_eng.c (search for sortSprite(..) method).

Even if the code look a bit complicated (because of the double linked list structure and many pointers to update) it's still quite efficient :)
You rarely update more than 10 sprites depth at same time, also you can lower the number of depth level to reduce number of sorting operation (for instance you can use depth = Y / 16).
Post Reply