Now that I have baddies moving around, it was time to start trying to get the sprites over. The first task, is getting them into ZXNext format, from the C64 format. A C64 sprite is pretty simple at 24×21 in a simple row order byte stream. So why is it only 21 high and not 24? Because that fits really nicely into 64 bytes, and makes sprite addressing for the hardware really simple.
So I read in the sprite file to my C# converter, and decode the 2bit colours and transform them into the nibble format the ZXNext uses. I keep that values at 0-3 rather than making them the C64 colours, so that I can then emulate the C64 sprite colour – but more on that later. For now, I setup a grey colour palette and build up 4x16x16 sprites, taking 128 bytes in total. I do waste a lot of space here because my sprites are obviously 32×32, but it’s all we have to work with so…
I uploaded the first 128 sprites and tried to display them, which showed various conversion bugs, and when I (eventually!) fixed them, I was ready to put in the sprite cache.
So… what exactly is this sprite cache? Well, is a system I came up with on the Plus/4 for my shooter XeO3, where I’d cache rotated sprites, saving me from having to keep rotating a sprite over and over again. The idea is pretty simple, I’ll keep a list, and keep the “most used” in the list, letting those not in use “drop off” and that space to be reused for new items.
I do this by creating a structure with a doubly linked list through it. So what’s a linked list?
A 1D linked list is pretty simple. A structure, with a pointer to the next one. That pointer could be an index or an address or a handle – whatever. Basically, a blob of data and a pointer. And that’s all that a linked list is.
A 2D linked list, is similar, but with links both way
Simply put, what this means, is each structure has both a forward and backwards link. Now why would you have this, well it means you can loop both ways, but it also means, you can remove an item without having to loop through the whole list to find it’s previous link, making it much faster.
Now what on earth does this have to do with our cache? Well, this is fundamentally it. I have 32 structs in a doubly linked list. The “most” used is at the front of the list, and the least, and the end. When I need to upload a new sprite, I grab the one off the end, set it to the new sprite, and stick it onto the front – as it’s just been used. The only other trick, is whenever a sprite is requested, if it’s already IN the cache, remove it from whatever slot it’s in, and stick it onto the front again.
This continual moving a used sprite to the top of the list, works really well as a “most used”, and unused items naturally fall to the end, and get reallocated. If they get used, then they’re thrown to the front of the list again.
Now technically, this isn’t perfect, as if you have 10 sprites, and 8 use A, 1 uses B and 1 uses C… then A should always be at the front. But if all the A sprites come first, then B and C will push it down until the next frame. But that would take multiple passes over the list, and be a lot slower, and as long as the pool is larger than the sprites we need each frame, it actually works out pretty well.
So as a simple example, here we see item “4” has been used again, so it’s moved to the top of the list, meaning it’ll take all the other 4 items to be used before it falls out the cache and is reallocated to something else. This is basically it. It’s very simple – which is exactly what 8 bit machines need.
I also wrote an interrupt driven DMA process, allowing the sprites to be setup in the main loop, and then have the interrupts push the shapes up to sprite shape memory. This helps sync up the visuals and stops graphics changing mid frame. I had to do this on the SNES for Lemmings, so this was a much simpler version, but works just the same.
So what did this do for the game?
Here we can see it allocate the different sprites, and upload them on demand – without animations. This does mean nothing is falling out the cache as there aren’t that many baddie “types”, but it is testing the initial allocation and IRQ driven upload process. So, all good yes? Well… not quite.
In the next instalment, I’ll tackle sprite animations, bugs, and colours