Tiling Theory

According to the first line of the science fiction classic Dune, "A beginning is the time for taking the most delicate care that the balances are correct." My articles on creating tilesets up to this point have assumed that the reader already understands what a tileset is and why you would use one. This post will remedy that knowledge gap.

To begin, let us consider how graphics are normally displayed today. The monitor you are using to read this sentence is most likely running in what is known as True Color mode. In this mode, each pixel, a tiny rectangle or square making up your screen can take on any of roughly 16.7 million different colors (specifically, two to the power of 24 different colors). These colors are determined by specifying three values: the red, green, and blue intensity, each having 256 different unique values (note that 2^24 = 256^3). if your display size matches mine, namely 1920 pixels wide by 1200 pixels high, then you have roughly 2.3 million pixels. Those of you doing the math at home can determine that in order to specify an image to be displayed on my monitor, you need 1920 * 1200 * 24 bits, which works out to just under 6.6 MB.

Nowadays, that is not an impressive amount of bytes. My machine has twelve gigabytes of memory, so my display only uses a half of a tenth of a percent of what I have available. I don't need to do anything fancy to reduce the memory required to show my display.

Now, let us travel back in time to 1985. The NES is released to the North American market, containing only 2 KB of memory. A single frame of my monitor's display would exhaust the memory of over three thousand NES consoles. The engineers of the time had to do some serious optimizing in order to display some interesting graphics back then.

One way to reduce the amount of memory needed to specify an image is to use what is known as Indexed Colour. This technique works a lot like the 'colour by numbers' colouring books you may have seen. To begin, you must decide on a palette, typically of 256 colours. Having done so, you can create an image by writing each pixel value, not with the actual colour of the pixel, but by an index into your palette. If you use a 24-bit palette, your image can still be made up of any of 16.7 million different colours; however, you are restricted to using no more than 256 unique colour values. If you are at all familiar with the GIF image format, you now know why GIFs are restricted to only 256 colors.

For an image W pixels wide and H pixels high, direct colour requires W * H * 3 bytes to record an image, while a 256-indexed colour requires only 3 * 256 + W * H bytes. Thus, 256-indexed colour becomes more efficient for storage when W * H >= 384. This is actually very small: a 20 pixel by 20 pixel image is already 400 pixels.

We can go one step higher. Rather than specifying each value individually, we can instead group pixels into larger units, called tiles. Under this scheme, we first define a palette as before. We then define a tile, an eight pixel by eight pixel square, using indexed color. We can then compose our images by having to define only our tiles.

Remember our water from before?

Here is what it looks like when I specifically call out the tiles from which it is composed:

Under magnification, we can see that our ocean water tiles are actually made up of only four eight by eight tiles. These tiles were specifically created so that when they are arranged in the correct manner, they are seamless. You can't tell where one tile ends and another begins, although you know that there must be some sort of repeating pattern to them.

Say your display was 256 by 256 pixels in size. Using eight by eight tiles, it is 32 by 32 = 1024 tiles in size. Specify each tile using 16-indexed colour (four bits per pixel), and give yourself sixteen different palettes. This lets you display 256 different colours at a time, but only sixteen can be drawn in any given eight by eight part of your display. Each eight by eight square in your image only takes two bytes to specify (10 bytes for any of 2^10 source tiles, four bytes for any of 16 different palettes, and one bit each to allow you to flip the source tile horizontally or vertically). This means that your entire display can be specified using only 2 KB of memory.

A scheme similar to this was used for the Picture Processing Unit (PPU) of the SNES. You still required a relatively large amount of storage for the tiles themselves, 32 bytes each, but the tiles could be hard-coded into the cartridge ROM. A typical SNES game was 32 MB, and a large percentage of their total storage capacity was used to store all of their tileset tables.

In comparison, the NES used 4-indexed, eight pixels by eight pixels tiles, which took up half as much ROM as an SNES tile, and its palettes were only four colours each, so it could squeak by using only one byte per screen tile, or 1 KB of memory.

The restrictions on the display hardware seem restrictive today, and they certainly were, but they were necessary at a time when RAM was still measured in kilobytes. Even still, they weren't as harsh as they seem for talented artists. Consider this screenshot from the SNES classic Mega Man X I cribbed from Wikipedia:

Looking carefully at the image, you can see that there are in fact fairly few colours, and the rock composing the ground and ceiling are definitely repeating themselves. When you are playing the game, however, you tend not to notice this effect, and instead just register a rocky corridor with bats swooping down to kill the Blue Bomber.

This, then, is the reason why I am writing a series of posts on how to create tilesets. Artists will tell you that "form is liberating": that having constrains placed on your materials and methods leads to more creative works by forcing you to master the limited resources available and find creative workarounds for their shortcomings. The skills necessary to create beautiful images using tiles are becoming quite rare, and so I seek to study them and pass them on, lest they be forgotten.