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

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!