Recently, while working on Soul Force, I’ve optimised the sprite allocate / free system, so thought I’d post about it, just in case someone found it interesting…
My old system used a bit array, allocating a bit per sprite. Since my sprite multiplexer uses a maximum of 24 sprites, 3 bytes was enough to store the allocate flags. I won’t detail the system as it’s now gone for good and is embarrassingly over complicated compared to my new code…
The new system uses a sprite index stack, along with a stack pointer. The stack is nothing fancy, just a linear array of bytes. To set it up I use code like the following:
ldx #maxspr-1 ; initialise loop counter + stack pointer.
Once the stack is initialised, to allocate a sprite, I use code like the following:
; returns X = virtual sprite index
Basically, this code grabs an index from the top of the stack and stores it in the X register before decrementing the stack pointer. My actual code does more, but I’ve left it out for clarity.
I do use a bit of error checking on the sprite allocation, but it’s no more than checking the sprite stack pointer and branching to an error routine if it is negative as this indicates the system has run out of sprites. An alternative is to return -1 in X and let the game code handle allocation failures. Currently I’m not doing that for the sake of code simplicity.
To free a sprite, all that is needed is the following code:
; X = virtual sprite index to free
txa ; transfer index into A.
inc *SPR_sp ; increment stack pointer.
sta spr_stack,x ; store sprite index onto top of stack.
This simply increments the stack pointer before storing the index to be freed at the top of the sprite stack. Again, my actual code does a little bit more, but not much.
I should add that some allocation systems use two lists: a free list, and a used list. The way my sprite system works, I don’t need a used list, so that simplifies the code.
And that’s it! Simple, but it works!