Working on platforms with tight memory budgets like the ZX Spectrum requires some head scratching work on how to cram in as much data as possible into such a tiny amount of space.
One of the biggest potential uses of memory is storing map data. Whilst working on our ZX Spectrum project we had iterated through 3 different map formats! Below I work through these map formats, showing their pros and cons before describing the final format which we'll be using on Gloop Troops 2.
Format 1: No compression on tiles.
First of all we tried exporting data directly to see what kind of memory hit we would take. Our maps are 32 x 22 tiles in size, with each tile representing 8x8 pixels of screen space. This leaves a space 2 tiles blocks for the HUD at the top of the screen. Initially we stored all the tile data uncompressed but compressed all the tiles attributes using a simple form of run length encoding.
The way we stored attributes very simple. After all the tile data was written to the map file we'd write out all the attributes.. There is 1 attribute setting per tile block used in the map. We would start by writing out an attribute's value into the map file and then check to see if there were subsequent tiles which had a matching attribute value. If so we'd scan along the rest of the map counting the number of times this attribute occured without changing and write this number as a second byte after our written attribute value. If there were no matches ( so only 1 instance of this attribute before it changed ) then we'd set the FLASH bit of the attribute to ON. This is because we knew we'd never have any background tiles with the FLASH bit set as it tended to look ugly.
Example attribute data ( uncompressed ), 5 attribute tiles with the value 8 followed by one of 16, followed by 2 3's, and finally another 0x8:
0x8, 0x8, 0x8, 0x8, 0x8, 0x10, 0x3, 0x3, 0x8
Example of compressed attributes:
0x88, 0x5, 0x10, 0x83, 0x2, 0x8
So we've written out attribute our attribute 0x8 with the top bit ( the FLASH bit ) which changes the number to 0x88 ( 10001000 ). We've then written out the number 5, which is the number of times this attribute occurs, followed by attribute 16 ( 0x10 ) without the top bit set ( so the number stays as 0x10 ). We've then written attribute 0x3 with the top bit set ( becoming 0x83 - 10000011 ), followed by the number 2 ( as there were 2 instances of the number 0x3 in our uncompressed data ). Finally we have the number 0x8 as the last attribute, and there was only one instance of this in a row so no FLASH bit and counter byte set.
We also stored the width and height of each map at the top of the map file. This is because we'd envisioned having a variety of map sizes and could save some space.
The pseudo code for the map file was:
Width - 1 byte.
Height - 1 byte.
For tile_y = 0 to 21 do
For tile_x = 0 to 31 do
Tile_Id - 1 byte.
next tile_x
next tile_y
{ Attribute data }
The advantage with this method is each screen can look distinct as there are no rules regarding which tiles can be adjacent to another tile. But the big problem with this format is that whilst the attribute data compresses nicely the tile data still uses up 704 bytes, which is quite a bit of space on a machine with only 48k!
Format 2: Mixed - Tile brushes and custom tiles data.
This was the method used for Gloop Troops 1 and offered up a sizeable saving but still wasn't enough. We realised that a lot of the tile data tended to repeat throughout a map, so rather than storing each tile individually we could store a single "brush" which would store many tiles worth of data.
Example tile brush: This is a 3x2 Tile brush which stores 6 tiles worth of data.
[ 4 ][ 4 ][ 4 ]
[ 7 ][ 8 ][ 9 ]
We stored the tile brushes separately from the map data so that they could be used by several levels. Tile brushes were written out without attribute data and in the format:
Width - 1 byte.
Height - 1 byte.
For tile_y = 0 to brush_height do
For tile_x = 0 to brush_width do
Tile_Id - 1 byte.
next tile_x
next tile_y
Our map format changed to:
Width - 1 byte.
Height - 1 byte.
Num_Tile_Brushes_Used - 1 byte.
For tile_brush_id = 0 to Num_Tile_Brushes_Used
Tile_Brush_Id = 1 byte.
Tile_Brush_X_Pos - 1 byte.
Tile_Brush_Y_Pos - 1 byte.
Next tile_brush_id
For tile_y = 0 to 21 do
For tile_x = 0 to 31 do
if ( tile_is_not_part_of_tile_brush )
Tile_Id - 1 byte.
next tile_x
next tile_y
{ Attribute data }
This meant we'd write out all the tile brushes first, then for any parts of the map which weren't covered by a tile brush we'd write out the tile data. We also did a simpler compression to tile 0 as what we did with attributes. If we wrote a 0 as the tile ID then we'd write a second byte indicating how many tile 0's to write out. This is because tile 0 represented blank space on the map, and there would typically be many of these in a row.
The advantage of this method meant that we could cover most of the map with a few tile brushes and then touch up areas with a few individual tiles. The compression on this was a lot better but still not fantastic.
Format 3: Tile brushes only and flood fill attribute.
This is the method we'll be using on GT2 - we'll be ditching the concept of individual tiles and purely using tile brushes. By default our screen will be flood filled to a particular attribute ( and tile 0 ) and tile brushes will also now store attribute data. The attribute data will still be stored in a simple run length encoded method inside the tile brush data.
Height - 1 byte.
Default_Attribute - 1 byte.
Num_Tile_Brushes_Used - 1 byte.
For tile_brush_id = 0 to Num_Tile_Brushes_Used
Tile_Brush_Id = 1 byte.
Tile_Brush_X_Pos - 1 byte.
Tile_Brush_Y_Pos - 1 byte.
Next tile_brush_id
We found that this now gives a far superior compression for each screen for some sacrifice of flexibility ( which we found we'd hardly used ).
This should mean less space wasted on storing map data and more space dedicated to graphics, game-play and sound!
