You need to play Morrowind.

(Warning: below are a few paragraphs of praise from Morrowind, so you can safely skip them and go to the very essence of the post.)

At the beginning of Morrowind, you are just a stunned who has just stepped down from a prison ship with 87 gold in your pocket (in this world, one loaf of bread costs 1 gold, that is, about 35 pounds - this is how much you have to pay for 87 packages of sliced ​​white bread at Tesco) . Your first task will be to receive a parcel from a person in another city, and you can either take a ride on a silt strider (a huge long-legged insect that is probably driven by a perpetually drunk creepy driver - almost like in London buses) or take a walk there on foot through the wilderness fighting the hordes of overgrown birds of prey with an iron dagger that you pulled from the census bureau. Only your dagger always misses, because, you see, the creators of the Morrowind combat system were inspired by tabletop role-playing games, and the animators were not paid much, so even if your weapon is obviously stuck into the fleshy body of the one you guarantees that you actually hit.
')
Therefore, having broken a couple of mice because of thousands of furious clicks, you decide to quit Morrowind and spend your life on something more interesting.

Or do you continue to play and learn how fatigue affects your chances of someone hitting (and hitting someone), study game mechanics, buy a new mouse, get to Balmor and dive into one of the richest worlds that I seen in games. You live a story that raises questions about organized religion, xenophobia, colonialism, tribal legends, prophecies, free will and the choice of priorities between your own interests and the interests of the organization to which you belong.

And somewhere in the process of this research, you realize that your waving of your settling dagger no longer passes by. In fact, the dagger is no longer a slop. In fact, you no longer use a dagger, but found a stunning sword in a dungeon guarded by a couple, perhaps too sexy and extremely dangerous creatures. You decide to kill God and take away his soul, because it possesses the greatest possibility of enchantment. When you need to get somewhere, instead of a long walk through the wastelands, you use a single amulet to teleport to the nearest Temple, jump bunny-hop (because it turns out to move faster) or levitate to the city, go to the Mages Guild, use teleport Guilds, use another amulet and finally get to the desired point. In a drug intoxication, you just cut out entire cities just for the pleasure of it, and then load the last saved one. You rob the treasure houses of the Great Houses, steal rare armor and weapons just to get to a distant island and sell them to a huge crab. You say that you chose him because he offers the best price, but in reality everyone else is simply afraid of you.

Just like in real life.

(Here the praise of the game ends.)

Recently, I decided to re-play Morrowind and in the middle of the process of earning high rank I was a bit bored with the constant “bring the subject” quests that I have to perform to get a promotion in some guilds. Therefore, I thought about creating a route planner. This is not a trivial task, because the number of options in Morrowind is very large:

• Walking (or levitation, because a self-respecting player has already enchanted an object with the constant effect of levitation)
• A trip to the Silt Strider (or boat) - but it is worth considering that you cannot instantly get to the desired city and you will have to change transport in one of the bad parts of the city. In-game time is spent on this, but we will assume that the movement takes place instantly, as it is perceived by the player.
• The magicians guild teleport is also instant. You need to talk to the magicians, but in fact they are good guys.
• Divine / Almsivi Intervention - here everything becomes more interesting. Divine Intervention teleports us to the nearest Imperial fort (Morrowind is part of the Empire, though still not reconciled with this thought), and Almsivi Intervention (Almsivi intervention) teleports us to the nearest Temple of the Tribunal (which is the official Morrowind religion and existed long before the Empire).
• Mark / Recall - two spells, one places the mark, and the second teleports you to this mark.
• Propylon (Propylon Indices) - a long time ago someone decided to build on the island in a circle a bunch of beautiful fortresses. Good news: there is a teleportation room connecting them all in a circle. The bad news is that you will need a propylion mark for each of these fortresses, and they are often difficult to find. In addition, these fortresses are filled with a bunch of different creatures, and usually next to them is not very nice. For now, I will exclude them from my analysis.

Due to the appearance of sharks on the Koltsevaya Line, slight movement delays are expected.

You can understand what interesting ways of moving can occur when combining these tools. For example, you can skip Almsivi Intervention to teleport to the nearest Temple, and then Divine Intervention to teleport to the Imperial Fort, then use the Guild teleport and immediately skip another Almsivi to get into another city.

