project Morrowind, part 4

Welcome back to project Morrowind, in which we use technology to oppress people for our own political gains.

A couple of hungover Telvanni wizards came by to my house this Saturday morning. They went to Master Aryon's tower the night before for a round of drinks, which quickly escalated to several rounds of drinks. Long story short, Aryon managed to wander away somewhere and hasn't been seen since. Worse even, a Council meeting was supposed to take place next Monday and Aryon not attending it would be disastrous.

The wizards wondered if I could map out the locations Aryon might possibly be in so they would be able to better concentrate their agents' efforts across various cities in Vvardenfell and recover him before the meeting.

Imagining all kinds of blog posts I could write about this, I agreed.

Regenerating the graph

I first had to alter the weights between the edges on the travel graph, since in actual game time travel by silt strider or boat isn't instantaneous. But it's easy to calculate from the distance anyway: the speed of travel is in a game setting that defaults to 16000 units per game hour. For example, the distance between Seyda Neen and Balmora is about 55000 units, so if in the beginning of the game you decided to spend money on public transport instead of walking, you would get to Balmora and finish your first quest in less than 3.5 game hours.

Determining the walking time between locations also required some digging. The minimum walking speed in the game is 100 game units per real-world second and the game time by default flows 30 times faster than real time. So walking 16000 units would take about 16000 / 100 * 30 / 3600 = 1h20m of game time. As you see, this is not much slower than taking the silt strider and if you saw one you would realise why.

Obviously, if our travel NPC has "Guild Guide" in his class name, traveling with him doesn't take any time - because magic.

Having rebuilt the graph and re-run Dijkstra on it, we can easily determine how long it would take Aryon to reach any point in the game world, assuming he uses the fastest route. Go through all points in the graph we know the shortest travel time to and find the one for which the total travel time (shortest time to travel to that point + time to walk from that point to the destination) is the smallest.

There is an optimisation which I haven't done: we actually only care about points on the graph where we can get by any other route than plain walking. Consider this: if a shortest path to a point is formed by first teleporting to some point A, then walking to point B and then finally walking to point C (all in a straight line), why not walk from A to C directly (we're assuming here that Aryon can levitate and move between the points as-the-crow-flies, so any 3 points that are in the exterior follow the triangle inequality).

But of course just giving the Telvanni wizards a list of in-game coordinates would be a faux pas. They required a map, and a map I would provide. An affine map, of all things.

A quick, incomplete and mostly wrong introduction to linear algebra

The problem here is that we want to find a way to convert a pair of pixel coordinates on the game map to coordinates in the game world. Luckily, this transformation has an important property: a line between any two points on the game map is also a line in the actual world. Such transformations are called affine: they can be composed out of primitive operations like translation, rotation, reflection etc.

The good news is, they can be represented by a matrix product.

$$ \begin{pmatrix}x_{GAME} \\ y_{GAME} \\ 1 \end{pmatrix} = M \begin{pmatrix}x_{MAP} \\ y_{MAP} \\ 1\end{pmatrix} $$

So if we have a pair of map coordinates and this 3x3 matrix M, we'll be able to calculate the actual in-game coordinates, and vice versa. The third component of the vector being 1 is an ugly hack that allows us to encode translations (movement), since otherwise the vector (0, 0) on the map would map (he-he) to the vector (0, 0) in the game. More on Wikipedia.

How do we find such a matrix? Well, we can use it to transform several vectors at the same time:

$$ \begin{pmatrix}x_{GAME, 1} & x_{GAME, 2} & x_{GAME, 3} \\ y_{GAME, 1} & y_{GAME, 2} & y_{GAME, 3} \\ 1 & 1 & 1 \end{pmatrix} = M \begin{pmatrix}x_{MAP, 1} & x_{MAP, 2} & x_{MAP, 3} \\ y_{MAP, 1} & y_{MAP, 2} & y_{MAP, 3} \\ 1 & 1 & 1 \end{pmatrix} $$

And (by inverting the matrix on the right and multiplying the whole equation by it) this can be rewritten to

$$ M = \begin{pmatrix}x_{GAME, 1} & x_{GAME, 2} & x_{GAME, 3} \\ y_{GAME, 1} & y_{GAME, 2} & y_{GAME, 3} \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}x_{MAP, 1} & x_{MAP, 2} & x_{MAP, 3} \\ y_{MAP, 1} & y_{MAP, 2} & y_{MAP, 3} \\ 1 & 1 & 1 \end{pmatrix}^{-1} $$

Essentially, if we get 3 sets of coordinates in the game world and on the map, we can use those to recover our mapping. These 3 points also can't be on the same line because then the determinant of the matrix of map coordinates is zero and it doesn't have an inverse.

So I picked the game coordinates of 3 locations that were fairly well spread (to minimize the error) and tried to pinpoint the corresponding pixel coordinates on the map.

In the end this is the matrix I found:

$$ M = \begin{pmatrix}185.38 & -0.43327 & -126720 \\ 1.2986 & -0.018372 & 218470 \\ 0 & 0 & 1 \end{pmatrix} $$

To test it out, I plotted the three reference points I used to calculate it (in red) as well as Aryon's initial location (in blue): the exterior door to his house is located at game coordinates (85730.77, 117960.3, 5081.284) which he matrix mapped to (1147.33, 555.21).

I can see your house from here! (the actual map comes from http://thegamersjournal.com/rpg/pc/morrowind/maps/map_rendered_m.jpg)

This edition of project Morrowind was overdue by about two months, so I sadly have to stop here. But next time I'll definitely tell you how we managed to track Aryon and save the Telvanni council from collapse.