Code Poetry
and Text Adventures

by catid posted (>30 days ago) 11:49am Mon. Mar 18th 2013 PDT
At Game Closure we often compress sprite sheets with PNG for deployment to cellphones.  This is pretty terrible for a number of reasons:

(1) PNG is OLD.

Really old.  And everything that goes with that.  There have been a ton of improvements in image compression since then.

(2) PNG isn't designed for sprite sheets.

So it cannot take advantage of common features of sprite sheets.

So let's come up with something new!  Image file formats are daunting to most people, but they're really not that complicated for someone who has studied information theory.  Especially the image formats that can be decoded really fast -- those formats tend to be very simple.

The tools that we can use since we care about speed are: static Huffman and LZ.

Decoder basis:
LZ: Same approach as LZ4. (This includes RLE)
Static Huffman: Same approach as LZHAM (CBloom's version too)

Start with modeling the files we want to compress: Sprite sheets.

Here's a sprite sheet:

Some things you can notice immediately: There's one dominant color that takes up the sheet (the background).  So the first step should be to reduce the image to pixels with this color and everything else.  Encode that one color as a monochrome compressed image, and then only store information about the remainder.

The other feature of this monochrome sub-image is that the dominant color tends to make up continuous spatially-correlated parts of the image.  It seems like a good way to encode this would be with RLE.

1. Mode, Number of pixels off, Number of pixels on, Number of pixels off, Number of pixels on...  for the first line.

To take more advantage of repetition, encode the difference in these numbers from the last number off or on.

Then for the second line, only record the delta from the previous line in the number of pixels off or on.

The resulting stream has statistics that can be encoded with a static Huffman code.  So long as there isn't a huge number of zeroes in the resulting data, Huffman will be near optimal.  Where many zeroes are encountered, RLE can be employed.

Furthermore, LZ would be applicable to this data since it should have a lot of repetition.  Fast LZ decoding is easy to write and there are lots of good examples out there.

There may be other ways to encode these better but I think this would be a good first attempt.

And this would give me a good groundwork to expand it up to supporting the RGB channels in the next phase of development.

Why is this exciting in the overall sense?  With the direction I'm going in, we should be able to compress images twice as well as PNG and decompress in a third of the time.  That means our game downloads will be down to half the size and load up to three times faster.  Seems like a good idea!
last edit by catid edited (>30 days ago) 12:32pm Mon. Mar 18th 2013 PDT