My Faxanadu level editor is coming along nicely so it's about time I write another update on the internals of the game. Today's post is the beginning of a mini-series about the data the game uses to create levels and to display them on the screen. Most of the mini-series is based on
Vagla's document. Whenever that document is incomplete or erroneous I'm going to try my best to correct the information from there.
Let's start with a brief overview of how levels are loaded. Every screen in the game is made up of several independent datasets which are combined by the game whenever a new screen is loaded. These datasets are:
- Screen data: A screen consists of 16x13 blocks. This data defines which blocks appear on a screen.
- TSA (Tile Squaroid Assembly) data: Each block is made up of 4 tiles. Which tiles these are is stored here.
- Block attributes: Defines the palette to be used when drawing the tiles of a block.
- Block properties: Defines the behaviour of a block (air, solid, ladder, ...)
- Scroll data: Defines on what edge of a screen it's possible to leave the screen.
- Door location table: Defines where doors are located.
- Door destination table: Defines where doors lead to.
- Palettes: Defines which colors are used to draw a screen.
Today's part of the mini-series begins with the first step: The screen data. But before I'm going to explain how to read that data I'm going to give a brief overview of how the data is stored in the file.
There are 8 different major areas in the game. Each screen in that area shares most (often all) data with all other screens in that area. These 8 areas are:
Area 0: The first town
Area 1: The fog world you enter after completing the fountain quests.
Area 2: All other towns.
Area 3: The world between the first town and the fog world.
Area 4: The world between the fog world and the last world.
Area 5: The last world.
Area 6: The inside of buildings.
Area 7: The maze before the last boss and his room.
In Vagla's document these 8 areas are called chunks. The offsets where they can be found and how the data can be interpreted doesn't need to be repeated because Vagla's document already takes care of that. To reiterate though, the screen data this post is dealing with are the block IDs that define which images (blocks) are used as background images for a given screen and on what position of the screen they appear.
What I want to elaborate on is how the screen data is stored. It's stored in compressed form and a level editor obviously needs to be able to uncompress that data when loading the ROM file and to re-compress it when saving the edited data back to the ROM file. In the next few paragraphs I'm going to mention a few quirks I've found in the decompression algorithm that are not mentioned in Vagla's document and at the end of this post you're going to find the C++ code I'm using to uncompress and compress level data.
The compression is pretty straight-forward. Compressing a screen data begins with the block in the upper-left corner of the screen. The other blocks follow in order from left to right and from top to bottom until all 16x13 blocks have been compressed.
If the next block equals the block to the left of it (the one placed before) two bits (00) are added to the compressed level data. Two bits (01) are also added to the compressed data if next the block equals the block that was placed at the same column but one row above. If the next block equals the one that was placed one row above and one column to the left the two bits 10 are added to the compressed data. When a block can't be repeated from either of these three positions it needs to be created explicity. This is done by adding the two bits 11 to the compressed data followed by 8 bits which identify the block.
Decompressing a compressed screen is of course the opposite of a compression.
I wanted to mention that it's possible to refer to the block before the next block even if the x-coordinate of the next is 0. In that case the last block of the row before is copied. It's also possible to copy the block above and to the left of the next block if the current column is 0. In that case the last block from two rows above is copied.
The first screen that uses both of these little quirks is screen 13 of area 1. It's the screen that you can see at the beginning of this post. Here's its data in decompressed form. I've marked the three occasions where the aforementioned situation occurs.
12 24 0b 04 0c 05 04 04 04 04 05 05 05 04 0c 0c
12 04 05 0c 04 12 06 04 11 08 0e 13 09 26 05 04
12 27 26 08 0e 12 06 0e 20 0e 0e 23 0c 24 03 04
12 05 0e 0e 12 25 04 24 25 20 23 24 24 4f 03 06
04 04 12 12 24 14 14 32 14 25 24 4f 4d 45 03 05
05 23 23 25 30 00 00 00 14 25 39 49 4d 48 03 25
20 20 24 32 32 32 32 32 14 39 0c 49 42 48 03 05
04 24 07 14 14 14 14 39 39 25 0c 49 46 48 03 06
05 04 07 04 05 05 05 05 05 04 11 49 47 48 03 06
04 30 07 07 07 07 07 07 07 07 04 05 05 05 05 04
05 30 30 30 14 14 14 14 14 07 07 07 07 07 05 1d
05 14 14 14 14 03 14 03 14 03 14 14 07 05 05 1d
2f 03 03 03 03 03 01 03 25 03 25 41 07 05 05 05
There's another oddity I've witnessed when playing with the level data. In the original Faxanadu ROM the size in bits of every screen in the compressed level data is evenly divisible by 8 without any padding bits. That's not a coincidence but actually enforced by the compression algorithm. Strictly speaking it's actually enforced by the number of blocks on a screen.
There are 16x13 = 208 tiles on a screen. Therefore a screen needs 208 x [2 | 10] bits (that notation is supposed to represent the fact that each tile is represented by either 2 or 10 bits). That expression can be changed to 8 x (26 x [2 | 10]) and lo and behold the exact number of bits used for each block becomes irrelevant. The compressed size of an entire screen is always a multiple of 8.
Here's the promised C++ source.
In one of my first updates about the level data of Faxanadu levels I've explained how to decode the compressed screen data of the screens of a level. What I didn't mention back then was how the game itself actually decompresses that data. That's what
Tracked: May 27, 14:37