Thursday, July 03, 2008

Multiplexor fun!

I've been playing with trying to speed up the multiplexor sorting, and I thought I had a much quicker way of doing it too. The old method was dumb, really dumb. I'd run through all 16 sprites, get the smallest Y value one store it, set it to $FF and then loop again until there were none left. VERY simple stuff. However that means for the worst case its doing a 16*16 loop, with a preloop of 16 to setup some values.

So, I though, "How about an insertion linked list?" Simply add a sprite index to a 1D indexed-linked-list at the correct point. Now, worst case shouldn't be as bad as 16*16 since you will only ever check with whats in the list already. Now for the 1st few, that means theres only a couple of entrys there, while the last few will obviously check to n-1(ish). Now this sounds all very good, and I'd hoped that it double the speed.... however, that was not to be. Would you believe for the worst case, its only about 1 scanline faster! Damn!

It's still not working 100% but its mostly there, and while the code is around 72 bytes smaller, its much harder to follow (since linked lists under 6502 are tricky anyway) so I'm wondering which version I should take....

After the sort I need to copy all the sprite data into the IRQ buffer for displaying, so thats another N loop as well. On the plus side, when theres not as much on screen its quite a bit quicker, and only gets bad once a load of things come on. I guess this means that when I'm displaying lots of character sprites and only a couple of H/W sprites I'd win out over all; still, worst case is usually the ones to watch for.... *sigh*


Anonymous said...

I wonder, how does your multiplexer sorting algo (didn't take peek in your source actually to see how it works, maybe it is already similar) compare with simple "insertion" (Atleast I think it's insertion sort) sort?

I know some variation of that algo were used in Konami etc. games atleast. has source code for it.

Sprite positions don't generally change massively much from one frame to next, and because of that, there's basically quite good prediction for order already...

Mike said...

MMmmmm...Im not sure. Interesting idea I guess, and yes I'm sure it would be good in lots of situations but I've no idea how it would compare.

Theres nothing to stop you implementing another one - theres already 3 there you can use as an example!

If you do decide to add another, don't forget to send it back to me for inclusion in the framework. :D

Anonymous said...

Heh, yea. That insertion sort is very simple anyway :)

I can't think that many situation in "games" where that sort is not performing quite good. Sprites rarely jump randomly in Y position :) They move few pixels up/down => usual situation is that there are few swaps per frame and that's about it.

Maybe I'll have to take peek in that framework of yours :) Been quite a while since I last did C64 coding (Getting old I guess ;P) so maybe I manage persuade meself that this is good excuse to do some coding again :D

Btw, your blog has been interesting read when I'm now in some nostalgic moods... :D