Encoding schemes for map data

This seems to be a recurring topic in my Twitter, because every time I start a new project I try to find what is the best way to deal with the map data. I guess I haven’t found the perfect encoding or, at least, an encoding that is good for all cases.

In this post I’m going through the different approaches I’ve used in my games.

Of course, use compression!

This is common to all my games: I compress the map data. Which is funny because, there’s always someone on Twitter suggesting it: “have you tried compression?”. Sure!

Unfortunately compression is not enough targeting some microcomputers and a big number of screens.

For example, looking at Golden Tail, it uses screens of 20x10 tiles with tiles of 8x16 (although it is irrelevant for what we are looking at here, it means the tile map is smaller). The game had a total of 40 screens –not a large map–, which adds up to 8000 bytes with no compression. That is a bit too big for a 64K single-load Amstrad CPC game.

So the idea is compressing each screen independently and you uncompress the screen you need to draw. You may get better compression ratios by grouping screens, but that means a larger memory area to uncompress a group. In Golden Tail I was still using UCL compression –which is good, but the compression library is very fiddly–, and it really helps to reduce those 200 bytes.

Now, this example may not be ideal because in Golden Tail I was already limiting the amount of tiles you can use per screen –explained on the next point– and the screens are optimised for that, but in this case UCL gives us an average of 88.4 bytes per screen, which is 3536 bytes in total, saving us a 55.8%. Not bad!

Bit packing

It is possible that you want to reduce even further the size of the map data. For example, it could be that your tile/sprite engine is using a lot of memory, or the fact that you are writing the game in C –which will use much more space than hand written assembler–. Bit packing can help to go beyond what compression can provide.

One way to do that is limiting the amount of tiles you can use on a single screen, so the tile index uses less than 8-bits, and bit packing the map data before compressing.

Continuing with Golden Tail’s example, using 4-bit per tile, one screen is now 100 bytes (we store 2 tiles in one byte), and the average UCL compressed screen is 79.5 bytes. The 40 screens are now 3180 bytes, giving us a further 4.45% of savings. Again, this is not a good example because Golden Tail’s data is already optimized to use 4-bit per tile, so the plain compression is already giving very good results even without bit packing.

What is the downside of this approach? You have less tiles to design your screens, which makes things harder, but it is just matter of practice. Golden Tail didn’t look too bad despite using a maximum of 16 tiles per screen, if I say so myself.

Let’s look at a more extreme example: Night Knight.

Night Knight screens are 16x22, which is 352 bytes per screen, and the game has 80 screens. That’s 28160 bytes!

In this MSX game I used 2-bit per tile, allowing up to 4 tiles per screen. It also has some information that is not stored in the map data and instead is added by the game: shadows and brick patterns.

By using 2-bit per tile, our screens are now 88 bytes, making the complete set 7040 bytes. Although I’m talking about only map data, game usually include entities –like enemies– that need to be added to the screen, and those are stored in sequences of bytes –in this game is 3 or 4 bytes per entity–, and accounting those the real total is 9864 (123.30 bytes per screen, on average).

If we apply compression –I used UCL in this game as well–, we get a total of 7028 bytes with an average of 87.85 bytes per screen.

Night Knight is a type of game that can use 2-bit per tile, using different tile-sets during the game, and the screen still looks nice. It always depends on the game, but I would say 4-bit per tile is a good compromise. Besides we can always cheat using an entity that allows adding tiles out of the tile-set, in exchange for some memory, of course.

Using objects instead of tile maps

So far the methods I have described are more or less level design friendly, because is just drawing your scene using tiles with your favourite map editor –I use tiled, and I explained how on a video–.

A different approach is to not use a tile map at all but describe objects instead, that will be interpreted by your map renderer to draw the scene.

Brick Rick uses 20x22 screens, which would be a tile map of 440 bytes per screen. The game has 50 screens, which adds up to 22000 bytes –without counting the entities–.

By describing each screen with a set of objects (“fill area”, “draw platform”, etc) –plus adding shadows, brick patterns, etc–, those 50 screens use 3112 bytes, with and average of 62 bytes per screen.

Obviously we want to use the smaller amount of memory to describe those objects. Brick Rick implemented 3 objects encoded as 1 byte offset from the previous object, 3 bits for the type of object, 5 bits for width, and then depending the object, there could be one extra byte.

The end result is very optimized, but the level design is tedious because we have to draw those objects, which is less direct that putting together a tile map, and we won’t have a visual cue of what the screen looks like. This may be more a mismatch of the tool I’m using than an issue with the technique, but I ended drawing the tile map and then putting the objects on top of that using a different layer. Not the end of the world, just a bit of extra work.

In this case, the end result is so tight that there is no benefit from using compression.

Like in extreme bit packing, this method depends on the type of game. If I had to design screens as detailed as in Golden Tail, I would probably need more object types, and the end result wouldn’t be as good. In the case of Brick Rick, the resulting screens are richer than what I could get with 2 or 3-bit per tile.

Using meta-tiles

Some people call this super-tiles, but the idea is the same: use an intermediate table grouping your base tiles, and then use those groups –the meta-tiles– in your map data.

This is the system I’m using in my WIP title for the ZX Spectrum 48K: Outpost.

This game is not finished, so I don’t have a lot of data to show final numbers here, but I can provide some approximations that may be useful.

Outpost screens are 32x20 tiles, which is 640 bytes. Say we go with a small game like Golden Tail, that would add up to 25600 bytes. I plan to add more screens than that, and I’m targeting the 48K model with single-load, so I should do better than that!

If we use 4x4 meta-tiles, 64 meta-tiles would be 256 bytes –the speccy is 1-bpp, and the meta-tiles don’t need to store attributes; is just an indirection to the actual tile data–, and this reduces our screen size to 160 bytes (width and height are the half of the size with regular tiles). Besides, the meta-tiles based maps have the property of generally compressing better than small tiles, so when we apply compression –in this project I’m using aPLib compression, with the awesome apultra–, we reduce this to an average of 62 bytes –with the caveat that I have designed only a few screens, but the number sounds about right to me–.

So going back to our hypothetical 40 screens, that’s now 2480 bytes –plus the 256 bytes overhead of the meta-tiles table, and probably a bit of extra code–.

The downside of this method is that the level design is tricky because we have to draw our tiles and group them in meta-tiles, and then use those meta-tiles to design our screens. In my case I threw Python to it until the problem was simple enough. At the end the game expands the meta-tiles to just tiles, so things like the collision detection are just as usual.

Conclusion

Obviously the game size doesn’t necessarily translate into more or less fun, but if the game works, more game is likely to be better. We will always want to cram in as many screens as possible, and considering that other parts of the game are harder to make smaller –graphics, the code itself–, keeping the map data under control is very important.

As you can see, there is not a “one size fits all” approach, so knowing what are your options when you start to plan a new game, is always useful to avoid ending with a good game that is too short!