Another day, another lesson. I’m skipping over collision detection for the time being, as I don’t think I see eye to eye with the general stance on NES collision detection. We’re going to go straight into data compression, yay! Stick with me though, it’s not as boring as it sounds.
As I’ve said before, NES games typically use a form of meta-tiles. What this does is allow you to paint a large group of tiles with a single byte. This is already a form of data compression, but we can do better.
Code:
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3
data 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3
data 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2
data 6, 6, 3, 5, 4, 6, 6, 4, 5, 3, 3, 3, 3, 5, 6, 2
data 5, 5, 3, 3, 4, 3, 5, 4, 3, 3, 3, 3, 3, 5, 5, 2
data 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 2
to produce this picture:
Now that’s all well and good, it produces a pretty picture and the data is easily read by a human, but there’s a lot of wasted space in that big chunk of data. We can use some simple compression to knock it down.
There are a lot of ways we can do this, we’re going to focus on two of the simplest called Run Level Encoding (RLE). One way we’ll call a hybrid compression, it would allow for both compressed and uncompressed data within the same block. The other way assumes all of the data is compressed. There are benefits to both methods, depending on how complicated your background designs turn out to be. If you have a fairly simple background with lots of repetition, compressing all of the data is the way to go. If your backgrounds are complicated and use a lot of different meta-tiles without much repetition, you may be better off with the hybrid approach.
We’ll start with the hybrid compression. Both systems are very simple, the only difference is that the hybrid compression uses a flag in the data to signal when the game should draw repeating tiles. So let’s say the flag to trigger compression is 99. If you look at the data above, we want to draw the “0″ meta-tile 14 times in the first line. So we’d set the flag for compression, 99, then set the tile we want to draw, 0, then the number of times we want to draw it, 14. We’ve just reduced 14 bytes of information down to 3. After that, the rest of the line doesn’t have any repeating tiles, so we don’t set the compression flag.
So using the hybrid compression, the first line of data for our background looks like this:
99, 0, 14, 1, 2
We just knocked 16 bytes of data down to 5. But can we do better? Maybe, it depends on the data we’re trying to compress. And that’s where assuming all of the data is compressed comes into play.
So instead of using a flag to tell the drawing function which data should be repeated, let’s assume all of the data is formatted that way. So for our first line we have tile 0, repeated 14 times. Then we have tile 1, 1 time, then tile 2, 1 time.
So if we were to draw that out, our first line would look like this:
0, 14, 1, 1, 2, 1
This knocks our 16 bytes of background data down to 6 bytes. You can see even though we took out the control byte to flag compression, the end result is slightly larger. Which system works best depends on the data being compressed. You would probably have to try each one and see which produces a smaller chunk of data. Generally speaking, the more complicated the design, the better the hybrid method would work.
The lesson of the day? Using a combination of compression and meta-tiles, we can designate 32 background tiles in as little as 2 bytes. For our example above, we knocked 32 tiles into 5 bytes. We could actually go farther with the compression if we need/wanted to, but generally this is pretty sufficient. You’ll quickly start getting into algorithms that take too much CPU time, or too much rom code. This is a pretty happy trade off between code, storage, and CPU time.
