Mapping Matrices

Many 2D games were able to present large, varied game worlds on very limited machines. The trick was to use compression techniques to make data fit on the very small memory chips. As an example, let's analyze how much memory a top-down game such as The Legend of Zelda required. To support the argument, I'll assume the game level occupies 5x5 television screens across, and that every screen is 256x200 pixels, palletized to 16 colors. If you do the math, you'll discover that a bitmap with those dimensions would take up 1.25MB of space, clearly more than a Nintendo console had at that time. There must be a trick somewhere, and that trick is called mapping.

Mapping is a compression technique that will allow us to create good-looking game worlds at a fraction of the memory footprint. We will lose some visual variety in the process, but our dream game will fit on our target platform. Mapping is an extremely popular technique. It was used in thousands of games for classic consoles and arcades, and is still used today, even in some 3D games. The key idea is to divide our game world into a set of tiles or basic primitives. Each tile will represent a rectangular pattern, which we will combine with other tiles to represent the level. So, if our game world must represent grass, stone, snow, and sand, we will use four tiles, and then map them as if we were putting tiles on the floor.

The compression comes from the fact that, if we repeat the same pattern frequently, we will only have it once in memory. To prove this, let's assume we represent our initial game with a tile set. We will use 256 different tiles (more than enough to provide richness to the game world). Each tile will be 8x8 pixels.

So, each tile occupies

8x8 = 64 = 32 bytes (we are using 16 colors only)

The whole tile set will require

32x256 = 8KB

We will call this structure the tile table (more on tile tables in the next section). We will then need a second data structure, called the mapping matrix. This structure stores the layout information: how the tiles should be arranged in game level. From the sprite size, we know the size of our mapping matrix will be

256x5/8=160
200x5/8=125

Because each entry will be a byte-sized value so we can index the 256 possible tiles, the whole table will require

160x125 = 20000 bytes

So, our compressed map will take up around 19.5KB, with 8 extra kilobytes dedicated to the tile list. On the whole, that is 27.5KB, down from 1.25MB. That means dividing by a factor of 50 approximately. Clearly, there is a big gain to mapping, and that's the reason mapping was extremely popular in the '80s. Games such as Mario Bros, Zelda, 1942, and many others use variants of the mapped scheme.

Tile Tables

We have seen how to encode character graphics. We have also explored how to store a game map based on a mapping matrix. It is time to talk about the background graphics or tiles. Thus, the data structure we will now cover is the tile table (TT). Put simply, it is a list of background images that can be tiled and combined using a mapping matrix to create a complete game map. Some platforms, such as the NES, had this structure defined in the hardware's specifications. Others, like PCs, allowed the developer to specify its own. Whatever the case, the TT is used to store unique tiles that will later be mapped to the screen. There are a number of decisions involved in creating an efficient TT.

Format of the Tiles

First and foremost, we need to know the format of the tiles we will be storing. This is a really important choice, because different formats dramatically affect the table's size. Traditionally, tile sizes used to be powers of 2, as this allowed some optimization in the blitting routines used to transfer them to the screen. Instead of transferring bytes, we can use words or even 32-bit values for increased efficiency.

We also need to decide whether all tiles will be the same size or if they will differ. Classic games used equal-sized tiles for easier screen rendering. But if we consider a real-time strategy game that uses an isometric view where buildings are all different sizes, wouldn't it be wiser to allow for different tile sizes?

In addition, we must decide the color format of the tiles. In the old days, tiles were palletized, so each pixel was encoded in one byte that indexed the color palette. However, more recent games have used high-color modes (16 bits encoding RGB in 6-5-5) or even true color (24 bits encoding RGB as 8-8-8). Clearly, the more colors the better. But keep in mind that more colors means more memory, more bus usage, and thus less performance.

However, there is an equation that will give us the memory size of a single tile, as a function of several parameters. Keep this in mind when designing your game so your graphics fit in memory:

Number of Tiles

The number of tiles held in the TT will be as important as their format. On one hand, more tiles means nicer graphics. On the other hand, memory use will increase dramatically in more ways than you think.

Imagine that our game needs to hold 256 different tiles. The TT will encode them in positions 0 to 255. Thus, each position in the mapping matrix will need to index that table using an unsigned, 8-bit number. However, imagine that our artist raises the bar to 300 tiles. The TT will grow accordingly, but the mapping matrix will also undergo some changes. We cannot encode 300 values in a byte. We have two options:

• Use 9 bits, which allow 512 values, but require some rather obfuscated code to access.

• Use a 16-bit value, which will take up double the memory but give us simple access.

An alternative to allow this in platforms that have some sort of file system is to ensure that only 256 tiles are used per level, so each level has a different TT. This way we can preserve the variety without the memory hit. But some platforms require the full program (including data) to be in main memory at the same time, so there is no way to select the TT.