www.retrosoftware.co.uk
http://www.retrosoftware.co.uk/forum/

Simple linear time bucket sort assembler sample
http://www.retrosoftware.co.uk/forum/viewtopic.php?f=3&t=614		 Page 1 of 1
Author:  tricky [ Wed Apr 20, 2011 12:13 am ]
Post subject:  Simple linear time bucket sort assembler sample
I have just added an assembler routine to [Sample Code Library > Linear time bucket sort] http://www.retrosoftware.co.uk/wiki/index.php/Linear_time_bucket_sort

I would be happy to hear comments / improvements and answer questions here.

tricky
Author:  RichTW [ Tue Jan 22, 2013 4:30 pm ]
Post subject:  Re: Simple linear time bucket sort assembler sample
Must've missed this the first time round... (got here from 6502.org!)

That's a nice little routine, and a nice twist on the 'regular' counting sort algorithm, in that it produces an index list which you can iterate from the highest index down, i.e. LDX #num-1 / DEX / BNE, instead of LDX #0 / INX / CPX #num / BNE ... saves a few more cycles here and there.

In the past I just used a simple insertion sort to do the job, but I guess I was only moving max 8 sprites. I guess you used something like this in Jeltron, right?
Author:  tricky [ Wed Jan 23, 2013 10:27 pm ]
Post subject:  Re: Simple linear time bucket sort assembler sample
Jeltron doesn't use it, I can't actually remember if we sorted.

We started drawing immediately after the mode switch between the "play area" and the "score board" and ... I can't remember :-O
Author:  tricky [ Fri Jan 25, 2013 6:54 pm ]
Post subject:  Re: Simple linear time bucket sort assembler sample
I've just noticed, I wasted a whole byte!
LDX buckets__1 : LDY #0 : TXA : AND #1 : BEQ odd
couls have been
LDX buckets__1 : LDY #0 : TXA : LSR A : BCS odd
looking again, should that have been BNE - I probably only tested even numbers!

No, because 1 means I have 1 and 0 to do, so 1 is even ;-)
LDX buckets__1 : LDY #0 : TXA : LSR A : BCC odd

I seem to reply to my posts more than everyone else put together :-O
Author:  RichTW [ Sat Jan 26, 2013 9:12 pm ]
Post subject:  Re: Simple linear time bucket sort assembler sample
Haha, I thought I was the only one who concerned themselves with things like that :lol:

Actually, I love this little routine for a couple of reasons - firstly, because it's such a neat and efficient algorithm for doing something you're quite likely to want to do in a game. For sorting sprites by screen line, you don't even need the precision of a normal sort: 8 buckets would probably be enough (to split the screen into 8 zones), and this would execute super quickly using this routine.

Second reason I love it is that this algorithm just translates so nicely into 6502, using exactly all three registers, and needing no more (e.g. no temporary stores to stack or zp).

I'll definitely turn to this routine any time that I need to do some raster chasing in the future - thanks a lot for posting it.
Page 1 of 1 All times are UTC [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/