Simple Sprite Allocation

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:

init_sprites

ldx #maxspr-1   ; initialise loop counter + stack pointer.
stx *SPR_sp

.loop

txa
sta spr_stack,x
dex
bpl .loop
rts

Once the stack is initialised, to allocate a sprite, I use code like the following:

; returns X = virtual sprite index

sprite_alloc

ldy *SPR_sp
ldx spr_stack,y
dec *SPR_sp
rts

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

sprite_free

txa                        ; transfer index into A.
inc *SPR_sp         ; increment stack pointer.
ldx *SPR_sp
sta spr_stack,x    ; store sprite index onto top of stack.
rts

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!