Geekly Articles each Day
📜 ⬆️ ⬇️

Morrowind speedran planning using simulated annealing

image

Well, you and sleepyards, even yesterday’s storm did not wake you. They say we have already sailed to Morrowind. We will be released and allowed us to make a speedran, that's for sure!

Introduction


There is the famous speedrow of the main quest Morrowind, in which, in essence, the player moves to the end of the game, uses several scrolls and spells, and then kills the boss.

However, there is no category of speedranes Morrowind, in which the player seeks to become the head of all factions. Despite the love of critics and a great storyline, most of the quests of Morrowind are in the tasks “bring a thing” or “kill this type”, and there are not so many quests in which something else is needed. But planning such a speedran route can still be extremely interesting for the following reasons:


Given all these features, the task can be very difficult. On the way to the chosen goal of the quest, the player can pick up another quest or pick up an item that at some point may be necessary for the quest of another faction, of which he is not even a member. What seems to be an effective route through all the quests of one faction may slow down the route when playing the game for all factions, because there may be points on this route that you still need to visit to complete the quests of other factions, and so on.

In other words, planning an effective route with the passage for all factions will be an interesting task about automated data processing.
')

Note on Morrowind skill and level requirements


There are a couple of factions, the last quest of which can be completed immediately, but the result will be just a journal entry reporting that the player’s character is now the head of the faction (and this increase does not affect the character’s parameters). I decided that instead I want to get to the top in the most honest way.

Unlike Skyrim and Oblivion, the increase in Morrowind factions requires the player to have certain skills with a certain level. Morrowind has 27 skills and each faction has 6 so-called “preferred skills.” To become the head of the faction, the player must have a very high level of one of these skills (approximately 80-90 out of 100) and two of them - at an average level (approximately 30-35).

In addition, Morrowind characters have 7 attributes, each of which "controls" several skills. Attributes also affect rank enhancement in fractions.

This is sad news for us, because in the speedran we will not have enough time to develop character skills. However, the good news is that skills teachers are scattered around Morrowind who can, for a fee, instantly enhance these skills. Sad news - these teachers will not be able to raise skills higher than the attributes that control them. Increasing the levels requires increasing the levels, and this task in Morrowind has a very long history . I will tell you about the strategy of raising the levels later.

Different routes for individual factions


I quickly got tired of pulling out the quests from the game files (because most of the quests are managed and updated with a multitude of interactive conditions and in-game scripts), so instead I used the Morrowind UESP quest page and manually created several spreadsheets for each faction I entered into the quests given their reputation and their approximate requirements.

Here is an example of one of these spreadsheets:


The complexity of the Morrowind factions is already clear from this table. There are two intended ways to reach the top of the Mages Guild: gain enough reputation and skills to become a Master Wizard, complete all Edwin Elbert quests and challenge the Archmage to a duel, or complete all Skink-in-Shadow-Tree quests and receive a letter from the management telling you the removal of the current Archmage. Later I found another way - to reach the rank of the Wizard (one rank lower than the Master Wizard), and then talk to the Archmage about the duel, which turns out to be faster.

In addition, there are many different ways to complete the quest. In the last three quests of Edwinna Elbert, where the player is required to bring her gnome artifacts, it is actually not necessary to go to places recommended by her: you can get artifacts in other places or even buy them.

Generating all possible routes to pass the faction


