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


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

Registered: Apr 2002
Posts: 4065
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 :)
 
... 145 posts hidden. Click here to view all posts....
 
2017-09-25 08:32
Trash

Registered: Jan 2002
Posts: 95
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 10:13
The Human Code Machine

Registered: Sep 2005
Posts: 101
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 22:35
Digger

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

Registered: Aug 2004
Posts: 644
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 06:52
lft

Registered: Jul 2007
Posts: 282
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 06:59
lft

Registered: Jul 2007
Posts: 282
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 08:54
lft

Registered: Jul 2007
Posts: 282
(removed)
2017-09-26 10:00
ChristopherJam

Registered: Aug 2004
Posts: 644
(intrigued)
2017-09-26 10:05
lft

Registered: Jul 2007
Posts: 282
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 10:11
ChristopherJam

Registered: Aug 2004
Posts: 644
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 | ... | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 - 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
Cruzer/CML^Oxy^Λrsenic
nucleus/TempesT
Trash
Mr.Ice
Didi/Laxity
Acidchild/Padua
Guests online: 47
Top Demos
1 Uncensored  (9.7)
2 Edge of Disgrace  (9.7)
3 Coma Light 13  (9.6)
4 Quad Core 100%  (9.6)
5 The Shores of Reflec..  (9.6)
6 Lunatico  (9.6)
7 Comaland 100%  (9.5)
8 Incoherent Nightmare  (9.5)
9 Wonderland XII  (9.5)
10 Comaland  (9.5)
Top onefile Demos
1 Pandemoniac Part 2 o..  (9.6)
2 Field Sort  (9.6)
3 Dawnfall V1.1  (9.5)
4 Daah, Those Acid Pil..  (9.5)
5 Treu Love [reu]  (9.4)
6 Dawnfall  (9.2)
7 Veterans of Style  (9.2)
8 KAOS 64  (9.2)
9 One-Der  (9.2)
10 Game of Thrones [2sid]  (9.2)
Top Groups
1 Booze Design  (9.4)
2 Censor Design  (9.4)
3 Oxyron  (9.4)
4 Crest  (9.3)
5 Finnish Gold  (9.3)
Top Diskmag Editors
1 Jazzcat  (9.5)
2 Peter  (9.4)
3 Newscopy  (9.4)
4 Remix  (9.3)
5 Vengeance  (9.3)

Home - Disclaimer
Copyright © No Name 2001-2017
Page generated in: 0.251 sec.