Faxanadu level data - Part I

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.