| |
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 |
Quote: mixing some ideas this could be powerful. I'm thinking of a chained list of rasterlines having sprites, and each element in this list would point to another list having the sprites. ;)
Care to elaborate?
Superficially that sounds exactly like what my bucket sort does today, except I think you meant something entirely different.. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
well at a second look it might be not a good idea, as walking the chain each time a new sprite is inserted is something like an insertion sort using doublechained elements :P it would be better not to chain the raster list, instead using a 256 byte table, the end result would be counting sort with chained sprites :) or if you want like your radix sort without separate lsd/msd :)
edit, ok this one fails when you have to reset the 256 byte table :P maybe you could collect the used entrys somewhere during the proces tho. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1408 |
Hmm. Perhaps you could insert 'start actor' and 'end actor' events into one each of (say) 50 buckets, one every four rasters.
Then whenever an actor is done with you could add the sprite you used to a free list, and whenever a sprite is required you could take one off the free list. No sorting required - you just need to look ahead in the bucket table to see when the next raster interrupt is required. |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
how about binary trees? %) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote: how about binary trees? %)
I doubt it. Any kind of balancing would be way to complicated, and you'd almost certainly encounter nasty edge cases without it. Having to implement an AVL or red-black tree on this machine terrifies me. A splay tree just might be feasible but I'm not sure whether it'd solve the problem. Anyone here with a real CS background who can tell for sure?
Unless you mean a heap sort with it's implicit tree? |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1408 |
Hmm. I'm sure I've used heap-sort for something on this beasty. May have been hidden-surface-removal for a solid 3d renderer.. (edge events as you traverse a scanline push/pop surfaces) |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: I doubt it. Any kind of balancing would be way to complicated, and you'd almost certainly encounter nasty edge cases without it. Having to implement an AVL or red-black tree on this machine terrifies me. A splay tree just might be feasible but I'm not sure whether it'd solve the problem. Anyone here with a real CS background who can tell for sure?
Unless you mean a heap sort with it's implicit tree?
Nah... stick to radix sort and the like since they're O(n). General sorting using trees etc are O(n log n) and on this platform they'll have a nice quite big constant put in front also due to overhead. Those constants are ofcourse negliable for very large n's, however a multiplexer doesn't have large n. ;D
For a complete sort I have serious doubts that anything can out perform a well written radix sort (2 step bucket sort as you have shown before).
If you have similar sort order from frame to frame I'd recommend bubble sort actually. They're O(n^2) worst case but O(n) if sort order is similar + they're dead easy to implement and optimize.
Maybe one could have some code that would realise when to use a full sort with radix-sort and when to "just fix" the sort order using bubble sort. This would improve the average time ofcourse but slightly worsen the worst case ofcourse.
Also as Cadaver mentioned, it's seldom the sort order actually changes that much from one frame to another. On could be smart when you get new enemies etc by spreading the sort for the actors that are about to enter the screen, over several frames.
F.e. you will need some kind of data structure to know what kind of actors that will emerge soon in the scrolling direction. You could have those somewhat pre-sorter and/or prepare-sort them on the way there.
Tons of ideas.... =) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1408 |
Hmm. For most shooters the enemy paths are completely predetermined. You could pre-sort all of them (keeping dead enemies onscreen with a blank sprite definition), or at least provide new sortlists for any points in time that a bubble sort is going to be expensive.
That would even allow you to determine in advance when a slightly shuffled order is acceptable :)
Speaking of load management, can anyone think of a situation that an 8-sprite muxer that needs to handle a player in an arbitrary position will always be able to cope with that a 7-sprite muxer with the player on sprite 0 would not? (other than forcing the player to avoid certain y-ranges by using scenery collisions) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote:Hmm. For most shooters the enemy paths are completely predetermined. You could pre-sort all of them (keeping dead enemies onscreen with a blank sprite definition), or at least provide new sortlists for any points in time that a bubble sort is going to be expensive. Yeah, that'd probably work. If you were writing Armalyte 2..
But it would be way to limiting for my tastes. You've got to at least have bullets fired towards the player in the kind of game I'm trying to write.
Quote:Speaking of load management, can anyone think of a situation that an 8-sprite muxer that needs to handle a player in an arbitrary position will always be able to cope with that a 7-sprite muxer with the player on sprite 0 would not? (other than forcing the player to avoid certain y-ranges by using scenery collisions) Sure. Bullets in a vertical shooter tend to be separate from the player and able to reuse the player's sprite. As long as they are spawned a couple of scanlines above the player at least.
Besides I'm happy with allowing a bit of flicker every now and then, especially if it's mostly in the two player mode, in return for a greater amount of objects and not having to worry myself to death over how the enemy paths should be designed as to guarantee zero flicker. Best-effort multiplexing FTW! |
| |
Oswald
Registered: Apr 2002
Posts: 5086 |
I'm strongly beside that the player sprite shouldnt be handled exclusively, except the case of more than 8 sprites on a line. also if this happens I'd alternatively reject sprites frame to frame, thus in a flickery fashion but still all sprites would be visible. I've seen this in some soccer game, and I like it |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... | 21 - Next |
