O.k. since we are on an optimizing kick I thought I'd throw out my most
time-consuming piece of code and see what Andrew and Jim could do with
it! (Hmmm, an optimizing competition). This is a sorting routine that
is necessary for my multi-game engine to work properly. Optimizing for
time is necessary, not space, so if you can do it in fewer cycles that
would be awesome and larger code size is o.k. I don't care if you use
something other than a bubble sort either, but since MAXSPRITE only
equals 5, I don't think another algorithm would save much time. Now
this piece of code executes in the VBLANK section of my game, keep that
in mind as you optimize it because there is an issue that is necessary
to remember - but I'm not going to point that out yet because I want to
see if anyone picks up on it. Just a hint - it's something that is in
most bubble sorts, but missing from here - and for a good reason too :)
The scenario:
sprtlst is a pointer to a MAXSPRITE + 1 byte area of RAM (There are 6
sprites) containing the sprite number (0 - 5). The routine initializes
the sprtlst with sprite #'s 0 - 5 because they are not guaranteed to be
in the list when the routine is called. vpos is a pointer to a
MAXSPRITE + 1 byte area of RAM containing the verticle position of the
sprite. The verticle position is guaranteed to be a positive number
(i.e. bit 7=0).
The stack is not used because I am using so much RAM in this kernel that
I can't afford to use it. The sprites should be sorted in descending
order by vpos. Oh, and you can use other temp variables as needed.
MAXSPRITE = $05
srtsprt
ldx #MAXSPRITE ;2
il0a ;necessary to initialize sorting routine
txa ;2
sta sprtlst,x ;4
dex ;2
bpl il0a ;2/3 = (11 * MAXSPRITE) + 10 = 76
stx tempvar2 ;3 = 81
nxtsrt ; = nxtsrt costs 16 cycles (plus srtloop,
but we'll figure that in)
ldx #MAXSPRITE-1 ;2
srtloop ; = srtloop costs 38 cycles
ldy sprtlst,x ;4
lda vpos,y ;4
ldy sprtlst+1,x ;4
cmp vpos,y ;4
bpl noswtch ;2/3
lda sprtlst,x ;4
sty sprtlst,x ;4
sta sprtlst+1,x ;4
noswtch
dex ;2
cpx tempvar2 ;3
bne srtloop ;2/3
inc tempvar2 ;5
lda tempvar2 ;3
cmp #MAXSPRITE-1 ;3
bne nxtsrt ;2/3
rts
nxtsrt executes max 6 times
srtloop executes max (n-1) + (n-2) + (n-3) + (n-4) + (n-5) times where n
= MAXSPRITE = 15 times
so if I calculated correctly, this will take (6 * 16) + (15 * 38) = 666
(aaaaack! an evil number) cycles.
As you can see, this is very expensive! Have at it, and thanks in
advance (TIA) :)
Bob
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/stella.html