But of course, it would be boring if I just spent some time reading these Morrowind displacement maps, creating a graph and executing the Dijkstra algorithm for it. First, it would not have turned out such a good post. Secondly, it would not help us if we were somewhere in the wasteland (see this area in the middle, surrounded by Falasmaryon, Valenvaryon, Rotheran, Indoranyon, Falensarano, Ald'Ruhn and Maar Gan? Yes, you should not go there ).

Finally, there are some pretty big fan add-ons to Morrowind, including Tamriel Rebuilt , because I lied to you, and in fact this island is not called Morrowind, but Vvardenfell, and Morrowind is a province of which Vvardenfell is a part. The authors of Tamriel Rebuilt tried to recreate the entire province (yes, all of Morrowind did not enter the game with the name Morrowind. Moreover, Tamriel is the whole Empire, of which Morrowind is part, and yes, Tamriel Rebuilt is simply trying to recreate the Morrowind. In a game called Morrowind ).

All this I said in order to convince you that it would be a good idea to find a systematic way of pulling out this data from the game files in order to simplify our lives. Imagine what we can find out if we do this! Demographics! Heat maps of the population! Counts! We can even make graphs of prices and travel times!

In the next part of the Morrowind project, we will fight with intricate binary formats, strange assumptions, linear algebra, Python, and perhaps learn more about Morrowind Laura and his game mechanics.

Part 2

Next in the Morrowind project, we will begin to turn horrible binaries into beautiful data structures in the Python interpreter memory space. Technically, they still remain binary data, but let's not go so deep. Otherwise, we realize that everything is composed of atoms and we will be covered by an existential crisis, and there is nothing good in this.


I ... I don't even see the code. I only see wood, stone, marsh cane ...

Data dump

In the games of the Elder Scrolls series created by Bethesda Softworks, including Morrowind and its followers (Oblivion, Skyrim, in addition, they include Fallout 3 and 4) basic game data (i.e. maps and locations of various objects, but not textures / sounds / models) are stored in ESM (Elder Scrolls Master) format. Since the days of Morrowind, it has evolved, the Bethesda developers have added more and more features to it, but the basic idea remains the same: these files are a collection of records of various types.

For example, we may have an NPC_ entry that defines the character of the game, which will contain the definitions of gender, race, AI behavior of the character, etc. It can also contain links to other entries, for example, the inventory of a character that refers to the ARMO and WEAP entries. CELL entries describe the in-game cells (locations themselves) and contain links to everything that is contained in this cell, for example NPC_, ARMO, WEAP, or CONT (containers, for example chests). Morrowind's binary format is very well described here and every new release of Bethesda games promises players a lot of interesting tasks for reverse engineering small changes in the game data file format.

Bethesda came up with a clever idea - to make game save files overlay game data in this format. For example, if you kill someone in a certain location (which happens quite often in games of the Elder Scrolls series), then your save file will contain a redefinition of the CELL entry, which indicates the corresponding killed NPC. Unfortunately, this idea did not reflect on my project in any way, like many other clever ideas, but nevertheless it is interesting.

However, there are other difficulties: the cells can be external or internal. The outer cells are square and are connected edge to edge, creating stunning expanses of Morrowind. There is a different story with internal cells - each of them is in its own little reality and is connected with other cells by doors, which are essentially used here as teleports. A small house in an external cell is often much larger from the inside, so we cannot reliably judge where a player is when he enters.

Therefore, if we want to recreate the graph of ways to move around Morrowind, then we need to be considered as another way to move the door.

As for the Almsivi / Divine Intervention spells, there is a special marker object in each Temple and Imperial Fort - with the help of it the game determines where to teleport a player casting a certain spell. This is also simple for external cells (because the markers are inside the premises), but it is complicated in the case of internal cells. Some people claim that Morrowind uses the last external cell that the player was in (which sometimes leads to pathological cases - let's say we use the Guild teleport teleporting us from one room to another; then during the Intervention spell, we will be moved to a marker close to first guild, not the second) and the open-source implementation of the Morrowind engine OpenMW tries to solve this problem by using the cell closest to the player as a reference. For some reason, my copy of Morrowind behaves correctly, so I simulate this behavior.

Much better is that if the NPC offers transportation services (a Silt Strider, a boat, or a guild teleport), it will be encoded in its record.

In general, it seems, we need to pull out all of the CELL and NPC_ records, because they contain everything we need.

Extracting all of the CELL and NPC_ records

Although I thought it would be quite possible and interesting to decode binary data in accordance with this wonderful specification, I decided to cheat and used the Morrowind Enchanted Editor , the low-level editor of ESM files. In particular, I used the “Dump to Text File” function, which turns unreadable binary chaos into readable ASCII chaos.


Meet the character Todd's Super Tester Guy , supposedly created by Todd Howard himself.

It is already possible to work with this: each element in the record is on a separate line and has a key in the form of a subrecord (for example, FNAM is the full name, RNAM is the name of the race, etc.). First, we can extract only the NPC_ and CELL records, and then convert the data into tokens , converting them into a stream of key-value pairs (that is, the string NPC_ NAME todd turns into a tuple (NAME, todd), because we already know that refers to the NPC_ record.)

(I was going to show it here block by block and explain the source code, but today WordPress turned against me. I promise I will post it on GitHub later. Seriously, who thought to convert> to & gt; after the save cycle, and then back to & amp; gt?)

As a result, we get something like this:

In [6]: cells[:10] Out[6]: [('NAME', ''), ('DATA', '\x02\x00'), ('DATA', '23'), ('DATA', '7'), ('RGNN', "Azura's Coast Region"), ('NAME', ''), ('DATA', '\x02\x00'), ('DATA', '23'), ('DATA', '6'), ('RGNN', "Azura's Coast Region")] npcs[:10] Out[7]: [('NAME', 'player'), ('FNAM', 'player'), ('RNAM', 'Dark Elf'), ('CNAM', 'Acrobat'), ('ANAM', ''), ('BNAM', 'b_n_dark elf_m_head_01'), ('KNAM', 'b_n_dark elf_m_hair_01'), ('NPDT', '1'), ('NPDT', ''), ('NPDT', '')] 

Parsing a stream of NPC_ records into an NPC list is not such a difficult task. I found out that the simplest way is to pass the stream to the class constructor and allow it to read from there everything necessary for its initialization. But do not forget that we need to stop the parsing when we see the NAME subrecord of the next NPC, and if we have already used it, it is too late, so we need to define an iterator that allows us to look at the next element without using it.

Parsing the list of locations we are looking for the Holy Grail is also very simple - just look at this example (this is one of the places where Todd's Super Tester Guy can deliver us):

 NPC_ DODT 1822.641 NPC_ DODT -231.5323 NPC_ DODT -292.9501 NPC_ DODT 0 NPC_ DODT 0 NPC_ DODT 0.5 NPC_ DNAM ToddTest 

We literally get a list of 6 numbers: the coordinates x, y, z and the angle (which is not important to us). Sometimes, if we are in the inner cell, there is a DNAM subrecord.

Add the repr method and we can see the list of NPCs!

 npcs[:10] Out[15]: [NPC (player, player, Dark Elf, Acrobat), NPC (todd, Todd's Super Tester Guy, Dark Elf, Guard), NPC (Imperial Guard, Guard, Imperial, Guard), NPC (agronian guy, Tarhiel, Wood Elf, Enchanter), NPC (murberius harmevus, Murberius Harmevus, Imperial, Warrior), NPC (madres navur, Madres Navur, Dark Elf, Acrobat), NPC (farusea salas, Farusea Salas, Dark Elf, Commoner), NPC (erval, Erval, Wood Elf, Commoner), NPC (Dralas Gilu, Dralas Gilu, Dark Elf, Rogue), NPC (uulernil, Uulernil, High Elf, Smith)] npcs[1].inventory Out[16]: [('steel battle axe', 1), ('glass war axe', 1), ('steel mace', 1), ('chitin guantlet - right', 1), ('chitin guantlet - left', 1), ('chitin boots', 1), ('chitin greaves', 1), ('chitin pauldron - right', 1), ('chitin pauldron - left', 1), ('chitin cuirass', 1)] 

(Interestingly, there are three problems with the “Argonian guy” (agronian guy) named Tarhiel. First, the name of his race is spelled Argonian. Secondly, he is not an Argonian, but a Wood Elf. And finally he has mental problems, but also abilities .

Next, we turn to attempts to decode CELL data, in which there are other interesting points (for example, the fact that they contain most of what the player can perceive). But we have already talked about the basics and the most boring, so we will start moving faster and maybe we will get to create a real movement graph!

Part 3

Today, in the Morrowind project, we will take decades of studying the process of visualizing 3D scene descriptions into beautiful photorealistic worlds, and throw them into the trash.


I finally gave up trying to non-trivial formatting in WordPress. I hope he will not spoil the text at least in the pictures.

Load cell data

There are several difficulties with parsing Morrowind cells. The first is how to give cells unique names. This is easy to do in the case of internal cells, because they have the NAME field, for example, “Uncle's Workshop Sweet Share” (and this is not a joke ). However, external cells can be about three different types. The first is the cities and remarkable landmarks, like those shown in the picture. They have RGNN, NAME and the coordinates of the location of a huge outer square cell. However, there are many Vivek cells (because Vivec is huge ), so we will use the coordinates of the area to identify them.

Secondly, wasteland cells, for example, other parts of the region of the Ascadian Islands will be called using this method and their external coordinates.

Finally, there are external cells with no cell name and area, but with coordinates — in the TES Construction Set they are called Wilderness [x, y], so we will use the same name.


Each of these areas is itself a city, and they are all connected by bridges. In addition, they are on the water. Who would not want to live here?

The next step is to parse the contents of each cell, which is essentially an object ID and other data about the current link instance (for example, position, amount of health (for NPC) or possible destinations (for doors or NPCs offering transport services)).

And, yes, sometimes the links can be deleted - but instead of simply deleting the data from the file, they are simply marked as deleted. Perhaps this is because it would have to rewrite the entire file to remove them (because all the pointers in the file must be recalculated) - today this is nonsense, but in 2002 this would probably take too many resources.

It is also worth mentioning that object definitions can appear before or after they are referenced, so we have to parse the file in two passes - first writing down only the link IDs as strings, and then linking them to Python objects.

Fuh, the work is complete!

 In [1]: mages Out[1]: Vivec, Guild of Mages In [2]: mages.is_interior Out[2]: True In [3]: mages.destinations Out[3]: [(Vivec, Foreign Quarter Plaza, (-826.792800, 357.833600, 309.695400))] 

I did not add location cells to the list of destination points to which NPCs could be transferred from a cell to a player (for example, in the case of teleportation services) - it lists only the locations to which the doors in the cell lead.


The full version is here , but neatly - it weighs approximately 10MB.

Even using only this information we can create beautiful graphs. For example, I created the picture shown above in GraphViz, the nodes in it are cells and they are connected by edges when there is a door between them. The big group in the middle is Vivek. Small groups are scattered around the picture; these are not such big cities (like Balmora , Caldera or Ald'Runa ). Here there are also star-like formations - the center is the cell with the name, and the cells connected to it will be internal, which can be penetrated through it - these are smaller settlements.

But we did not strive for this. We want to know how to get from point A to point B with everything that the world can offer us, not just doors. Let's talk about how we describe the real movement graph.

Create a route planner

Obviously, the game has an infinite number of points, but we do not need to consider them all. We need to consider only the starting point, the end point and all possible important points through which our route can pass. Therefore, we can simply specify the nodes of the graph as follows:

• For each object that offers “moving” services (NPCs / doors), the location of the object and the moving point
• The location of each Divine / Almsivi Intervention marker.

That's all. The description of our route will then be approximately as follows: “From the starting point go up to this door (point 1), go through it to another cell (point 2), go up to the NPC offering transport services (point 3), move to another city (point 4 ), go to the destination (point 5). " So let's see how you can connect the nodes of the graph.

• The location of the move offering service (door, teleport / Silt Strider NPC driver) is connected to the destination point with an edge with a length of 0.
• If two nodes are in the same cell (or both are in the outside world), then they are connected by an edge whose length is proportional to the distance between them (that is, we ignore, for example, mountains in the outside world and an impassable obstacle in internal cells).
• Each node is connected to the nearest Temple / Imperial Fort (using direct Euclidean distance in the case of external cells or distance from the nearest external cell in the case of internal cells).

Using this method, I came to the displacement graph consisting of 6424 vertices and 16065 edges only teleportation - they include Intervention doors / transport services / spells, but not direct movements inside the cells, because in this case it is very easy to find the distance between any two dots on the fly.

One interesting feature of the shortest path search algorithms is that finding the shortest path between two nodes (the shortest path for one pair) is as computationally expensive (it has the same asymptotic complexity) as finding the shortest path from a node to all points of the graph (shortest path). path from one point). It is intuitively clear that this happens because our ideal path for the task of one pair can include any point of the graph, so we still calculate the shortest path from one source to this point.

With such things Dijkstra's algorithm copes quite well, finding the shortest paths from one point to all points in O (| V | ²) (where | V | is the number of nodes in the graph). It can be improved using the Fibonacci heap for storing unexplored vertices and getting those closest to O (1), which gives us the time complexity O (| E | + | V | log | V |). I decided that searching for only 6000 vertices would not take too much time, so I didn’t implement it, but maybe I’ll do it later.

I used Arion as an experimental rat in this experiment - he becomes the main questgiver at the later stages of the Telvanni quest line and lives in a rather remote tower in the wilderness with an almost complete lack of transportation services. Therefore, although you can use Mark / Recall to get to him, his quests can send you to different points of the game world, getting into which quickly becomes a non-trivial task.

After feeding this graph to Dijkstra’s algorithm (which took about 10 minutes, which is quite long), I received two lists: the first one for each point indicates the weight of the cheapest (in our case, fast) route from Arion to this point. The second for each point indicates the previous point on the fastest route. Thanks to this, we can quickly recreate the optimal route by following these links to the point of interest.

For example, how do we get from Arion to the Dunmer fortress of Chlormaren on the other side of the island? Like this:

 target Out[35]: (Hlormaren, Dome, (384.000000, -408.000000, 384.000000)) route = chain_prev(prev, target) route Out[37]: [(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)), (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)), (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)), (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)), (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)), (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)), (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)), (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)), (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)), (Balmora, Guild of Mages, (-755.896600, -1002.733000, -644.627900)), (Balmora, [-3,-2], (-22130.610000, -8582.789000, 889.572800)), (Hlormaren, [-6,-1], (-43200.000000, -3448.000000, 3072.000000)), (Hlormaren, Dome, (320.000000, -256.000000, 402.000000)), (Hlormaren, Dome, (384.000000, -408.000000, 384.000000))] 

