Title screen name table compression

SecretServiceDude · Post by **SecretServiceDude** » Fri Oct 24, 2008 3:02 pm

Right now the name table for my game's title screen is uncompressed (960 bytes), and I'm looking for a good algorithm to reduce its size.

The title is drawn at a perspective, kind of like the Mega Man games. I mention this to give you guys a sense of how much tile repetition occurs (not a whole lot).

The title screen differs from the main game in that it isn't really suitable for partitioning into metatiles; however, it does have some characteristics that I hope to exploit:

1) Many of the tiles consist of nothing but the background color (tile #0 in my pattern tables). If I start my name table initialization by filling it with zeroes, then my title screen data would only need to specify the tiles with a nonzero tile index.

2) For the remaining tiles, there are long stretches where successive tile indices increase by one. I could use RLE compression for each of those stretches.

What do you guys think? Any ideas?

Dwedit · Post by **Dwedit** » Fri Oct 24, 2008 6:31 pm

Encode it such that you just read alternating bytes, one byte holds the number of zeroes, then the next byte stores the number of increasing tiles, keep going back and forth between the two modes. Maybe also an escape to specify N literals.

SecretServiceDude · Post by **SecretServiceDude** » Fri Oct 24, 2008 6:42 pm

Cool, that's exactly what I'll do. I'll let you guys know how it goes.

SecretServiceDude · Post by **SecretServiceDude** » Sat Oct 25, 2008 4:00 am

Okay, here's what I've got so far:

There are 4 encoding modes, which are determined by bits 7-6. They are described below.

Immediate Mode: %00xxxxxx; x = tile index
This mode is used for sequences of tiles whose indices are random but lie in the range [0, 63]. This allows storage of multiple literal values while eliminating the extra byte used by N Literal Mode.

N Literal Mode: %01nnnnnn; n = loop count - 1
This mode is similar to Immediate Mode, except an additional byte is used to specify how many tile indices follow. Also, the tile indices can be anywhere in the range [0, 255].

RLE Mode: %10nnnnnn xxxxxxxx; n = loop count - 1, x = tile index
This mode is used for sequences of tiles whose indices are identical.

Ascend Mode: %11nnnnnn xxxxxxxx; n = loop count - 1, x = 1st tile index
This mode is similar to RLE Mode, but is used for sequences of tiles whose indices increase by 1.

Using this method, I've reduced the title screen name table data from 960 bytes to 160 bytes, which comes out to 83.33% compression! It might be possible to reduce the data size even further, but probably not without increasing code size, so it would appear I've reached the point of diminishing returns.

Should I call it good?

@Dwedit: Thanks for your suggestions. They helped quite a bit.

Post by **tepples** » Sat Oct 25, 2008 4:55 am

Good job. You might eventually want to explore the more complicated things if you're planning to add more static screens, such as menu screens or instruction screens, because you can amortize the code size across them.

Roth · Post by **Roth** » Sat Oct 25, 2008 6:48 am

Man, that is some hella compression for a nametable! Awesome work! I don't quite understand all of the details of what you posted, but I'm sure in time I will get it. How many static screens do you plan to use this on, and how many bytes does the total decoding routine take?

Celius · Post by **Celius** » Sat Oct 25, 2008 11:32 am

Very good job! This is a great compression scheme. 160 bytes is really great compared to 960, especially for a title screen. The only thing that I wouldn't like is only being able to use 64 immediate tiles.

You know what you might benefit from? Compressing the title screen into blocks, or objects. Say you have a rectangular box that holds the title. Use your compression scheme, but specify the dimensions of the box that holds the title, and have your engine store that onto the screen by itself. That way, you could layer things all over the screen to save bytes. Like how your title screen is mostly tile #0. You could define a 32x30 block of tile #0, and store that in one chunk, which would be 8 bytes by itself (Though 10, 2 bytes for defining that it's 32x30 tiles). On top of that you could store the box with the title and other things, and I'm pretty sure save yourself some bytage. Things compress better if they're in separate chunks sometimes.

EDIT: Okay, it'd actually be 4 bytes for each object definition. 2 define the dimensions, and 2 define the placement on screen. So this would really only help if you had lots of layering going on. But it would help save bytes for rows of tile #0.

Bregalad · Post by **Bregalad** » Sat Oct 25, 2008 11:58 am

