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

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!