Success compressing tiles?

[tokumaru]

I know I have started a topic about this before, but nothing good came out of it... =)

I'd like to ask you guys if anyone had any luck trying to compress pattern table data so that you can store it in CHR-RAM carts using less space?

I just tried out my latest idea for this, something based on quadtrees. I encode each bit plane separately, because they seem to have much more flat areas than when combined to make the 2bpp tile.

The pixels in a each tile are checked, and if they are all equal a flag indicating this is output, and the color comes next. So, a tile that uses only one color will be encoded in only 4 bits, 2 for each plane. But that rarely happens, of course.

If any of the pixels is different, a flag is output to indicate this, and the tile is divided into 4 4x4-pixel blocks, and each of them is processed the same way. These blocks will be divided into 2x2-pixel blocks if needed, and those will either share the same color or all 4 pixels are output.

The worst case would be when all squares need to be divided into smaller squares, because all the pixels will be there, and so will the flags that indicate that the blocks should be divided. In that case, the tile would be encoded in 149 bits, instead of the usual 128. Quite a bit of expansion there.

I was not so happy with the results. SMB's tileset was compressed to 71% of it's size. 8KB of some Mega Man tiles compressed about the same, 72%. So I guess the results do not get any better than this.

A really good compression ratio would be about 50% I guess... But is that a realistic goal for lossless compression of NES graphics? When I ZIP the SMB tileset I get a file about 1KB smaller than my own compression. When I ZIP my compressed file, nothing seems to happen, so that results in a bigger file than compressing the original data.

Just for fun, I also tested the algorithm on other types of data, such as JPEG images and NES code. All those tests resulted in some expansion of the original files.

Anyway, this method was my best idea so far, but I'm not really pleased with the results. Does anyone have any ideas on how to improve compression of tiles?

EDIT: Just to give you an idea of what my algorithm did, it turned this:



into this:



The compressed data was successfully decompressed back into the original data, the only problem is the sub-optimal compression ratio.

[Memblers]

I was gonna use LZ77, with Mickael Pointier's FilePack, but I had some kind of bug in the decompression that corrupted the gfx a bit. Was kinda weird modifying it to do all the reading through $2007, heh. But I've stuck with RLE for going direct to VRAM, it's quick and easy.

From my Garage Cart project for example:
Solar Wars CHR
32,768 bytes originally (unused ones removed, many blank tiles)
15,248 bytes with RLE
13,191 bytes with LZ77

992 bytes squid.chr
736 bytes squid.rle
484 bytes squid.lz7

Looking at CHR data in an hex editor, it always seems like there'd be some really good way of compressing it. But it really depends on the tiles.

[tokumaru]

Was kinda weird modifying it to do all the reading through $2007, heh.

Did you actually set the PPU address twice for each byte copied (once for reading it and once for writing it)? That is crazy!

But I've stuck with RLE for going direct to VRAM, it's quick and easy.

Yeah, good, old, easy RLE. I'd never think it would work well with CHR data.

15,248 bytes with RLE

This is impressive, but then again, there were the unused and blank ones you talked about.

736 bytes squid.rle
484 bytes squid.lz7

The difference is quite big here. But is the difference worth the trouble of implementing more complex compression schemes? I don't know.

Looking at CHR data in an hex editor, it always seems like there'd be some really good way of compressing it.

This is true.

I don't think LZ77 is a good option for the NES, mainly because of that linear nature of the PPU. On the other hand, if you are dealing with compression, time is hardly and issue, so it'd be OK to set the PPU address a million times.

My decompression scheme needs a 16-byte buffer, to decompress one plane of the tiles at a time. But it's kinda complex when compared to RLE, and maybe the difference in size does not pay off.

Maybe I should try my compression against RLE, and see how that goes. but there has to be another option... I'll keep thinking about it.

[Bregalad]

