Today on project Morrowind, we take decades of research into rendering 3D scene descriptions to beautiful photorealistic worlds and throw it away.

I finally give up on any nontrivial formatting in WordPress and hope it can't mangle text in pictures.

Loading cell data

There are a few catches to parsing cells in Morrowind, the first one being how we can uniquely name one. It's easy with interiors, since each interior has a NAME field, like "Uncle Sweetshare's Workshop" (and that's not a joke). However, there are about three types of exteriors. The first one is cities and notable landmarks - like the example in the picture, those will have a RGNN, a NAME and some coordinates of where the massive exterior square cell is located. However, there are many Vivec cells (since Vivec is really big) and so we'll use the region coordinates as well to identify one.

Secondly, wilderness cells like other parts of the Ascadian Isles Region will be named just using that and their exterior coordinates.

Finally, there are exterior cells without neither a cell nor a region name but with coordinates - those are named Wilderness [x, y] in TES Construction Set, so let's use that as well.

Each one of these cantons is a city by itself and they are all joined by bridges. Also, it's on the water. Who wouldn't want to live here? (from http://www.uesp.net/wiki/File:MW_Map_Vivec.jpg)

The next step is parsing out the contents of each cell, which is basically an ID of an object and other data about the given instance of the reference (for example, the position, the number of hit points (for an NPC) or possible destinations (for doors or NPCs offering travel services)).

Oh, also, references can sometimes be deleted - but instead of them being removed from the data file, they are just marked as deleted. This could be because actually wiping them from the file would imply rewriting the whole file over (since all the pointers in the file would have to be recalculated), a joke now but something that would probably take up way too many resources back in 2002.

One thing that should be noted is that the actual object definitions can appear before or after they are referenced and so we have to parse the file in two passes - first recording just the reference IDs as strings and then linking those to actual Python objects.

Whew, we're done!

In [1]: mages
Out[1]: Vivec, Guild of Mages

In [2]: mages.is_interior
Out[2]: True

In [3]: mages.destinations
Out[3]: [(Vivec, Foreign Quarter Plaza, (-826.792800, 357.833600, 309.695400))]

I haven't included the locations that NPCs in the cell can take the player to (like the teleportation services) in the cell destinations' list - it only lists where the doors in the cell lead to.

The full version is at https://mildbyte.files.wordpress.com/2016/03/graph-2016-2.png, but beware - it's about 10MB large and might break your browser's assumptions about how large PNGs can get.

But even with this information, we can create cool-looking graphs. For example, I produced the picture above with GraphViz, on it the nodes are cells and they are joined with an edge if there's a door between them. The large clump in the middle is Vivec. There are some smaller clusters dotted around, being slightly smaller cities (like Balmora, Caldera or Ald'runh). There are also some hub-spoke formations in there as well, the hub being a named exterior cell and the cells joined to it being the interiors that are accessible through it - these are smaller settlements.

Yet this is not what we came here for. We want to know how to get from point A to point B while exploiting everything this world has to offer us -- not just the doors. So let's talk about how we will define the actual travel graph.

Building a travel planner

Clearly, there's an infinite number of points in the game, but we don't need to look at them all. We only need to consider our start point, our end point and all potential points of interest our travel can go through. So we can easily define the nodes in our graph:

• For every object offering travel "services" (NPCs/doors), the object's location and the travel destination.

• The location of every Divine/Almsivi Intervention marker.

That's it. A description of our route would then be something along the lines of "From the starting point, go to this door (point 1), go through it to a different cell (point 2), walk to the person offering travel services (point 3), travel to a different city (point 4), walk to your destination (point 5)". So let's see how the nodes in the graph can be joined.

• A travel "service" provider's location (a door or an actual teleporter/silt strider driver NPC) is joined to its destination with an edge of length 0.

• If two nodes are in the same cell (or both are in the exterior world), they're joined with an edge of length proportional to the distance between them (so we ignore, say, mountains in the exterior world or impassable obstacles in the interior).