I decided to code the title screen for my game using a bit-based format.
A '1' bit means that the tile index is incremented by one, a '0' bit means that a blank tile should be drawn instead.
I did that over 3 year ago, so I didn't know as much as I do today. But yeah, your format seems kind of supperior to mine. For long runs, I'd still have a lot of $ff or $00 in my data, while yours just can be handled in one byte. And your format allows to re-use tile or place them in any order, mine doesn't it's either increment or blank (I don't use that format for the text present arround the title of course).

Post by **tepples** » Sat Oct 25, 2008 2:38 pm

Celius wrote:Very good job! This is a great compression scheme. 160 bytes is really great compared to 960, especially for a title screen. The only thing that I wouldn't like is only being able to use 64 immediate tiles.

You can use as many immediate tiles as you want. It's just that a literal string including only the first 64 has a slightly more compact representation than a literal string including other tiles. If a layout has a lot of short literal strings between runs, that could add up.

You know what you might benefit from? Compressing the title screen into blocks, or objects. Say you have a rectangular box that holds the title. Use your compression scheme, but specify the dimensions of the box that holds the title, and have your engine store that onto the screen by itself.

But how much would such a "window" system save over encoding the span of tile #0 from the end of each row of the box to the start of the next row, unless perhaps you want to add windows to an existing title screen?

SecretServiceDude · Post by **SecretServiceDude** » Sat Oct 25, 2008 7:18 pm

Thanks for all the helpful insights, everyone! I've now got the name table data down to 124 bytes, a whopping 87.08% compression!

@Roth: We should trademark that. It's all about Hella Compression™.

@Celius: Your idea of decomposing the title screen into rectangular regions worked beautifully!

@tepples: Thanks for the reminder about amortizing the code size across multiple static screens. You gave me the courage to revise my compression scheme even if it increases code complexity somewhat.

So, here's the scheme as it currently stands:

First, the title screen is decomposed into rectangular regions. Each region is chosen such that it yields the smallest possible representation. Also, the regions are allowed to overlap. If overlap occurs, the new region will overwrite the old one.

Each region contains a 4-byte header followed by region data. The header specifies position, width, height and fill mode. The header format is as follows:

Region Header: %ff-xxxxx ---yyyyy ---wwwww ---hhhhh

f = fill mode (described below)
x = x-position of the upper left corner in tiles; range = [0, 31]
y = y-position of the upper left corner in tiles; range = [0, 29]
w = width in tiles - 1; range = [0, 31]
h = height in tiles - 1; range = [0, 29]
- = unused

String Fill Mode: f = %01; data size = varies
The region is filled with a string of (random) tile indices. The region data consists of a variable-length string of literals. Additionally, the string is compressed according to the scheme outlined in my previous post.

Solid Fill Mode: f = %10; data size = 1
The region is filled with a single tile index. The region data consists of a single byte (the tile index).

Ascending Fill Mode: f = %11; data size = 1
The region is filled with tile indices that increase by one. The region data consists of a single byte (the starting tile index).

In order to get maximum benefit from the Ascending Fill Mode, I actually duplicated a few tiles in the CHR-ROM, which allowed me to construct a sequence of strictly increasing tile indices across a large rectangular region (30 tiles x 6 tiles). Representing those 180 tiles with 5 bytes really floats my boat.

Dwedit · Post by **Dwedit** » Sat Oct 25, 2008 8:30 pm

Waste 16 bytes for each repeated tile?

SecretServiceDude · Post by **SecretServiceDude** » Sat Oct 25, 2008 8:49 pm

Dwedit wrote:Waste 16 bytes for each repeated tile?

Come again?

Dwedit · Post by **Dwedit** » Sat Oct 25, 2008 8:57 pm

I just meant, Is it worth wasting 16 bytes to repeat a tile instead of encoding the nametable differently?
Unless of course your tiles are decompressed to CHR-RAM and are LZ compressed first.

SecretServiceDude · Post by **SecretServiceDude** » Sat Oct 25, 2008 9:08 pm

Oh, I see what you mean. Thanks for clarifying.

At present, I'm using a fixed size CHR-ROM for background tiles (4KB). I had some unused tiles in there, so the duplicates aren't costing me anything.

Truth is, I'm still fairly new to NES programming, so I went with the most expedient setup that allowed me to get started. I haven't begun to mess with mappers, CHR-RAM, bank switching, etc.

I'll have to cross those bridges when I get to them.

Celius · Post by **Celius** » Sat Oct 25, 2008 9:55 pm

Hey, glad the idea worked! I plan to do something involving the chunking method for my title screen (though I might actually load a lot of it with plain code and little data). Looks like you've got quite the compression scheme.

I see in your first byte that you could actually have 7 different fill modes if you used bit 5. Do you plan on using this for anything?

Also, you know, to save time, since you're already using 2 bytes to define X and Y, you could just put the PPU address in there instead of X/Y coords. Well, only 12 bits of it are unique, as the high 4 bits are always 0010 for the NT address. So instead of:

%ff-xxxxx ---yyyyy

you could have:

%ff--hhhh llllllll

where h represents the 4 real MSB of the name table ID and l is the LSB. So for example, you want a tile on name table #0 to start at tile 2,4, you'd normally define it like so:

%ff-00010 ---00100

Where you could define it as:

%ff--0000 10000010

where 000010000010 is $082, which is the low 12 bits of the NT address $2082. And if you do it this way, you could actually store stuff on any name table, if you wanted to do some scrolling.