Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 3

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Introduction

Last time, I showed a way to generate a decent route through the quest graph as well as came up with a rough character progression that can be used to quickly complete all faction questlines in Morrowind.

Today, I'll analyse Mark/Recall and other miscellaneous transport modes, deal with an interesting Temple quest, showcase the final route and finally publish the code for the route planner.

Here's a map of the route for those of you who like migraines:

The points of interest here are joined with colour-coded lines. White is walking or flying, red is Mages Guild teleports, blue is Almsivi/Divine Intervention spells, yellow is travel by boat/silt strider and green is Recalls.

Total Recall

Mark/Recall are a pair of spells in Morrowind that allow the player to teleport around the game world. Casting Mark remembers a given place and Recall teleports the player to the last position the Mark was cast. Only one Mark can be active at a given time: casting it again removes the previous Mark.

Imagine casting Mark at the beginning of a dungeon (unlike Skyrim, Morrowind dungeons don't have a quick shortcut back to the start of the dungeon from its end) and teleporting there, or placing a Mark next to an NPC providing transport services. This could shave a considerable amount of time from the route.

There are several questions here. Firstly, given a route, what's the most efficient arrangement of Mark and Recall casts for it? Secondly, can we change the optimiser to take into account the Mark/Recall spells? The most optimal route through the quest graph might not be the most optimal when Mark/Recall spells are used.

Single Mark

For now, imagine we have already settled on a route and can only place a Mark once in the game, in fact only at one node in the quest graph (and not anywhere on the route between nodes). What's the best place for it?

Since we have a matrix of fastest node-to-node travel times, given a Mark position, at each node in the route we can decide whether we want to proceed to the next node directly or by first teleporting to the Mark and then going to the next node. Try placing a Mark at each the nodes in the route and see which one gives the fastest overall time:

def get_best_mark_position(route):
    return min(
        # can't use the mark until we've placed it
        (sum(get_node_distance(r1, r2) for r1, r2 in zip(route[:i], route[1:i]))
         + sum(
            # after placing the mark, we have a choice of recalling to it and going to the next node
            # or going to the next node directly
            min(get_node_distance(r, r2), get_node_distance(r1, r2)) for r1, r2 in zip(route[i:], route[i + 1:])),
         i, r) for i, r in enumerate(route)
    )

I ran that and found out that by far the best position for a single Mark was right at the questgiver who's standing next to the Mages Guild teleport. This makes a lot of sense: a Recall to the Mages Guild gives the player instant access to 4 cities. Coupled with Intervention spells, this lets the player reach essentially any town in the game within a matter of minutes, if not seconds.

Multiple Marks

Now, again, given a single route through the quests, let's allow the player to place multiple Marks so that they can Recall to the last one they placed.

I first tried the same idea that I did for the route optimiser: take multiple possible arrangements of Marks (basically a Boolean array of the same length as the route that determines whether, at each node, we place a Mark there or not after we visit it), mutate each one (by randomly adding or removing Marks) and score it (sum up the decreased travel costs by considering at each node whether it's better to proceed to the next node directly or via a previous Mark).

I let this run for a while but it wasn't giving good results, quickly getting stuck in local minima. A big problem with this approach was that it didn't consider placing Marks in places visited between nodes, which excluded strategies like placing a Mark at the beginning of a dungeon (while a door to the dungeon is a point in the travel graph, it isn't a point in the quest graph).

To do that, I'd have to have a matrix of best travel times between each pair of nodes in the travel graph, not just the quest graph. Given how long my implementation of Dijkstra took to create the matrix for 100 nodes, I wasn't going to get away with reusing it.

Speeding things up

Floyd-Warshall is the nuclear option of pathfinding algorithms. Instead of finding shortest paths from a single source like Dijkstra would, it finds the shortest paths between any two vertices in the graph. Not only that, but it does in \( \Theta(V^3) \), independently of the number of edges, making it perfect for dense graphs.

It took about 15 minutes to run my Python implementation of Floyd-Warshall on the coalesced 700-node graph. But this wasn't enough. I realised that coalescing vertices in the same in-game cell to a single one was giving strange results, too: for example, each node had an Almsivi/Divine Intervention edge towards the nearest Temple/Imperial Cult Shrine that has a weight considerably larger than zero (due to the fact that the central vertex for that cell was far away from the actual teleportation destination) and I was wondering if that could be skewing the route.

I hence decided to rerun the route planner on the full unprocessed 6500-node graph and rewrote the Floyd-Warshall implementation in C++. It still took 15 minutes to run it, but this time it was on the whole graph. Most of this time, in fact, was spent loading the input and writing the output matrices, since I serialised those into text and not binary.

And by that point I was on a roll anyway and rewrote the route planner in C++ as well. The Python program would now instead export the quest node distance matrix and the dependency graph to a text file. I didn't perform detailed measurements, but it definitely became a couple of orders of magnitude faster.

Adding Mark/Recall awareness to the optimizer

I tried rerunning the Mark/Recall planner on the fully expanded route (which enumerates each vertex on the travel graph) but by this point, it was getting more and more clear that simply maintaining a Mark at any Mages Guild teleporter was a really good option that was difficult to improve on.

This is a slightly trippy picture, but it's basically a contour plot that shows the average travel time (in real seconds, assuming a travel speed of about 750 units per second, which is achievable with an artifact that I'll talk about later) to any node in the quest graph from any point in the travel graph, interpolated using nearest-neighbour on pixels that didn't map to any points on the travel graph. I also added a travel cost of 5 seconds to public transport and Mages Guild teleporters. This was to account for the time spent in the game's UI as well as to nudge the optimiser into flailing less around multiple towns.

Strictly speaking, I should have actually calculated the average time at each pixel, but this picture is good enough. The colour map here ranges from blue (smallest average travel time) to green (largest). For example, Vivec (south of the game map) has the largest average travel times to any point of interest in the route. This is because the Temple of Vivec (one possible destination of an Almsivi Intervention spell) is on the other side of the city from other transport modes (boats/silt striders/Mages Guild) and so anyone near Vivec would have to first teleport to the Temple and then walk across the city to continue their journey.

On the other hand, despite being basically a wasteland, the southeast corner of the map has good travel connections: this is because a Divine Intervention spell takes the player to Wolverine Hall on the east side, right next door to the Mages Guild.

Silent Pilgrimage

There's a cool quest in Morrowind's Temple questline that involves the player completing a pilgrimage from the southernmost part of the game map to the northernmost. Sounds easy, right? Well, the only problem is that the player can't speak to anyone during the pilgrimage, which means the player can't use any public transport or Mages Guild teleports.

The honest way to do this is to actually walk or levitate the whole distance, which would take a few minutes even with Speed-increasing spells. The mostly-honest way to do this would be casting Divine/Almsivi Intervention spells in strategic places that would teleport the player part of the way between the spheres of influence of different Temples/Imperial Cult shrines. The dishonest way would be casting a Mark at the shrine during a previous visit and simply Recalling there when the pilgrimage starts.

However, the first version of the route planner wasn't really aware of that quest. I had a "Set Mark at Sanctus Shrine" graph node and a "Do the Sanctus Shrine quest" node, but the optimiser wasn't encouraged to put them close together. In the best route it had come up with, those two nodes were far apart and about 3/4 of the route was with the Mark stuck at the Shrine.

Hence, if we want to maintain a Mark at a Mages Guild, we also have to juggle that with having a Mark at the Sanctus Shrine in order to complete the Silent Pilgrimage. So the question now was kind of an inverse one: given that we can teleport to a Guild at any time (except for when the Mark is at the Shrine and so we'd get teleported there instead), what's the best route through the game quests?

I decided to produce two travel graphs: when there's a recall edge to a Mages Guild (it doesn't matter which one, since we can almost instantaneously teleport to any of them once we're there) and when there's a recall edge to the Sanctus Shrine.

The optimiser would get these two versions of the node-to-node distance matrix as well as the instructions specifying which matrix to use when. That way, it could also try to exploit the Mark in the northern part of the game map.

The best route it could come up with (not counting time spent in dialogue, combat, training or getting all required items/money at the start at the game) now took about 2500 seconds of real time, which looked quite promising.

Propylon Chambers

There's a mode of transport in Morrowind that I hadn't mentioned at all: Propylon Chambers. They're located inside 10 ancient Dark Elf strongholds that are scattered roughly in a circle around the map. Each stronghold has a Propylon Index that's hidden somewhere in the game world, and discovering a given stronghold's Index allows the player to travel to that stronghold from either of the two adjacent to it.

(from http://stuporstar.sarahdimento.com/other-mods/books-of-vvardenfell/key-to-the-dunmer-strongholds/)

Can they be useful here? After looking at their placement, it sadly doesn't seem so. Firstly, there are very few strongholds that are closer to quest objectives than ordinary towns and secondly, their Indices are often in inconvenient places (for example, the Rotheran Index is located in Rotheran itself).

But perhaps it's worth including Propylon Chambers in the route anyway? To test that, I assumed that the player has all Propylon indices from the beginning and regenerated the travel graph with the addition of teleportation between adjacent Dunmer strongholds. This would provide a lower bound on the route length and show whether there is enough time saving to make getting any of the Indices worthwhile.

Turns out, there really isn't. The best route without Propylon Chambers takes about 2500 seconds, whereas including them improves the route by only two minutes. There are a few places the optimiser decided to exploit this method of teleportation:

• When performing quests around Suran, going to Marandus and teleporting to Berandas in order to get the Boots of the Apostle in that stronghold.
• Then teleporting from Berandas to Falensarano on the eastern part of the game map to get Ring of the Wind from the cave nearby as well as (later on) deliver an item to a mine.
• Teleporting to Valenvaryon several times for easier access to the island north of the map.
• Teleporting from Hlormaren (a stronghold west of Balmora) to Falasmaryon where the Marksman master trainer lives.
• Teleporting from Berandas to Rotheran close to the end of the route to grab the Ice Blade of the Monarch (located in that stronghold).

Given that simulating actually getting the Indices would also be a pain (I'd have to keep track of the optimal travel time between any two quest nodes for when the player has any combination of indices out of \( 2^{10} = 1024 \)), I decided to skip them for now.

Opening gambit and various exploits

There are a few things that are worth doing at the beginning of the game to ensure a smooth progression through the route as well as raise enough money to pay our way through training and some faction quests.

I'd use enchantments for most of the in-game activities, including dealing damage, teleporting and movement. Enchantments are spells that can be put on equipment. They require a soul gem to produce, which determines how much charge the item will have, but enchanted items recharge over time, don't use up player's Magicka reserves and spells cast from them can't fail and are instantaneous. This means that teleporting takes a few seconds faster since we don't need to wait for the cast animation, but more importantly, casts can't be interrupted by someone hitting the player.

The items enchanted with all three types of teleportation (Divine/Almsivi intervention and Recall) are easily obtained at the beginning of the game: the first two during Edwinna Elbert's initial questline and the final one can be bought from a merchant in Caldera. I hence changed the optimiser a bit to always have these two starting nodes (Ajira and Edwinna's Mages Guild quests) at the beginning of the route and would do some more preparation as part of these before proceeding.

Dealing damage

I had played around with various ways of dealing damage to NPCs. I first thought of using Blunt weapons, since the player would have to train that skill anyway and one of the best Blunt weapons has to be acquired as a part of an Imperial Cult quest, but it still takes several swings to kill anyone with it, since the player can miss, especially at lower skill levels.

Then I remembered about the Drain Health enchantment: it reduces the target's maximum health by a given number of points. It's supposed to be used as a cheap way to weaken the enemy, but it can also be exploited. If one casts Drain Health 100pt on someone, even for one second, they will die if they have fewer than 100 hit points. Paired with a 100-point Weakness to Magicka effect, this allows for a cheap way to kill anybody with fewer than 200 hit points, which is an overwhelming majority of game characters.

Movement

Despite all the teleportation, there still is a lot of walking to be done in the game. While the character will have access to Fortify Speed potions, I only wanted to use them for long movement segments, since making enough of them to cover the whole route would take too much time.

Thankfully, there is an artifact in the game that gives the player a constant Fortify Speed effect: Boots of Blinding Speed. They boost the player's speed by 200 points (essentially tripling it) at the expense of blinding (it's in the name) the player. The blinding effect can be resisted: if the player has a Resist Magicka spell active for the split second when they put the boots on, the effect is nullified.

Moreover, levitation is important, since it allows the player to bypass various obstacles as well as avoid annoying enemies. Due to the way levitation speed is calculated (the main component is the sum of player's Speed and the levitation effect magnitude), 1 point of Levitation is sufficient for the player to start flying and it's cheaper to increase speed by manipulating the character's Speed attribute. 1 point of Levitation for about 90 seconds would be another enchantment.

Unlock, frenzy

Chests and doors in Morrowind can have a lock with a level ranging from 1 to 100. Hence, we'd need to also enchant a piece of clothing with Open 100pt.

There are quite a few times in the route where we need to kill someone who's not attacking us without attracting the guards' attention (like when doing Morag Tong assassinations before the actual quest starts). One way to do it is taunting the NPC until they attack, which takes time and needs a moderately high Speechcraft skill. Luckily, there's a magic effect for that, too. Frenzy increases the Fight rating of an NPC and 100pt for 1 second is enough to make them attack the player. When the effect wears off, they don't stop attacking and can be slain in self defence without legal issues.

Alchemy feedback loop and fundraising

When a player creates a potion in Morrowind, their chance of success as well as the potion's strength, duration and value is partially governed by the player's Intelligence attribute.

The player can also create a potion that boosts their Intelligence attribute.

Do you see how the game can be broken with this? There's no limit on how many potions the player can consume per second and there's no cap on the player's Intelligence. Hence we can have all our monetary problems taken care of by exploiting this and repeatedly creating stronger and stronger Intelligence potions to sell. Not only that, but we can also use this to create Restore Health potions that restore player's health faster than anybody can damage it as well as use the Intelligence boost to create enchanted items manually (instead of paying a specialist to do it). Finally, we can also create Fortify Speed potions that increase the player's raw speed.

There are merchants in Morrowind that restock some of their ingredients as soon as the player stops trading with them and lots of them sell ingredients for Fortify Intelligence and Restore Health potions.

We need about 75000 gold pieces to get through the game, including all training and faction quests. Luckily, there's a merchant in the game that has 5000 gold in his inventory and buys items at face value. My tests showed I needed about 150 Health potions to get me through the game, so I'd sell any extra ones to the Creeper to get me to the target number.

Fortifying player's Speed (beyond the boost provided by the Boots) is more difficult: there are only two ingredients in the game that restock and provide the Fortify Speed attribute, Kagouti Hide and Shalk Resin. However, they are quite expensive (52 gold pieces in total for the two) and also have a Drain Fatigue side effect (which makes the player lose consciousness when their Fatigue is close to zero). Hence they have to be paired with another two ingredients that have a Restore Fatigue effect.

Final route

Here's the final route that I came up with: it opens with the sequence of money-making and enchantments that I had described before and then continues with the list of things to do that was produced by the optimiser. This initial sequence took me about 28 minutes to complete and the rest of the route is located here. I also uploaded the route that assumes the player can use all Propylon Chambers here.

• Create the character (build). Steal the Limeware Platter from the Census & Excise office before leaving and pick up the Ring of Healing from the barrel on the way.
• Give the ring to Fargoth to boost relationship with Arrille. Go there, sell the platter, buy a Resist Magicka Spell, 2 Drathis' Winter Guest scrolls and an Iron Warhammer.
• On the way to the silt strider, grab the 4 types of mushrooms (needed for Ajira's first quest). Take the silt strider to Balmora.
• Join the Mages Guild, take all supplies from the chest and take the Ceramic Bowl from Ranis Athrys' table. Go downstairs to Estirdalin and make a spell of Resist Magicka 100% on Self. Hand in the first Ajira quest. Teleport to Caldera Mages Guild.
• Steal the alchemy set from the tower in the Guild as well as 1 Dreugh Wax (needed for the Seven Graces quest).
• Go north-west towards Gnaar Mok to meet Pemenie. Kill her with a combination of Thunder Fist (Nord racial power), the Drathis' scrolls and the Warhammer.
• Use the Fortify Willpower and Restore Magicka potions from the supplies chest to successfully cast Resist Magicka spell and equip the Boots. Use the Almsivi Intervention scroll to go to Ald-Ruhn.
• Go to the Mages Guild, take all supplies from the chest there.
• Buy 2 Mark scrolls from Tanar Llervi (she sells one at a time but they restock after leaving the Barter menu).
• Take Mages Guild teleport to Balmora, place a Mark while facing Masalinie Merian (Guild teleporter).
• Do all remaining Ajira quests:
  • Make sure to steal the Grand, the Large and the two Common Soul gems as well as the Platter and any other Soul Gem (needed as a donation for a Temple quest) during the second quest.
  • Flowers: Willow Anther and Heather can be bought from Ajira herself. The other two can be stolen from Millie Hastien's shop. On the way there, sell the Platter to Ra'Virr next door.
  • Sell all rewards (potions) back to Ajira to have roughly 1000 gold for the next part.
• Mages Guild teleport to Sadrith Mora, Go to Aunius Autrus in the Imperial Shrine.
• Alchemy loop time!
  • Use all money to continuously buy 10 Ash Yam, 5 Bloat and 5 Netch Leather from Aunius Autrus (should roughly end up with 260, 130 and 130 of each, respectively).
  • Use all Bloat and half of Ash Yams to make Intelligence potions, drink them all.
  • Use all Netch Leather and Ash Yams to make Intelligence potions, sell enough to Aunius to get all his money, drink the rest.
  • Go to Scelian Plebo and buy 10 Saltrice and 10 Marshmerrow 30 times.
  • Make 300 Restore Health potions with these ingredients. Sell enough Health potions to Scelian to get all his money.
• Buy Drain Blood (has the Drain Health effect) and Frenzying Touch (has the Frenzy Humanoid effect) from Uleni Heleran in the Mages Guild on the way back.
• Teleport to Balmora, Almsivi Scroll to the Temple.
• Go to Nalcarya of White Haven. Buy 1 diamond (future Thieves Guild quest) and 4 Daedra Hearts (future Temple quest), sell her enough potions to drain her of money.
• Go to Millie Hastien next door. Buy 1 Exquisite Amulet, 1 Exquisite Ring, 1 Extravagant Pants and an Extravagant Belt.
• Back to Balmora MG, buy spells from Marayn Dren: Levitate, Ondusi's Open Door, Dire Weakness to Magicka.
• Whilst still under the effect of Intelligence potions, make the following enchantments:
  • Exquisite Amulet: Weakness to Magicka 100% on Touch, Drain Health 100% on Touch (use the stolen Grand Soul Gem).
  • Expensive Belt: Levitate 1pt 90s on Self (use the stolen Greater Soul Gem)
  • Exquisite Ring: Open 100pt on Touch (Common Soul Gem)
  • Expensive Pants: Frenzy Humanoid 100pt on Touch (Common Soul Gem)
• Do hotkeying. I prefer having the Amulet on 1, Belt on 7, Ring on 8 and Pants on 9.
• Whilst still under the effect of Intelligence potions, teleport to Sadrith Mora.
• Buy 100 Shalk Resin and 100 Kagouti hide from Pierlette Rostorard (will need to sell her Health potions a couple of times in order to afford the ingredients).
• Buy 100 Hound Meat and 100 Scuttle from Threvul Serethi.
• Make 100 potions of Fortify Speed (+ Restore Fatigue) from these 4 ingredients. Alchemy should be slightly beyond 70 by this point (requirement for some Guild promotions). Hotkey Speed potions to 2.
• Recall and teleport to Caldera. Sell Restore Health potions to Creeper until have about 75000 gold. Hotkey remaining ones to 3.
• Recall, buy 6 Drathis' Winter Guest scrolls from Galbedir and buy Chronicles of Nchuleft from Dorisa Darvel, then steal a Dwemer Tube from Vorar Helas' house.
• Recall, teleport to Ald-Ruhn and do all Edwinna Elbert quests up to and including Dwemer Tube. Should be rewarded with the Almsivi and Divine Intervention amulets. Hotkey those to 4 and 5, respectively.
• Proceed as per the rest of the route.

Finally, there are several NPCs that have to be killed as part of the run and have to be damaged first before they can be killed with the Amulet, either with the Drathis' scrolls or with the Iron Warhammer/Skull Crusher when it's picked up:

• Relas Arothan has one Sanguine Item required for extra Morag Tong reputation.
• Lorbumol gro-Aglakh needs to be killed as part of the Fighters Guild questline. While he has 199 health, he has some natural magic resistance, decreasing the effect of the amulet.
• Burub gra-Bamog also has some natural resistance to Magicka.
• Orvas Dren, brother of the Duke and head of the local criminal syndicate, has to be killed as part of the House Hlaalu questline and has 250 hit points.
• Varus Vantinius is the current head of the Imperial Legion and has to be killed in a duel to finish that faction's questline.

Conclusion

I think that's it! The code to produce most of this is on my GitHub, together with the code from the previous set of articles. One day I might even actually record myself trying to follow this route, but I'm sure actually planning it out is more fun that running it.

Finally, feel free to follow me on Twitter at twitter.com/mildbyte!

Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 2

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Introduction

Previously, we left off by converting the problem of finding a route that completes all faction questlines in Morrowind into the general case of the travelling salesman problem with dependency constraints. Today, we'll come up with a way to produce a good enough solution to it.

Generating a travel time matrix

There are two graphs I'm talking about here: one is the quest dependency graph from the previous part and the other one is the travel graph that I had generated back in an earlier article.

The dependency graph had about 110 geographically distinct nodes at this point, so the first order of business was creating a matrix of fastest routes and travel times between any two of those nodes, since the final route could indeed include travelling between any two points.

To do that, I used Dijkstra's algorithm: since it's an single-source-shortest-path algorithm, if I ran it for one geographical node in the quest dependency graph, I'd get shortest routes (on the travel graph) to all other points. Hence I only had to run it a hundred times.

There was a problem, though: the travel graph had about 6500 vertices and 16000 teleportation edges (that is, travelling with public transport or using an Almsivi/Divine Intervention spell: this doesn't include actual physical travel edges between points in the same cell). It took about 10 minutes to run Dijkstra for a single source, so I was looking at spending about a day generating the travel time matrix.

Hence I decided to prune the travel graph a bit by coalescing vertices that were in the same cell. For every cell (interior or exterior), I'd replace all vertices in it with a single one with average coordinates and then recalculate the cost of travelling between them:

def coalesce_cells(vertices, edges):
    # Replaces all vertices in the graph in the same cell with a single one (average location)
    vertices_map = defaultdict(list)

    for v in vertices:
        vertices_map[v.cell].append(v)

    # Calculate the average vertex for each cell    
    average_vertices = {}
    for cell, vs in vertices_map.items():
        coords = tuple(sum(v.coords[i] for v in vs) / float(len(vs)) for i in range(3))
        average_vertices[cell] = Location(coords=coords, cell_id=vs[0].cell_id, cell=vs[0].cell)

    new_vertices = set([average_vertices[v.cell] for v in vertices])

    # Group edges by average vertices they belong to
    grouped_edges = defaultdict(lambda: defaultdict(list))
    for v1 in edges:
        av1 = average_vertices[v1.cell]
        for v2 in edges[v1]:
            av2 = average_vertices[v2.cell]
            # Calculate the new edge cost
            grouped_edges[av1][av2].append((edges[v1][v2][0], get_distance(av1.coords, v1.coords) / WALKING_SPEED + edges[v1][v2][1] + get_distance(v2.coords, av2.coords) / WALKING_SPEED))

    new_edges = defaultdict(dict)
    for av1 in grouped_edges:
        for av2 in grouped_edges[av1]:
            # Replace all possible edges between the two new vertices with the cheapest one
            new_edges[av1][av2] = min(grouped_edges[av1][av2], key=lambda md: md[1])

    return new_vertices, new_edges

With this pruning, the travel graph shrunk to about 800 vertices and 2200 teleportation edges and I successfully managed to create a matrix of fastest travel times between any two nodes on the dependency graph.

Here's one of cool things you can do with such a distance matrix: use a clustering algorithm to visualize clumps in which quest points of interest are organized (the image is clickable).

For example, the top left corner of this heatmap has a group of NPCs that are all located on a set of remote islands at the north of the game map. Getting to them is a pain and takes a lot of time, hence it's worth arranging our quests in such a way so that we only have to visit there once.

Simulated annealing (genetic algorithm?)

Let's now say we have a candidate route, which is one of topological sorts of the dependency graph. We can see how long this route takes by simply adding up the cost of travel between consecutive nodes using our cost matrix.

How would we find an optimal route? Brute force won't help here. I decided to do a slightly less stupid thing: let's take a route and randomly perturb it. Sure, the route we end up with might be less efficient than it was before. But imagine we do that for tens of thousands of randomly generated routes, keeping a fraction of them that's the most efficient, randomly perturbing the best routes again and again. Eventually we'd converge on a decent route, if not the most optimal one.

The final algorithm I used is:

• Start with a pool of candidate routes: take a single topological sort and repeat it 20000 times
• Do until I get bored and terminate the optimization:
  • sort the routes by their total time, keep top 1000
  • for each remaining route:
    • generate 20 candidate routes from it:
      • pick a random point in the route and move it a random number of steps up or down
      • check the dependency graph is still satisfied, if not, try again
      • do this perturbation 30 times
  • the pool now has 20000 routes again, repeat

Of course, the actual constants can be played with and the termination condition could be better defined. Some call this a genetic algorithm (where we kind of simulate evolution and random mutations in the gene pool), some call it simulated annealing (where the magnitude of random perturbations decreases over time until the solution pool settles down). "Genetic algorithm" sounds sexier, which is why I mentioned it in this paragraph.

I left this to run overnight and in the morning came back what seemed to be a decent route through the game.

The times here were inferred from in-game travel distances, assuming the minimum walking speed of about 100 game units per second. Of course, there are potions and spells to increase the player's walking speed. In addition, this doesn't account for the time spent in the menus or actually killing whatever the player is supposed to kill.

Overall, there are some things the optimiser came up with that made me go "aha!".

I wrote a pretty printer that would take the graph nodes and expand them into an actual travel plan that uses Almsivi/Divine Intervention spells and public transport. In this fragment, for example, the route planner set up the faction questline progress just right so that all six objectives in the desolate southwest corner of the map could be completed in one go (lines 592-618).

However, there are a few problems with this route:

• It doesn't account for the uses of Mark/Recall spells. These are immensely powerful: a Recall teleports the player to the location of the last time a Mark spell was cast.
• It doesn't account for skills training in order to progress through faction quests.

Skills training

Advancement in Morrowind factions requires not only quest completion, but also skills training. I had already mentioned that while we can pay to train a skill, it can't be trained above its governing attribute.

Attributes can only be raised when the player levels up. A game character has 5 out of 27 skills as major skills (which lets them level faster and gives a flat +25 bonus to them at the beginning of the game) and 5 minor skills (which also lets them level faster, albeit not as fast as major skills, and adds a +10 bonus). The character levels up when they have gotten 10 points in their major or minor skills.

This is where it gets weird. At level up, the player picks 3 attributes to raise. How much they are raised by is determined by the skills the player had trained. For example, if they got 10 points in Alchemy (governed by Intelligence), then, if Intelligence is picked at level up, it will increase by 5 points instead of 1. However, if the player had leveled up by training 1 point in Long Blade (governed by Strength) and 9 points in Alchemy, they'll only get a 4x multiplier to Intelligence and 1x to Strength.

The player can also train skills that aren't major or minor to get enough points to boost the attribute multiplier. Let's say the player also trains 1 point in Security (governed by Intelligence) which isn't their major or minor skill. It won't count towards the 10 points required for a level up, but it will count towards the attribute multiplier calculations. Hence the player will be able to raise their Intelligence by 5.

I hence had to tactically choose my character's major/minor skills as well as the race (which gives bonuses to certain skills and attributes) in order to be able to quickly meet each faction's expectations.

Overview of factions and required skill levels

This is a list of skill levels that each faction requires in order for the player to be able to become the head of that faction. Note that this might not necessarily meet the skill requirements for the highest rank of that faction, since most factions stop checking the player's credentials during their final questlines and just promote the player to the highest rank once the questline is completed.

• Mages Guild: Alteration, Destruction, Alchemy, Enchant, Illusion, Mysticism. One skill at 70, two at 25, Intelligence and Willpower 33.
• Fighters Guild: Axe, Long Blade, Blunt Weapon, Heavy Armor, Armorer, Block; 70/25/25, Strength and Endurance 33.
• Thieves Guild: Marksman, Short Blade, Light Armor, Acrobatics, Sneak, Security; 80/30/30, Agility and Personality 34.
• Tribunal Temple: Alchemy, Blunt Weapon, Conjuration, Mysticism, Restoration, Unarmored; 80/30/30, Intelligence and Personality 34.
• Morag Tong: Acrobatics, Illusion, Marksman, Light Armor, Short Blade, Sneak; 80/30/30. Speed and Agility 34.
• Imperial Cult: Speechcraft, Unarmored, Restoration, Mysticism, Enchant, Blunt Weapon; 90/35/35. Personality and Willpower 35.
• Imperial Legion: Athletics, Spear, Long Blade, Blunt Weapon, Heavy Armor, Block; 70/25/25. Endurance and Personality 33.
• House Hlaalu: Speechcraft, Mercantile, Marksman, Short Blade, Light Armor, Security; 70/25/25. Speed and Agility 33.

Character planning

With that in mind, I decided to have Alchemy, Blunt and Marksman as high level skills. Alchemy (main skill for the Mages Guild) could be trained really quickly by making potions. Blunt was shared between 4 factions (Fighters Guild, Temple, Imperial Cult and Imperial Legion) and would have to be trained to 90. Marksman would cover the other 3 factions (Thieves Guild, Morag Tong and House Hlaalu) and trained to 80.

The other skills had to be chosen partially to cover the remaining, weaker requirements, partially so that training them would boost either Strength or Agility to 90 or 80, respectively (otherwise Blunt or Marksman wouldn't be possible to be trained). I hence decided to go for a character that starts with high Strength and a bonus to Blunt weapons and train Long Blade to boost Strength (and cover the Fighters Guild/Imperial Legion secondary skill requirement).

For Agility, I would train Block, Light Armor and Sneak. All three of those are governed by Agility and training them to required levels would result in Agility being boosted enough to allow me to train Marksman to 80.

Enchant and Mysticism would cover the secondary requirements for the Temple, the Mages Guild and the Imperial Legion.

Here's the final character sheet. The major and minor skills that she starts with are:

• Major:
  • Alchemy: 35. To be trained to 70 by making potions (main skill for MG, secondary skill for T).
  • Blunt: 40. To be trained to 90 (main skill for FG, IL, IC and T).
  • Marksman: 30. To be trained to 80 (main skill for TG, MT and HH).
  • Mysticism: 35, doesn't need to be trained (secondary skill for MG, T and IC).
  • Enchant: 35, doesn't need to be trained (secondary skill for MG and IC).
• Minor:
  • Long Blade: 25. To be trained to 45 to get extra Strength points (secondary skill for FG and IL).
  • Sneak: 15. To be trained to 30 (secondary skill for TG and MT).
  • Block: 15. To be trained to 30 (secondary skill for FG and IL).
  • Speechcraft: 15. To be trained to 25 for extra 5 Personality points (secondary skill for HH).
  • Light Armor: 15. To be trained to 30 (secondary skill for TG, MT and HH).

Encoding training in the quest dependency graph

I decided not to load up Morrowind trainer data in order to incorporate it into the route planner. Instead, I looked up the best trainers for Blunt and Marksman (since they're the only ones that will let the player reach the required level) as well as some second best ones and tried to come up with people that the player character would meet en route anyway. There were some hilarious coincidences, like Alveleg who has to be killed as part of a Fighters Guild quest but who can also train the player in Block, Sneak and Marksman up to fairly high levels.

I then added some extra nodes to the dependency graph to reflect the new training sessions:

# Training nodes
training_alveleg:
  # we're killing him as part of the FG quest and he trains Marksman (45), Sneak (42) and Block (38)
  description: Train Block x10 (up to 25), Sneak x15 (up to 30), Marksman x15 (up to 45), should get Agi 60
  giver: alveleg
training_bolnor:
  description: Train Light Armor x15 (up to 30), Marksman x5 (up to 50), should get Agility 70
  giver: bolnor andrani
  prerequisites:
    - training_alveleg
training_eydis:
  description: Train Long Blade x20 (up to 40), Blunt x30 (up to 70), Strength 85
  giver: eydis fire-eye
training_ernse:
  description: Train Blunt x20 (up to 90)
  giver: ernse llervu
  prerequisites:
    - training_eydis
training_missun:
  description: Train Marksman x30 (up to 80)
  giver: missun akin
  prerequisites:
    - training_bolnor
training_falvel:
  description: Train Mercantile x10 (should get Personality 35)
  giver: falvel arenim

They would then become prerequisites for some later quests in faction questlines:

tt_tharer_1:
  description: Get and hand in all Tharer Rotheloth quests
  giver: tharer rotheloth
  prerequisites:
    - tt_7graces_vivec
    - tt_7graces_gnisis
    - tt_7graces_kummu
    - tt_7graces_gg
    - tt_cure_lette
    - tt_mount_kand
    - tt_mawia
    - tt_kill_raxle_berne
    - training_eydis # Curate (50 blunt) to hand in Galom Daeus quest

In some cases, the requirements I added were stronger than necessary. For example, one could get promoted to Master of Fighters Guild with a Blunt skill of 80, yet it depends on a graph node training Blunt to 90. The reasoning behind it was that we don't want to visit the Master Blunt trainer more than once: if we're visiting her, we might as well train Blunt to the maximum we'll need.

Conclusion

Next up, we'll try to add the usage of Mark and Recall spells to the route as well as discuss some miscellaneous Morrowind tricks and glitches that can help during a speedrun.

Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 1

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Well, not even last night's storm could wake you. I heard them say we've reached Morrowind, I'm sure they'll let us go and do a speedrun.

Jiub

Introduction

There's the famous speedrun of Morrowind's main quest that involves basically travelling to the final game location using a few scrolls and spells and killing the boss.

However, there isn't a Morrowind speedrun category where someone tries to become the head of all factions. For all its critical acclaim and its great story, most of quests in Morrowind are basically fetch-item or kill-this-person and there aren't many quests that require anything else. But planning such a speedrun route could still be extremely interesting for many reasons:

• There are 10 joinable factions in Morrowind (Mages/Thieves/Fighters Guild, Imperial Cult, Imperial Legion, Tribunal Temple and the Great Houses: Hlaalu, Redoran, Telvanni). The player can only be a member of one Great House in a playthrough, but that still leaves 8 factions to do.
• The transport system. It's not just a matter of fast travelling to certain locations like one would do in Skyrim or Oblivion. Instead travel is by several transportation modes including boats, caravans and teleportation spells that I had previously investigated. Walking is required a lot and so it's important to manage faction questlines to avoid unnecessary redundant trips to different cities.
• There are many ways to become the head of a given faction. Faction questlines use a promotion system where new questlines open up as the character attains higher ranks at a faction. Promotion is a matter of not only reputation points (awarded by quests) but also player skills and attributes.
• Some quest objectives can be pre-completed or done in a different way. For example, if the quest giver wants the player to kill someone, that someone can often be killed before the quest even starts, at which point, most of the time, the quest giver will give the player the reward anyway. However, sometimes this might not work and the player will lose out on reputation points required to unlock further questlines. Similarly, in most fetch quests the questgiver suggests where the player can get a given item, but doesn't care if it was bought in a nearby shop a few minutes ago.

So given those features, this can get really complicated. On the way to a given quest objective the player can pick up another quest or pick up an item that might be needed at some point for a quest for a different faction that they aren't even a member of. What could be an efficient route through one faction's quests might be inferior to a slower route when all factions are played through since it could be that points in that route are visited in other factions' quests anyway, and so on.

In other words, planning an efficient route through all factions would be a fun computer science problem.

A note on skill requirements and Morrowind's levelling system

There are a couple factions where the final quest can be completed immediately, but that just results in a journal entry saying that the player character is now the head of the faction (and the advancement is not reflected in the character stats). I decided I wanted to rise to the top the mostly-honest way instead.

Unlike Skyrim and Oblivion, advancement in Morrowind factions requires the player to have certain skills at a certain level. There are 27 skills in Morrowind and each faction has 6 so-called "favoured skills". Becoming head of a faction requires the player to have one of these skills at a very high level (roughly 80-90 out of 100) and 2 of them at a medium level (about 30-35).

Morrowind characters also have 7 attributes, each of which "governs" several skills. Attributes also play a role in faction advancement.

So that's kind of bad news, since in a speedrun we won't have enough time to develop our character's skills. The good news is there are trainers scattered around Morrowind that will, for a certain fee, instantly raise these skills. The bad news is that these trainers won't train skills above their governing attributes. Raising attributes requires levelling and levelling in Morrowind is a very long story. I'll get into the actual levelling strategy later.

Different routes through a given faction

I quickly gave up on scraping quest data from the game files (since most quests are driven and updated by a set of dialogue conditions and in-game scripts) and instead used the UESP's Morrowind Quests page to manually create a series of spreadsheets for each faction that included quests, their reputation gain and rough requirements.

Here's an example of one such spreadsheet:

This spreadsheet already shows the complexity of Morrowind factions. There are two intended ways to reach the top of the Mages Guild: by having enough reputation and skills to become a Master Wizard and either completing all of Edwinna Elbert's quests and challenging the current Arch-Mage to a duel or completing all of Skink-in-Tree's-Shade's quests and getting a letter from the upper management telling the current Arch-Mage to step down. I later found another way, by reaching the rank of Wizard (one rank below Master Wizard) and then talking to the current Arch-Mage about a duel, which is quicker.

Other than that, there's also multiple ways to complete a quest. Edwinna Elbert's final 3 quests requiring the player to bring her some Dwarven artifacts don't require the player to actually go to the places she recommends: the artifacts can be acquired from different locations or even bought.

Generating all possible routes through a faction

...turned out to be tricky. The first cut of this was encoding each quest in a YAML file as a set of prerequisites and required items/actions for completion. For example:

  edwinna_2:
    giver: edwinna elbert
    prerequisites:
      rank: Conjurer
      quest: Chimarvamidium 2
    quests:
      - Dwemer Tube:
          rep: 5
          completion:
            items: misc_dwrv_artifact60
      - Nchuleftingth:
          rep: 10
          completion:
            go_person: anes vendu
      ...

This encodes the start of Edwinna Elbert's advanced questline, Dwemer Tube from Arkngthunch-Sturdumz, which requires the player to have become a Conjurer in the Guild and completed Edwinna's previous quest. To complete this quest, the player needs to have the tube in their inventory (I used the in-game item ID). Completion gives the player 5 faction reputation points.

The questline continues with Nchuleftingth Expedition and to complete that quest, the player needs to go to a certain NPC (he's an archaeologist who has, as it turns out, perished). Unlike the previous quest, this action (of going to a person and interacting with them) requires us to have started the quest.

So with that in mind, we can generate a set of all possible ways to complete a guild using breadth-first search:

• set of all sequences completing the guild S = empty
• do:
  • for each sequence in S:
    • if it already completes the guild, ignore it
    • otherwise, get all possible next quests that can be done in this sequence:
      • where the quest prerequisites have been met (e.g. a previous/required quest in the questline has been completed)
      • where there's enough reputation to start a new questline
    • add each one of these possible quests to a sequence to create several new sequences
    • replace the current sequence with the newly generated ones
• until S stops changing

Combinatorial explosions, combinatorial explosions everywhere

What could possibly go wrong? Well, firstly there's an issue of ordering. If the player is juggling two parallel questlines from different questgivers, each possible interleaving of those is counted, which causes a combinatorial explosion. Secondly, routes that are strictly worse than existing routes are generated too. For example, if completing a certain guild requires us to only complete quests A, B, D and E, there's no point in generating a route A, B, C, D, E: there's no way doing D won't take extra time.

I hence did some culling by making sure that during generation we wouldn't consider a sequence if it were a superset of an already existing quest sequence. This brought the number of generated routes (subsets, really) down to a mildly manageable 300.

Is this good? Well, not really. This only accounted for which sets of quests could be completed. There was no mention of the order in which these quests could be completed (yielding probably millions of permutations), the ordering of actual actions that would complete a given quest (for example, completing a given quest could involve killing someone and that could happen even before the player character was aware of a quest) or the alternative routes (like fetching a required item from a different place or doing an extra objective to get more faction reputation).

Worse even, this was just the route generation for one faction. There were 7 more factions to do (and I had to pick a Great House that would be the quickest to complete too) and even if they didn't have that many ways to complete them, brute-forcing through all the possible routes with all factions would definitely be unreasonable.

This method also wouldn't let me encode some guild features. For example, Morag Tong, Morrowind's legal assassin guild, has several questgivers around the world, any of which can give the player their next contract. Furthermore, the reputation required for the final questline to open can be gathered not only by doing assassination contracts, but also by collecting certain items spread around the world, each yielding about the same reputation as a contract. These items can quite often be found in dungeons that the player has to visit for other factions anyway and it could be the case that doing those quests to collect these items is overall faster.

Attempt 2: a single quest dependency graph

I hence decided to drop the idea of combining all possible routes from all guilds and instead did some experimentation to find out if there are obviously quick routes through most guilds. Turns out, there were and so instead of solving a few million instances of the Travelling Salesman Problem, I could do with just one. Still impossible, but less impossible.

Quick overview of fastest routes for a given faction

In the Mages Guild, the introductory questline can be completed in a matter of minutes and yield 22 reputation points and then Edwinna's quests can be completed en route to other quest locations that will likely have to be visited anyway. Those two questgivers would bring the player character over the 70 reputation limit required to challenge the current Arch-Mage (at that point, I wasn't looking at skills training yet).

The Fighters Guild could be completed by doing all quests from one questgiver (most of which involved killing bandits in roughly the same area which can be done even before the quest begins), a couple from another one and then proceeding on to a final questline (which does have a quest requiring to bring some items to the middle of nowhere, but the alternative ending requires many more reputation points).

The Thieves Guild has some conflicts with the Fighters Guild and so the two questlines have to be carefully managed together. Almost all quests in the Thieves Guild need to be done (since doing some Fighters' Guild quests decreases reputation with the Thieves Guild), but the good news is that they share the antagonist and so after reaching a certain reputation with the Thieves Guild, finishing the Fighters Guild promotes the character to Master Thief.

Morag Tong can basically be completed in one go: after the initial contract required to join the Guild, the player collects enough Sanguine items to skip all contracts straight on to the final questline and the location of the final boss is visited twice in other guilds' quests.

Tribunal Temple starts with a mandatory pilgrimage that visits a few locations around the game map. There are several more pilgrimages as part of the questline and some of those can be completed even without having joined the faction.

Imperial Legion has a questline that takes place in a single town and requires the player to visit the location that's visited anyway in Edwinna Elbert's questline in the Mages Guild. In addition, one quest gives additional reputation with the Temple, allowing to skip one quest there.

Imperial Cult has three questlines. One of them involves fundraising and, just like in real life, the player can simply give the money to the questgiver on the spot instead of asking others for it. The other one involves fetching several powerful artifacts and visiting a couple of locations that are visited in other guilds' questlines.

After eyeballing the Great Houses' questlines, I settled on House Hlaalu. House Redoran has a way too long questline, most of the action in House Telvanni happens on the East side of the game map that mostly isn't visited in other quests and the final Hlaalu questline that leads to becoming Grandmaster can be started at an earlier rank.

Quest dependency graph

Now that I had a single route for each guild, instead of encoding each and every quest requirement and location in a graph, I opted for an easier way. Each node in a quest dependency graph would be something that's fairly quick to complete and happens in the same location. It could be a quest, or a series of quests, or the action of clearing out some dungeon that is featured in several future quests.

A node contains two things: where this node is located (for example, the in-game ID of the questgiver or an NPC in the location that the player needs to clear out or find a certain item) and nodes that the player needs to have completed before.

For example:

# Coalesced Ajira questline
mg_ajira_1:
  giver: ajira
# Edwinna's quests up until Nchuleftingth expedition, all done in one go (Dwemer tube stolen
# from Vorar Helas in Balmora, then Chimarvamidium, Skink and Huleen)
mg_edwinna_1:  # also gives Almsivi/Divine amulets
  giver: edwinna elbert
  prerequisites:
    - mg_ajira_1
mg_edwinna_2:
  giver: edwinna elbert
  prerequisites:
    - mg_edwinna_1
    - mg_edwinna_nchuleftingth
    - mg_edwinna_scarab_plans
    - mg_edwinna_airship_plans
# locations of items we need to collect to complete Edwinna's quests
mg_edwinna_nchuleftingth:
  giver: anes vendu # can discover his body before the quest begins
mg_edwinna_scarab_plans:
  giver: Khargol gro-Boguk # orc in Vacant Tower with the other copy of the plans
mg_edwinna_airship_plans:
  giver: lugrub gro-ogdum # located near the orc in Gnisis Eggmine that is also a part of the IL quest
mg_master:
  giver: trebonius artorius
  prerequisites:
    - mg_edwinna_2

In this case, the Dwarwen plans required by Edwinna can be collected even before the questline begins and then all handed in at the same time.

When talking to someone had to be done as a part of the quest, I encoded it as several nodes that depended on each other:

fg_eydis_1_start: # join FG and start first quest
  giver: eydis fire-eye
fg_eydis_1_do:
  giver: drarayne thelas # actually do the first quest
  prerequisites:
    - fg_eydis_1_start
fg_eydis_1_end: # hand the quest in
  giver: eydis fire-eye
  prerequisites:
    - fg_eydis_1_do

Here's the final quest dependency graph:

This was much better than messing around with reputation points and quest prerequisites. Any topological sorting of this dependency graph would be a valid route through the game's quests (assuming I encoded my dependencies correctly). Since each node had a fixed geographical location, I could use a pathfinding algorithm and the data from my previous project to find out the time that any given route satisfying this dependency graph (using teleportation and public transport) takes.

However, there's still a problem: there are many possible topological sortings of a given graph and counting them is #P-complete.

This is a general case of the travelling salesman problem: if here we need to find the shortest tour that visits all nodes subject to a set of dependencies (e.g. we can't visit A before we've visited C), then in TSP we need to visit all nodes without any dependencies. Having dependencies decreases our search space (in the most extreme case the dependency graph is a line and so there's only one possible route), but not by enough.

I hence had to develop some approximations to turn this graph and the matrix of travel times between its nodes into a good-enough route.

Conclusion

Next up, I'll try a couple of random approximations to solve this problem, including simulated annealing (also kind of known as a genetic algorithm). There's also the matter of planning out the player character and his/her skill development in order to minimize the amount of time we need to spend training up to get promoted in various guilds. Stay tuned!

Let's go on a treasure hunt!

@mildbyte 5 years, 10 months ago | programming | games | python | telegram | bots |

Chatbots are basically a clunky commandline interface to things that sometimes really need a custom UI.

But what if I do want to make something that uses some of the features (a GPS receiver, a camera, a microphone) that a modern phone has? I'm too lazy to write device-specific code and dig around in the intrinsics of Android/iOS APIs.

So after doing some research on modern messenger apps (I kind of fell behind on what was going on after the WhatsApp acquisition and turns out billions more have popped up since then) I stumbled upon the Telegram bot API. And it's actually pretty simple. In a nutshell, you create a bot (by messaging another bot) which gives you a token. The token is the only thing your bot needs to communicate with the Telegram servers (so no coding up handshakes or managing session keys): it makes up your REST endpoint that you can throw queries at. The connection is over SSL, so that takes care of your ISP or a kid with a WiFi dongle and Wireshark grabbing hold of your token. Bot chats aren't end-to-end encrypted though, so Telegram are still able to read whatever you talk to the bot about.

With that in mind, receiving messages is easy: just shoot a GET request at https://api.telegram.org/bot(TOKEN)/getUpdates (reference) and it will come back with a JSON-serialised list of events (message sent, message edited etc) that happened to your bot. Each one has a unique sequence number which you can use to seek around in the update log (to say get updates only starting from the last one you processed). Updates related to messages have in them a chat ID identifying your conversation with a given user -- and you include that chat ID in your POST requests to https://api.telegram.org/bot(TOKEN)/sendMessage (reference) in order to send messages back to that user.

You can also send around various other things besides text messages, like locations (latitude-longitude pairs), photos (your bot gets some links to various-sized thumbnails of the photo), contacts etc.

So I managed to write Indiana, a treasure hunt bot that comes up with a random location inside Hyde Park (well, the rectangle whose all 4 points lie within Hyde Park and yes, that means it can sometimes put the treasure in the water or in some restricted areas and I take no responsibility for you ending up there) and, when sent a location, replies back with a rough estimate of how far the treasure is. Sort of like Pokemon Go without having to lug around an extra power pack. Note you also can send the bot a manual location -- it can't distinguish between that and a physical location read from GPS (thankfully).

project Morrowind, part 7

@mildbyte 5 years, 10 months ago | programming | games | morrowind | python |

So that you don't think that the 1-year delay in posting part 6 was due to me manually drawing the population heatmaps in Paint, I finally split the code I used to produce all the plots into a set of modules and uploaded them to GitHub. You'll need the usual scientific Python stack (NumPy, SciPy, matplotlib as well as PIL) and a C++ compiler. Since I wasn't sure if it's a good idea to post the game data dump that I produced, you'll have to make it yourself: you'll need the original Morrowind.esm data file and Enchanted Editor (instructions on how to produce the dump are in the README).

With all that in mind, I've run the code end-to-end and it spit out a similar set of images to what I have on the blog, which makes me incredibly happy.

Now it's time to get back to Cookie Clicker!

project Morrowind, part 6

@mildbyte 5 years, 10 months ago | programming | games | morrowind | python |

I told you I'd be back in a year's time.

With Aryon safe back in his tower and with all inhabitants of the island maximising the efficiency of their travel, it was time to approach a new challenge and create some more pretty pictures. The next question was simple: where the hell are all the people and what do they do?

Let's try and use our cool matrix that converts in-game coordinates to coordinates on a map to its full extent and create some sort of a population heatmap. This isn't difficult to do since we already have all the pieces of the puzzle: we know where all the NPCs are located and what their occupation, race and gender are. The only problem is dealing with NPCs that are in the interior: remember how interiors are completely separate mini-worlds? This means that we can't simply infer someone's location in the exterior by taking the coordinates of the two doors and adding up an offset of the NPC from the door, since interiors often are bigger on the inside than what they look like from the outside. Since we'd only be looking at a world-scale overview, I decided not to bother with precision: the actual exterior location of an NPC is simply the location of the closest exterior door they can get to (by number of cells they have to traverse to get outside).

Armed with these tools, I went through all the NPCs in the world, getting their exterior location, and converted that location into coordinates on the map. I had a map-sized matrix where I accumulated those coordinates: the number at each pixel was the number of NPCs whose exterior coordinates fell within that square. This meant that I'd get disproportionately large amounts of people piling up at the doors of densely-populated interiors, which wasn't optimal as it was difficult to see on the image (after all, it's just one pixel) and wasn't representing the in-game reality well: after all, we are interested in the population in a given city/region and people don't really stand in one spot either, instead roaming around.

Hence I applied a Gaussian blur to my matrix so that instead of 10 people assigned to one pixel we'd be looking at something like 2.2 people on that pixel, 1.1 people one pixel away, 0.5 people 2 pixels away etc. If this feels like chopping people into parts and throwing those body parts around so they form a nice hill, it's because it kind of is.

With that out of the way, I normalised the matrix so that all values were between 0 and 1, applied one of the numerous colormaps that matplotlib has (I quite liked the one called blues) and blended it with the original map. I also toyed around with applying a transfer function to the inputs before pushing them into the colormap since I didn't like the way it looked by default -- I chose a logistic function:

\[ f(t) = \frac{1}{1 + e^{-k(t-c)}} \]

I didn't really have a methodology here: varying $k$ changes the steepness of the curve (how quickly things go from the left side of the colormap to the right side, getting brighter) and varying $c$ changes where it's centered, so I tinkered with them for each picture until it looked good.

With that in mind, let's see what we ended up with!

draw_npcs(filter_sigma=25, sigmoid_k=8, sigmoid_c=0.2, output='map_population.png') (full)

We get dark blobs in large population centres like, bottom to top, Vivec (and Ebonheart next to it), then Balmora (southwestern part of the island), Sadrith Mora (far east), Ald'ruhn (north of Balmora) and Gnisis (northwest of Ald'ruhn). There are also some minor places highlighted around -- these are either smaller settlements or larger dungeons/strongholds/shrines.

What else can we do with it? How about mapping out all the Dark Elves? Easy, just don't go through all the NPCs:

draw_npcs(filter_sigma=25, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_darkelf.png') (full)

Yes, it looks just like the population heatmap. How about seeing where they are overrepresented or underrepresented? We can divide the two overlays by one another to essentially get fractions of Dark Elves amongst the population:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=4, sigmoid_c=0.5, output='map_population_darkelf_relative.png') (full)

I did have to play around with the parameters for this one (increasing the blur radius and moving the centre of the sigmoid to 0.5), but we can sort of see how the Dark Elves (natives of Morrowind) are less represented in the southwestern part of the island (which is more cosmopolitan and welcoming towards foreigners) and more represented in the eastern territories as well around the Ashlander camps (which almost completely consist of them).

What else can we do? Morrowind has slavery! Let's find out where all the slaves are concentrated:

draw_npcs(relative=True, filter_sigma=25, mark_npcs=[n for n in npcs if n.class_name == 'Slave'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_slave_relative.png') (full)

No blobs around big cities and towns -- which makes sense since this is a relative fraction. Instead what we have highlighted for us are random dungeons and plantations around the world where slaves are held, including Abebaal Egg Mine or Dren Plantation or some slave markets or Rotheran or Hlormaren (interestingly, for the latter the blob (west of Balmora by the sea) is west of the actual stronghold -- this is because the slaves are held in sewers from where the exit is around there).

Of course we would never use this tool for our own selfish purposes:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.is_female], sigmoid_k=12, sigmoid_c=0.7, output='map_population_female_relative.png') (full)

There are very few places on the island where females are overrepresented (note I set the centre of the sigmoid at 70%) -- the only one of them that's a town is Tel Mora in the northeast. That's because the councilor of that town "does not enjoy the presence of men" and all residents of that town are indeed women. Another place is Odirniran in the southeast, a Telvanni stronghold under attack by House Hlaalu. Northwest of that we have Assu with two sorceresses and north of that is Tel Uvirith -- a stronghold that gets built for the player as part of the Telvanni questline. It's disabled at the start of the game (and is invisible), but the scraper obviously didn't care about that.

Next year on project Morrowind, I promise I'll actually get around to cleaning up the source code that was used to make all this and releasing it. Promise.

project Morrowind, part 5

@mildbyte 6 years, 10 months ago | programming | games | morrowind | python |

Look what I found in my drafts folder. Welcome back to project Morrowind.

The nice visualization of where Aryon could be was very close now. I went with the stupidest approach: go through all pixels on the map, convert each one into a point in the game world and find how long it would take Aryon to get there (by using the method I mentioned previously: 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).

Except I forgot this was Python and I was going to go through, for each point on the map, about 2400 possible routes through exterior points. And there were 1650x1900 = about 3 million points. Sure, I could be smart about it and use various optimisations (like coalescing exterior points that are close enough to each other and treating them as one or exploiting the triangle inequality (as mentioned in the previous post) or looking at 2x2 blocks on the map instead of each pixel or using all 4 cores of my CPU instead of one). Or I could farm it out to a C++ program.

So I dumped the list of known exterior coordinates and times of the shortest routes to those to a file as well as the in-game coordinates of the 3-ish million points on the map I was interested in. The program would take those and spit out, for each sought coordinate, the shortest time it would take for Aryon to get there from his tower. In fact, it took 40 lines and ran in about 10 seconds. It's pretty amazing how fast you can be if you speak to the bare metal.

I then used matplotlib's contour plot to visualize the heatmap I got. I didn't manage to get it to actually overlay on the map in the map's original resolution, but the wizards were still extremely impressed and said that I should speak to them whenever I was interested in seed funding for my startup.

Picture time!

So this actually makes sense. There's a 2h circle around Aryon's home (northeast portion of the island) from where he could either walk or teleport to Wolverine Hall through Divine Intervention (an island east of Vvardenfell). Wolverine Hall has a Mages' Guild, so that means he could instantaneously get to four other major towns (a blob along the west edge of the island). So there are quite a few places he could get in 2 hours!

After that, he would have to take the Silt Strider or a boat, which would slow him down. In 4 hours he would barely be able to reach Gnisis (northwest corner of the island) or Maar Gan (the little arc at the top of the 4h contour around the main population centres). He, of course, could walk from his original location for 4 hours but he wouldn't get very far.

In 6 hours he could be anywhere on the island and in 8 he would be able to reach the northern edges of Dagon Fel, a small island north of Vvardenfell. Finally, in about 11 hours he could very possibly be having breakfast with Big Head in the most desolate corner of Morrowind. Perhaps he had some business there?

The wizards said last time they ever saw Aryon was at about 2am, so he'd been gone for almost 10 hours by that point. Luckily as we were trying to figure out if he would deliberately take the most efficient route to get as far away from his tower as possible, we heard a loud noise from a nearby wardrobe and an asleep but still alive Aryon fell out of it.

In the end, he loved my contour plot as well and hung it up on his wall. Some people say the tower steward still uses it to track down people who go missing in action during Aryon's wild parties.

Next year on project Morrowind, we'll talk about my assignment with Vvardenfell Office for National Statistics to make sense of the island's demographics.

project Morrowind, part 4

@mildbyte 7 years ago | programming | games | morrowind | python |

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.

project Morrowind, part 3

@mildbyte 7 years, 2 months ago | programming | games | morrowind | python |

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!

project Morrowind, part 2

@mildbyte 7 years, 2 months ago | programming | games | morrowind | python |

Today on project Morrowind, we will start turning some horrible binaries into beautiful data structures in the memory space of a Python interpreter. They are still technically binary, but let's not dwell on it too much. Otherwise we will realise we're all made of atoms and will have an existential crisis and that wouldn't be very nice.

I…I don't even see the code. All I see is tree, rock, marshmerrow...

Exposition dump

Elder Scrolls games made by Bethesda Softworks, including Morrowind and its successors (Oblivion, Skyrim and that peculiarly also kind of includes Fallout 3 and 4) store their core game data (that is, maps and locations of various objects, but not textures/audio/meshes) in the ESM (Elder Scrolls Master) format. It's been evolving ever since Morrowind as the Bethesda developers have been adding more and more features to it, but its main idea remains the same: these files are a collection of records of different types.

For example, we can have an NPC_ record, defining a character in the game, which will contain entries for the character's gender, race, AI behaviour etc. It can also have references to other records, for example, the inventory of a character, which refer to ARMO and WEAP records. CELL records describe in-game cells (actual locations) and contain references to, well, everything that is located in that cell, like NPC_, ARMO, WEAP or CONT (containers, e.g. chests). The actual binary format for Morrowind is described very well here and every release of a new Bethesda game promises players lots of fun in reverse engineering their ever so slightly minor alterations to the game data file format.

One clever idea that Bethesda had was making game save files an overlay on the game data files in this format. For example, if you were to kill someone in a certain location (pretty much what usually happens in Elder Scrolls games), your save file would have a redefinition of the CELL record that would list the NPC in question as perished. Sadly, this idea has no relevance to this project, just like lots of other clever ideas, but it's interesting nonetheless.

There are more complications though: cells can be exterior or interior. Exterior cells are square-shaped and are joined together edge-to-edge to create the actual great (dubious) outdoors of Morrowind. With interior cells, all bets are off - each of them resides in its own little reality and is joined to other cells by doors which basically function as teleports in this case. A small house in the exterior cell often is quite a bit larger from the inside, which means that you can't reliably judge where the player actually is when they're indoors.

So if we want to reconstruct a graph of how you can travel around in Morrowind, we have to take care of doors, amongst all other means of movement.

With regards to the Almsivi/Divine Intervention spells, there are special marker objects in every Temple and Imperial fort - this is how the game determines where to teleport the player when they cast a particular spell. It's again easy with the exterior cells (as all markers are located outside), but gets more complicated with interiors. Some people claim Morrowind uses the last exterior cell you've been to (which has some pathological cases - say you use a Guild Teleport that teleports you from the indoors to the indoors again, so casting an Intervention spell will warp you to the closest marker to the first Guild, not the second one) and OpenMW, an open-source reimplementation of the Morrowind engine, tries to fix that by using the closest exterior to you as a reference. My copy of Morrowind behaves the correct way for some reason, so I'll emulate that.

In much better news, if NPCs offer travel services (be it silt strider, boat or Guild teleport), it will be encoded in their record.

All in all, it seems like we want to scrape the hell out of all CELL and NPC_ records, as they contain everything we need for now.

Scraping the hell out of all CELL and NPC_ records

Now, as much as I thought it would be feasible and fun to decode the binary data according to that excellent spec, I still decided to cheat and used Morrowind Enchanted Editor, a low-level editor for ESM files. In particular, I used the "Dump to Text File" function, which turned the unreadable binary mess into a readable ASCII mess.

Meet Todd's Super Tester Guy, presumably made by Todd Howard himself.

This is something we can work with: each entry in the record is on a separate line and is clearly keyed by the subrecord (e.g. FNAM is the full name, RNAM is the race name etc). As a good starting point, we can easily extract just the NPC_ and CELL records and tokenize the data by just converting it into a stream of key-value pairs (so a line NPC_ NAME todd would get turned to a tuple (NAME, todd) since we already know it belongs to an NPC_ record).

(I was going to put source code and explain it, block-by-block, here, but WordPress decided to not be on my side today. I'll post it on GitHub later, promise. I mean, seriously, who the hell converts > to > after a save cycle and then again to &gt?)

In the end, we get something like this:

In [6]: cells[:10]
Out[6]:
[('NAME', ''),
('DATA', '\x02\x00'),
('DATA', '23'),
('DATA', '7'),
('RGNN', "Azura's Coast Region"),
('NAME', ''),
('DATA', '\x02\x00'),
('DATA', '23'),
('DATA', '6'),
('RGNN', "Azura's Coast Region")]

npcs[:10]
Out[7]:
[('NAME', 'player'),
('FNAM', 'player'),
('RNAM', 'Dark Elf'),
('CNAM', 'Acrobat'),
('ANAM', ''),
('BNAM', 'b_n_dark elf_m_head_01'),
('KNAM', 'b_n_dark elf_m_hair_01'),
('NPDT', '1'),
('NPDT', ''),
('NPDT', '')]

Parsing the stream of NPC_ records into a list of NPCs isn't that difficult. I found the neatest way was to pass the stream to a class constructor and allow it to consume as much from it as it needs to initialize itself. But keep in mind that we need to stop parsing when we see the next NPC's NAME subrecord and if we've already consumed that, it's too late, so we need to define an iterator that allows us to peek at the next item without consuming it.

Parsing the list of destinations, one of the Holy Grails that we're looking for, is easy too - just look at this example (which is one of the places that Todd's Super Tester Guy can take us):

NPC_    DODT    1822.641
NPC_    DODT    -231.5323
NPC_    DODT    -292.9501
NPC_    DODT    0
NPC_    DODT    0
NPC_    DODT    0.5
NPC_    DNAM    ToddTest

We literally get a list of 6 numbers: the x, y, z coordinates and the angle (which we don't really care about). Sometimes there's also a DNAM subrecord if we're in an interior cell.

Add a repr method and we can see a list of actual NPCs!

npcs[:10]
Out[15]:
[NPC (player, player, Dark Elf, Acrobat),
 NPC (todd, Todd's Super Tester Guy, Dark Elf, Guard),
 NPC (Imperial Guard, Guard, Imperial, Guard),
 NPC (agronian guy, Tarhiel, Wood Elf, Enchanter),
 NPC (murberius harmevus, Murberius Harmevus, Imperial, Warrior),
 NPC (madres navur, Madres Navur, Dark Elf, Acrobat),
 NPC (farusea salas, Farusea Salas, Dark Elf, Commoner),
 NPC (erval, Erval, Wood Elf, Commoner),
 NPC (Dralas Gilu, Dralas Gilu, Dark Elf, Rogue),
 NPC (uulernil, Uulernil, High Elf, Smith)]

npcs[1].inventory
Out[16]: 
[('steel battle axe', 1),
 ('glass war axe', 1),
 ('steel mace', 1),
 ('chitin guantlet - right', 1),
 ('chitin guantlet - left', 1),
 ('chitin boots', 1),
 ('chitin greaves', 1),
 ('chitin pauldron - right', 1),
 ('chitin pauldron - left', 1),
 ('chitin cuirass', 1)]

(Interestingly, there are three problems with the "agronian guy" named Tarhiel over there. Firstly, that race name is spelled Argonian. Secondly, he's not an Argonian, he's a Wood Elf. And finally, he has some mental issues but also talents.

Next time on project Morrowind, we'll move on to trying to decode CELL data, which has some more peculiarities (like the fact that it contains most of what the player can perceive). But now that we've gotten through the background and the boring bits, we will start moving faster and might even get around to constructing an actual travel graph!

project Morrowind, part 1

@mildbyte 7 years, 2 months ago | programming | games | morrowind | python |

You should play Morrowind.

(warning: lots of skippable praise for Morrowind here, scroll down for the meat of the post)

At the beginning of Morrowind, you're a chump who just got off a prison ship with 87 gold pieces (one loaf of bread costs 1 gold piece in this world, so that's conveniently about £35 - that's how much you would pay for 87 packs of Tesco Everyday Value Sliced White Bread). Your first assignment is to take a parcel to a guy in a different city, and you either have to take the silt strider (a massive insect with long legs piloted by a possibly drunk creepy guy, not unlike London buses) or walk there through the wilderness, fighting off hordes of oversized carnivorous birds with the iron dagger you had just stolen from the Census office, except the dagger always misses because, see, Morrowind's combat system is inspired by tabletop roleplaying games and they didn't pay their animators that much, so even if your weapon clearly appears to hit the mushy body of whatever it is you, the player, are aiming at, there's no guarantee at all that you have actually hit.

So after ruining a couple of mice with repetitive rage-filled clicks, you decide to quit Morrowind and do something better with your life.

Or you keep going and learn about how fatigue affects your chances to hit everything (and on everything), read up on game mechanics, buy a new mouse, make your way to Balmora and get immersed in one of the richest worlds I've ever seen in gaming. You go through a story that raises questions about organized religion, xenophobia, colonialism, tribal legends, prophecies, free will and the priorities of an individual versus the organization that they belong to.

And somewhere during that process of discovery, you realise that the swings with your crappy dagger don't miss anymore. In fact, your dagger is no longer crappy. In fact, you don't even use a dagger, instead having found an amazing sword in a dungeon guarded by a couple of possibly too sexualized and extremely dangerous monsters. You decide to murder a God and capture his soul because it has the biggest enchantment capacity. When you need to get somewhere, instead of a long slog through the wasteland you use one amulet to teleport to the nearest Temple, bunny-hop (because that makes you move faster) or levitate your way through whatever town you ended up at, enter the Mages' Guild, use the Guild Teleport, use another amulet and finally fly to your destination. You murder entire cities in drug-fueled rampages just to please yourself and then reload the last save. You pilfer the treasuries of great Houses and steal rare armor and weapons, just to go to a remote island and sell them to someone who just happens to be a massive crab - you say it's because he gives you the best prices, but it's actually because everybody else is scared of you.

Just like real life.

(skippable praise ends here)

I decided to replay Morrowind recently and in the middle of that "high-ranking executive" stage, as I got slightly annoyed by all the fetch quests I had to do to get promoted in some guilds, thought about making myself a journey planner. This is not a completely trivial task because there are so many ways you can get around in Morrowind:

• Walking (or levitating, because any self-respecting player has already enchanted something with a constant Levitation effect)

• Taking the silt strider (or the boat) - but note you can't immediately get to your target town and might have to change through one of those bad parts of town. Takes in-game time, but we'll say it's instantaneous as perceived by the player.

• Guild of Mages Teleport - instantaneous as well. You have to talk to mages, but they are a nice bunch, really.

• Divine/Almsivi Intervention - this is where it gets interesting. Divine Intervention teleports you to the nearest Imperial fort (Morrowind is part of the Empire and is still quite reluctant about that idea) and Almsivi Intervention teleports you to the nearest Tribunal Temple (which is the official religion of Morrowind that was around way before the Empire).

• Mark/Recall - two spells, one places a mark and the other one teleports you to that mark.

• Propylon Indices - long ago, someone decided to build lots of cool-looking strongholds in a circle around the island. Good news: there's a teleport chamber linking them in a round-robin fashion. Bad news: you need a Propylon Mark for each one of those strongholds to use their teleport and those are often tough to find. Also, these strongholds have been overrun by various nasties and generally aren't pleasant to be around. I'll exclude them from my analysis for now.

There are minor delays on the Circle Line due to sharks (from http://www.terminally-incoherent.com).

So you can see how some interesting ways to get to places can arise by combining these means. For example, you could totally cast Almsivi Intervention to get teleported to the nearest Temple, then Divine Intervention to get teleported to an Imperial Fort, then use a Guild teleport and immediately cast another Almsivi to get to yet another town.

But of course it would be boring if I just spent some time reading those Morrowind travel maps, making a graph and running Dijkstra on it. For one, that wouldn't make for a good blog post. In addition, it doesn't help you if you end up somewhere in the wilderness (see that area in the middle, circled by Falasmaryon, Valenvaryon, Rotheran, Indoranyon, Falensarano, Ald'Ruhn and Maar Gan? Yeah, don't go there).

Finally, there are quite a few large fan-made add-ons to Morrowind, including Tamriel Rebuilt, because, see, I've been lying to you and that island isn't called Morrowind, it's actually Vvardenfell and Morrowind is the province Vvardenfell is part of. Tamriel Rebuilt tries to recreate this whole province (yes, the whole Morrowind isn't in the game called Morrowind. What's more, Tamriel is the whole Empire of which Morrowind is a part and, yes, Tamriel Rebuilt just tries to recreate Morrowind in-game. In the game called Morrowind).

All of this was me trying to convince you that it's a good idea to find a systematic way to scrape this data out of game files to make our lives easier. And imagine the kinds of things we'll learn if we do that! Demographics! Population heatmaps! Graphs! We might even plot property prices and travel times!

Next time on project Morrowind, we will battle with confusing binary formats, bizarre conventions, linear algebra, Python and will possibly learn more about the lore of Morrowind and its game mechanics. Stay tuned!

Remaining posts in this series...