ucosty.io

KKnD 2 Buildings and Units

Published on the 17th of July 2024

In the first part of this series, I reverse engineered the archive format used by the KKnD 2 game assets. In the second part, I reverse engineered the game's tile map format and wrote a little utility to display the map data. I noticed that the MAPD file did not include any information about units or buildings present on the map, this information had to be stored elsewhere.

Going back to my the KKND map editor, it was easy to create a map with the minimum required number of units. By altering this map in small ways, it was possible to correlate a change in the map editor to the change in the map files.

The first step was to determine which file contained the unit information. A quick comparison of two exported versions of a map, with only one unit position changed, showed that the CPLC file was the only one that was different between versions.

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00000000 de c0 ad de 30 17 0b 00 84 01 00 00 44 17 0b 00 |....0.......D...| 00000010 e4 17 0b 00 44 17 0b 00 78 18 0b 00 04 00 00 00 |....D...x.......| 00000020 00 00 00 00 00 00 00 00 00 00 00 00 b0 17 0b 00 |................| 00000030 00 00 00 00 b0 17 0b 00 00 00 00 00 0b 00 00 00 |................| 00000040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000050 00 00 00 00 01 00 02 00 00 00 00 00 00 00 00 00 |................| 00000060 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000070 00 00 88 13 88 13 88 13 03 00 01 00 05 00 00 00 |................| 00000080 01 00 00 00 00 00 5a 00 09 00 00 00 00 40 00 00 |......Z......@..| 00000090 00 40 00 00 00 00 00 00 78 18 0b 00 44 17 0b 00 |[email protected]...| 000000a0 e4 17 0b 00 44 17 0b 00 04 00 00 00 00 00 00 00 |....D...........| 000000b0 00 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 |................| 000000c0 00 60 03 00 00 80 00 00 00 00 00 00 00 00 00 00 |.`..............| 000000d0 38 18 0b 00 38 18 0b 00 b0 17 0b 00 04 00 00 00 |8...8...........| 000000e0 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................| 000000f0 00 00 00 00 64 00 64 00 32 00 06 00 06 00 06 00 |....d.d.2.......| 00000100 02 00 ff 7f ff 7f 00 00 00 00 00 00 00 00 aa aa |................| 00000110 43 00 00 00 00 a0 01 00 00 c0 01 00 00 00 00 00 |C...............| 00000120 e4 17 0b 00 78 18 0b 00 78 18 0b 00 e4 17 0b 00 |....x...x.......| 00000130 70 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |p...............| 00000140 00 00 00 00 00 00 00 00 02 00 00 00 5f 00 00 00 |............_...| 00000150 7e 00 00 00 00 c0 00 00 00 80 03 00 00 00 00 00 |~...............| 00000160 38 18 0b 00 b0 17 0b 00 00 00 00 00 38 18 0b 00 |8...........8...| 00000170 d7 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................| 00000180 00 00 00 00 00 00 00 00 01 00 00 00 12 00 00 00 |................| Yet another inscrutible hex view

By adding another unit to this map, we can observe the changes to the output. The unit format wasn't quite as straightforward as I imagined it would be. I assumed it would be a simple list, perhaps a value somewhere representing the number of units in the map followed by a simple list. Judging from the diff, it looks like changes were scattered through the whole file.

< 00000000 de c0 ad de 30 17 0b 00 84 01 00 00 44 17 0b 00 |....0.......D...| > 00000000 de c0 ad de 30 17 0b 00 c4 01 00 00 44 17 0b 00 |....0.......D...| --- < 000000d0 38 18 0b 00 38 18 0b 00 b0 17 0b 00 04 00 00 00 |8...8...........| > 000000d0 b8 18 0b 00 38 18 0b 00 b0 17 0b 00 04 00 00 00 |....8...........| --- < 00000120 e4 17 0b 00 78 18 0b 00 78 18 0b 00 e4 17 0b 00 |....x...x.......| > 00000120 b8 18 0b 00 78 18 0b 00 b8 18 0b 00 e4 17 0b 00 |....x...........| --- < 00000160 38 18 0b 00 b0 17 0b 00 00 00 00 00 38 18 0b 00 |8...........8...| > 00000160 38 18 0b 00 b0 17 0b 00 00 00 00 00 b8 18 0b 00 |8...............| --- < 00000190 > 00000190 7e 00 00 00 00 a0 01 00 00 80 03 00 00 00 00 00 |~...............| > 000001a0 e4 17 0b 00 38 18 0b 00 78 18 0b 00 38 18 0b 00 |....8...x...8...| > 000001b0 d7 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................| > 000001c0 00 00 00 00 00 00 00 00 01 00 00 00 12 00 00 00 |................|

The biggest change was the addition of 64 bytes of data to the bottom of the file. This is presumably the new unit. Near the start of the file, right after the file header, a value changed which seems to correspond with the file's size. There are also some seemingly random value changes in a few strategic spots through the file.

Mapping Out the Data

As we saw in the last part, data stored within a KKnD map archive can contain references to other sections of data that are relative to the file's position within the archive. In the case of this example file, the file was originally stored at offset 0xb1730 within the map archive. Since the file is 456 bytes (excluding the header), the possible range of valid offsets is from 0xb1730 - 0xb18f8.

By just eyeballing it, I determined the file header (or at least part of it) looked like the following:

+-----------+-----------+-----------+-----------+-----------+
| File Size | Pointer 1 | Pointer 2 | Pointer 3 | Pointer 4 |
+-----------+-----------+-----------+-----------+-----------+

On a hunch, I went ahead and found all of the values that looked like pointers in the file and decided to map it out.

And here it is

... and that didn't clarify much. I was expecting to see some kind of structure emerge from the chaos, but it felt like every node randomly connected to other nodes with no discernable pattern. I spent a while staring at this diagram, not making much progress, until I started to copy the diagram down on to paper.

When I had made the diagram above, I started at the 'header' and followed the four pointers. I then created nodes for each unique pointer. For each of these new nodes, I repeated the process. This was a simple way to create the diagram, but it prevented me from noticing an important part of the graph.

If, instead of drawing all of the connections at once, I started by only following the first pointer. When it reaches a node, I draw the node and follow that new node's first pointer. I keep going until either I reach an existing node, or hit a NULL pointer.

A more linear diagram

The result was this much more readable diagram. It turns out that the game stores the map entries as a simple linked list, except instead of the nodes being part of one single list (or a doubly-linked list), the nodes are part of 4 different linked lists. The same nodes can be reached in different orders by traversing one of the four different lists.

Filling in the Details

With the general structure of the file figured out, what was left was to understand the contents of each node. I already knew each entity had at least 32 bytes of header data, of which half was made up of linked list pointers. I also knew each entity started with an identifier number, which likely referred to the kind of entity the block of data was for. That left 15 bytes of unidentified data. By comparing the values in the file to the map editor, I quickly realised the remaining two values were the X and Y coordinates of the object on the map. Summarised, that means that each entity has a common header that looks like the following diagram.

Entity header

My next step was to figure out what the IDs correlated to. This was easy enough, fire up the map editor again and drop in one of each unit kind sequentially. I could then parse the resultant file to get a list of entity IDs. Doing this yeilded a map of unit ids to their names.

0x00 => UnitKind::TargetArea,
0x01 => UnitKind::CpuPlayerInformation,
0x02 => UnitKind::DetentionCenter,
0x03 => UnitKind::NewDetentionCenter,
0x04 => UnitKind::MapConfiguration,
0x06 => UnitKind::PatrolPoint,
0x07 => UnitKind::MatrixAnimation,
0x09 => UnitKind::ScrollStart,
0x0a => UnitKind::Reinforcements,
0x0b => UnitKind::EvolvedAltaroftheScourge,
...

There was one more source of information I could use. The map editor wasn't hardcoded with unit and building information, but rather loaded it from a file called Creature.klb. Using ImHex, I wrote a simple parser for the creature library format. I then re-wrote it in Rust, which is what I've used instead of having a hardcoded list of entity names.

In addition to getting a list of entity names, I also got the expected amount of data each entity is supposed to contain. From this I realised most of the entities has exactly the same data - 32 bytes of header followed by 32 bytes of configuration. That left only a small list, 22 of 145, with different amounts of data.

0x0: name = Target area, size = 62
0x1: name = CPU player information, size = 82
0x2: name = Detention Centre, size = 84
0x3: name = Newfashioned Detention Centre, size = 84
0x4: name = Level information, size = 108
0x5: name = Waypoint, size = 76
0x6: name = Patrolpoint, size = 56
0x7: name = Matrix animation, size = 60
0x9: name = Scroll start, size = 52
0x8: name = Multiplayer start position, size = 54
0x112: name = Multiplayer tech bunker, size = 52
0xa: name = Reinforcements, size = 80
0xa8: name = Survivor Small Constructible, size = 68
0xa7: name = Survivor Med Constructibl, size = 68
0xa6: name = Survivor Huge Constructible, size = 68
0xa0: name = Evolved Small Constructible, size = 68
0x9f: name = Evolved Med Constructible, size = 68
0x9e: name = Evolved Huge Constructible, size = 68
0xa4: name = Series 9 Small Constructible, size = 68
0xa3: name = Series 9 Med Constructible, size = 68
0xa2: name = Series 9 huge Constructible, size = 68
0xa9: name = Ripples, size = 54

Bringing it Together

As in the previous two parts, I have another code repository on Github at https://github.com/ucosty/kknd2-cplc-parser. It can parse an extracted CPLC file, and display the parsed results on the console.

If I spent some time parsing the game sprite files, I'd be able to combine this CPLC parser with the map viewer I made for part 2 to display the units and buildings right on the map view. That'll have to be for the next part.

Comments

There have been no comments made yet.

Submit a Comment