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

Table of Contents

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.