| |
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....
|
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
I'm attempting something like this:
;; initialize the buckets
ldx #$81
!for i,0,16 {
sta lsd_bucket+i
}
lda #$fe
!for i,0,6 {
sax msd_bucket+i*2+0
stx msd_bucket+i*2+1
sbx #-3
}
;; lsd sort
lda #$0f
!for i,0,32 {
ldx actor_ypos+i
sbx #$00
ldy lsd_bucket,x
sty actor_link+i
ldy #i
sty lsd_bucket,x
}
;; msd sort
!for i,0,13 {
ldx lsd_bucket+i
bmi .next
.msd ldy actor_ypos,x
lda msd_table,y
tay
lda msd_bucket,y
stx msd_bucket,y
ldy actor_link,x
sta actor_link,x
bmi .next
ldx actor_ypos,y
lda msd_table,x
tax
lda msd_bucket,x
sty msd_bucket,x
ldx actor_link,y
sta actor_link,y
bne .msd
.next }
;; finally in the mux writer.
;; for each sprite, alternating x and y
ldx actor_link,y
bpl .ok
.bucket lda msd_bucket-$80,x
tax
bmi .bucket
.ok ...
The idea is to use linked lists for the buckets. Sort all possible actors in the first pass (invalid ones having high y values), you can optimize it by trying to keep the maximum actor number as low as possible and skipping those high entries. And we can link the actors together in the actual multiplexer instead of a separate pass. Also the sentinels in the msd buckets can help us to skip buckets easily.
Finally we don't need more than about 13 buckets since not all y coordinates are valid, and as a bonus we can collect the invalid ones into a single "death" list automatically by tweaking the division table. Another bonus is that by sticking a store in the bucket skipping code of the multiplexer you can easily link together a complete list of actors which IMO is more convenient to work with than an order list (i.e. you only need to know the current actor's index to move to the next one, no need to keep track of an order index). Furthermore just about everything is kept on the zeropage, thought only temporarily of course.
All in all it seems to work out to about 28 raster lines. Except I'm not at all certain whether this will actually work yet.. ;) |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
wow, very creative ! :) 28 lines sounds very good :) tho I have yet not an idea how progressive sort can perform when there's little changes ;) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote: wow, very creative ! :) 28 lines sounds very good :) tho I have yet not an idea how progressive sort can perform when there's little changes ;)
It depends really. A progressive sort is faster in 95% of the cases but it's that twentieth missed frame which fucks up the flow in an action game. Then again I'm writing a twitch game which aspires to be a bullet hell shooter, but a platformer (say) would obviously have other requirements.
The radix sort is only something like 15 cycles (per actor) slower than my current bucket sort. So if I can get it to work I'll probably switch, and I'd be happy to share the final code if I do. Weighting the extra cycles vs. the extra sprites makes it a tough choice. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1370 |
I just used insertion sort starting with the ordering from the previous frame in Teradyne, setting up the first 8 sprites in the end-of-frame IRQ, and then moving each sprite down with an IRQ at the end of its previous use. If the next sprite needs moving before I returning from the IRQ I do it then instead of setting up another.
I stagger creation of all the sprites in a new formation over several frames to spread the workload, then there's never too much work for the sorter to do. |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quote: I just used insertion sort starting with the ordering from the previous frame in Teradyne, setting up the first 8 sprites in the end-of-frame IRQ, and then moving each sprite down with an IRQ at the end of its previous use. If the next sprite needs moving before I returning from the IRQ I do it then instead of setting up another.
I stagger creation of all the sprites in a new formation over several frames to spread the workload, then there's never too much work for the sorter to do.
But then you've mostly got horizontal movement, right? I've got to worry about a laser moving 21 lines per frame and other nasty things :(
Of course managing not to overload the multiplexer in a horizontal shooter is much harder. So I guess I'm still better off ;) |
| |
Oswald
Registered: Apr 2002
Posts: 5017 |
btw some inspiration on the attack waves, and enemies: http://youtube.com/watch?v=Aj23K8Ri68E&mode=related&search= a lot if this could be done on a c64 imho. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11100 |
an ikaruga-like shooter would be generally a cool idea :) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1370 |
Yeah, the movement is largely horizontal, with a few loop-the-loops, and that "X of death" formation the reviewer complained of. The times I drop a formation in from above or raise it from below it can struggle a little if there's already a dense formation it has to cross over.
A danmaku shooter like Ikaruga would indeed be awesome, but also a serious challenge to implement! |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
I don't think I've ever done a multiplexor where the sprites could move freely around, but is it really necessary to sort them?
Wouldn't it be enough with a map consiting of a byte per rasterline where the bit pattern indicated which sprites were used. To allocate a new sprite, just ora all the bytes for the sprite's y-position and 21 positions down, and see which 0's are left, or if the result is $ff it's too bad.
21 oras per sprite might still be a little heavy, but this could of course be optimized by reducing the precission a bit, e.g. to 3rd line, which means only 7 oras/sprite.
Edit: And of course you need to insert 7 values in the table afterwards as well. :-) Still think it's faster than sorting though.
|
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
I guess that's basically a "zone" multiplexer except with better granularity, sort of.. Don't forget that you've got to search through the scanlines first to see if any sprite channel is free all the way down before marking them. Then you'd also need another set of tables to keep track of which virtual sprite is bound to which sprite channel.
Finally you'd have to walk through the array line-by-line to figure out when to trigger the interrupts. I suppose the easiest way would be to walk the array from the bottom up to find the earliest possible line to program the sprite.
Except it'd have to be fairly coarse to win-out over a sort-based approach.
edit: I suppose you wouldn't have to check all entries, just the first and the last one. Or maybe only the first if the flag was interpreted to mean that the sprite is free to be reused here. Hmm..
Either way I figure it'd be a nice way to deal with y-expanded sprites and other special cases for linked sprites as well as for dealing with sprite priorities, i.e. the sprites would be allocated in the order of priority. |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... | 21 - Next |
