Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Sorting
2007-10-08 16:08
Oswald

Registered: Apr 2002
Posts: 5007
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....
 
2017-09-25 06:32
Trash

Registered: Jan 2002
Posts: 122
Quoting lft
Typo on line 4, should increment at SortTable,x.



Thanks, missed that..


Quoting lft
The problem with this approach is that you have to compute the upper 5 bits of the y-position somehow, and that will take time. It can be done during sorting, at the cost of an additional 2 cycles per actor, like this:


Or it could be done in a precalculated table, whatever fits your needs..

Quoting lft
Nevertheless, it is nice to know that this option is available, in situations where the sprites aren't packed too closely but rastertime is tight.


Yes, but if you have small amounts of rastertime you either should pre-sort your data or have data that fits with a bubblesort like the one THCM implemented...

I am (like you) not convinced that this sorter is the best for all use-cases but for some it's certainly the best option.
2017-09-25 08:13
The Human Code Machine

Registered: Sep 2005
Posts: 109
In most game scenarios an optimized bubble sort with special routines to add or remove an actor should be faster. In my example the sorter takes ~20 raster lines most of the time with sprites moving up and down. For a game, accurate sorting is important, to get an optimal multiplexing result with reusing a free sprite slot as soon as possible. (as lft said above)
2017-09-25 20:35
Digger

Registered: Mar 2005
Posts: 420
btw. Nice tool for visualising various sorting algos, Counting Sort included: https://visualgo.net/en/sorting
2017-09-25 20:57
ChristopherJam

Registered: Aug 2004
Posts: 1359
Well, an unrolled bubble iteration should only take about 8 lines for 32 actors if there's no change, 10ish if there are four or five swaps.

I do like Falco Paul's suggestion of kicking off an Ocean Sort but aborting and switching to bucket sort (or some other constant time algorithm) if the number of swaps passes a certain threshold.
(cf http://www.codebase64.org/doku.php?id=base:sprite_multiplexer_s.. )

As for making lft's suggestion a little more memory flexible, I'm wondering if writing an RTS into the increment field could be cost effective?
2017-09-26 04:52
lft

Registered: Jul 2007
Posts: 369
I have thought of a different way to relax a memory constraint. Consider this variant of the bucket-emptying routine:

        sty     endptr+1
        lax     ylink,y
        pha
        lda     actorlink,x
        sta     ylink,y
        bpl     endptr

        sta     inyfield,y
endptr  jmp     inyfield


The worst-case execution time is the same, while the case of multiple actors in the same bucket is now slower. But now the location of the link table is unconstrained.
2017-09-26 04:59
lft

Registered: Jul 2007
Posts: 369
Quoting ChristopherJam
I'm wondering if writing an RTS into the increment field could be cost effective?


That would imply a JSR out of the increment field, right? That still means you have to put the bucket-emptying routine in four different, fixed places. Meanwhile the execution time increases by a rasterline.

Perhaps you meant the other way around, JSR into the increment field and RTS to the bucket-emptying routine. That would indeed make the memory layout more flexible, but at the cost of three rasterlines.

(Edit: I see now that I misread your post. Of course you mean the second thing.)
2017-09-26 06:54
lft

Registered: Jul 2007
Posts: 369
(removed)
2017-09-26 08:00
ChristopherJam

Registered: Aug 2004
Posts: 1359
(intrigued)
2017-09-26 08:05
lft

Registered: Jul 2007
Posts: 369
I wrote a post about how JSR/RTS would interfere with pushing the result to the stack. But that is only a problem if you do it the wrong way, putting JSR in the field and RTS in the emptying routine. So it was a non-issue after all.
2017-09-26 08:11
ChristopherJam

Registered: Aug 2004
Posts: 1359
Ah!

Well, FWIW I forgot the results were being pushed to the stack when I was wondering if a TXS:JMP would be a faster way to return to the fieldÂ… (ie, just keep start of empty routine at top of stack)
Previous - 1 | ... | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
zzarko
Guests online: 322
Top Demos
1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 No Bounds  (9.6)
6 Comaland 100%  (9.6)
7 Uncensored  (9.6)
8 The Ghost  (9.6)
9 Wonderland XIV  (9.6)
10 Bromance  (9.6)
Top onefile Demos
1 Party Elk 2  (9.7)
2 Cubic Dream  (9.6)
3 Copper Booze  (9.5)
4 Rainbow Connection  (9.5)
5 TRSAC, Gabber & Pebe..  (9.5)
6 Onscreen 5k  (9.5)
7 Dawnfall V1.1  (9.5)
8 Quadrants  (9.5)
9 Daah, Those Acid Pil..  (9.5)
10 Birth of a Flower  (9.5)
Top Groups
1 Booze Design  (9.3)
2 Nostalgia  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)
Top Graphicians
1 Sulevi  (10)
2 Mirage  (9.8)
3 Lobo  (9.7)
4 Mikael  (9.7)
5 Archmage  (9.7)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.058 sec.