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: 4058
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 :)
2007-10-08 18:23
doynax

Registered: Oct 2004
Posts: 209
I tried both a bubble sort, an insertion sort and a bucket sort for my game. All of them progressive. The insertion sort was usually the fastest but in the end the bucket sort was the most stable and reliable (i.e. fever missed frames) even with the loss of precision.
It's just not worth having to worry about spawning new sprites at an appropriate position, and not let things move too fast lest the list get too far out of sync.

I can't remember precisely how much raster time it consumes right now but it isn't big deal really compared with all the other work involved.
2007-10-08 18:30
Oswald

Registered: Apr 2002
Posts: 4058
what is the name of your game? I'd like to check it :) I have made an unrolled insertion sort, which will be progressive (if I ever got to that). it takes 22 cycles including the cmp/bcc when a number is moved (swapped) around.
2007-10-08 18:40
Burglar

Registered: Dec 2004
Posts: 782
some games use sprite regions, so there's no need for sorting, just put the sprites in the right regions and you're done. I think Turrican uses that method.

you might want to check out games from Hannes Sommer/Cosmos Designs as well (ie Lions of the Universe +7 ), those should have some good multiplexers...
2007-10-08 18:42
doynax

Registered: Oct 2004
Posts: 209
It far from finished so maybe I shouldn't be giving advice, nevertheless I always appreciate a chance to plug my newest project. http://www.minoan.ath.cx/~doynax/6502/Balls_of_the_Scrolling_Th..

Anyway, the bucket sort probably takes something like 50 cycles per sprite. But that's still far better than the worst case of the insertion sort.
2007-10-08 18:44
Groepaz

Registered: Dec 2001
Posts: 8120
uh, you should be able to sort 64 sprites in the border easily =) even my crappy multiplexer does 48 sprites in border, and i know it's not the most optimized one around :)

the basic idea in games usually is bucket sort first (what burglar called regions), then (if necessary) bubblesort on the buckets.
2007-10-08 18:48
Oswald

Registered: Apr 2002
Posts: 4058
groppie, I'm afraid you're comparing here 'progressive' performance with full rnd sorting. as said swapping around ~4 sprites takes less than 10 lines.
2007-10-08 18:48
JackAsser

Registered: Jun 2002
Posts: 1227
Quote: uh, you should be able to sort 64 sprites in the border easily =) even my crappy multiplexer does 48 sprites in border, and i know it's not the most optimized one around :)

the basic idea in games usually is bucket sort first (what burglar called regions), then (if necessary) bubblesort on the buckets.


Also... when re-using the sort order from frame to frame most algorithms are close to O(n). It's seldom a game hits the theoretical maximum complexity. I really dunno if you should calculate on worst case here since worst case never will happen.
2007-10-08 18:53
doynax

Registered: Oct 2004
Posts: 209
Quote: Also... when re-using the sort order from frame to frame most algorithms are close to O(n). It's seldom a game hits the theoretical maximum complexity. I really dunno if you should calculate on worst case here since worst case never will happen.

Not the worst case perhaps. But the difference I saw between the best and worst case, even when catering to the multiplexer when inserting things, was still something like 300%.
And in an action game it's all about maintaining a smooth framerate no matter what happens.
2007-10-08 18:53
Oswald

Registered: Apr 2002
Posts: 4058
jack, well its just ammazing to me that how slow this operation really is. without tricks sorting alone can eat most of a frame. Taking into account how unoptimized games used to be its nice they can pull off their plexed sprites, and the rest in 50fps :)

edit: to gro, 132 rasterlines is the time it takes to sort 32 totally random numbers.
2007-10-08 18:59
Groepaz

Registered: Dec 2001
Posts: 8120
Quote:

groppie, I'm afraid you're comparing here 'progressive' performance with full rnd sorting. as said swapping around ~4 sprites takes less than 10 lines.


nope, my plexer doesnt take advantage of that, its full random sorting. the key is to use a reasonable amount of buckets, plus an unrolled bubblesort. (and if you can live with a little error you can leave out the bubblesort completely, which is what i did)
 
... 59 posts hidden. Click here to view all posts....
 
Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 - 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
Thinker/Bytestar
hedning/G★P
Zaz/Dual Crew
Tom-Cat/Nostalgia
Peiselulli/tRSi
lft
grass/LETHARGY
Frantic/Hack'n'Trade
reidrac/usebox.net
Knut Clausen/SHAPE
Guests online: 43
Top Demos
1 Uncensored  (9.7)
2 Edge of Disgrace  (9.7)
3 Coma Light 13  (9.6)
4 The Shores of Reflec..  (9.6)
5 Lunatico  (9.6)
6 Comaland 100%  (9.5)
7 Incoherent Nightmare  (9.5)
8 Wonderland XII  (9.5)
9 Comaland  (9.5)
10 Wonderland XIII  (9.5)
Top onefile Demos
1 Veterans of Style  (9.5)
2 Dawnfall V1.1  (9.5)
3 Daah, Those Acid Pil..  (9.5)
4 Treu Love [reu]  (9.4)
5 Dawnfall  (9.3)
6 SidRok  (9.3)
7 F1 Evolution  (9.3)
8 One-Der  (9.2)
9 Tunnel Vision  (9.2)
10 Game of Thrones [2sid]  (9.1)
Top Groups
1 Pond  (10)
2 Booze Design  (9.4)
3 Censor Design  (9.4)
4 Oxyron  (9.4)
5 Crest  (9.3)
Top Cover Designers
1 Duce  (9.8)
2 Electric  (9.8)
3 Junkie  (9.7)
4 The Elegance  (9.4)
5 Cuc  (9.2)

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