It is currently Fri Sep 21, 2018 2:57 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 10 posts ] 
Author Message
PostPosted: Fri Aug 31, 2018 9:58 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2749
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.


Top
 Profile  
 
PostPosted: Fri Aug 31, 2018 10:34 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796
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.


Top
 Profile  
 
PostPosted: Fri Aug 31, 2018 10:48 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
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


Top
 Profile  
 
PostPosted: Fri Aug 31, 2018 10:51 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6809
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sat Sep 01, 2018 6:25 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2749
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.


Top
 Profile  
 
PostPosted: Sun Sep 02, 2018 1:03 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 579
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.


Top
 Profile  
 
PostPosted: Sun Sep 02, 2018 7:02 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Sun Sep 02, 2018 8:30 pm 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2749
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:
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.


Top
 Profile  
 
PostPosted: Mon Sep 03, 2018 1:42 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 579
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.


Top
 Profile  
 
PostPosted: Wed Sep 12, 2018 3:16 am 
Offline

Joined: Mon Jul 01, 2013 11:25 am
Posts: 249
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).


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group