osx's compression

Member
Posts: 194
Joined: 2009.02
Post: #1
I'm working on getting down a tile/map storage scheme for my game and I managed to compress my entire 276 kb map into 4kb, I tried with larger sized map and it seems to scale right. This seems shocking to me since I'm use to getting quite poor results when using osx's compress on app bundles.

I'm using stdio functions, fwrite() to write out binary data.

Here's what my tile structure and map array look like

Code:
typedef struct
{    
    unsigned short palette_index : 13;
    
    unsigned short room_flag : 3;
    
    unsigned char location_flag : 2;
    unsigned char active : 1;
    unsigned char level_flag : 3;
    unsigned char building_flag : 2;
}tile_type;


g_tile_map[100][100][7];


And so my question is, why the enormous compression ratio? Is there something really inefficient about my store method that allows for it?

On a side note, the map array I'll be using in the end will be huge, not 276 kb.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
Well, at least 7 bits in 32 are unused (though not necessarily zero, you should take care to zero them if you want better compression). That's before we even consider that a tile map is likely to have lots and lots of identical tiles.

Try compressing plain text files for comparison. /usr/share/dict/words for example compresses to 30% its original size using gzip. That's not quite as good as you, which suggests you have even less variety than english.

Images don't compress well, since they're already stored compressed and therefore don't have much redundancy. Compressing app bundles is probably mostly an image recompression test, so not representative of anything useful.
Quote this message in a reply
Member
Posts: 194
Joined: 2009.02
Post: #3
OneSadCookie, thanks a lot that was a great explanation. So I gather from what you say that the compression routine/program keeps track of unique elements of data, and upon reading in new data checks it against the list, if there's no match then it appends the new element to the list of unique data elements- and each data element would actually be an index to the list, do I understand you correctly? If correct, this would explain the extreme compression ratio.

I'm not quite sure I understand you on the 7/32 thing. Do structs automatically allocate 32 bits or something?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #4
Compression works by exploiting redundancies in data. English text is very redundant -- there are only 2x26 letters, 10 digits, space, newline, and a handful of punctuation used in regular prose. That means that out of the 256 possibilities for each byte, only about 70 are actually used, and among the ones that are actually used, some (space, e, etc.) are hugely more frequent than others, so using fewer bits to encode those than say semicolon, or x, allows further shrinkage. You should read up about it if you're interested, perhaps starting here: http://en.wikipedia.org/wiki/Huffman_coding

About the size of your struct:

Code:
OneSadMBP:~ keith$ cat > test.c
typedef struct
{    
    unsigned short palette_index : 13;
    
    unsigned short room_flag : 3;
    
    unsigned char location_flag : 2;
    unsigned char active : 1;
    unsigned char level_flag : 3;
    unsigned char building_flag : 2;
}tile_type;
main(){__builtin_printf("%zu\n", sizeof(tile_type));}
OneSadMBP:~ keith$ gcc -arch i386 -arch ppc -arch x86_64 test.c
OneSadMBP:~ keith$ arch -i386 ./a.out
4
OneSadMBP:~ keith$ arch -ppc ./a.out
4
OneSadMBP:~ keith$ arch -x86_64 ./a.out
4