I think the results are pretty good. 70% ratio isn't awesome, but in some case it'll still be significant.
Compression may be worth it or not depending on how far you're from getting your overall size of a power of 2. Let's say, you may use compression if you're game is going to just fit a 128kb PRG ROM and you don't want it to be 256kb. Or if your game is so big you are just going to do anything to have it fit a 256kb EPROM and not need a cartridge with 512kb, often meaning a bigger mapper (MMC1 and UxROM isn't possible any longer, only SUROM, TGROM, etc... could do this).

If on the other side, your game is something like 196kb in size and you know you'll never stripe it down to 128kb, but you ask yourself what data you'd have to fit to make a total of 256kb while wasting the less space for just being blank, don't bother using compression.

[tokumaru]

I just want to fit more graphics in my 256KB cart. Tiles used during the levels will not be compressed, because those can be modified during the course of the level, so they must be copied quickly (and always using the same ammount of time). There will be 64KB dedicated to those tiles.

But a chunk of 32KB will hold compressed graphics, to be used in the title screen, cutscenes, and so on, and those will be compressed. Since these are typically bigger images, I'm not sure if I should use a totally different (maybe even lossy) compression scheme that worked on larger blocks than a tile. Maybe including palette information and all that, like a standalone graphics file format.

With graphics only using 96KB of the space, there will be a lot of room for all the level maps and code. My level maps take another 96KB of the ROM. The rest is for code and any extra data it needs.

EDIT: You know what? Now that I think of it, the compression ratio I achieved is very good, considering that the algorithm only works with individual planes of tiles, not making use of global redundancy of data. Tiles do not use data from other tiles for their compression. So, the fact that, in average, each tile was reduced to 71% of it's size, with no use of external data, is impressive.

So, if there is a way to combine this method with some way of using global redundancy, the compression ratio might grow significantly. Maybe some sort of delta coding of adjacent tiles (and planes), so that the difference between similar tiles results in a tile full of flat areas, that compress better. Maybe before encoding each tile, I could look for a similar tile already encoded/decoded, then point to that tile and encode the difference. I'll think about it today.

[Dwedit]

Anyone tried Huffman yet?

[tokumaru]

I, personally, am trying to avoid anything that uses a significant ammount of RAM, as that is very scarce on the NES, and reserving a relatively large chunk of it to the decompression routine may be a big disadvantage to the main engine of most complex games. Plus, I don't think huffman alone will do very well either.

[Matrixz]

I coded a compressor that gets me around 80% ratio.. the decompression routines only use 32 bytes of RAM to work each tile, though. It also allows seeking for a certain tile to start decompression from. It uses no official methods, i can provide the binary, source code, asm, if anyone is interested. (I'd hate to waste my time if not.)

[CKY-2K/Clay Man]

I know this isn't NES related, but does anyone know how to uncompress wario land 2?

[tokumaru]

I coded a compressor that gets me around 80% ratio..

I always get confused when talking about compression ratios and percentages... when you say "80%" do you mean that the encoded data is 80% the size of the original? Or that the compression ratio is 80%, meaning that the encoded file is 20% of the original?

the decompression routines only use 32 bytes of RAM to work each tile, though.

Mine is like that too, but I currently only use 16 bytes, since I work with each plane of the tile at a time. If I do implement the delta coding, I'll probably use 32 bytes of RAM too.

It also allows seeking for a certain tile to start decompression from.

This can't be done with my compressed data, as it's all bit-oriented, and the idea was to have "packages" of tiles, with a byte indicating the number of tiles in the stream, followed by the stream of compressed tiles. One would have to know the address of each package to decompress all tiles in it.

It uses no official methods, i can provide the binary, source code, asm, if anyone is interested. (I'd hate to waste my time if not.)

I think that a brief description of your method would be more interesting now. I'd like to know what kind of technique has the characteristics you described above.

[Matrixz]

I always get confused when talking about compression ratios and percentages... when you say "80%" do you mean that the encoded data is 80% the size of the original? Or that the compression ratio is 80%, meaning that the encoded file is 20% of the original?

Its 80% the size of the original.

I think that a brief description of your method would be more interesting now. I'd like to know what kind of technique has the characteristics you described above.

First, it works byte-by-byte on the tile data instead of pixel-wise.

Also, the compressed data is jumbled together as values with different bit-lengths.

I'll use an example tile:
FF FF FF 1F 00 00 00 00 1F 1F 1F 1F 00 00 00 00

Basically, each tile is divided into 3 components. Before all that, a 5-bit value tells how many bytes the compressed tile uses.

First, there's an area telling which bytes of the tile has 00's or FF's (those are kind of common). A 1-bit value at the start tells if this data is used at all.

I'll make up a loop thing to explain.
the cursor is at the first tile byte.
loop start:
* A 4-bit value tells how many bytes from the cursor to skip before start outputting a series of 00 or FF. This value is added to the cursor.
* Next, a 4-bit value tells how many bytes makes the 00/FF serie.
* Next, a 1-bit value tells if the serie is of 00's or FF's.
* Set bytes in the tile memory to 00/FF, starting from the cursor.
* The size of the 00/FF serie is added to the cursor.
* then loop back to start. the loop is broken when the cursor is past the tile's 16 bytes.

Also, the decompression routine registers which bytes have been set to any value.

The 2nd area is the common area. A bit tells if the common area is used. If so, a 8-bit value tells the common byte (for the example this would be 1F, it makes up all the bytes expect the 00's and FF's).

This component works similar to the 00/FF area, it switches between skipping bytes, leaving them for the moment, and setting an array of bytes to the common byte, using 4-bit values to tell the distances.

The last area is the fill area. Any byte which haven't been set by
the two previous steps, is put here. The whole array is now filled.

I didn't feel i succeeded to make complete sense.. :/

Anyway, writing this gave me some new ideas.

[Bregalad]

Yes, tokumaru, I think you pick mostly the right decisions for coding your graphics. Having a part not compressed and a part compressed is a good idea.
And I really think you should not use any lossy compression, because of the low resolution of the NES. That makes few sense. Your compression sheme seems pretty good (but I'm no expert), and this will allow you to fit 1.4 times the graphics you would fit uncompressed, wich is quite nice, especially considering the very low cost in RAM. Using your delta thing may be even better, so I really think you've mastered the task here.

[Zepper]

Umm... firstly, you should try "overlayed tiles". You know, each tile supports 4 colors. Technically, it's possible to overlay 3 letters, as example, using different "colors", since your font seems to be monochrome. Anyway, if mind doesn't fail, I saw this in a demo made by tepples...

[tokumaru]

Having a part not compressed and a part compressed is a good idea.

Yeah, whatever can be dynamically loaded during game play is not compressed, because those tiles have to be copied fast. I have given uncompressed tiles twice the space I reserved for compressed graphics, so it'd be nice to compress them really well, so that the difference in the number of tiles (when compared to the uncompressed ones) is not very big.

And I really think you should not use any lossy compression, because of the low resolution of the NES. That makes few sense.

Yeah, I guess you are right. Even a few pixels out of place can look weird...

Your compression sheme seems pretty good (but I'm no expert)

I'd say that 30% of compression when working only with each individual bit plane indicates good compression. Can't wait to see the results of when I try the delta coding!

About the RAM, this will always use 8 bytes of it for the buffer, even after I implement the delta coding. Those 16 bytes plus the few variables (have to implement the decoding in 6502 asm to see how many bytes they'll use) is all the memory it'll use. Anyway, the variables will probably use more memory than the buffer!

Umm... firstly, you should try "overlayed tiles". You know, each tile supports 4 colors. Technically, it's possible to overlay 3 letters, as example, using different "colors"

I don't see how it'd be possible to have 3 different bitmaps with only 2 bit planes. After you draw something with color 1 (plane 0) and something with color 2 (plane 1), what you'll see using color 3 is the intersection of those two, and you can't really manipulate that without screwing the other bitmaps.

Are you talking about that that technique of using the tiles to hold 2 1-bit bitmaps so that when you display them using different palettes you see one pattern or the other? That's not really useful for compression, as this can only represent monochrome graphics, and you have to waste a full palette to display only 2 colors.

With my compression scheme, if an empty plane is found (as happens with all the letters in that tile set), it's coded using only 2 bits, so I really see no reason to encode them in any different way.

since your font seems to be monochrome.

Not really my font, those are the tiles from Super Mario Bros. I used just for testing. =)

[tokumaru]

UPDATE:

I implemented the delta-coding thing, and the Super Mario Bros. tile set now compresses to about 64.5% of it's original size. I think I was expecting more. I guess it's still a good improvement. I don't know if I could improve it even more. I think this is still a respectful ammount of compression.

Good thing is that decompression is just a little bit more complex than before, an aditional step is required to XOR the similar (already decoded) tile to the decompressed data, but that's not complicated at all.

Compression got a lot more complex (and slow), but that's not an issue since the only goal here is to have the data ready, so that a fast decompressor in the game can use it.