Reading a KKnD2 Map

Published on the 9th of July 2024

Continuing where we left off in part 1, we now have access to the contents of the game archives. I think it's time to work on understanding the game's map format. By the end we will be able to parse the game maps and even display them.

If you're only here for the code, you can find the resulting map viewer on Github at https://github.com/ucosty/kknd2-mapview. The UI is quite rough, but it works well enough to show that the map has been decoded.

To start, there were a number of options I had to decipher the map file format. I could

Reverse engineer the game to see how it read the map contents
Reverse engineer the map editor to see how it exported the map format
Hack at the file directly, looking for things like offsets and patterns in data

I wound up using a combination of all three. Neither the game nor the map editor were easy to decipher on their own. At least I could control the map data I was looking at, by using the mission editor to create and export maps. These maps could then be decoded using the tools I made in part 1 and analysed.

First Look at the Map File

I have a few techniques to analyse binary files. Opening the file in a hex editor will give you an idea of the structure of a file. Binwalk's entropy mode can help you identify encrypted or compressed data. I also write one-off throwaway programs to read the binary data and hand parse it into structures, a form of printf analysis.

It's a map

After creating a simple map in the mission editor I exported it, and then I unpacked the data using the kknd-unpack tool I wrote. This is a hex dump of the first 560 bytes of the file.

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00000000 de c0 ad de 04 00 00 00 01 00 00 00 02 00 00 00 |................| 00000010 18 02 00 00 0c 33 00 00 00 01 00 00 00 2c 00 00 |.....3.......,..| 00000020 02 00 02 00 02 00 42 00 42 08 44 00 04 00 44 00 |......B.B.D...D.| 00000030 44 08 46 08 84 08 84 00 86 00 86 08 c6 08 84 10 |D.F.............| 00000040 86 10 86 10 86 10 c6 10 c6 18 88 08 c8 08 c8 10 |................| 00000050 c8 10 0a 11 4a 11 4e 11 0c 19 88 08 c8 08 8a 08 |....J.N.........| 00000060 88 10 c8 10 c8 18 ca 10 ce 08 8c 10 cc 10 cc 18 |................| 00000070 08 19 08 09 08 11 0a 11 0a 19 4a 11 0c 09 4e 01 |..........J...N.| 00000080 0c 11 0c 19 4c 19 0e 11 0e 19 4e 11 4e 19 8c 11 |....L.....N.N...| 00000090 8e 11 8e 19 08 21 0a 21 4a 21 4a 21 4a 29 8c 29 |.....!.!J!J!J).)| 000000a0 0c 21 4c 21 4c 29 4e 21 4e 29 8e 21 8e 29 ce 29 |.!L!L)N!N).!.).)| 000000b0 8e 31 ce 31 50 19 90 11 d2 19 d0 11 d2 11 90 21 |.1.1P..........!| 000000c0 d2 21 90 21 d2 29 d6 21 d4 31 14 1a 16 1a 14 2a |.!.!.).!.1.....*| 000000d0 9c 22 58 32 92 10 14 00 56 00 52 01 10 11 50 19 |."X2....V.R...P.| 000000e0 12 11 90 19 d0 19 d2 19 54 11 56 11 d6 09 94 11 |........T.V.....| 000000f0 96 11 96 19 50 21 52 21 90 21 d0 29 92 21 92 29 |....P!R!.!.).!.)| 00000100 d2 21 d2 29 d2 39 94 21 d4 21 d4 29 d6 21 d6 39 |.!.).9.!.!.).!.9| 00000110 18 09 98 11 98 19 d8 19 da 19 dc 11 dc 19 9e 11 |................| 00000120 d8 31 18 3a 12 1a 54 0a 54 1a 94 1a 96 1a 96 12 |.1.:..T.T.......| 00000130 12 2a 52 2a 54 22 14 2a 54 2a 56 2a 14 32 54 32 |.*R*T".*T*V*.2T2| 00000140 16 32 56 32 56 3a 96 22 96 2a d8 0a dc 0a 18 32 |.2V2V:.".*.....2| 00000150 58 32 5a 3a 98 2a d8 22 1c 1a 5e 1a 9e 12 1a 22 |X2Z:.*."..^...."| 00000160 9a 2a da 2a 98 32 98 3a 9a 3a da 3a 1c 22 1c 2a |.*.*.2.:.:.:.".*| 00000170 5c 22 dc 32 9e 32 1a 23 5c 2b 5e 23 1c 3b 1e 3b |\".2.2.#\+^#.;.;| 00000180 9c 23 9c 2b de 2b 9e 33 12 42 52 4a 56 4a 94 52 |.#.+.+.3.BRJVJ.R| 00000190 d8 42 5c 53 5a 42 9a 42 98 42 da 4a 1c 43 5c 43 |.B\SZB.B.B.J.C\C| 000001a0 5e 43 1c 5b 1e 53 5a 63 5c 63 5e 63 9c 6b 9e 63 |^C.[.SZc\c^c.k.c| 000001b0 df 13 df 5b 9f 01 5f 22 9f 2a df 2a 1f 3b 5f 3b |...[.._".*.*.;_;| 000001c0 1f 43 5f 43 9f 43 df 4b df 53 9f 43 9f 53 9f 63 |.C_C.C.K.S.C.S.c| 000001d0 df 6b df 6b df 43 df 01 df 01 df 1a ff 7b ff 2b |.k.k.C.......{.+| 000001e0 ff 2b ff 33 ff 33 ff 5b ff 53 ff 73 ff 7b ff 73 |.+.3.3.[.S.s.{.s| 000001f0 ff 73 ff 73 ff 5b ff 5b ff 43 ff 63 ff 63 ff 73 |.s.s.[.[.C.c.c.s| 00000200 ff 63 ff 63 ff 73 ff 73 ff 7b ff 6b ff 7b ff 7f |.c.c.s.s.{.k.{..| 00000210 ff 7f ff 7f ff 7f ff 7f ff 7f ff 7f 4c 52 43 53 |............LRCS| 00000220 20 00 00 00 20 00 00 00 32 00 00 00 32 00 00 00 | ... ...2...2...|

The first highlighted section (bytes 0 - 8) are the file header I added. Bytes 0 - 3 are a magic 0xdeadc0de used to identify this as an extracted resource file. Bytes 4 - 7 are the file's original offset within the map archive, in this case the offset was '4'.

The next two 32-bit words are '1' and '2', could be anything at this point. This is followed by two interesting numbers. Bytes 0x10 - 0x13 reads as the hex value 0x218. If you add the files offset you get 0x21c. Looking back at the hex dump, the data at offset 0x21c (the last 4 bytes on the row starting 00000210) is LRCS. Doing the same with the next 32-bit word (offsets 0x14 - 0x17) reveals another LRCS tag. This suggests that the earlier '2' (bytes 0xc - 0xf) is a count of the number of pointer entries exist. At this point it's all a guess.

What we have decoded so far looks like this:

+----------------------------+ 0x0
| Magic (0xdeadc0de)         |
| Orignal File offset (4)    |
+----------------------------+ 0x8
| 0x00000001                 |
+----------------------------+ 0xc
| Pointer count (2)          |
| Pointer to 0x218           |
| Pointer to 0x330c          |
+----------------------------| 0x18
|                            |
| 516 bytes of unknown data  |
|                            |
+----------------------------+ 0x21c
| 'LRCS' literal             |
+----------------------------+ 0x220
|                            |
| The rest of the file...    |

Taking a closer look at that 516 byte unknown section, starting at offset 0x18, I notice that the first 32-bit word contains the value 256 (0x100). Subtracting the size of this integer leaves 512 bytes of unknown data, or alternatively a 256-long array of 2-byte entries.

Map Layer Data

Starting from the LRCS tag, the data looks something like this:

+----------------------------+ 0x21c
| 'LRCS' literal             |
+----------------------------+ 0x220
| 32-bit word (32)           |
| 32-bit word (32)           |
| 32-bit word (50)           |
| 32-bit word (50)           |
+----------------------------+ 0x230
| 32-bit word (1600)         |
| 32-bit word (1600)         |
| 32-bit word (10568)        |
+----------------------------+ 0x23c
| The rest of the file...    |

I know that the map I made had a size of 50x50 tiles. I also know, from counting the pixels, that a tile is 32x32. It would be reasonable to assume that the first four values (0x220 - 0x230) are the tile size followed by the map size. By quickly making another map with different dimensions, I determined that the coordinates are specified as you'd expect, with width first. Putting that together, we end up with a layer header with the following structure:

+----------------------------+ 0x0
| 'LRCS' literal             |
+----------------------------+ 0x4
| Tile width in Pixels       |      -> value is 32
+----------------------------+ 0x8
| Tile height in Pixels      |      -> value is 32
+----------------------------+ 0xc
| Layer width in Tiles       |      -> value is 50
+----------------------------+ 0x10
| Layer height in Tiles      |      -> value is 50
+----------------------------+ 0x14
| Layer width in Pixels      |      -> value is 1600
+----------------------------+ 0x18
| Layer height in Pixel      |      -> value is 1600
+----------------------------+ 0x1c
| Offset to the attributes   |      -> value is 0x2948
+----------------------------+ 0x20

Between the end of the header and the start of the next 'LRCS' token, there are 12,500 bytes. That's a suspiciously nice and round number. The offset value sits 10,000 bytes into the 12,500 bytes of data. That divides up into:

10,000 bytes of tilemap data, or 50 x 50 x 4 bytes
2,500 bytes of attribute data, or 50 x 50 bytes

In a move that should feel totally familiar by now, each tile in the tilemap is an offset to the tile data within the map file. Blank tiles are represented by a zero value, and all other tiles point to a graphical tile.

Tile Graphics

Now we know (more or less) how the map is composed, the next thing we need to go about displaying it is to figure out the tile graphics format. Luckily there was a clue from earlier that helped a lot. We know that before the layer data there was a 256-entry table of values, contents unknown. This game comes from an era of games using 8-bit graphics composed together into a 16-bit framebuffer. If we assume that the 512-byte data is a palette, we can also assume each tile will be a 32x32 array of 8-bit values with each value corresponding to an entry in the palette.

To test this out, I wrote an application in Rust which decodes the map according to the logic above. You can find the code for this at https://github.com/ucosty/kknd2-mapview.

It works!

Each entry in the tilemap points to a 32x32 blob of raw pixel data. Each pixel value in those tiles points is an index into the palette from the start of the file. There are a few common ways to store colour information in a 16-bit format. Microsoft even have some documentation about a couple of 16-bit colour formats used in DirectShow, with a bit of code to convert between these formats and a standard 24-bit RGB format. After trying both RGB565 (5 bits of Red, 6 of Green, and 5 of blue) and RGB555 (5 bits of Red, Green and Blue), I found the graphics palette is stored in RGB555. There is also a special case, where palette entry 0 is reserved for transparent sections. This isn't useful on the base layer, but is used on the top layer extensively.

Batteries Not Included

As far as I can tell, this map file only contains the graphics and attribute tiles. The rest of the map information, such as unit and buildings, faction information, and other map metadata must be stored elsewhere.

Next, I'm going to take a look into the sprite graphics. Once I have those decoded, and I've found where the unit information is stored, I'd like to extend the map viewer to also display units and buildings.

ucosty.io