The disadvantage here is that we don’t actually see the mode of movement required for the transition between nodes, so knowledge of the game is required to decipher the travel plan. In essence, we need to use the Divine Intervention spell to get to Fort Wolverin Hall, then enter the Imperial Sanctuary, unceremoniously go through it to the inner part of the fort, enter the Magician's Guild, teleport to Balmor and then leave / fly away from there to Chlormarin.

What about getting into the family tomb of Saris , which is located on a remote island in the southwestern edge of the map? Easier nowhere.

 [(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)), (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)), (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)), (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)), (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)), (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)), (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)), (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)), (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)), (Vivec, Guild of Mages, (3.520470, 1391.325000, -385.853300)), (Ebonheart, [1,-13], (8703.056000, -100602.000000, 1383.638000)), (Bitter Coast Region, [-5,-9], (-37659.390000, -69956.550000, 322.489000)), (Sarys Ancestral Tomb, (7028.375000, 4415.659000, 15001.790000))] 

We need to go back to the Sadrit Mora's Guild and teleport, this time to Vivec. Then we once again cast Divine Intervention and find ourselves in Ebonhart, which is on the same boat ride from the island to the tomb.

Later in the Morrowind project we will try to make the recommendations of the planner a little more understandable by placing them on the game map. Maybe mapping and other things. Perhaps the article will even be the source code!

