project Morrowind, part 3

Today on project Morrowind, we take decades of research into rendering 3D scene descriptions to beautiful photorealistic worlds and throw it away.

morrowind3
I finally give up on any nontrivial formatting in WordPress and hope it can’t mangle text in pictures.

Loading cell data

There are a few catches to parsing cells in Morrowind, the first one being how we can uniquely name one. It’s easy with interiors, since each interior has a NAME field, like “Uncle Sweetshare’s Workshop” (and that’s not a joke). However, there are about three types of exteriors. The first one is cities and notable landmarks – like the example in the picture, those will have a RGNN, a NAME and some coordinates of where the massive exterior square cell is located. However, there are many Vivec cells (since Vivec is really big) and so we’ll use the region coordinates as well to identify one.

Secondly, wilderness cells like other parts of the Ascadian Isles Region will be named just using that and their exterior coordinates.

Finally, there are exterior cells without neither a cell nor a region name but with coordinates – those are named Wilderness [x, y] in TES Construction Set, so let’s use that as well.

mw_map_vivec
Each one of these cantons is a city by itself and they are all joined by bridges. Also, it’s on the water. Who wouldn’t want to live here? (from http://www.uesp.net/wiki/File:MW_Map_Vivec.jpg)

The next step is parsing out the contents of each cell, which is basically an ID of an object and other data about the given instance of the reference (for example, the position, the number of hit points (for an NPC) or possible destinations (for doors or NPCs offering travel services)).

Oh, also, references can sometimes be deleted – but instead of them being removed from the data file, they are just marked as deleted. This could be because actually wiping them from the file would imply rewriting the whole file over (since all the pointers in the file would have to be recalculated), a joke now but something that would probably take up way too many resources back in 2002.

One thing that should be noted is that the actual object definitions can appear before or after they are referenced and so we have to parse the file in two passes – first recording just the reference IDs as strings and then linking those to actual Python objects.

Whew, we’re done!

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 haven’t included the locations that NPCs in the cell can take the player to (like the teleportation services) in the cell destinations’ list – it only lists where the doors in the cell lead to.

graph-2016-2
The full version is at https://mildbyte.files.wordpress.com/2016/03/graph-2016-2.png, but beware – it’s about 10MB large and might break your browser’s assumptions about how large PNGs can get.

But even with this information, we can create cool-looking graphs. For example, I produced the picture above with GraphViz, on it the nodes are cells and they are joined with an edge if there’s a door between them. The large clump in the middle is Vivec. There are some smaller clusters dotted around, being slightly smaller cities (like Balmora, Caldera or Ald’runh). There are also some hub-spoke formations in there as well, the hub being a named exterior cell and the cells joined to it being the interiors that are accessible through it – these are smaller settlements.

Yet this is not what we came here for. We want to know how to get from point A to point B while exploiting everything this world has to offer us – not just the doors. So let’s talk about how we will define the actual travel graph.

Building a travel planner

Clearly, there’s an infinite number of points in the game, but we don’t need to look at them all. We only need to consider our start point, our end point and all potential points of interest our travel can go through. So we can easily define the nodes in our graph:

  • For every object offering travel “services” (NPCs/doors), the object’s location and the travel destination.
  • The location of every Divine/Almsivi Intervention marker.

That’s it. A description of our route would then be something along the lines of “From the starting point, go to this door (point 1), go through it to a different cell (point 2), walk to the person offering travel services (point 3), travel to a different city (point 4), walk to your destination (point 5)”. So let’s see how the nodes in the graph can be joined.

  • A travel “service” provider’s location (a door or an actual teleporter/silt strider driver NPC) is joined to its destination with an edge of length 0.
  • If two nodes are in the same cell (or both are in the exterior world), they’re joined with an edge of length proportional to the distance between them (so we ignore, say, mountains in the exterior world or impassable obstacles in the interior).
  • Every single node is joined to the nearest Temple/Imperial Fort to it (using the straight as-the-crow-flies Euclidean distance for exteriors or the distance from the nearest exterior cell for the interiors).

With this method, I ended up with a travel graph that had 6424 vertices and 16065 teleport-only edges – that includes doors/transport services/Intervention spells but not direct within-cell travel, as it’s very easy to find the distance between any two points in that case on the fly.

One interesting thing about shortest-paths algorithms is that finding the shortest path between two nodes (single-pair shortest-path) is as computationally expensive (has the same asymptotic complexity) as finding the shortest path from a fixed node to everywhere in the graph (single-source shortest-path). Intuitively, this is because our ideal path in a single-pair problem could include any point in the graph and so we are calculating the shortest path to that point from our source anyway.

Dijkstra’s Algorithm works pretty well for these kinds of things, finding the shortest paths from a single source to everywhere in O(|V|²) (where |V| is the number of nodes in the graph). This can be improved by using a Fibonacci Heap to store unexamined vertices and fetch the closest ones in O(1), giving a time complexity of O(|E| + |V|log|V|). I didn’t think just 6000 vertices would make the search take too much time, so didn’t implement one, but perhaps will do later.

I used Aryon as a guinea pig for this experiment – he becomes your main questgiver in the latter stages of the House Telvanni questline and happens to live in a fairly isolated tower in the middle of nowhere with almost no travel services. So while you can use Mark/Recall to get to him, his quests can send you across the game world to places reaching which quickly can be nontrivial.

After unleashing Dijkstra upon this graph (which admittedly took 10 minutes, slightly too long) we get two lists: first, for each point, the weight of the cheapest (fastest in this case) route from Aryon to that point. Second, for each point, what is the previous point in the fastest route. Hence we can easily reconstruct the optimal route for a point of interest by following those links.

For example, how do we get from Aryon to Hlormaren, a Dunmer stronghold on the other edge 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))]

