| |
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.... |
| |
Axis/Oxyron
Registered: Apr 2007 Posts: 91 |
Quote: So i examined the tickcounts of the code I've got, with heavy use of zeropage it can sort 32 elements in 1188 cycles, without zp it does the same job in 1448 cycles (unless my calculations are incorrect). The drawback is that every value you want to sort has to be reduced in accuracy in order for it to work (eg two lda, sta in two different tables)...'
*edit*
HCL actually drops a hint for this sorter in the commentsection of Classics
That ADC STA sequence mentioned in the comments of classics looks like 1 of the passes of a radix-sort. But in pure speed that wont be competitive to the ideas already posted here. Atleast as long as you dont reduce accuracy and really work with 200 different y-positions. My latest version has around 2400 cycles for the given use-case, if I remember right.
But the radix approach has some really nice properties compared to the bucket-sort mostly used here. It sorts in perfect 8 bit accuracy and sorts stable. That makes it more generally usable (e.g. for sorting 3D Bobs and polygons without any flickery). And in critical cases it can even avoid bugs in multiplexing. E.g. when big groups of sprites batch in small areas. |
| |
Rastah Bar
Registered: Oct 2012 Posts: 336 |
Quote: Quoting Color BarI'm sorry, but I think you missed 2 cycles: PLA / STA *+4 / JMP (jumptable) takes 13 cycles. This means that the approach in post #103 is 2 cycles faster.
Damn, you're right. The SBX#$06 takes two cycles less than the LDY newBranchTableValue,x
FWIW, the 'more than one sprites on a line' case could be improved by replacing the SKW instructions with JMP *+3; it saves a cycle. And you're still using SBX at least :)
Yes, I was a bit too eager to use illegals. Nevertheless, what I don't like about post #103 is that it will crash when there are more than 10 sprites on a line.
So I lean to sticking to the combination of posts #91 and #101. |
| |
Rastah Bar
Registered: Oct 2012 Posts: 336 |
Quoting Axis/OxyronThat ADC STA sequence mentioned in the comments of classics looks like 1 of the passes of a radix-sort. But in pure speed that wont be competitive to the ideas already posted here. Atleast as long as you dont reduce accuracy and really work with 200 different y-positions. My latest version has around 2400 cycles for the given use-case, if I remember right.
But the radix approach has some really nice properties compared to the bucket-sort mostly used here. It sorts in perfect 8 bit accuracy and sorts stable. That makes it more generally usable (e.g. for sorting 3D Bobs and polygons without any flickery). And in critical cases it can even avoid bugs in multiplexing. E.g. when big groups of sprites batch in small areas.
The approach proposed here (the combination of posts #91 and #101 or #103) counts down the actor list, so when there are multiple actors with the same Y value, they are added to the bucket in reverse order, but in the second pass the order is restored. So I think this approach is stable as well.
If think the method also has full 8 bit accuracy. The numbers of cycles mentioned are for visible sprite positions and that means 220 buckets. This can be increased to 255 buckets. |
| |
lft
Registered: Jul 2007 Posts: 369 |
Field Sort |
| |
Rastah Bar
Registered: Oct 2012 Posts: 336 |
Nice!
I think this 32K of ram usage you refer to applies to combining posts #91 and #103. When combining #91 and #101 it can be considerably lower (but it will still be a lot).
Btw, how many sprites with the same Y value can your routine handle? |
| |
ChristopherJam
Registered: Aug 2004 Posts: 1378 |
Yes, nice work! This will take some investigating to unravel.
SHX $FE00,Y ^ is basically stx $fe00,y on account of the mask being $fe+1, yes? |
| |
lft
Registered: Jul 2007 Posts: 369 |
Color Bar, yes I realise that you went through a number of different versions, trading memory for cycles. But I thought it fair to mention the version that beats mine in running time.
There can be any number of sprites on the same line; They are linked. Of course, the multiplexer drops them if there are too many, as is evident from the flickering in the demo.
This is a generic full random sorting routine for 8-bit values, although in the demo it is limited to 220 different y-values to make it comparable with your benchmarks.
Christopher Jam: That is correct. It's nice to find a use for this opcode where it actually improves performance, because it's quite constrained: The masking drops off if the instruction is suspended by DMA, and page crossings cause the wrong value to be written. So the best bet is indeed to stick to the operand $fe00. |
| |
Rastah Bar
Registered: Oct 2012 Posts: 336 |
Quote: Yes, nice work! This will take some investigating to unravel.
SHX $FE00,Y ^ is basically stx $fe00,y on account of the mask being $fe+1, yes?
Yes, check out this document (pages 38 and 41):
No More Secrets v0.91 |
| |
chatGPZ
Registered: Dec 2001 Posts: 11108 |
lft: now it would be very cool if you could expand this routine to handle excess sprites in a way that they will be displayed on alternating frames ("interlaced") - then it would work perfectly fine for a game (MUCH better than sprites disappearing) |
| |
ChristopherJam
Registered: Aug 2004 Posts: 1378 |
Dear lords. So the n-actors snippets leading up to $fe00 insert each actor ID in to a linked list with the head at $aa00+yposition, and the 'next' pointers are at $10+actorID, and also replaces the INY at $fe00+yposition with a JMP to a bucket emptying routine.
Here's a sample snippet:
.C:fb52 A4 90 LDY $90+0 ; Y coordinate of actor 0
.C:fb54 9E 00 FE SHX $FE00,Y ; this is effectively STX $fe00,y
.C:fb57 B9 00 AA LDA $AA00,Y ; bucket head
.C:fb5a 85 10 STA $10+0 ; next pointer for actor 0
.C:fb5c A9 00 LDA #$00 ; actor id 0
.C:fb5e 99 00 AA STA $AA00,Y
The INYs that fill $fe00 to $feff increment Y through all the potential bucket indices, jumping off to a bucket emptying routine wherever an INY has been replaced with a JMP
There are four routines at 4c4c, 4cc8, c84c and c8c8 to handle each of the cases where zero to two of the next two buckets are also nonempty.
The bucket emptying routine takes advantage of the list heads being stored in page $aa to reuse the $aa as a TAX instruction when looping over a bucket that contains more than one actor, and the lists are terminated with $c8, which is both negative and doubles as the INY that needs to be written back to $fexx to clear the bucket for the next frame. (it's also written to $aaxx, just like the flagged bucket sort on codebase).
Each bucket emptying routine returns to the scene of the crime after writing the INY back, which bumps Y the value needed for the next bucket. Hence, the four bucket emptying routines are in fact identical; here's a sample:
.C:4c4c 8C 5E 4C STY $4C5E ; patch return address
.C:4c4f BF 00 AA LAX $AA00,Y ; fetch bucket head
.C:4c52 48 PHA
.C:4c53 B5 10 LDA $10,X ; read 'next' pointer.
.C:4c55 10 FA BPL $4C51 ; Actor ids are positive, INY is not
.C:4c57 99 00 FE STA $FE00,Y ; restore INY
.C:4c5a 99 00 AA STA $AA00,Y ; empty linked list
.C:4c5d 4C 7E FE JMP $FE7E
I think that just about covers it. Lft, that's a mighty fine piece of work. |
Previous - 1 | ... | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | ... | 21 - Next |