Part 4

I welcome you again to the Morrowind project, in which we will use technology to put pressure on people in their own political interests.

This Saturday morning a couple of hangover Telvanni wizards approached my house. Last night, they went to the tower of Master Arion to skip a glass, which quickly turned into several glasses. In short, Arion managed to get somewhere, and since then no one has seen him. Moreover, next Monday there will be a meeting of the Council, and the absence of Arion will be a disaster.

The wizards asked me if I could show locations on the map where Arion might be located in order to concentrate the efforts of my agents and have time to find him before the meeting.

Having imagined which posts you can write about in your blog, I agreed.

Graph regeneration

At first I had to change the weights between the edges of the displacement graph, because in the internal game time, moving on a silt strider or boat is not instantaneous. But it can still be calculated from the distance: the speed of movement is a game parameter, by default equal to 16000 units per game hour. For example, the distance from Seyda Ning to Balmora is about 55,000 units, so if at the beginning of the game you decided to spend money on public transport and not go on foot, then you would get to Balmore and complete your first quest in less than 3.5 hours of play.

To determine the time of movement on foot between locations also required research. The minimum walking speed in the game is 100 game units per second of the real world, and the game time by default flows 30 times faster than the real one. That is, the passage of 16,000 units will require approximately 16,000/100 * 30/3600 = 1 h 20 min of playing time. As you can see, this is not much slower than riding a silt strider, and if you see it , you will understand why.

