| |
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 :) |
|
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
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. |
| |
Burglar
Registered: Dec 2004
Posts: 1085 |
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... |
| |
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) |
... 193 posts hidden. Click here to view all posts....
|
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... | 21 - Next |