Your struct needs 25 bits, which means it can't be smaller than 4 bytes. If you got rid of a bit you might be able to get it to pack into 3 bytes, but "short" has two-byte alignment, so you'd have to force that off (which I've had no success doing!) or split the two-byte field into two.
Quote this message in a reply
Sage
Posts: 1,232
Joined: 2002.10
Post: #5
It's very informative to look at how tilemap compression was done on old NES games, like Metroid.

They use a hierarchy of data, for example:

* raw 8x8 tiles (2bpp, all graphics compress to <4k with dumb RLE)
* 2bit indices -> RGB CLUT (48 bytes)
* 8x8 -> 16x16 block table (256 bytes)
* tokenized chunks (blocks combined to form platforms, doors etc, ~512 bytes)
* rooms (lists of chunk ids + x,y to form entire rooms, ~1500 bytes)
* world (room ids, 1k)

This way all of the graphics and map data for the entire game squeezes into a handful of kilobytes. Modern tilescroller games will use bigger, higher bitdepth graphics, but the idea of tokenizing repetitive chunks of map data is still good.
Quote this message in a reply
Moderator
Posts: 3,577
Joined: 2003.06
Post: #6
arekkusu, this may sound a little weird, but could you google that for me? I take a stab at it about once per year in the off-chance that I might figure out a little more about NES compression scheme(s), but I get frustrated quickly whilst digging through piles of nonsensical forum babble and give up easily. It's an interesting subject (especially in relation to Metroid 1), but not one that I've ever been able to justify moving any higher on the list of priorities than maybe what an odd Sunday evening can produce. Do you have a killer link or two you could share which might detail this subject a little more?
Quote this message in a reply
Sage
Posts: 1,232
Joined: 2002.10
Post: #7
MetEdit can show you the tokenized blocks/chunks/rooms, which is a pretty illuminative view into how the level designers created the data.

To actually figure out the tokenization scheme you just need a hex editor and some patience Wink

The MetEdit author also posted his commented disassembly of the ROM.

Various other documents have been written detailing the internals of many classic games.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #8
arekkusu Wrote:It's very informative to look at how tilemap compression was done on old NES games, like Metroid.

They use a hierarchy of data, for example:

* raw 8x8 tiles (2bpp, all graphics compress to <4k with dumb RLE)
* 2bit indices -> RGB CLUT (48 bytes)
* 8x8 -> 16x16 block table (256 bytes)
* tokenized chunks (blocks combined to form platforms, doors etc, ~512 bytes)
* rooms (lists of chunk ids + x,y to form entire rooms, ~1500 bytes)
* world (room ids, 1k)

This way all of the graphics and map data for the entire game squeezes into a handful of kilobytes. Modern tilescroller games will use bigger, higher bitdepth graphics, but the idea of tokenizing repetitive chunks of map data is still good.

Actually, I'd like an explanation of some of that too.
1) How is it RLEd? Using 2bit symbols, your escape code uses 1/4 of the total symbols, and only gives marginal (8bits to 6bits) when using a repeat of 4. Seems like this would bloat the data in the average case.
2) 48bytes to store colors for a 4 entry CLUT?
3) What exactly is a block table? A 16x16 tile table of 256 possible 8x8 pixel blocks?

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Moderator
Posts: 3,577
Joined: 2003.06
Post: #9
Most excellent, thank you for those links arekkusu! Smile

I don't know why, but that source code link gives me a 404. I found it though. ... actually, it doesn't 404 now that it's in the browser's cache from the page that links to it. I don't get these interwebs sometimes...

I forgot about MetEdit. I was going to try it out but was too lazy to dig the Dell out of the closet at the time. Sneaky

That romhacking site is quite a treasure trove of information!
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #10
Ooh, awesome. I'll definitely spend some time examining this stuff... Thanks for the links!
Quote this message in a reply
Member
Posts: 194
Joined: 2009.02
Post: #11
Thanks a lot arekkusu for the links, fascinating stuff. Might I press you for a bit more detail on the metroid method.
Quote this message in a reply
Moderator
Posts: 373
Joined: 2006.08
Post: #12
These are awesome links; thanks arekkusu Grin

Worlds at War (Current Project) - http://www.awkward-games.com/forum/
Quote this message in a reply
Sage
Posts: 1,232
Joined: 2002.10
Post: #13
Skorche Wrote:Actually, I'd like an explanation of some of that too.

1) How is it RLEd?
I mis-remembered about the RLE. I was using plain old GIF to compress the tiles, so it was LZW, which handles short bit entries. But some console games do use RLE. Consider that you don't have to treat a single pixel as the smallest element-- you could compress based on 8 or 16 bits, and still catch runs of similar color across groups of pixels. For some special-case patterns (like checkerboards) this can actually produce tighter compression.

Quote:2) 48bytes to store colors for a 4 entry CLUT?
Palette data on the NES is convoluted. In my reconstruction, I kept a master palette, and a set of per-area indices into the master. Each area defined 12 palettes of 4 indices each.

Quote:3) What exactly is a block table?
It's a mapping from 8x8 tiles to 16x16 blocks.

I extracted and squished all of the non-sprite graphics into a single image containing 256 tiles:
[Image: metroid.gif]
Note that's not the original data; I took advantage of some horizontal/vertical symmetry and 90 degree rotation to remove redundant tile data. These tiles are re-assembled into larger 16x16 blocks using the block table (along with a couple flip/rotate bits.) The blocks are then indexed by higher level tokens to construct rooms etc. I also laid out the tiles spatially to allow inter-block filtering during i.e. 2xSAI upsampling-- another couple of bits control the per-block edge wrapping/clamping during filtering.

The specifics of this stuff isn't really interesting-- it's the idea of tokenizing data which I think is still relevant. Hierarchies of tokens improve compression.
Quote this message in a reply
Post Reply