Obviously, if the words “Guild Guide” are in the name of the NPC relocation class, then relocating with it does not take time, because it is magic.

By rebuilding the graph and running Dijkstra’s algorithm for it again, we can easily determine how long it would take Arion to move to any place in the game world, given that he used the fastest route. We need to go through all points of the graph where we know the shortest travel time, and find the one for which the total travel time (the shortest time to move to this point + time to walk from this point to the destination point) will be the smallest.

There is an optimization that I did not use: in fact, we are interested only in those points of the graph, into which we can get by any route, except on foot. Consider this case: if the shortest path to a point is created from teleportation to some point A, and then walking to point B, and then walking to point C (all this in a straight line), then why not walk directly from A to C (we assume here that Arion can levitate and move between the points in a straight line, so any three points in the outer cells follow the triangle inequality).

But, of course, simply giving Telvanni wizards a list of in-game coordinates is not worth it. They need a map, and I will give them a map. Affinity card, oddly enough.

A quick, incomplete and mostly erroneous introduction to linear algebra

The problem here is that we want to find a way to convert a pair of pixel coordinates on the game map to the coordinates of the game world. Fortunately, this transformation has an important property: the straight line between any two points on the game map will also be direct in the world itself. Such transformations are called affine: they can be created from primitive operations like transfer, rotation, reflection, etc.

