How was sprite Z sorting done in games?
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
How was sprite Z sorting done in games?
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.
Re: How was sprite Z sorting done in games?
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.
Truncated bubble sort for approximate sorting
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.
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
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.
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
- rainwarrior
- Posts: 8732
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact:
Re: How was sprite Z sorting done in games?
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.
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: How was sprite Z sorting done in games?
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.
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
Re: How was sprite Z sorting done in games?
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.
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.
Re: How was sprite Z sorting done in games?
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: How was sprite Z sorting done in games?
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.
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.
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
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
Re: How was sprite Z sorting done in games?
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.
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.
Re: How was sprite Z sorting done in games?
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).
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).