There’s a disadvantage here in that we don’t actually see the method of travel to get between nodes and so this travel plan takes some game knowledge to decipher. Basically, we want to use a Divine Intervention spell to go to the Wolverine Hall Fort, then enter the Imperial Shrine, unceremoniously walk through it into the Fort interior, enter the Mage’s (sic) guild, get ourselves teleported to Balmora and then walk/fly from there to Hlormaren.

How about getting to Sarys Ancestral Tomb, which is located on a remote island on the southwest corner of the map? Easy.

[(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 want to again go to the Sadrith Mora Guild and get teleported, this time to Vivec. Then we cast Divine Intervention one more time and end up in Ebonheart, which is a swim away from the island on which the tomb is located.

Next time on project Morrowind, we’ll try to make the planner’s advice slightly more readable by plotting it on the game map. And maybe plot other things on the map. There might even be some source code!

Advertisements

project Morrowind, part 2

Today on project Morrowind, we will start turning some horrible binaries into beautiful data structures in the memory space of a Python interpreter. They are still technically binary, but let’s not dwell on it too much. Otherwise we will realise we’re all made of atoms and will have an existential crisis and that wouldn’t be very nice.

morrowind_esm
I…I don’t even see the code. All I see is tree, rock, marshmerrow…

Exposition dump

Elder Scrolls games made by Bethesda Softworks, including Morrowind and its successors (Oblivion, Skyrim and that peculiarly also kind of includes Fallout 3 and 4) store their core game data (that is, maps and locations of various objects, but not textures/audio/meshes) in the ESM (Elder Scrolls Master) format. It’s been evolving ever since Morrowind as the Bethesda developers have been adding more and more features to it, but its main idea remains the same: these files are a collection of records of different types.

For example, we can have an NPC_ record, defining a character in the game, which will contain entries for the character’s gender, race, AI behaviour etc. It can also have references to other records, for example, the inventory of a character, which refer to ARMO and WEAP records. CELL records describe in-game cells (actual locations) and contain references to, well, everything that is located in that cell, like NPC_, ARMO, WEAP or CONT (containers, e.g. chests). The actual binary format for Morrowind is described very well here and every release of a new Bethesda game promises players lots of fun in reverse engineering their ever so slightly minor alterations to the game data file format.

One clever idea that Bethesda had was making game save files an overlay on the game data files in this format. For example, if you were to kill someone in a certain location (pretty much what usually happens in Elder Scrolls games), your save file would have a redefinition of the CELL record that would list the NPC in question as perished. Sadly, this idea has no relevance to this project, just like lots of other clever ideas, but it’s interesting nonetheless.

There are more complications though: cells can be exterior or interior. Exterior cells are square-shaped and are joined together edge-to-edge to create the actual great (dubious) outdoors of Morrowind. With interior cells, all bets are off – each of them resides in its own little reality and is joined to other cells by doors which basically function as teleports in this case. A small house in the exterior cell often is quite a bit larger from the inside, which means that you can’t reliably judge where the player actually is when they’re indoors.

So if we want to reconstruct a graph of how you can travel around in Morrowind, we have to take care of doors, amongst all other means of movement.

With regards to the Almsivi/Divine Intervention spells, there are special marker objects in every Temple and Imperial fort – this is how the game determines where to teleport the player when they cast a particular spell. It’s again easy with the exterior cells (as all markers are located outside), but gets more complicated with interiors. Some people claim Morrowind uses the last exterior cell you’ve been to (which has some pathological cases – say you use a Guild Teleport that teleports you from the indoors to the indoors again, so casting an Intervention spell will warp you to the closest marker to the first Guild, not the second one) and OpenMW, an open-source reimplementation of the Morrowind engine, tries to fix that by using the closest exterior to you as a reference. My copy of Morrowind behaves the correct way for some reason, so I’ll emulate that.

In much better news, if NPCs offer travel services (be it silt strider, boat or Guild teleport), it will be encoded in their record.

All in all, it seems like we want to scrape the hell out of all CELL and NPC_ records, as they contain everything we need for now.

Scraping the hell out of all CELL and NPC_ records

Now, as much as I thought it would be feasible and fun to decode the binary data according to that excellent spec, I still decided to cheat and used Morrowind Enchanted Editor, a low-level editor for ESM files. In particular, I used the “Dump to Text File” function, which turned the unreadable binary mess into a readable ASCII mess.

morrowind_esm_parsed
Meet Todd’s Super Tester Guy, presumably made by Todd Howard himself.

This is something we can work with: each entry in the record is on a separate line and is clearly keyed by the subrecord (e.g. FNAM is the full name, RNAM is the race name etc). As a good starting point, we can easily extract just the NPC_ and CELL records and tokenize the data by just converting it into a stream of key-value pairs (so a line NPC_ NAME todd would get turned to a tuple (NAME, todd) since we already know it belongs to an NPC_ record).

(I was going to put source code and explain it, block-by-block, here, but WordPress decided to not be on my side today. I’ll post it on GitHub later, promise. I mean, seriously, who the hell converts > to > after a save cycle and then again to &gt?)

In the end, 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 the stream of NPC_ records into a list of NPCs isn’t that difficult. I found the neatest way was to pass the stream to a class constructor and allow it to consume as much from it as it needs to initialize itself. But keep in mind that we need to stop parsing when we see the next NPC’s NAME subrecord and if we’ve already consumed that, it’s too late, so we need to define an iterator that allows us to peek at the next item without consuming it.

Parsing the list of destinations, one of the Holy Grails that we’re looking for, is easy too – just look at this example (which is one of the places that Todd’s Super Tester Guy can take 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 x, y, z coordinates and the angle (which we don’t really care about). Sometimes there’s also a DNAM subrecord if we’re in an interior cell.

Add a __repr__ method and we can see a list of actual 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 “agronian guy” named Tarhiel over there. Firstly, that race name is spelled Argonian. Secondly, he’s not an Argonian, he’s a Wood Elf. And finally, he has some mental issues but also talents.

Next time on project Morrowind, we’ll move on to trying to decode CELL data, which has some more peculiarities (like the fact that it contains most of what the player can perceive). But now that we’ve gotten through the background and the boring bits, we will start moving faster and might even get around to constructing an actual travel graph!

project Morrowind, part 1

You should play Morrowind.

(warning: lots of skippable praise for Morrowind here, scroll down for the meat of the post)

At the beginning of Morrowind, you’re a chump who just got off a prison ship with 87 gold pieces (one loaf of bread costs 1 gold piece in this world, so that’s conveniently about £35 – that’s how much you would pay for 87 packs of Tesco Everyday Value Sliced White Bread). Your first assignment is to take a parcel to a guy in a different city, and you either have to take the silt strider (a massive insect with long legs piloted by a possibly drunk creepy guy, not unlike London buses) or walk there through the wilderness, fighting off hordes of oversized carnivorous birds with the iron dagger you had just stolen from the Census office, except the dagger always misses because, see, Morrowind’s combat system is inspired by tabletop roleplaying games and they didn’t pay their animators that much, so even if your weapon clearly appears to hit the mushy body of whatever it is you, the player, are aiming at, there’s no guarantee at all that you have actually hit.

So after ruining a couple of mice with repetitive rage-filled clicks, you decide to quit Morrowind and do something better with your life.

Or you keep going and learn about how fatigue affects your chances to hit everything (and on everything), read up on game mechanics, buy a new mouse, make your way to Balmora and get immersed in one of the richest worlds I’ve ever seen in gaming. You go through a story that raises questions about organized religion, xenophobia, colonialism, tribal legends, prophecies, free will and the priorities of an individual versus the organization that they belong to.

And somewhere during that process of discovery, you realise that the swings with your crappy dagger don’t miss anymore. In fact, your dagger is no longer crappy. In fact, you don’t even use a dagger, instead having found an amazing sword in a dungeon guarded by a couple of possibly too sexualized and extremely dangerous monsters. You decide to murder a God and capture his soul because it has the biggest enchantment capacity. When you need to get somewhere, instead of a long slog through the wasteland you use one amulet to teleport to the nearest Temple, bunny-hop (because that makes you move faster) or levitate your way through whatever town you ended up at, enter the Mages’ Guild, use the Guild Teleport, use another amulet and finally fly to your destination. You murder entire cities in drug-fueled rampages just to please yourself and then reload the last save. You pilfer the treasuries of great Houses and steal rare armor and weapons, just to go to a remote island and sell them to someone who just happens to be a massive crab – you say it’s because he gives you the best prices, but it’s actually because everybody else is scared of you.

Just like real life.

(skippable praise ends here)

I decided to replay Morrowind recently and in the middle of that “high-ranking executive” stage, as I got slightly annoyed by all the fetch quests I had to do to get promoted in some guilds, thought about making myself a journey planner. This is not a completely trivial task because there are so many ways you can get around in Morrowind:

  • Walking (or levitating, because any self-respecting player has already enchanted something with a constant Levitation effect)
  • Taking the silt strider (or the boat) – but note you can’t immediately get to your target town and might have to change through one of those bad parts of town. Takes in-game time, but we’ll say it’s instantaneous as perceived by the player.
  • Guild of Mages Teleport – instantaneous as well. You have to talk to mages, but they are a nice bunch, really.
  • Divine/Almsivi Intervention – this is where it gets interesting. Divine Intervention teleports you to the nearest Imperial fort (Morrowind is part of the Empire and is still quite reluctant about that idea) and Almsivi Intervention teleports you to the nearest Tribunal Temple (which is the official religion of Morrowind that was around way before the Empire).
  • Mark/Recall – two spells, one places a mark and the other one teleports you to that mark.
  • Propylon Indices – long ago, someone decided to build lots of cool-looking strongholds in a circle around the island. Good news: there’s a teleport chamber linking them in a round-robin fashion. Bad news: you need a Propylon Mark for each one of those strongholds to use their teleport and those are often tough to find. Also, these strongholds have been overrun by various nasties and generally aren’t pleasant to be around. I’ll exclude them from my analysis for now.
fullmap_travelroutes1
There are minor delays on the Circle Line due to sharks (from http://www.terminally-incoherent.com).

 

So you can see how some interesting ways to get to places can arise by combining these means. For example, you could totally cast Almsivi Intervention to get teleported to the nearest Temple, then Divine Intervention to get teleported to an Imperial Fort, then use a Guild teleport and immediately cast another Almsivi to get to yet another town.

But of course it would be boring if I just spent some time reading those Morrowind travel maps, making a graph and running Dijkstra on it. For one, that wouldn’t make for a good blog post. In addition, it doesn’t help you if you end up somewhere in the wilderness (see that area in the middle, circled by Falasmaryon, Valenvaryon, Rotheran, Indoranyon, Falensarano, Ald’Ruhn and Maar Gan? Yeah, don’t go there).

Finally, there are quite a few large fan-made add-ons to Morrowind, including Tamriel Rebuilt, because, see, I’ve been lying to you and that island isn’t called Morrowind, it’s actually Vvardenfell and Morrowind is the landmass around this island. Tamriel Rebuilt tries to recreate this landmass (yes, the whole Morrowind isn’t in the game called Morrowind. What’s more, Tamriel is the whole Empire of which Morrowind is a part and, yes, Tamriel Rebuilt just tries to recreate Morrowind in-game. In the game called Morrowind).

All of this was me trying to convince you that it’s a good idea to find a systematic way to scrape this data out of game files to make our lives easier. And imagine the kinds of things we’ll learn if we do that! Demographics! Population heatmaps! Graphs! We might even plot property prices and travel times!

Next time on project Morrowind, we will battle with confusing binary formats, bizarre conventions, linear algebra, Python and will possibly learn more about the lore of Morrowind and its game mechanics. Stay tuned!

mr mildbyte, I presume?

So I decided to dust down this old blog for once. I realise I haven’t posted anything in the last 3.5 years, but that just means I have a lot to write about, right?

Here’s a quick recap of what went on since the last post:

  • I went to university, managed to graduate with a decent degree and met lots of cool people (you all know who you are!)
  • My final year dissertation project was at the intersection of bioinformatics, machine learning (Bayesian networks) and kind-of-but-not-really-high-performance Python.
  • My Raspberry Pi is still alive, bar a single memory card failure (there are two types of people: those who do backups and those who don’t do them yet). I decided against running large-scale raytracing experiments on it, so it now hosts some random lightweight services (files, wiki).
  • tRayce got some cool new features. I tried adding global illumination to it (photon mapping at first, but then settled on simple pathtracing), as well as importing OBJ files and textures. Here’s the Stanford Bunny, painstakingly pathtraced to perfection.
bunny-hires
I’m getting some Donnie Darko vibes from this.

For my next trick, I’m going to try posting here more often that once every 43 months.