Talk:SkyRoads level format

From looking at the roads.lzs file I've been able to determine the following:

The first 2 bytes (7C 00) seem to be an offset. The next 2 I'm not sure about, but starting at address 0004 is a table of addresses and lengths for each level (2 bytes for the address and 2 for the length). (30 * 4) + 4 = 124 = 7C in hex.

Each level has the following format: 2 bytes for gravity (4 = 100, 5 = 200 etc.) Anything below 4 causes odd behaviour. 2 bytes for fuel. 2 bytes for oxygen. Then follows a 72 colour palette (3 bytes each for RGB)

After the palette is the actual level data. This is definitely compressed in some way (differences between level addresses are smaller than the lengths, plus substituting bytes yields no discernable pattern).

The first level starts at address 02CB, so my guess is that the data at 007C and the 2 bytes at 0002 have something to do with the compression.

Wolfy 03:40, 2 January 2011 (GMT)

It turns out that the first 4 bytes are actually the address and length for a duplicate copy of "over the base" level 1

Wolfy 04:39, 2 January 2011 (GMT)

The closest I've found to a pattern yet: changing the high nibble of byte 03B2 causes the road sections of level 1 to be out of sequence. A difference of 70h will move the whole thing along by a couple of sections (but anything above 70h = nonsense).

Wolfy 05:37, 2 January 2011 (GMT)

Very interesting! I've confirmed these details and added them to the main article page. It looks like the road data is almost certainly compressed, but in what format I don't know. I'm only familiar with LZW and it doesn't really look like this, although the .lzs file extension makes me wonder whether it's LZSS. -- Malvineous 01:44, 3 January 2011 (GMT)

I have a hunch that it might be deflate or something similar.

The first 4 bytes are almost always the same for each road and if not then they are at least very similar which suggests it might be a huffman tree.

Wolfy 03:55, 3 January 2011 (GMT)

The LZS algorithm does use Huffman coding... -- Malvineous 04:44, 3 January 2011 (GMT)

Uncompressed Huffman trees are easily detected, they nearly always contain the string $01FB $01FC $01FD or $01FD $0000 (Root nodes.). They're harder to detect in things like DEFLATE since these often rearrange or compress the tree though. Does anyone have a link to the file I can poke at? -Endian? What are you on about? 05:16, 3 January 2011 (GMT)

Here are the first three files: road.0 road.1 road.2 The first level is road.1 (the second file in roads.lzs). Note that the compressed data starts at offset 0xDE (after the palette), as per the main article page. -- Malvineous 05:22, 3 January 2011 (GMT)

I slept through most of the lectures on compression (they were all in the morning) but as far as I remember, deflate takes the data from the LZ77 stage, combines some of it then huffman encodes the data for that about 2 or 3 times (a bit mental) and one of those stages uses a fixed order alphabet. Anyway - the first 4 bytes from what I've looked at are usually 05 08 0A C1. Sometimes the last one is C0. This is about as far as I can go with it so hopefully someone else will crack that last bit :) Wolfy 15:05, 3 January 2011 (GMT)