| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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....
|
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
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. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11350 |
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
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. |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11350 |
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) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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 |
| |
chatGPZ
Registered: Dec 2001
Posts: 11350 |
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)
|
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... | 21 - Next |
