| |
Oswald
Registered: Apr 2002
Posts: 5020 |
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....
|
| |
Digger
Registered: Mar 2005
Posts: 421 |
btw. Nice tool for visualising various sorting algos, Counting Sort included: https://visualgo.net/en/sorting |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
Well, an unrolled bubble iteration should only take about 8 lines for 32 actors if there's no change, 10ish if there are four or five swaps.
I do like Falco Paul's suggestion of kicking off an Ocean Sort but aborting and switching to bucket sort (or some other constant time algorithm) if the number of swaps passes a certain threshold.
(cf http://www.codebase64.org/doku.php?id=base:sprite_multiplexer_s.. )
As for making lft's suggestion a little more memory flexible, I'm wondering if writing an RTS into the increment field could be cost effective? |
| |
lft
Registered: Jul 2007
Posts: 369 |
I have thought of a different way to relax a memory constraint. Consider this variant of the bucket-emptying routine:
sty endptr+1
lax ylink,y
pha
lda actorlink,x
sta ylink,y
bpl endptr
sta inyfield,y
endptr jmp inyfield
The worst-case execution time is the same, while the case of multiple actors in the same bucket is now slower. But now the location of the link table is unconstrained. |
| |
lft
Registered: Jul 2007
Posts: 369 |
Quoting ChristopherJamI'm wondering if writing an RTS into the increment field could be cost effective?
That would imply a JSR out of the increment field, right? That still means you have to put the bucket-emptying routine in four different, fixed places. Meanwhile the execution time increases by a rasterline.
Perhaps you meant the other way around, JSR into the increment field and RTS to the bucket-emptying routine. That would indeed make the memory layout more flexible, but at the cost of three rasterlines.
(Edit: I see now that I misread your post. Of course you mean the second thing.) |
| |
lft
Registered: Jul 2007
Posts: 369 |
(removed) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
(intrigued) |
| |
lft
Registered: Jul 2007
Posts: 369 |
I wrote a post about how JSR/RTS would interfere with pushing the result to the stack. But that is only a problem if you do it the wrong way, putting JSR in the field and RTS in the emptying routine. So it was a non-issue after all. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1378 |
Ah!
Well, FWIW I forgot the results were being pushed to the stack when I was wondering if a TXS:JMP would be a faster way to return to the field
(ie, just keep start of empty routine at top of stack) |
| |
JackAsser
Registered: Jun 2002
Posts: 1989 |
Just some thoughts...
Multiplexers in game scenarios, is the sorting normally done in the vertical blank or is the sorting performed in the main loop bur for the next frame's sprite setup?
Was just thinking of the ideas of not sorting at all and the fact that the vertical blank period is a bit crowded. A lot of other stuff must be updated there such as the scrolling etc.
What if the multiplexer simply scans the remaining actors for the next entry? This is in total of course a O(n^2/2) algorithm and dead slow. Worst case to handle would be 8 sprites having to be multiplexed directly below. So you have 21/8 raster lines to find the lowest index in the remaining actors.
Think I'll test this approach some day soon.. |
| |
cadaver
Registered: Feb 2002
Posts: 1153 |
There are games that do both. I remember at least Midnight Resistance *not* doublebuffering the sorted sprites, so it was doing the sort in the vblank / scorepanel area.
Generally I'd recommend not making something timecritical that absolutely doesn't need to be, therefore rather pre-calculate the sorted sprites anywhere when the main program has time.
If you do the sorting "on the fly", you can't take advantage of last frame's sorting result. In a tight sprite formation, you barely have enough time to load the sprite registers from pre-sorted data, so would imagine you would run into trouble with a "find the next sprite" approach, even with unrolled code. |
| Previous - 1 | ... | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 - Next |
