Monday, July 16, 2007


So the sprite cache is in, I thought I should tell you all how it works, for the record.

The sprite cache is used to maintain a least recently used list of all the entries so that we can reuse an entry that will have as little impact as possible, the whole point of the sprite cache is to minimise the work done when drawing a sprite.

The main data structure is a doubly linked list that is setup like a queue where we know the top item and the end item. So each time a sprite is rendered it is moved to the top of the queue, then when we need a sprite entry we use the end of the queue.

Now normally a doubly linked list needs to be updated in an operation like moving to the top of the list requires some coniditionals (for updating the head and tail of the list). So in C# (I like to prototype the ideas first and these days C# is the language of choice).

so in this snippet m_cachePrev and m_cacheNext are arrays of ints (pointing at the previous and next entries in the list, First is the first entry in the list and End is the last entry in the list.

public void MoveToTop( int _index )
// unhook previous entry
int prev = m_cachePrev[ _index ];
int next = m_cacheNext[_index];

if (next != End)
m_cachePrev[next] = prev;
Last = prev;

if (prev != End)
m_cacheNext[prev] = next;
First = next;

m_cachePrev[_index] = End;
m_cacheNext[_index] = First;
m_cachePrev[First] = _index;
First = _index;

Now on the 6502 because the flags are set on load then Mike can get some benefits and speed ups, so this type of code is fine for Mike, but on the Z80 the flags are not set when an entry is loaded but only after specific operations. So I have been looking for a method of doing this that minimised the branching to make the Z80 code a bit nicer, well my first area of attack was on the First and End entries and the checks that go in there.

So why do we use End as an indicator that this is the start or end of the list? Well just convention really (normally End would be set to NULL) but if End was set to an entry within the array then First and Last could be set to those entries. So I have set End to be the last index of the array and allocate an extra entry (so if we have 128 entries in the cache then the 129th entry becomes the First and Last entries)

First == m_cacheNext[ End ];
Last == m_cachePrev[ End ];

then we can lose the conditionals because the actions would be the same. So the code becomes in C#

// unhook previous entry
int prev = m_cachePrev[_index];
int next = m_cacheNext[_index];

m_cachePrev[next] = prev;
m_cacheNext[prev] = next;

m_cachePrev[_index] = End;
m_cacheNext[_index] = First;
m_cachePrev[First] = _index;
First = _index;

and then in Z80 this becomes

ld h,high sprite_cache_entry_prev
ld b,h
ld l,c
ld e,(hl) ; e = prev
ld (hl),SPRITE_CACHE_END ; m_cachePrev[_index] = SPRITE_CACHE_END
ld h,high sprite_cache_entry_next
ld d,h
ld c,(hl) ; c = next
ld a,e
ld (bc),a ; m_cachePrev[next] = prev
ld a,c
ld (de),a ; m_cacheNext[prev] = next
ld a,(de) ; a = First
ld (hl),a ; m_cacheNext[_index] = First
ld c,a
ld a,l
ld (bc),a ; m_cachePrev[First] = _index
ld (de),a ; First = _index

If you spot any optimisations then let me know.

Wednesday, July 11, 2007


Well the sprites have been in for some time now and I've taken the time to reorganise the code and tidy things up and do some tests.

I can get 10 masked sprites on screen and still have time to render bullets and even some map sprites (these are cheaper to do as they do not need to be masked, but they do need to be ORed), so I feel fairly comfortable with where I am and I could do a fairly faithful representation of the Plus4 version.

The main difference is that 10 - 16x16 sprites makes the screen fairly busy, as the Plus4 has a wider effective screen than the Spectrum, so I might revise that down for aesthetic (rather than technical reasons).

So the next thing to do, are the path code for the enemies and it will start to feel like a game.

Thursday, July 05, 2007

Now with added sprites!

I now have a simple sprite routine up and running as outlined below, it all seems to be working pretty well and the sprite cache is working too which is a double plus.

Currently it is not using masks or anything like that so it all looks very dull, but all the logic is in place now.

I have to tidy up a few things, and I'll post the sprite cache linked list code in the near future as I have managed to make it branchless which improves the readability of it and I believe performance on the Z80 (as the flags are not set on load for Z80, so I have to introduce an instruction to check for zero).

Anyway, progress is being made and I hope to have something with several sprites flying around over the next few days.

And then I'll work on getting the path code working so that we can have formations of enemies.

This page is powered by Blogger. Isn't yours?