Hug maps part 3 - Data structures, features, and bugs



In this part we'll explain some of the data structures the TrackMania track editor uses. This will let us understand how the various bugs and features we've been using work, and how to extend them.

To fully understand this material it will help if you have some background in computer programming.

Note that this information is as best we can determine it from having worked with the editor bugs and a little knowledge of the map file formats. It's not guaranteed to be exactly the way that TrackMania does it.


Data Structures

The TrackMania track editors (all of them as far as we know) use two main data structures to hold the map data: The editor is supposed to keep these data structures in synchronisation. When it fails to do this, we get some interesting effects that we took advantage of in part 1 and part 2.


Bugs and Features

Here's a list of some of the bugs and features we've used so far:
Item Description Bug? TM versions
1. Pressing F1 then F12 leaves the editor in a state between terrain and block editing and allows us to place land in the air. This is a bug. TM 1.2.5 and earlier only.
2. Blocks can be placed on that land. This is not a bug. All versions of TM.
3. When loading a map, certain blocks on land as created above get put into the list of blocks, but they do not get put into the array (correctly). It's at this point that the two data structures go out of synchronisation, and it's very important for us. This is a bug. All versions of TM.
4. Road can be put through these blocks or land under them, etc. Consequence of the above bug (3.) All versions of TM.
5. When we load a map with two blocks in the same cube, they get put into the list correctly, but although the 1st block gets written to the array, the 2nd one then overwrites it (and so on if there are more blocks in the same cube). Again this is a very important feature for us. See the footnote about why this isn't a bug. This is not a bug All versions of TM.
6. Only the last block placed in each cube is considered when placing a new block, i.e. only the last block is checked to see if it joins with the new block OK. Consequence of 5. All versions of TM
7. When a block is deleted, it is removed from the list, and the element(s) of the array which it occupied are cleared. This means that as far as the editor is concerned there are no blocks occupying those cubes. Consequence of 5. All versions of TM
8. Clips are created when blocks are placed, not when the map is loaded. This is not a bug. All versions of TM.
Footnote: The reason item 5 isn't a bug is because we're trying to load data that's considered invalid. In TM a cubelet should never have more than one block in it, so any data that has that breaks what should be an invariant property. From a software engineering point of view, it's a good principle to handle invalid data as gracefully as possible. For playing the map, silently loading such data as best we can is a good strategy. Arguably loading it in the same way in the editor is a bug, because doing so breaks an invariant property of the data structures. Remember, playing the map doesn't involve the 3D array, but loading it into the editor does.

Note: when saving and loading a map, blocks stay in the same order as they were originally placed.

One very interesting thing that you might notice about the above list of bugs and features is that the only one that isn't in every version of TM is the first one - the F12 "land in the air" bug. Therefore in other TM versions we only need to get the editor into some state where a block appears in the list but not in the corresponding part of the array, and then we can do all our block merges etc. no problem. We will look at taking advantage of this in the next part.


More about clips

Clips are just a special type of block that occupies a cube like any other. They're special in that they only say "there's a clip here", and there's no information about the type of clip (well, there's a little to say if it's a ground clip or an air clip), and the information about its rotation is often not used directly. When TrackMania loads a map, it tries to do something clever with the clips - it looks at all the neighbouring blocks and works out whether they need a clip or not, what type it should be, and what rotation it has. This way you can have multiple types of clip in one cubelet even though the block list only says "there's a clip here".

This also means that when you delete a block that has a clip, TM has to again look at all the blocks neighbouring the clip to work out if it should leave a clip there or not. This helps explain the behaviour we described in part 1, step 10, second part.

TrackMania also does other weird "intelligent" stuff with clips, pylons, and terrain, and we'll look at that in some later part.