I've been thinking about how to add efficient, fast compression of level data to Alex Kidd. Currently, the widest level possible (unpacked) due to memory constraints is 1280px wide (or, 160 characters, or 5 screens). The level in the current Alex Kidd demo fully exploits that space, and it is the smallest I have in my current designs. This takes slightly less than 4k of RAM (3840 bytes, to be exact).
So, I need to come up with a form of compression of the levels that has a number of characteristics:
- Compress the data enough so that total memory consumption for a map of 3072px wide (the largest map I currently have designed) is less than the 3840 bytes currently available (and actually, I probably need to shoot for something around 3kb 'cause I need some memory back for other things, such as longer music tracks).
- Is extremely fast to unpack to VDP: I need to copy three to six rows (96 - 192 bytes) of unpacked data to the VDP every frame, depending on how fast Alex is running (he runs fast enough to need two-pixel scroll increments at times). Add to that the 128 bytes for the sprite table that need to be uploaded every frame, as well as the game logic even with the uncompressed map I'm close to the edge of the the machine can do with the current C code.
- Allow for dynamic modifications to the map. This is probably the most annoying requirement, but since Alex can destroy parts of the world (rocks get replace by nothing, boxes replaced by money bags or special items, specials items and money bags by nothing) I need to be able to take those out for as long as that part is potentially on screen. Because of that, simple RLE is out of the question.
So I ruled out RLE. Besides that, the obvious one is to look at the way the levels are built up: every item on screen can be represented by a 16x16 meta-tile. Using the meta-tile approach, the map data itself of course compresses to 25% of it's original size, and the meta-tile dictionary will take up around 800 - 1024 bytes, depending on the complexity of the map. This puts the largest map at around 2k, so the compression result is excellent.
However, uploading this to the VDP turns out to be slower than expected. In iterating over the metatiles, I need to see whether I'm uploading odd or even rows, and starting from odd or even columns and that code slows things down enough to push me over the limit of what I still have available in the time for one frame (well, when Alex is running at least, when he moves slowly, I only need to do this for three rows and that still seems to work fine).
I can do a couple of things to remedy this (optimize the lookup code, unroll some loops, hand code it in assembly, ...), but I wanted to see of someone else can think of a super-duper way of compressing the data that is nearly free when it comes to turning it into something that I can upload to the VDP.