... turned out to be a challenge. The first attempt was to encode each quest in the YAML file as a set of prerequisites and items / actions required to perform. Here is an 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 is how the beginning of Edwinna Elbert’s quest line is coded - the Dwemer pipe from Arkngtunch-Sturdumts , which requires the player to become a Conjurer in the Guild and complete Edwinna’s previous quest. To complete this quest, the player must have a tube in his inventory (I used the item's in-game ID). Completing the quest gives the player 5 faction reputation points.

The quest line is continued by the expedition to Nchuleftingt , and in order to complete this quest, the player needs to get to a certain NPC (an archaeologist who, as it turns out, was dead). Unlike the previous quest, this action (moving to the character and interacting with it) requires the player to start the quest first.

Considering all this, we can generate a multitude of all possible ways of guild passing by using breadth-first search:


Combinatorial explosions, combinatorial explosions everywhere


What could go wrong? Well, firstly, there is a problem with the order. If a player juggles with two parallel quest lines from different quest issuing characters, each possible intersection is taken into account, which leads to a combinatorial explosion. Secondly, routes are generated that are absolutely definitely worse than existing routes. For example, if the passage of a certain guild requires us to complete only quests A, B, D, and E, then there is no point in generating route A, B, C, D, E: performing D will require additional time anyway.

Therefore, I performed the pruning, making sure that during the generation we did not consider the sequence, if there is a superset of an already existing sequence of quests. This reduced the number of routes generated (in fact, subsets) to 300 manageable ones.

Is it good? Well, not really. Here only those sets of quests that can be completed are taken into account. There is no consideration of the order in which these quests can be completed (which would probably give us millions of permutations), the order of actions for completing a specific quest (for example, to complete a quest you may need to kill someone, but it may happen before how the player’s character learns about the quest) and alternate routes (for example, getting the desired item from another place or completing an additional task to get more faction reputation points).

But even worse is that it was generating a route for only one faction. It will be necessary to process 7 more factions (besides, I will need to choose the Great House, the passage of which is the fastest), and even they will not have many ways to pass, simply going through all the possible routes for all factions will definitely become unjustified.

In addition, this method will not allow me to encode the features of some guilds. For example, the guild of legal killers Morag Tong has several quest givers around the world, each of whom can give the player his next contract. Moreover, the reputation required for the last quest line to be opened can be obtained not only by fulfilling murder contracts, but also by collecting certain items scattered around the world, giving approximately the same reputation as the contract. These items can often be found in the dungeons, which the player must attend for other guilds, and may be. that the execution of such quests to collect items can generally be faster.

Attempt 2: dependency graph of individual quests


Therefore, I abandoned the idea of ​​combining all possible routes from all the guilds, and instead experimented to find out if there are obvious fast routes for most of the guilds. It turned out that they exist, and instead of solving millions of examples of the traveling salesman problem, I decided to choose only one. The solution is still impossible, but less impossible.

Overview of the fastest routes for a specific faction


The introductory quest line of the Mages Guild can be completed in a matter of minutes and get 22 points of reputation, and Edwinna’s quests can be completed on the way to the locations of other quests that are likely to be visited anyway. These two quest givers can bring player character points that exceed the 70 reputation points needed to challenge the Archmage (at this stage I hadn’t considered learning skills).

The guild of fighters can be completed by completing all the quests of one quest giver (most of which are connected with killing gangsters in approximately one area; this task can be accomplished even before the quest begins), a couple from another quest giver and going to the last quest line (which has a quest that requires bringing items to some wilderness , but the alternative ending requires much more reputation points).

The Thieves Guild has several conflicts with the Fighters Guild, so two quest lines need to be carefully taken into account. Almost all quests in the Thieves Guild need to be completed (since some of the Soldiers Guild quests diminish the reputation of the Thieves Guild), but the good news is that they have one common antagonist, therefore, after reaching a certain reputation in the Thieves Guild, passing the Mages Guild boosts the character rank to master affairs.

Morag Tong , in fact, can be completed in one step: after the first contract required to enter the Guild, the player collects enough Sanguin artifacts to skip all the contracts and go directly to the last quest line, and the location of the last boss is visited twice in the quests of others guilds.

The Temple of the Tribunal begins with an obligatory pilgrimage with visits to several points on the game map. There are several more pilgrimages in the quest line, and some of them can be done without even joining a faction.

The quest line of the Imperial Legion is performed in a single city and requires the player to visit a place that he already visits in the quest line of Edwinna Elbert in the Mages Guild. In addition, one quest gives an additional reputation at the Temple, which allows you to skip one of his quest.

The Imperial Cult has three quest lines. In one of them, a fundraiser is required, therefore, as in real life, a player can simply give the quest giver money on the spot and not solicit it from others. In the other, you need to collect several powerful artifacts and visit a couple of places visited in the quest lines of other guilds.

After reviewing the quest lines of the Great Houses, I settled on House Hlaalu . The quest line of House Redoran is much longer, and the main action of House Telvanni takes place in the eastern part of the game map, which usually does not need to be visited for other quests. In addition, the last quest line Hlaalu , which leads to becoming the Chairman of the Council, can be started with a lower rank.

Quest Dependency Graph


Now that I had the only route for each guild, instead of coding each requirement and location of the quest in the graph, I chose a simpler method. Each node in the quest dependency graph will be something that can be completed relatively quickly and what is happening in one location. This can be a quest, a series of quests, or an action to clear a dungeon involved in several future quests.

The node contains two elements: the location of this node in the game (for example, the quest giver's in-game ID or NPC in a location that the player must clear or find a specific item) and nodes that the player must perform before the current one.

For example:

 #     mg_ajira_1: giver: ajira #      ,      ( ,  #     ,  ,   ) mg_edwinna_1: #    Almsivi/Divine 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 #  ,      mg_edwinna_nchuleftingth: giver: anes vendu #        mg_edwinna_scarab_plans: giver: Khargol gro-Boguk #         mg_edwinna_airship_plans: giver: lugrub gro-ogdum #        ,        mg_master: giver: trebonius artorius prerequisites: - mg_edwinna_2

In this case, the Dwemer drawings that Edwinna needs can be taken even before the start of the quest line and transmit them all at the same time.

When part of the quest is communicating with someone, I coded it as several nodes depending on each other:

 fg_eydis_1_start: #         giver: eydis fire-eye fg_eydis_1_do: giver: drarayne thelas #    prerequisites: - fg_eydis_1_start fg_eydis_1_end: #   giver: eydis fire-eye prerequisites: - fg_eydis_1_do

Here is the final quest dependency graph:


This is much better than fussing with reputation points and quest prerequisites. Any topological sorting of this dependency graph will be the correct route through the quests of the game (assuming that I correctly coded all the dependencies). Since each node has a fixed geographic location, I can use the pathfinding algorithm and the data from my previous project to find the time required for each specific route that satisfies this dependency graph (using teleportation and public transport).

However, there is still a problem: there are many possible topological sorts of a given graph, and their calculation is # P-complete .

This is a common case of the traveling salesman problem: if we need to find the shortest route here, visiting all the nodes subject to multiple dependencies (for example, we cannot visit A ​​until we have visited C), then in the traveling salesman problem we need to visit all the nodes without dependencies. The presence of dependencies reduces the search space (in the most extreme case, the dependency graph is a direct one, that is, there is only one possible route), but it does not reduce it sufficiently.

Therefore, I had to develop approximations in order to turn this graph and the time matrix of moving between its nodes into a reasonably good route.

Generation of displacement time matrix


Here we will talk about two graphs: the first is the dependency graph of quests described above, and the second is the displacement graph, which I generated in a previous article .

At this stage, the dependency graph contains about 110 geographically distant nodes, so the first step is to create a matrix of the fastest routes and travel time between every two of these nodes, because the final route will, of course, be used to move between some two points.

For this, I used the Dijkstra algorithm: since it is an algorithm for finding the shortest path from a single point, if I run it for one geographic node in the quest dependency graph, I will get the shortest routes (in the movement graph) to all the other points. Therefore, it was enough for me to do it a hundred times.

However, there is a problem: the movement graph contains about 6,500 vertices and 16,000 teleportation edges (that is, moving by public transport or using Almsivi / Divine Intervention spells: this number does not include the edges of physical movements between points in one cell). It took about 10 minutes to execute the Dijkstra algorithm for one starting point, so I would spend about a day on generating the displacement time matrix.

Therefore, I decided to truncate the displacement graph a little by combining the vertices located in the same cell. For each cell (internal or external), I replaced all the vertices in it with one vertex with averaged coordinates, and then recalculated the costs of moving between them:

 def coalesce_cells(vertices, edges): #           ( ) vertices_map = defaultdict(list) for v in vertices: vertices_map[v.cell].append(v) #       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]) #     ,     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] #      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]: #           new_edges[av1][av2] = min(grouped_edges[av1][av2], key=lambda md: md[1]) return new_vertices, new_edges

Due to this truncation, the displacement graph narrowed down to about 800 vertices and 2,200 teleportation edges, and I successfully managed to create a matrix of the shortest travel time between any two nodes in the dependency graph.

Here is one of the things that can be done with such a distance matrix: use the clustering algorithm to visualize the groups into which the points important for the quests are ordered (click on image to enlarge).


For example, on the upper left side of this heat map, there is an NPC group located on a number of remote islands in the north of the game map. It is difficult to get to them and it takes a lot of time, so it is worth ordering our quests in such a way that we have to get here only once.

Annealing Simulation (Genetic Algorithm?)


Suppose we have a candidate route, which is one of the topological sorts of the dependency graph. We can see how much this route takes by simply summing the cost of moving between successive nodes using our cost matrix.

How do we find the best route? Simple brute force does not help here. I decided to do something a little less stupid: take the route and randomly mix it. Of course, the resulting route may be less effective than it was before. But imagine that we will do this for tens of thousands of randomly generated routes, save the part that turned out to be the most effective, and then again mix the best routes again. Gradually, we will come to a decent route, if not the most optimal one.

As a result, I used the following algorithm:


Of course, you can experiment with constants, and the termination condition can be determined better. Someone calls this a genetic algorithm (in which we simulate evolution and random mutations in the genetic pool), others - imitation annealing (in which the magnitude of random movements decreases with time until we arrive at a solution pool). The “genetic algorithm” sounds more interesting, so I mentioned it in this paragraph.

I left the program to work at night and in the morning I saw a route that seemed suitable for passing the game.


The travel time here is derived from in-game distances, given that the minimum walking speed is approximately equal to 100 game units per second. Of course, there are potions and spells that increase walking speed. In addition, it does not take into account the time spent on the menu or the killing of those who must kill the player.

In general, at some points the optimizer pleasantly surprised me.


I have written a handy program that takes graph nodes and expands them into a movement plan using Almsivi / Divine Intervention spells and public transport. For example, in this fragment, the route planner correctly set up progress in the quest faction line, so that all six tasks in the remote southwestern corner of the map can be completed in one go (lines 592-618).

However, this route has some problems:


Learning skills


Raising the rank of Morrowind factions requires not only completing quests, but also learning skills. I have already mentioned that although it is possible to pay to learn a skill, it cannot be raised above its controlling attribute.

Attribute values ​​can only be increased when elevated. As the main skills, a player’s character has 5 of 27 skills (which allow him to increase their level faster and give a +25 bonus to these skills at the beginning of the game) and 5 side skills (which also allow them to increase their level faster, although not so quickly , as in the main, and also give a bonus of +10 to these skills). The character raises the level when he scores 10 points on the main or side skill.

And here everything starts to get weird. When increasing the level, the player chooses 3 attributes, the level of which he wants to increase. The amount of increase depends on the skills the player has learned. For example, if he got 10 points in Alchemy (managed by Intellect), then if Intellect is selected when the level rises, it will increase not by 1, but by 5 points. However, if a player has raised a level by learning 1 point in Long Blades (controlled by the Force) and 9 points in Alchemy, he will receive a 4x multiplier for Intelligence and 1x for Strength.

Also, the player can learn skills that are not basic or side to get enough points to increase the attribute multiplier. Suppose a player also learns 1 point in Security (managed by Intellect), which is not his primary or secondary skill. It will not be counted in the 10 points needed to increase the level, but is taken into account in the calculation of the attribute multiplier. Therefore, the player will be able to increase his Intelligence by 5.

Therefore, I needed to tactically choose the basic / side skills of my character, as well as his race (which gives bonuses to certain skills and attributes) in order to quickly achieve the requirements of each faction.

Overview of factions and skill levels required


Below is a list of the skill levels required by each faction so that the player can become the head of the faction. It is worth considering that he does not necessarily meet the skill requirements for the highest rank in the faction, because most factions stop checking the player’s parameters during their last quest lines and simply raise the player to the highest rank after the quest line is completed.


Character planning


With all this in mind, I decided to choose Alchemy, Blunt Weapon and Accuracy as high-level skills. Alchemy (basic skill for the Mages Guild) can quickly learn how to create potions. A crushing weapon is a common skill for 4 factions (Guild of Fighters, Temple, Imperial Cult and Imperial Legion) and should increase to 90. Accuracy is associated with the other 3 factions (Thieves Guild, Morag Tong and House Hlaalu) and rises to 80.

Other skills must be chosen partially in order to cover the remaining, weaker requirements, and partly because training them increases Strength or Dexterity to 90 or 80 (otherwise it will be impossible to learn Doubling Weapon or Accuracy). Therefore, I decided to pump a character starting with a high Strength and with a bonus to Blunt Weapons, and also to learn Long Blades to increase Strength (and to meet the requirements of secondary skills for the Guild of Fighters / Imperial Legion).

For Dexterity, I will be trained in Defense, Light Armor, and Stealth. All of them are controlled by Dexterity and training them to the required levels will lead to the Dexterity increase so that it will allow me to learn Accuracy to 80.

Enchantment and Mysticism meet the secondary requirements of the Temple, the Mages Guild, and the Imperial Legion.

Here is the final character scheme . She begins with the following basic and side skills:



I decided not to load the data from Morrowind teachers to be embedded in the route planner. Instead, I found the best teachers of Crushing Weapons and Accuracy (because these are the only skills that allow the player to reach the required level), as well as second -rate teachers, and tried to figure out the people with whom the player’s character would still meet on his way. So funny coincidences came to light, for example, Alveleg , who needs to be killed as part of the quest of the Fighters Guild, but who can also train the player in Defense, Stealth and Accuracy to fairly high levels.

Then I added a few extra nodes to the dependency graph to reflect the new learning sessions:

 #   training_alveleg: #             (45),  (42)   (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

Then they should become prerequisites for some later quests in the quest lines of the factions:

 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 add are more stringent. For example, a player may ascend to a Fighter Master Guild with a Crush Weapon skill of 80, but this depends on the Crush Training Training Node node at 90. The reason for this is that I don’t want to visit a Master Crush Master teacher more than once: if we visit her, we train for Crusher weapons to the maximum necessary level.

Conclusion


In the next article, we will try to add Mark and Recall spells to the route, as well as discuss some of the many Morrowind tricks and glitches that can help us during speedran.

Source: https://habr.com/ru/post/354204/

More articles:


All Articles