The good news is that they can be presented as a matrix product.

$$

$$\ begin {pmatrix} x_ {GAME} \\ y_ {GAME} \\ 1 \ end {pmatrix} = M \ begin {pmatrix} x_ {MAP} \\ y_ {MAP} \\ 1 \ end {pmatrix}$$

Therefore, if we have a pair of coordinates on the map and this matrix is ​​M 3x3, then we will be able to calculate the real in-game coordinates, and vice versa. The third component of the vector, equal to 1, is a dirty hack, which allows us to encode transfers (motion), because otherwise the vector (0, 0) on the map would correspond to the vector (0, 0) in the game. Read more about this in Wikipedia .

How do we find such a matrix? Well, we can use it to convert several vectors at the same time:

$$

$$\ begin {pmatrix} x_ {GAME, 1} & x_ {GAME, 2} & x_ {GAME, 3} \\ y_ {GAME, 1} & y_ {GAME, 2} & y_ {GAME, 3} \\ 1 & 1 & 1 \ end {pmatrix} = M \ begin {pmatrix} x_ {MAP, 1} & x_ {MAP, 2} & x_ {MAP, 3} \\ y_ {MAP, 1} & y_ {MAP, 2} & y_ {MAP, 3} \\ 1 & 1 & 1 \ end {pmatrix}$$

And this can be rewritten as follows (by inverting the matrix to the right and multiplying the whole equation by it):

$$

$$M = \ begin {pmatrix} x_ {GAME, 1} & x_ {GAME, 2} & x_ {GAME, 3} \\ y_ {GAME, 1} & y_ {GAME, 2} & y_ {GAME, 3} \\ 1 & 1 & 1 \ end {pmatrix} \ begin {pmatrix} x_ {MAP, 1} & x_ {MAP, 2} & x_ {MAP, 3} \\ y_ {MAP, 1} & y_ {MAP, 2} & y_ {MAP, 3} \\ 1 & 1 & 1 \ end {pmatrix} ^ {- 1}$$

In essence, if we take three sets of coordinates in the game world and on the map, then we can use them to recreate their relationships. In addition, these three points cannot be on one straight line, because in this case the determinant of the map coordinate matrix would be zero and it would not have an inverse matrix.

Therefore, I chose the game coordinates of three points, which are fairly widely distributed (to minimize the error) and tried to determine the corresponding pixel coordinates on the map.

As a result, I came to this matrix:

$$

$$M = \ begin {pmatrix} 185.38 & -0.43327 & -126720 \\ 1.2986 & -0.018372 & 218470 \\ 0 & 0 & 1 \ end {pmatrix}$$

