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 :)
 
... 123 posts hidden. Click here to view all posts....
 
2007-10-08 18:48
JackAsser

Registered: Jun 2002
Posts: 1229
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: 4065
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: 8148
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)
2007-10-08 19:01
doynax

Registered: Oct 2004
Posts: 209
Quote:

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)
I actually do a progressive bucket sort which seems to help a bit. Bullets and enemy formations and such tends to move in step with each other after all.
2007-10-08 19:06
Oswald

Registered: Apr 2002
Posts: 4065
doynax, whoaw, now thats a massive amount of sprites :) \o/ how do you make the d800 copy, and where ? :) btw what bugs me about bucket sort is how to deal with the random order in the multiplexer, also rejecting 9th sprites seems to be messy :P
2007-10-08 19:09
Groepaz

Registered: Dec 2001
Posts: 8148
Quote:

also rejecting 9th sprites seems to be messy


why reject? just make it so it's ignored :) (ie bucket can take more than 8 sprites, but plexer will only use first 8)
2007-10-08 19:13
doynax

Registered: Oct 2004
Posts: 209
Quote: doynax, whoaw, now thats a massive amount of sprites :) \o/ how do you make the d800 copy, and where ? :) btw what bugs me about bucket sort is how to deal with the random order in the multiplexer, also rejecting 9th sprites seems to be messy :P

The d800 copy is double buffered and evenly distributed across 16 frames, so it really doesn't take much raster time at all ;)
As for the bucket sort I don't quite see what you mean. The
output is still just an ordered list of sprites, just like for the insertion sort.
As for rejecting the 9th sprite I don't do any fancy multiplexer "overload" testing at all. The code just tries to optimistically display as many sprites as possible and if doesn't fit then it's just not displayed (at least that's what happens in the type of multiplexer I wrote).
2007-10-08 19:18
Groepaz

Registered: Dec 2001
Posts: 8148
Quote:

As for rejecting the 9th sprite I don't do any fancy multiplexer "overload" testing at all. The code just tries to optimistically display as many sprites as possible and if doesn't fit then it's just not displayed (at least that's what happens in the type of multiplexer I wrote).


thats probably how most game multiplexers work. (look at SEUCK...argl =D)
2007-10-08 19:23
Oswald

Registered: Apr 2002
Posts: 4065
you cant doublebuffer d800 :) for the bucket sort, I have to think it through as I'm totally new to this idea .) ie a multiplexer relies on the sorted list, wont bugs happen when sprites regs are not written in the order they should be ? :)
Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 - 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
Rebok
SAM
The MeatBall
Guests online: 35
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 Quad Core 100%  (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 Organizers
1 Burglar  (9.9)
2 Wotnau  (9.7)
3 Sixx  (9.7)
4 MWS  (9.7)
5 Frantic  (9.6)

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