| |
Oswald
Registered: Apr 2002
Posts: 5018 |
Sorting
are sorters really so slow in games? :) I have made my unrolled version for my theoretical game (;), and it takes 132 rlines to sort 32 numbers o_O worst case is ~200 lines. tho when its the case of 4 numbers have to be swapped only it does the job in ~10 lines. wastes a lot of memory but I like it :) |
|
... 193 posts hidden. Click here to view all posts....
|
| |
Bezerk
Account closed
Registered: Mar 2020
Posts: 5 |
Here's the zero-page usage in my test code. It obviously wastes 7 unused bytes per MSD bucket list head but it's just for testing.
I'd be happy to send you the source code. PM me if you're interested.
.const NUM_SPRITES = 32
.const NUM_LSD_BUCKETS = 16
.const NUM_MSD_BUCKETS = 14
* = $10 "Zeropage data" virtual
// Actor y positions in [0,223]
ypos:
.fill NUM_SPRITES,0
// Head of linked list per LSD bucket.
lsd_buckets:
.fill NUM_LSD_BUCKETS, 0
// Next "pointer" in (LSD or MSD) bucket list.
links:
.fill NUM_SPRITES, 0
// Head of linked list per MSD bucket.
msd_buckets:
.fill NUM_MSD_BUCKETS * 8, 0
Memory Map
----------
Default-segment:
*$0010-$00cf Zeropage data
|
| |
lft
Registered: Jul 2007
Posts: 369 |
It makes sense now. Thank you! |
| |
CyberBrain
Administrator
Posts: 392 |
Cool routine!! Thanx for sharing! Analyzing how it works was pretty illuminating (aka. fun) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
Nice work, Bezerk. Good to finally have a comparable radix sort implementation, and a well optimised one at that. Extraordinarily close to one raster line per actor!
The flagged bucket sort I put up at https://www.codebase64.org/doku.php?id=base:flagged_bucket_sort takes around 2423 cycles - significantly slower than field sort or radix.
Somewhat less onerous memory requirements at least; no magic pages, and the zero page use is contiguous :) |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
Bezerk, can you explain it in detail, frankly I dont understand anything of it :) |
| |
Bezerk
Account closed
Registered: Mar 2020
Posts: 5 |
You should Google "radix sort" for a thorough explanation but I can try to explain how the posted code works.
It's a two pass sort.
In the first (LSD) pass you assign each actor to a bucket based on the least significant digit (LSD) of the actor's y-position ($0-$f). Each bucket has a linked list of the actors whose y-position LSD is the same as the bucket index. For example, LSD bucket number $7 has a linked list of actors with y-position LSD = $7 (i.e. $07, $17, ..., $d7). The order in which the actors are processed doesn't matter in this pass.
In the second (MSD) pass you assign each actor to a bucket based on the most significant digit (MSD) of the y-position ($0-$d). In this pass the actors are processed in LSD bucket order (from $0 to $f) and each actor is prepended to the MSD bucket list. The end result is that each MSD bucket list contains actors whose y-position MSD is the same as the bucket index and sorted based on LSD. For example, MSD bucket number $d will have a linked list of actors with y-position MSD = $d (e.g. $da, $d3, $d0). Again, the important point is that each MSD bucket list of actors is sorted in descending y-position order because the actors were added in LSD bucket order.
The final sorted order is then output to the stack by outputting the MSD bucket lists from index $d to $0.
Hopefully this helps enough to let you decipher the code. |
| |
Frantic
Registered: Mar 2003
Posts: 1627 |
@bezerk: Don't hesitate to put the radix sort implementation on codebase64 :) |
| |
Krill
Registered: Apr 2002
Posts: 2847 |
Finally, the C-64 scene delivers an answer to the age-old question of which sorting algorithm actually is best. |
| |
Oswald
Registered: Apr 2002
Posts: 5018 |
thanks, now I get it :) |
| |
lft
Registered: Jul 2007
Posts: 369 |
I was able to improve the radix sort.
Writeup at codebase64.
This version can sort 32 actors in 1970 cycles. That's 61.6 cycles per actor.
Quoting ChristopherJamExtraordinarily close to one raster line per actor! Boom! |
| Previous - 1 | ... | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 - Next |