To test it, I plotted the three reference points that I used to calculate it (red), as well as Arion’s original location (blue dot): the outer door to his house is located in the game coordinates (85730.77, 117960.3, 5081.284), which we through are tied to (1147.33, 555.21).


From here I see your home!

In the next part, I will tell you how I managed to find Arion and save the Council of Telvanni from collapse.

Part 5

A good visualization of where Arion might be is already very close. I chose the stupidest approach: go through all the pixels of the map, convert each of them to the point of the game world, and find the time it would take Arion to get there (using the method I mentioned above: go through all the points of the graph, which we know the shortest time of movement and find the one for which the total time of movement (the shortest time of movement to this point + time to move from this point on foot to the destination point) is the smallest).

But I forgot that I work in Python and that I will have to go for about 2400 possible routes through external points for each point of the map. And there are only 1650x1900 = about 3 million points. Of course, you can come up wisely and use different optimizations (for example, collect external points that are close enough to each other and process them as one, or use the triangle inequality (what I said in the previous part), or consider blocks of 2x2 maps, not every pixel , or use all 4 cores of my processor instead of one). Or I can just make a decision in a C ++ program.

Therefore, I have merged into the file a dump of the list of known external coordinates and the time of the shortest routes to them, as well as the in-game coordinates of more than three million map points that interested me. The program took them and gave the shortest time for each coordinate considered that Arion would have needed to get there from his tower. In fact, it took 40 lines of code and 10 seconds of calculations. It is rather surprising how quickly problems can be solved if you communicate directly with the hardware.

Then I used the contour chart from matplotlib to visualize the resulting heat map. I did not manage to put it on the map in its original resolution, but the wizards were still extremely impressed and said that I could contact them when I became interested in finding the means for my startup.

!

It actually makes sense. There is a two-hour circle around Arion’s house (in the northeastern part of the island), from which he can walk or teleport to Wolverin Hall using Divine Intervention (to the island east of Vanderfell). In Wolverin Hall there is the Mages Guild, so he could instantly move to one of the four main cities (circle along the western edge of the island). That is, there are quite a few places that can be reached in two hours!

After that, he could take a silt strider or a boat, which would slow him down. For four hours, he could barely get to Gnisis (the northeastern corner of the island) or Maar Ghana (a small arc in the upper part of the four-hour contour around the main settlements). Of course, he could walk four hours from his starting point, but he would not get far.

In six hours he could have reached anywhere in the island, and in eight hours he could reach the northern edges of Dagon Fel, a small island north of Vvardenfell. Finally, after about 11 hours, he was likely to have breakfast with Bolshegolov in the most isolated corner of Morrowind. Maybe he had some business there ?

The wizards said that the last time they saw Arion was at about two in the morning, so by this time he had been away for almost 10 hours. Fortunately, while we were trying to find out if he could choose the most efficient route, in order to get as far away from his tower as possible, we heard a loud noise from the neighboring cabinet, from which Arion was sleeping, but unscathed.

In the end, he liked my outline schedule so much that he hung it on his wall. Some say that the tower manager still uses it to search for people lost after Arion’s crazy parties.

In the next part of the Morrowind project, we will talk about my appointment to the position in the Vvardenfell Bureau of National Statistics to analyze the island’s demography.

Part 6

So, Arion returned to his tower, and the entire population of the island maximized the effectiveness of their travels. It is time to take on another task and create some more beautiful pictures. The next question was simple: where do all these people live and what do they do?

Let's try to use all the power of our excellent matrix, which transforms in-game coordinates into coordinates on a map and create something like a heat map of the population. This is easy to do, because we already have all the pieces of the puzzle: we know where all the NPCs are and what they do, their race and gender. The only problem with working with NPCs is in the inner cells: remember that the inner spaces are completely separate mini-worlds? This means that we cannot simply display the character’s location by taking the coordinates of two doors and adding the NPC offset relative to the door, because the inside of the interior is often larger than they look from the outside. Since we will only be able to review the world, I decided not to care about such accuracy: the external location of the NPC is just the location of the nearest external door,to which they can get close (by the number of cells that they must pass in order to go outside).

