Oldschool Gaming - reviewing new games on classic computers
Map Compression Methods :: written by Jason Kelk :: added 19 Jan 2004

One of the major problems with writing an 8bit game is trying to cram a large playing area into what is a reasonably small space. For the purposes of this article, the screen has to be considered as a series of "cells" and, for the examples covered here, we'll be dealing with a theoretical screen which is 40*24 characters; that'll work out as 320 by 192 pixels and is, by coincidence the default size for an Atari 8-bit screen but the adaptation for other screen dimensions is fairly trivial to do. Since we're working with this theoretical machine, we therefore need to cover the specifics of screen handling a little bit. Machines that have bitmapped screens will need to take the data from the maps referred to later in the article and extrapolate them out by having 256 possible 8*8 pixel definitions which are referenced from the map and then written into the actual screen. Although any size could be chosen for these "characters", the 8*8 pixel dimensions used here are the one that all machines share in common and the majority of machines use for their own ROM character sets. Essentially, the machines using bitmaps are going to be converting characters up to bitmap data and displaying the same actual data on the screen as the other formats would be.

MAP DUMPS
To start with we have the easiest storage method of the lot; dumping a block of data into memory and chunking it out onto the screen as required. This is, of course, not a particularly efficient way of doing things since our theoretical platform requires 960 bytes of data per screen, so if we only have 32K available for screen data, that's a mere 34 screens. Yes, 34 sounds like a lot, but when you consider that, if each takes a minute to complete, that's only half an hour of play time, it doesn't quite seem as large!

The simplest way to scroll a screen (or at least, to handle the data involved) is, similarly, to simply have a large chunk of "map" data in memory and then to treat the screen as a "window" into that area, moving the origin point around to allow the window to view other parts of the map. For a fictitious (simply because it won't actually fit into an 8bit with 64K or less of memory and leave room for code) example, take a 256*256 byte map; the easiest way to visualise this is as a huge, character based screen memory, the top line being the first 256 bytes and the last being the final 256. If we have our 40 by 24 byte "window" on our actual screen, copying from the map to that block will, using some pseudo BASIC to illustrate, work like this:

For X=1 To 40
For Y=1 To 24

Read MAP (X,Y)
Write SCREEN (X,Y)

Next Y
Next X

That grabs a window from the map and writes it to the screen; it's pretty useless as is, but if we change it to Read MAP (X_WINDOW+X,Y_WINDOW+Y) we can now alter where in the map our window is looking at externally to the loop by changing those recently arrived variables. That's basically how it works and, in some cases at least, dedicating a large chunk of the memory to the level maps is workable; "Ghosts 'n' Goblins" on the C64 simply has the data dumped into the RAM in this way and the levels interlock to use the map's space to the absolute maximum - but that's a very rare example of getting away with it and, unless the plan is to multi-load the levels, a map dump simply isn't the most efficient use of the RAM, in particular for computers that have larger overheads for screen memory since the loss of a large chunk of their potential storage space to the level map isn't viable.

An example of single screen games which has the various screens uncompressed in memory would be Chiller by Mastertronic (C64, Spectrum and CPC), whilst examples of map dump scrolling include Mastertronic's One Man And His Droid (Spectrum, CPC, C64, C16, Atari 8-bit) or The Last V8 (C64, Atari 8-bit and Amstrad CPC) and it's unofficial sequel Red Max (C64 and Atari 8-bit) which was released by Codemasters.

CHUNK COMPRESSION
Chunk compression is, as the name suggests, a method to take a series of pre-defined chunks of map data and expand it out as the scrolling needs it; this is far simpler than tile compression (of which more later) but bears some similarities. As we've already seen, storing a map straight into RAM isn't particularly efficient on space and, if we were to assume that, for vertical scrolling, we'd need to stack up a large block of data in the RAM and shift it through the actual screen a line at a time. As also noted previously, that can be very memory intensive and for our theoretical machine, 32K of data will generate a mere 34 screens of scrolling, a paltry two minutes of landscape assuming a fixed speed of one pixel per frame. So instead we store chunks of landscape and have a running order that tells the scrolling routine which chunk to work it's way through next, where a chunk is the full 40 bytes wide but can be any size vertically we require. This means that, should the need arise, the same landscape feature (or group of features) can be repeated two, three or many more times in a row or throughout a larger map to drastically increase the length of the landscape and the chunks themselves can vary in size from a couple of bytes high to a complete screen of data as the detail dictates.

There are a few examples of chunk compressed scrolling, most of which are games by David and Richard Darling, later to be the driving force behind Codemasters; titles like BMX Racers (C64, C16 and Spectrum) and Dark Star (C64) which were both released by Mastertronic.

COLUMN COMPRESSION
Due to the way it's organised, "column compression" is, as with block compression, pretty much limited to working on a single axis; in other words games that scroll only horizontally or vertically and moving on both would be troublesome to say the least. Hopefully, the reason for this will become apparent as we go on. To start with, a map is needed and, for a horizontal scroll it will normally be 256 bytes wide by the height of the screen (since most 6502-based machines can count $00 to $FF at speed, it's common to work within that boundary), so for our example that's a block of 6K (256*24 bytes). On it's own, this map is only capable of providing about six and a half screens of terrain before "wrapping around" to the start, but the content of this map isn't a continuous terrain, it's all the elements needed to make one. Next we have the actual terrain data, this is a stream of bytes that say which column of the map data to display next. If the level data simply contained all of the bytes from 0 through to 255 the entire map would go past as if the compression wasn't there, but we also have the option to repeat sections of the map. And there is no need for the level data to be 256 bytes long, we can keep reading to our hearts content.

