ucosty.io

KKnD 2 Buildings and Units

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.

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.

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 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.

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.

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.