Armed with these tools, I walked around all the NPCs in the world, got their external location, and converted it to coordinates on a map. I had a matrix the size of a map in which these coordinates accumulated: the number for each pixel was the number of NPCs whose external coordinates correspond to this square. This meant that I would get a disproportionately large number of people accumulating at the doors of densely populated interiors, which was not optimal because it was difficult to see the image (after all, it was just one pixel). In addition, it poorly reflected the in-game reality: first of all, we are interested in the population of individual cities / regions, but people still do not stand in one place, but wander around the neighborhood.

Therefore, I applied to my matrixGaussian blur , that is, one pixel instead of 10 people is assigned to about 2.2, for the neighboring pixel - 1.1, for a pixel in two pixels from the original one - 0.5, and so on. This is similar to the fact that we cut people into pieces and throw these parts of the bodies so that a comfortable pile of them is assembled, because that's how we do it.

Having finished with this, I normalized the matrix so that all values ​​were in the range from 0 to 1, applied one of the many color maps available in matplotlib (I liked the card called blues) and mixed it with the original map. I also experimented with using the function of converting input values ​​before transferring them to a color map, because I did not like its default appearance - I chose a logistic function :

$$

$$f(t) = \frac{1}{1 + e^{-k(t-c)}}$$

I have not used any methodology here: variable $$changes the slope of the curve (the speed of movement of values ​​from the left side of the color map to the right side and the increase in brightness), and the variable$k$$$ changes the centering function, so I experimented with them until the picture looked good. With this in mind, let's see what happened as a result!$c$




draw_npcs(filter_sigma=25, sigmoid_k=8, sigmoid_c=0.2, output='map_population.png')

In large cities we got dark spots. From bottom to top: Vivek (and Ebonhart next to it ), then Balmor (in the southwestern part of the island), Sadrit Mora (in the east), Ald'Rune (north of Balmora) and Gnisis (northeast of Ald ' Fleece). There are also smaller spots here - either small settlements or large dungeons / fortresses / shrines.

What else can we do about it? How about mapping all the dark elves ? Yes, easily, just pass not all NPCs:


draw_npcs(filter_sigma=25, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_darkelf.png')

Yes, it looks exactly like a heat map of the population . Maybe check where they are too much or too little? We can separate these two layers one on another and get the proportion of dark elves in the whole population:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=4, sigmoid_c=0.5, output='map_population_darkelf_relative.png')

For this picture I had to play around with the parameters (I increased the blur radius and moved the center of the sigmoidal curve to 0.5), but we can see that dark elves (Aboriginal Morrowind is less represented in the southwestern part of the island (it is more cosmopolitan and hospitable towards strangers) and more represented in the eastern territories, as well as around Ashlander camps (which are almost entirely composed of them).

What else can we do? There is slavery in Morrowind! Let's find out where all the slaves are concentrated:


draw_npcs(relative=True, filter_sigma=25, mark_npcs=[n for n in npcs if n.class_name == 'Slave'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_slave_relative.png')

There are no spots around big cities - this is logical, because it is not a relative share. Instead, spotted random dungeons and plantations of the world, which contain slaves, including the Abebaal Egg Mine , Drain Plantation , several slave markets , Rotheran or Chlormairen (interestingly, for the latter, the spot (to the west of Balmora, behind great water) in the west of the fortress itself, because the slaves are kept in the sewer, the outlet of which is located somewhere here).

Of course, we would never use this tool for our own selfish purposes:


draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.is_female], sigmoid_k=12, sigmoid_c=0.7, output='map_population_female_relative.png')

There are very few places on the island in which there are too many women (note that I set the center of the sigmoidal curve to 70%). One of them is the city of Tel Mora in the northeast. This happened because the governor of the city "does not like the presence of men" and all the inhabitants of this city are actually women. Another place is Odirniran in the southeast, Telvanni fortress, attacked by House Hlaalu. To the northwest there is an Assu with two wizards, and to the north of him there is Tel Uvir , a fortress being built for the player as part of the Telvanni quest line. At the beginning of the game it is disabled (and invisible), but the program. Of course, it does not care.

Conclusion

Finally, I broke the code used to get all the graphs into a set of modules and uploaded it to GitHub . You need the usual scientific Python toolkit (NumPy, SciPy, matplotlib, and PIL) and the C ++ compiler. I decided that it would be a bad idea to publish the game data dump I received, so you will have to do it yourself: you will need the original Morrowind.esm and Enchanted Editor data file (instructions for creating the dump are in the README).

Given all this, I ran the code again, and he gave me a set of images similar to those used in this post, which I was incredibly happy about.