For example, we'll say that the first column of the map is blank and used only for gaps in the landscape; if we want an empty area of four characters across by 24 down to scroll go past, the level data would simply contain $00, $00, $00, $00 - in other words, use column $00 four times. Add to that assumption that we have some background detail in columns $01 to $03, for example a wall with a gap for the player to navigate through, and we wanted it displayed, the level data for that wall is simply contains $01, $02 and $03.

To scroll past a wall, an empty space and a second copy of the same wall, the data will read:

$01, $02, $03, $00, $00, $01, $02, $03

And, assuming there is another block of background detail in columns $04 to $08 and we need a bigger gap before we get to it:

$01, $02, $03, $00, $00, $01, $02, $03
$00, $00, $00, $04, $05, $06, $07, $08

Not including the map overheads, those sixteen bytes expand out to the equivalent of 384 going past, a block of 16*24 bytes of data. After that, it's just a matter of streaming level data through and, as long as the map data is laid out to contain only the possible elements of terrain needed, it should happily fit into the a reasonable amount of memory.

This same process can be applied to vertical scrolling by having a map of rows rather than columns and repeating them as the need arises and, whilst it's not the best method for the job in hand, compressing static screens becomes a matter of generating a map containing all the possible elements the screen will require and then a mere 40 bytes can represent an entire screen. The only issue that arises from using column compression for screens is that with only a finite number of possible columns, getting complex screen designs in will usually require several columns to be similar but not entirely the same, thus eating up precious map space.

Kikstart (C64 and Atari 8-bit) and Kikstart 2 (C64 and Spectrum) from Mastertronic are prime examples of column compression and the editor on Kikstart 2 even demonstrates the principle by allowing the user to overlay bits of the landscape and then remove the individual columns.

A selection of tiles from GR9 Strike Force on the C64
A selection of tiles from GR9 Strike Force (C64)
TILE COMPRESSION
This is probably the most powerful system of map compression and which subsequently makes it the most complex to program. But the dividends of using tile compression are high and most commercial games titles written for the 8bits during the 1980s and 1990s tend to rely on it for their data.

