| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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 |
It does fit on the zero-page since there are 14 MSD buckets (not 32). |
| |
lft
Registered: Jul 2007
Posts: 369 |
Right, but in that case, where do you fit 32 consecutive bytes of links and ypos? |
| |
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: 1408 |
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: 5086 |
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: 1646 |
@bezerk: Don't hesitate to put the radix sort implementation on codebase64 :) |
| |
Krill
Registered: Apr 2002
Posts: 2968 |
Finally, the C-64 scene delivers an answer to the age-old question of which sorting algorithm actually is best. |
| Previous - 1 | ... | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 - Next |
