Compressing Bouncy Ball levels

The levels in Bouncy Ball are not all that complicated to store in memory. But they are taking up a bit of memory, which is a bit of a concern if we don’t want to have to resort to reading the levels from disk. With some simple compression, I have been able to shrink a level from 5880 bytes to 870 bytes. That’s a 6:1 ratio, or over 6 times smaller!

I wrote a small utility in Java to read the uncompressed level text file, compresses it, then saves it to a header file that is ready to #include in the bouncy program. Pretty sweet!

The compression routine is very simple. It reads a byte from the uncompressed source, then counts how many times that byte is repeated. Then it writes the byte that we read, and then writes another byte for the count. So we could compress up to 255 bytes into 2. Realistically though, that isn’t what we find in the level data.

Here is the compression routine, in Java:

protected void compressNumbers()
{
    int key;
    int count;
    for(int i=0; i<numbers.size(); i++)
    {
        key = numbers.get(i);
        count = countSequence(i,key);
        compressedNumbers.add(key);
        compressedNumbers.add(count);
        i += count-1; //move past the sequence we just processed.
    }
}

And the supporting method for counting how big of a sequence there is of a particular byte:

protected int countSequence(int index,int key)
{
    int count=0;
    for(int i=index; i<numbers.size(); i++)
    {
        if(numbers.get(i) == key)
            count++;
        else
            break;  //no more of this sequence
    }
    return count;
}

Finally, the uncompress routine in C that Bouncy Ball uses:

void uncompress(byte* dest,byte* src,word srcSize)
{
    word uncompressedSize = 0;
    for(word i=0; i<srcSize; i+=2)
    {
        byte key = *(src++);
        byte count = *(src++);
        for(byte j=0; j<count; j++)
        {
            *(dest++) = key;
            uncompressedSize++;
        }
    }
}

This is what the sequence might look like:

stream1

Hold on there! The original and compressed version are the same size. That actually shows an issue that you could run into if the data you are compressing consists of runs of only 1 byte. Since it takes a minimum of 2 bytes to store a sequence, 1 byte would expand to 2 bytes. However, a 2 byte sequence breaks even, and we start saving at 3 bytes. If you look at the first 3 0’s 000 you can see it was compressed to 03. The 2 was expanded from 2 to 21. The next 2 0’s 00 broke even at 02. So you get the idea.

Just for fun I tried compressing the level using zip, and it deflated it down to 521 bytes.

So on average, for the type of data I’m compressing, I seem to get a 6:1 savings. I think with such a simple compression system, we are in pretty good shape.