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?
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.
Cool, that's exactly what I'll do. I'll let you guys know how it goes.
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.
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.
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?
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.
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).
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.
Quote:
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?
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.
Waste 16 bytes for each repeated tile?
Dwedit wrote:
Waste 16 bytes for each repeated tile?
Come again?
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.
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.
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.
That's an awesome idea! Storing the NT address directly in the data is pure genius. That'll make my decompression code much cleaner to boot.
You're totally right about the unused bit 5 allowing for additional fill modes. Offhand, I can't think of any other fill modes that would benefit me presently, but once I start adding other screens (cut scenes, menus, etc.) perhaps their layouts will open up some possibilities. For now, I think I'll save that bit for a rainy day.
It's really cool bouncing ideas back and forth with you guys. I can't say there are tons of folks programming NES games in my neighborhood, so it helps me feel less isolated.
I'm glad to hear my ideas are considered "pure genius" by someone!
Though I don't quite consider it that. It's a good idea though, I will admit.
I like talking about NESdev too, as I have like no one to talk to even about programming. I talk to my brother's friend who's a computer god about games and crap, though he doesn't program.
I have a small question regarding this compression algorithm. I'm still not yet to that part in my game but I will need to learn about it someday so why not asking here.
It seems to be used for single screen compression. How well would if fare to compress data for the name table/map data for a side scroller?
Banshaku wrote:
I have a small question regarding this compression algorithm. I'm still not yet to that part in my game but I will need to learn about it someday so why not asking here.
It seems to be used for single screen compression. How well would if fare to compress data for the name table/map data for a side scroller?
Personally, I only intend to use this compression scheme for single screens. As is, it's probably not ideal for use in the levels. It's hard to say at this point because I haven't designed a complete level yet.
For the levels, I'll probably group the tiles into 16x16-pixel or 32x32-pixel metatiles. Additionally, I may use a simple object definition for common entities such as platforms. In the latter case, instead of defining each tile (or group of tiles), I could just specify the position and dimensions of the platform.
Banshaku wrote:
How well would if fare to compress data for the name table/map data for a side scroller?
This kind of compression does not work well for level data, at least if applied directly to tile data. Most (if not all) NES games use a basic block (the metatile) size of more than 8x8. The use of metatiles by itself is already a compression scheme, and then you usually have others on top of this one. So you should first decide on the size of the basic blocks that make up your map (usually 16x16 pixels, 2x2 tiles) and how to encode them, then you decide what kind of compression to use on top of that.
Saving some RAM for the maps will probably help a lot, because you'll be able to buffer whatever the decompression algorithm outputs, and use that data for collision as well as for updating the nametables little by little.
Anyway, the best compression algorithm to apply on your metatiles will depend on the nature of your maps, what kind of redundancy they have. RLE will always save some space, since I can hardly think of a game that doesn't have wide areas of repeated blocks. An adaptive scheme like the one presented by SecretServiceDude could work well, because it has different types of compression, and at least one of them will be able to do something to a specific piece of data. It kinda reminds me of a
compression scheme used by Nintendo in SNES and Gameboy games. I don't know if any NES game used it.
At least SMB1 used a more primitive version of the (x, y, what's there) representation that Super Mario World maps use. And I'm pretty sure SMB3 does as well.
The one I linked to is not it. It's a mix of RLE, LZ, and some variations of those. There are 7 possible types of compression, and the compressor indicates the one that was used for a particular run using the top bits of the command byte, like SecretServiceDude was doing, but with less types of compression.
The decoder is finally working, and I successfully switched over to the compressed name table for my title screen display. I added a few bytes to the data in order to simplify the decompression code, so the total size of my name table comes out to 128 bytes: a programmer-friendly number if ever there was one.
So, what does 86.67% compression look like? Glad you asked:
I decomposed the title screen into 6 regions. I used layering, so some regions appear in two separate sections onscreen, even though there's only one region defined in the data.
Region #0 (Solid Fill Mode): The dark green background (covers the whole screen)
Region #1 (Solid Fill Mode): The two horizontal bars above and below the title
Region #2 (Solid Fill Mode): The light green background behind the title
Region #3 (String Fill Mode): The word
Bionic (lots of duplicate tiles)
Region #4 (Ascending Fill Mode): The word
Commander (no duplicate tiles)
Region #5 (String Fill Mode): The copyright notice
I'm no master artist, but I really dig that chrome effect.
Wow! That looks really cool. How many tiles does it use total out of 256? I don't know, the word "Commander" looks like it was a pain to make. I have a really hard time with fonts, especially slanted/distorted ones. I really like it. For 128 bytes, not bad at all. Good Job =)!
The screen looks great, definitely feels like commercial quality.
Celius wrote:
Wow! That looks really cool. How many tiles does it use total out of 256? I don't know, the word "Commander" looks like it was a pain to make. I have a really hard time with fonts, especially slanted/distorted ones. I really like it. For 128 bytes, not bad at all. Good Job =)!
smkd wrote:
The screen looks great, definitely feels like commercial quality.
Thanks for the compliments! I'm glad you guys like it.
So, here's the pattern table for the title screen:
So far I'm using 237 out of 256 tiles. The four red tiles are duplicates of tile[2]. Duplicating those tiles allowed me to describe the entire word "Commander" (30 x 6 tiles) as a single region with Ascending Fill Mode.
As you can see, the word "Bionic" exhibits decent economy of space; however, the word "Commander" screams wastefulness.
And that's exactly what I was going for.
To me, "bionic" connotes mechanical precision, whereas "commander" connotes unabashed bravado. I think the grossly imbalanced tile distribution captures that dichotomy nicely. You put those two ideas together, and you've got yourself a rad game!
That's an interesting interpretation of the title! I didn't really look that far, but it makes sense when you say it like that.
Yeah, I figured it used most of the tiles. It looks really cool. It might be cool if you added stuff in where the dark green background is, like a sky of some sort with a few clouds. Though this would increase the size of the compressed screen.
You inspired me to start making my own title screen. I'll post it up when I'm done with it. Maybe.
Celius wrote:
It might be cool if you added stuff in where the dark green background is, like a sky of some sort with a few clouds. Though this would increase the size of the compressed screen.
I'm actually thinking of adding some embellishments to the title screen using sprites. The title screen is looking good so far, but I want to
take it to eleven. I'll post my musings in a new thread.
Celius wrote:
You inspired me to start making my own title screen. I'll post it up when I'm done with it. Maybe.
Glad to hear it! Good luck my man.
I had been writing a bunch of engine code, which can get pretty dry after a while. I needed a reminder of
why I was making the game in the first place, so I decided to switch gears momentarily and focus on something artistic.
I must say, being greeted by a title screen when I fire up the ROM makes my game actually feel like a game now. A little bit of presentation goes a long way.
Haha! I love that in Spinal Tap. That whole movie is great.
Yeah, with my game in general, I hope to take it to eleven. My title screen won't really be THAT special, it'll probably just be the title with some lightning. In fact, if I upload a shot of it when I'm done, I'll do it as an animated GIF so you can see the whole effect.