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
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!
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
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
4 bytes per entity–, and accounting those the real total is
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.
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
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.
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!