• Every single node is joined to the nearest Temple/Imperial Fort to it (using the straight as-the-crow-flies Euclidean distance for exteriors or the distance from the nearest exterior cell for the interiors).

With this method, I ended up with a travel graph that had 6424 vertices and 16065 teleport-only edges - that includes doors/transport services/Intervention spells but not direct within-cell travel, as it's very easy to find the distance between any two points in that case on the fly.

One interesting thing about shortest-paths algorithms is that finding the shortest path between two nodes (single-pair shortest-path) is as computationally expensive (has the same asymptotic complexity) as finding the shortest path from a fixed node to everywhere in the graph (single-source shortest-path). Intuitively, this is because our ideal path in a single-pair problem could include any point in the graph and so we are calculating the shortest path to that point from our source anyway.

Dijkstra's Algorithm works pretty well for these kinds of things, finding the shortest paths from a single source to everywhere in O(|V|²) (where |V| is the number of nodes in the graph). This can be improved by using a Fibonacci Heap to store unexamined vertices and fetch the closest ones in O(1), giving a time complexity of O(|E| + |V|log|V|). I didn't think just 6000 vertices would make the search take too much time, so didn't implement one, but perhaps will do later.

I used Aryon as a guinea pig for this experiment - he becomes your main questgiver in the latter stages of the House Telvanni questline and happens to live in a fairly isolated tower in the middle of nowhere with almost no travel services. So while you can use Mark/Recall to get to him, his quests can send you across the game world to places reaching which quickly can be nontrivial.

After unleashing Dijkstra upon this graph (which admittedly took 10 minutes, slightly too long) we get two lists: first, for each point, the weight of the cheapest (fastest in this case) route from Aryon to that point. Second, for each point, what is the previous point in the fastest route. Hence we can easily reconstruct the optimal route for a point of interest by following those links.

For example, how do we get from Aryon to Hlormaren, a Dunmer stronghold on the other edge of the island? Like this:

target
Out[35]: (Hlormaren, Dome, (384.000000, -408.000000, 384.000000))
route = chain_prev(prev, target)
route
Out[37]: 
[(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)),
 (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)),
 (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)),
 (Balmora, Guild of Mages, (-755.896600, -1002.733000, -644.627900)),
 (Balmora, [-3,-2], (-22130.610000, -8582.789000, 889.572800)),
 (Hlormaren, [-6,-1], (-43200.000000, -3448.000000, 3072.000000)),
 (Hlormaren, Dome, (320.000000, -256.000000, 402.000000)),
 (Hlormaren, Dome, (384.000000, -408.000000, 384.000000))]

There's a disadvantage here in that we don't actually see the method of travel to get between nodes and so this travel plan takes some game knowledge to decipher. Basically, we want to use a Divine Intervention spell to go to the Wolverine Hall Fort, then enter the Imperial Shrine, unceremoniously walk through it into the Fort interior, enter the Mage's (sic) guild, get ourselves teleported to Balmora and then walk/fly from there to Hlormaren.

How about getting to Sarys Ancestral Tomb, which is located on a remote island on the southwest corner of the map? Easy.

[(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)),
 (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)),
 (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)),
 (Vivec, Guild of Mages, (3.520470, 1391.325000, -385.853300)),
 (Ebonheart, [1,-13], (8703.056000, -100602.000000, 1383.638000)),
 (Bitter Coast Region, [-5,-9], (-37659.390000, -69956.550000, 322.489000)),
 (Sarys Ancestral Tomb, (7028.375000, 4415.659000, 15001.790000))]

We want to again go to the Sadrith Mora Guild and get teleported, this time to Vivec. Then we cast Divine Intervention one more time and end up in Ebonheart, which is a swim away from the island on which the tomb is located.

Next time on project Morrowind, we'll try to make the planner's advice slightly more readable by plotting it on the game map. And maybe plot other things on the map. There might even be some source code!