| |
Oswald
Registered: Apr 2002
Posts: 5017 |
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....
|
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
you might miss sprites otherwise possible to display with the bucket sort.
spr1=70
spr2=74
bucket sort result:
spr2
spr1
then you fire an irq for the next sprite that will be spr2, and already late from spr1 |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote: you might miss sprites otherwise possible to display with the bucket sort.
spr1=70
spr2=74
bucket sort result:
spr2
spr1
then you fire an irq for the next sprite that will be spr2, and already late from spr1
The way I do it is to attach the IRQ to the end of the last use of the new sprite, and thus try to reprogram the "channel" as soon as possible. Then all you have to do is check if you're too late to generate next IRQ (if it is to run before the current scanline) and if so jump straight to the next handler. |
| |
cadaver
Registered: Feb 2002
Posts: 1153 |
If you preprocess the sprite-IRQs, you can take care to always take the upmost Y-coordinate as the basis for the IRQ, even if it isn't the first sprite in sort order. Did this in MW1-3 which had inexact sprite sorting. Brr, never again! :) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11114 |
now you are assuming too much :) ofcourse the displayer code must be written in a way that such thing can not happen. |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
Quote: If you preprocess the sprite-IRQs, you can take care to always take the upmost Y-coordinate as the basis for the IRQ, even if it isn't the first sprite in sort order. Did this in MW1-3 which had inexact sprite sorting. Brr, never again! :)
what was so bad about it, when you could get it 'right' afterall ? |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
Quote: The way I do it is to attach the IRQ to the end of the last use of the new sprite, and thus try to reprogram the "channel" as soon as possible. Then all you have to do is check if you're too late to generate next IRQ (if it is to run before the current scanline) and if so jump straight to the next handler.
hmm 'before the new' sprite approach allows more tight packing ;) clever solution nevertheless. |
| |
cadaver
Registered: Feb 2002
Posts: 1153 |
Oswald: well it was never completely "right" in those games, you could create unnecessary artifacts for example when several motorcycles (2x2 sprites) were coming at you and you jumped. But for example, if you have mostly airborne enemies coming at you from several heights and you're mostly on ground, it doesn't matter. |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
radix sort is a very interesting approach :) offers a constant sort time, but sadly that is much worse than progressive insertion sort. when fully unrolled I estimate a running time of ~55 rasterlines. |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote: radix sort is a very interesting approach :) offers a constant sort time, but sadly that is much worse than progressive insertion sort. when fully unrolled I estimate a running time of ~55 rasterlines.
The bucket sort we talked about earlier is just bucket sort is just a special case of the radix sort. Except it sorts in one step and with some loss of precision to reduce the number of buckets.
Anyway an optimized and unrolled two-step radix sort shouldn't be quite as bad as that. It ought to be possible to get it well below 55 lines. In fact it'd probably be faster than a bucket sort combined with a bubble sort fix-up stage.
Dammit.. Now I have to implement one just to see how it turns out ;) |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
here is my implementation:
there's 2 bucket arrays, each 256 bytes. each bucket can hold max 15 elements, 16th is the counter of the elements. adress of fex. bucket 3's element 5 is: 3*16+5.
bucket1 is used for the first pass
bucket2 for the 2nd.
each code snipplet is a code segment out of an unrolled loop. (ie stuff is missing like lda bucket1+bucketnr*16,x)
I dont see how this could be much faster :) some1 proove me wrong :)
;pass1
ldx sort+0
ldy spry,x ; get sprite y coord
lax and#0fmul16,y ;get bucket startadress
ora bucket1+15,x ;get adress INside the bucket
inc bucket1+15,x ;inc nr of elements
tax
smod sty bucket1,x ;store spr to bucket
;pass2
ldx bucket1+15
beq next ;empty bucket dont bother
blp1
ldy bucket1,x
lda spry,y ;get spr y
and #%11110000 ;upper 4 bits only this time
tay ;which is exactly our pointer
ora bucket2+15,y ;addy inside bucket
inc bucket2+15,y ;inc bucket counter
tay ;final bucket addy
sta bucket2,y ;store sprite
dex
bne blp1 ;any more in bucket1?
next
;pass3
ldy #$00 ; nr of sprites counter this is done only once
ldx bucket2+15
beq next ;empty bucket?
blp2
lda bucket2,x ;get sprite nr
smod sta final,y ;store to final list
iny ;final spr count
dex
bne blp2 ;any more in curr. bucket?
edit, ok, well some bugs there, destroying regs, but assuming they werent.. fixing those would make it even more slower tho |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... | 21 - Next |
