Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
 Welcome to our latest new user Facet ! (Registered 2018-08-14) You are not logged in 
CSDb User Forums


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

Registered: Apr 2002
Posts: 4273
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 :)
 
... 152 posts hidden. Click here to view all posts....
 
2017-09-26 08:00
ChristopherJam

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

Registered: Jul 2007
Posts: 355
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: 822
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)
2017-09-29 09:22
JackAsser

Registered: Jun 2002
Posts: 1351
Just some thoughts...

Multiplexers in game scenarios, is the sorting normally done in the vertical blank or is the sorting performed in the main loop bur for the next frame's sprite setup?

Was just thinking of the ideas of not sorting at all and the fact that the vertical blank period is a bit crowded. A lot of other stuff must be updated there such as the scrolling etc.

What if the multiplexer simply scans the remaining actors for the next entry? This is in total of course a O(n^2/2) algorithm and dead slow. Worst case to handle would be 8 sprites having to be multiplexed directly below. So you have 21/8 raster lines to find the lowest index in the remaining actors.

Think I'll test this approach some day soon..
2017-09-29 10:46
cadaver

Registered: Feb 2002
Posts: 1063
There are games that do both. I remember at least Midnight Resistance *not* doublebuffering the sorted sprites, so it was doing the sort in the vblank / scorepanel area.

Generally I'd recommend not making something timecritical that absolutely doesn't need to be, therefore rather pre-calculate the sorted sprites anywhere when the main program has time.

If you do the sorting "on the fly", you can't take advantage of last frame's sorting result. In a tight sprite formation, you barely have enough time to load the sprite registers from pre-sorted data, so would imagine you would run into trouble with a "find the next sprite" approach, even with unrolled code.
2017-09-29 11:21
JackAsser

Registered: Jun 2002
Posts: 1351
Quote: There are games that do both. I remember at least Midnight Resistance *not* doublebuffering the sorted sprites, so it was doing the sort in the vblank / scorepanel area.

Generally I'd recommend not making something timecritical that absolutely doesn't need to be, therefore rather pre-calculate the sorted sprites anywhere when the main program has time.

If you do the sorting "on the fly", you can't take advantage of last frame's sorting result. In a tight sprite formation, you barely have enough time to load the sprite registers from pre-sorted data, so would imagine you would run into trouble with a "find the next sprite" approach, even with unrolled code.


Ok, thanks for the insights.
2017-09-29 13:35
ChristopherJam

Registered: Aug 2004
Posts: 822
For applications where border time is a lot scarcer than display time, I suspect I'd lean towards a nice simple linked list based bucket sort; the times it takes a while to find next sprite are precisely when the next sprite is a fair way down the screen, so the time taken wouldn't be so critical. If the next sprite is in the next line or three there'd only be a few links to follow, which shouldn't take too long..
2018-08-06 06:54
Repose

Registered: Oct 2010
Posts: 139
Just wanted to mention an O(n) sort I invented long ago I call Fibonacci sort, for how one step does a running sum.

Now I realize it's been invented long ago and is called the counting sort.

I think it takes about 50 cycles per number.
#Fibonacci Sort
unsorted = [3, 1, 4, 1, 5, 9, 2, 6, 0]
counts = [0] * 10
fib    = [0] * (10 + 1)
sortd    = [0] * len(unsorted)

#First pass: find the counts
for n in unsorted:
    counts[n]+=1

#Second pass: do the Fibonacci magic
i = 0
total = 0
for n in counts:
    fib[i] = total
    total += n
    i+=1
    
#Third pass: output sorted
for n in unsorted:
    sortd[fib[n]] = n
    fib[n] += 1

#Results
print(sortd)


a very buggy version in assembler:
;count each number
ldx #$ff
count ldy unsort,x
inc count,y
dex
bne count;15/ea

;Fibonacci step
clc
lda count
inx
fib adc count,x
sta sta count,x
inx
bne fib;13/ea

;Copy sorted
sort ldy unsort
ldx count,y
sty sort,x
inc count,y
inc sort+1
bne sort/27/ea
2018-08-06 10:06
Oswald

Registered: Apr 2002
Posts: 4273
this is one case for (,x) if you want the usual indice indirection too.
2018-08-07 07:27
ChristopherJam

Registered: Aug 2004
Posts: 822
Nice work independently discovering counting sort, Repose

It's worth noting that this one is O(n)+O(m), where m is the number of buckets.

Pass 2 for a "perfect" sort of n sprites would take 220 iterations (256 in your example code)

That's around 220*10 cycles if you unroll the loop a little, so about 35 lines of overhead. Of course, you can cut that down considerably if you don't need as much accuracy or range.

Clearing the counts array also takes time, though you can drop that back from O(m) to O(n) by keeping it seperate to your "fib" array, persisting it frame to frame, and only clearing the entries you incremented in the first place.
Previous - 1 | ... | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 - 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
Krill/Plush
The Human Co../Maste..
Style/Chrome
blendo75
mad
Bieno/Commodore Plus
Guests online: 67
Top Demos
1 Uncensored  (9.7)
2 Comaland 100%  (9.7)
3 Edge of Disgrace  (9.7)
4 Coma Light 13  (9.6)
5 The Shores of Reflec..  (9.6)
6 Wonderland XII  (9.6)
7 We Come in Peace  (9.6)
8 Lunatico  (9.6)
9 Incoherent Nightmare  (9.5)
10 Wonderland XIII  (9.5)
Top onefile Demos
1 FMX Music Demo  (9.6)
2 Party Horse  (9.6)
3 Daah, Those Acid Pil..  (9.5)
4 Pandemoniac Part 2 o..  (9.5)
5 Arok 20 Invitation  (9.5)
6 Treu Love [reu]  (9.5)
7 Merry Xmas 2017  (9.4)
8 Dawnfall V1.1  (9.4)
9 In Memoriam BHF  (9.4)
10 Dawnfall  (9.4)
Top Groups
1 Oxyron  (9.4)
2 Booze Design  (9.4)
3 Censor Design  (9.4)
4 Finnish Gold  (9.4)
5 Crest  (9.3)
Top Mega Swappers
1 Aslive  (9.4)
2 R.C.S.  (9.3)
3 Dishy  (9.2)
4 Nightshade  (9.1)
5 Calypso  (9.0)

Home - Disclaimer
Copyright © No Name 2001-2018
Page generated in: 0.063 sec.