The system uses the word "tile" as an analogy to the ceramic things you stick up in the bathroom, on a screen a tile can be 2*2 bytes (16*16 pixels), 4*4 bytes (32*32 pixels) or indeed any dimensions required down to 1*1 byte (8*8 pixels, which is technically how the machines with bitmapped screens are already handling the graphics definitions). The examples shown here are 5x5 characters, drawn with the Shoot-Em-Up Construction Kit on the C64 for the game Cyberwing. These tiles are then stuck up next to each other to make a whole. The machines with bitmapped screens are already essentially handling a small-scale tile compression system when they are dealing with "characters".

To start with, lets assume our previous screen dimensions, that we want to use tiles that are 4*4 bytes and we'll want to have 64 possible tile definitions. For ease of access, the top left byte all 64 tiles are stored together for speed and that's followed by another 64 bytes for the second byte of the tile and so forth until the last byte at the bottom right corner - a total of 1K for all 64 tiles and much lower than the overhead for column compression.

For an encore, we need to divide the screen up into tiles as well; for our example screen that boils down to 10 tiles across by 6 down. To uncompress a screen of data, we need to do something along these lines:

For X=1 To 10
For Y=1 To 6

Read MAP (X_POSITION+X,Y_POSITION+Y)
Read TILES (offset in by MAP)
Write SCREEN_TILE (X,Y)

Next Y
Next X

The above example generates an entire 960 bytes of screen data from just sixty bytes in the map and how the reading and writing of these tiles is processed is open to interpretation, on bitmapped screens it can be a reference to a block of bitmapped data that is copied into place just as easily as a series of "characters" that are then used to copy in the actual definitions.

As before, X_POSITION and Y_POSITION are offsets into the map of data, but this time the map contains a list of tiles rather than being directly relational to what will appear on screen. Changing X_POSITION from zero to one causes the display to jump four characters across, similarly Y_POSITION causes the display to move four characters vertically. In order to use this for scrolling, it's necessary to clip the data at the edges of the screen to move the tiles around more finely, essentially the routine needs to handle 11*7 tiles but is only displaying fragments of the thirty two tiles around the edges of this area; that can be either done by uncompressing the current tiles in a back buffer and reading a window from that buffer as we've seen previously in the map dumping section, by having intelligent routines that can be told to start halfway through a tile and then shovel out the remaining data or simply by using a scroll routine that relies on fixed motion snap scrolling between tiles so that once a "move" is started, the player slides neatly onto the next tile boundary.

Tiles can be easily used for fixed axis scrolling as well and whilst in a comparison between 4*4 byte tiles and twenty four byte tall columns for a horizontal scroll the column compression will take only four bytes to represent 4*24 characters on the screen whilst tile compression needs six bytes, those extra two bytes allow for a much larger amount of variation and flexibility as to what is actually appearing. And finally, tile-based single screen games using 4*4 byte tiles on our theoretical machine need a miniscule 60 bytes of data, meaning they require nine hundred bytes less per screen, over 15,000 screens into the 32K block we've discussed previously in fact!

There are a large number of games using variations on tile compression to offer as examples, Cybernoid and Cybernoid 2 from Hewson on most of the 8-bits use a tile-based system for their backgrounds, as do Codemasters' various BMX Simulator incarnations. Shoot 'em ups like Thalamus's Armalyte (C64), Mission Genocide (CPC and C64) from Mastertronic and Warhawk (C64, CPC and Atari 8-bit) by Firebird all scroll in a fixed direction from tile maps and the Turrican series from Rainbow Arts are using multi-directional scrolling with tile decompression. Finally, Activision's Citadel on the C64 is an example of snap scrolling tiles, instead of having totally free movement around the map, the player moves from tile to tile almost like a chess piece.

Please note that this article was revised and expanded after initial publication by it's original author; changes were made on the 22nd June 2007, republishing was on the 1st July 2007.

Content copyright © 2004-2014 Oldschool Gaming     Designed and hosted by Enisoc Design