Solving The ‘Travelling Murderer’ Problem Of Morrowind’s ‘Leader Of Every Faction’ Speedrun

Beating Morrowind in a little over three minutes? Easy as. Now, do the same thing, except end the game as the leader of all Morrowind‘s factions. That’s a bit harder. OK, a lot harder. So hard that software engineer Artjoms Iškovs decided to tackle the problem with computer science.

In a three-part series (first part here), Iškovs starts by outlining the key points of the “leader of every faction” speedrun:

• There are 10 joinable factions in Morrowind … 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 … redundant trips.

He also points out that many of the factions offer several ways to become leader and that quests objectives don’t necessarily have to be completed in order.

You don’t even need to have certain quests to complete them, you just need to have done what’s required beforehand (“most of the time, the quest giver will give the player the reward anyway”).

The next step was to find the different routes to becoming leader of each faction, which Iškovs ended up doing by going through the Unofficial Elder Scrolls Pages (UESP) and hand-crafting spreadsheets containing “quests, their reputation gain and rough requirements”.

This data was then used to build dependency graphs to visual each quest “step”. However, this gave rise to the “travelling salesman” problem — or in Morrowind’s case, the “travelling murderer”:

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.

Parts two and three go into detail about how Iškovs went about solving his so-called “TMP”.

The end of part three has the solution in step-by-step form, including a massive one that demands crafting no less than 300 potions. The total time? 28 minutes… just a little longer than the normal speedrun of 3:07.

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