Original post on facebook: LINK
Please geek out with me for a second. I'm not the first to use Steganography to encode game data in easily shared images. I believe that title belongs to the Spore folks. Doesn't make the concept any less cool.
What is Steganography?
It's a message hidden in another message. In Monaco's case, all of the data that describes a level is hidden in the side-view image of the level itself. What's cool about this? Well, when people make their own levels in Monaco and they want to share them, they can just pass around this image file. I can also host an online repository with user-created levels and you will be able to browse through the levels by looking at the level images. You can get a sense for how big the level is, what time of day it is, whether it is well-crafted or not just by looking at this preview.
And the I use the level data to generate a side view of the level:
And each level has a unique foreground image:
So on the level select screen, I can composite these elements, along with a few other doodads, and then apply a bloom filter to get:
Why am I using Steganography?
The way levels used to work in Monaco is that there would be an XML file (this is like a text file, for those less techie folks) that contained the basic information about the world. Here's a link to a sample:www.pocketwatchgames.com/Mwyim/images/blog/Prison.xml
This file would then point to a different file containing the actual level data for each floor of the mission. Here's a sample:www.pocketwatchgames.com/Mwyim/images/blog/Prison0.xml
All that junk is actually the level data.
An Aside: Run Length Encoding
It's run-length encoded, which means that it's really just a whole bunch of numbers mashed together, alternating between the tile-type, and then the number of that tile-type that are in a row. (more about RLE here: En.wikipedia.org) RLE is great for Monaco because every map contains a 53x40 grid of 4 layers of tiles. The Floor layer tends to have fairly long runs of the same tile-type, and the other layers have fairly long runs of blank space.
But I didn't want people to have to pass these meaningless files around if they wanted to share levels. That's not FUN! It's way more fun to pass around these little images!
Back to Steganography: how does it work?
Remember that Steganography is about hiding messages in other messages. For us we want to hide it in such a way that you don't even notice.
Every pixel in an image is composed of 4 8-bit values, describing how Red it is, how Green it is, how Blue it is, and how Transparent it is. That means that the color and transparency of every pixel in an image is described by 32 binary numbers: 1's and 0's. The first 8 are for Red, then the next 8 for Green, then Blue, then Transparency.
That means that we can have up to 256 shade of red, green, and blue. But when you combine all these possibilities together, you get 16777216 different color possibilities.
Bits: The Building Blocks of Pixels
In binary, the first digit of the number is the MOST SIGNIFICANT BIT (bit.. bit.. bit... echo echo echo). So a red value of 10000000 is actually halfway up the red scale, despite all those zeros. Modifying that bit will change the color of a pixel drastically.
The last digit is the LEAST SIGNIFICANT BIT (said in my chipmunk voice). So a red value of 00000001 is nearly black, it has 1/256th of red in it.
So if we only modify the least significant bits of the R, G, and B values of each pixel in the image, the viewer probably won't even notice! We're only shifting the shade by 1/256th!
DRUMROLL....
So all I'm doing is I'm taking all that junk level data from above, and spreading it like butter across the least significant bits of every pixel in the image. Considering that the image is 1060x480 pixels (508,800 total pixels) and I have 3 colors which I can modify (I probably don't want to screw around with the transparency data in the image), that means I have 1,526,400 bits to work with. And if I run out, I can always move to the SECOND LEAST SIGNIFICANT BIT!!!
Since I compressed my data with Run-Length-Encoding, I've never actually had to move beyond the least-significant bit. The player will never notice! Especially with all that bloom and other junk obscuring the image.
You can really only see if if you take the image into an image processing program, remove the alpha, zoom in, and increase the contrast/saturation drastically!
Notice in the last image how there is a barely discernible horizontal line in the noise. That's the end of the level data. What this means is that I can actually fit all level data into a 265x120 pixel image, only using the least significant bit.
A TRICKY ADDENDUM:
Something I could do, and I believe that the Spore folks did as well, is actually use ALL of the color bits in pixels that are 100% transparent. Since those pixels are transparent, it doesn't matter what color you set them to. I can't do this, however, since I am using the entire image, which means that I have no transparent pixels to work with.
WOW, smart!
I also checked out your gameplay footage. This looks fun!
I saw your talk at GDC, that prompted me to google this up. Thank you for explaining and showing this technique off.