After a few days of tinkering with Hakyll and migrating my pages around/making sure everything looks okay I can now claim that I have an independent, statically-generated blog at http://mildbyte.xyz/. All new posts (ha-ha, as if you expected any) will go there, though some images will still be hosted on WordPress. Let’s see how it goes.
And here’s an equivalent announcement on the new blog that links back here.
Look what I found in my drafts folder. Welcome back to project Morrowind.
The nice visualization of where Aryon could be was very close now. I went with the stupidest approach: go through all pixels on the map, convert each one into a point in the game world and find how long it would take Aryon to get there (by using the method I mentioned previously: go through all points in the graph we know the shortest travel time to and find the one for which the total travel time (shortest time to travel to that point + time to walk from that point to the destination) is the smallest).
Except I forgot this was Python and I was going to go through, for each point on the map, about 2400 possible routes through exterior points. And there were 1650×1900 = about 3 million points. Sure, I could be smart about it and use various optimisations (like coalescing exterior points that are close enough to each other and treating them as one or exploiting the triangle inequality (as mentioned in the previous post) or looking at 2×2 blocks on the map instead of each pixel or using all 4 cores of my CPU instead of one). Or I could farm it out to a C++ program.
So I dumped the list of known exterior coordinates and times of the shortest routes to those to a file as well as the in-game coordinates of the 3-ish million points on the map I was interested in. The program would take those and spit out, for each sought coordinate, the shortest time it would take for Aryon to get there from his tower. In fact, it took 40 lines and ran in about 10 seconds. It’s pretty amazing how fast you can be if you speak to the bare metal.
I then used matplotlib’s contour plot to visualize the heatmap I got. I didn’t manage to get it to actually overlay on the map in the map’s original resolution, but the wizards were still extremely impressed and said that I should speak to them whenever I was interested in seed funding for my startup.
So this actually makes sense. There’s a 2h circle around Aryon’s home (northeast portion of the island) from where he could either walk or teleport to Wolverine Hall through Divine Intervention (an island east of Vvardenfell). Wolverine Hall has a Mages’ Guild, so that means he could instantaneously get to four other major towns (a blob along the west edge of the island). So there are quite a few places he could get in 2 hours!
After that, he would have to take the Silt Strider or a boat, which would slow him down. In 4 hours he would barely be able to reach Gnisis (northwest corner of the island) or Maar Gan (the little arc at the top of the 4h contour around the main population centres). He, of course, could walk from his original location for 4 hours but he wouldn’t get very far.
In 6 hours he could be anywhere on the island and in 8 he would be able to reach the northern edges of Dagon Fel, a small island north of Vvardenfell. Finally, in about 11 hours he could very possibly be having breakfast with Big Head in the most desolate corner of Morrowind. Perhaps he had some business there?
The wizards said last time they ever saw Aryon was at about 2am, so he’d been gone for almost 10 hours by that point. Luckily as we were trying to figure out if he would deliberately take the most efficient route to get as far away from his tower as possible, we heard a loud noise from a nearby wardrobe and an asleep but still alive Aryon fell out of it.
In the end, he loved my contour plot as well and hung it up on his wall. Some people say the tower steward still uses it to track down people who go missing in action during Aryon’s wild parties.
Next year on project Morrowind, we’ll talk about my assignment with Vvardenfell Office for National Statistics to make sense of the island’s demographics.
Welcome back to project Morrowind, in which we use technology to oppress people for our own political gains.
A couple of hungover Telvanni wizards came by to my house this Saturday morning. They went to Master Aryon’s tower the night before for a round of drinks, which quickly escalated to several rounds of drinks. Long story short, Aryon managed to wander away somewhere and hasn’t been seen since. Worse even, a Council meeting was supposed to take place next Monday and Aryon not attending it would be disastrous.
The wizards wondered if I could map out the locations Aryon might possibly be in so they would be able to better concentrate their agents’ efforts across various cities in Vvardenfell and recover him before the meeting.
Imagining all kinds of blog posts I could write about this, I agreed.
I first had to alter the weights between the edges on the travel graph, since in actual game time travel by silt strider or boat isn’t instantaneous. But it’s easy to calculate from the distance anyway: the speed of travel is in a game setting that defaults to 16000 units per game hour. For example, the distance between Seyda Neen and Balmora is about 55000 units, so if in the beginning of the game you decided to spend money on public transport instead of walking, you would get to Balmora and finish your first quest in less than 3.5 game hours.
Determining the walking time between locations also required some digging. The minimum walking speed in the game is 100 game units per real-world second and the game time by default flows 30 times faster than real time. So walking 16000 units would take about 16000 / 100 * 30 / 3600 = 1h20m of game time. As you see, this is not much slower than taking the silt strider and if you saw one you would realise why.
Obviously, if our travel NPC has “Guild Guide” in his class name, traveling with him doesn’t take any time – because magic.
Having rebuilt the graph and re-run Dijkstra on it, we can easily determine how long it would take Aryon to reach any point in the game world, assuming he uses the fastest route. Go through all points in the graph we know the shortest travel time to and find the one for which the total travel time (shortest time to travel to that point + time to walk from that point to the destination) is the smallest.
There is an optimisation which I haven’t done: we actually only care about points on the graph where we can get by any other route than plain walking. Consider this: if a shortest path to a point is formed by first teleporting to some point A, then walking to point B and then finally walking to point C (all in a straight line), why not walk from A to C directly (we’re assuming here that Aryon can levitate and move between the points as-the-crow-flies, so any 3 points that are in the exterior follow the triangle inequality).
But of course just giving the Telvanni wizards a list of in-game coordinates would be a faux pas. They required a map, and a map I would provide. An affine map, of all things.
The problem here is that we want to find a way to convert a pair of pixel coordinates on the game map to coordinates in the game world. Luckily, this transformation has an important property: a line between any two points on the game map is also a line in the actual world. Such transformations are called affine: they can be composed out of primitive operations like translation, rotation, reflection etc.
The good news is, they can be represented by a matrix product.
So if we have a pair of map coordinates and this 3×3 matrix M, we’ll be able to calculate the actual in-game coordinates, and vice versa. The third component of the vector being 1 is an ugly hack that allows us to encode translations (movement), since otherwise the vector (0, 0) on the map would map (he-he) to the vector (0, 0) in the game. More on Wikipedia.
How do we find such a matrix? Well, we can use it to transform several vectors at the same time:
And (by inverting the matrix on the right and multiplying the whole equation by it) this can be rewritten to
Essentially, if we get 3 sets of coordinates in the game world and on the map, we can use those to recover our mapping. These 3 points also can’t be on the same line because then the determinant of the matrix of map coordinates is zero and it doesn’t have an inverse.
So I picked the game coordinates of 3 locations that were fairly well spread (to minimize the error) and tried to pinpoint the corresponding pixel coordinates on the map.
In the end this is the matrix I found:
To test it out, I plotted the three reference points I used to calculate it (in red) as well as Aryon’s initial location (in blue): the exterior door to his house is located at game coordinates (85730.77, 117960.3, 5081.284) which he matrix mapped to (1147.33, 555.21).
This edition of project Morrowind was overdue by about two months, so I sadly have to stop here. But next time I’ll definitely tell you how we managed to track Aryon and save the Telvanni council from collapse.
Today on project Morrowind, we take decades of research into rendering 3D scene descriptions to beautiful photorealistic worlds and throw it away.
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.
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.
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.
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:
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.
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!
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.
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.
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.
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!
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:
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!
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:
For my next trick, I’m going to try posting here more often that once every 43 months.
I wanted to take a break from compiling kernel modules and making hardware work and so decided to compile tRayce, a raytracer that I wrote recently, on the Pi and see how slower it exactly was.
The first problem arose on the compilation stage: it was slow. tRayce has 8 source files and it took the Pi about 5 minutes to compile the first one. That wasn’t terribly inspiring, since I did plan to do some programming on it and didn’t have enough swords or chairs to help me tolerate long compilation times.
Hence I compiled a cross-compilation toolkit with crosstool-ng so that I could create binaries for the Pi on my laptop, which would be tremendously faster.
I used the instructions here, which was quite straightforward with the only effort required from me being waiting two hours for the toolkit to get compiled. I did mess up a bit by forgetting to choose to build the C++ compiler and so had to rebuild everything from scratch. I did mess up twice, actually, as the AUR already has the required packages. Oh well.
I compiled tRayce for the ARM architecture on my laptop, transferred the executable onto the Pi using scp and launched it.
It took about 2 minutes for the scene to render (the same scene took 2.5 seconds on my laptop) and there was another problem: the scene was dim. This probably was due to the compiler messing up some floating-point instructions. I changed all float variables to double in my code (which isn’t supposed to change the performance much) and recompiled it again.
It was better this time: my scene was ready in 30 seconds, however, the scene still wasn’t the same as the reference one I rendered on my laptop: the specular highlights on the spheres were bigger than on the reference. Still some floating-point issues or incorrect compiler flags.
(reference render and the render I got from the Pi.)
The next day, I decided to wait through the compilation on the Pi to see if the image was still different. To my surprise, the compilation went much quicker (~30s for the whole project) for no apparent reason. The scene, on the other hand, took about 3 minutes to render, which definitely was too much and probably meant that my system only supported soft ABI (instead of floating-point operations, the system uses integers and doesn’t delegate anything to the FPU, which is quite a waste). However, the scene now was completely the same as the reference.
According to the Raspbian FAQ, I could compile my program so that it could do the floating-point operations on the FPU and pass the function parameters around in FP registers (hard ABI). The bad news were, I couldn’t do that on a soft-ABI system — all libraries on my system must support hard ABI and I did confirm that the Arch ARM build that I was using wasn’t built with hard ABI support.
I could start using Rasbian, but this could lead me down the route where I would have to compile most of the needed packages myself, as the precompiled binaries wouldn’t be supported by my system. I also could theoretically rebuild all libraries and the whole toolchain to create a version that would only be used for tRayce (according to this StackOverflow comment), but there was an easier solution.
Luckily, GCC supports the flag –mfloat-abi=softfp that, according to this page, “allows use of VFP while remaining compatible with soft-float code”. The exact mechanism of compatibility, apparently, is that the resulting program uses the FPU, but all parameters are passed around using integer registers, which does have some overhead. Nevertheless, I compiled tRayce with these flags:
CFLAGS := -g -Wall -march=armv6 -mfpu=vfp -mfloat-abi=softfp -O2
and launched it, which brought the rendering time back down to ~40s and giving the same scene as the reference.
(In unrelated news, I printed out and glued together Punnet, a printable and together-glueable case, which probably should make the Pi hotter (in both senses)).
And this is a full-sized (1280×800) scene with 4x antialiased edges and soft shadows that was rendered on the Pi in 256 seconds (nice number), which is ~12 times slower than on my laptop (strange, since the light version of this scene was rendered ~20 times slower on the Pi).
Linux is very famous for having problems with certain hardware, including NVIDIA Hybrid SLI (and its successor, the infamous NVIDIA Optimus) -enabled GPUs and various wireless chips. The situation has been improving recently — there are a lot of open- and closed-source wireless drivers available (that still require some weird actions, like downloading things from a computer that doesn’t have the Internet connection to make the Internet connection work), but for some chips the situation is still bleak.
I had a D-Link DWL-G132 USB wireless dongle lying around. Plugging it into the Pi and doing lsusb revealed this:
Bus 001 Device 004: ID 2001:3a03 D-Link Corp. DWL-G132 (no firmware) [Atheros AR5523]
Bad news: there is no firmware for the wireless dongle. Good news: we found the name of the chip that it uses, i.e. Atheros AR5523. I first decided to acquire the firmware, since it seemed like the actual driver was already in the system.
A Google search revealed that there existed a driver called ar5523 (surprise!) and it apparently hadn’t made it yet into the kernel. I downloaded the firmware from its page, copied it into my /usr/lib/firmware and restarted the Pi. Nothing.
I tried using ndiswrapper, which is essentially a way to adapt the Windows driver to work on Linux, but a comment here stated that ndiswrapper only worked on the x86 architecture.
I then resorted to compiling the driver myself using the instructions here (I had some experience with kernel modules — I use the xps_nv module that disables the discrete video card on my Studio XPS so that it doesn’t draw power). However, simply following the instructions didn’t work — the kernel headers were missing. Or that’s what the build system thought. Since a recent update, the /lib folder in Arch Linux got deprecated and was supposed to be symlinked to /usr/lib (or that’s just the way Debian stores the kernel header files). I edited the Makefile again, pointing it to the actual headers and tried to compile the module again. Nope.
I then found some patches in the folder with the source code and applied them. Nothing. I also investigated this and this blog posts where the writer had exactly the same problem and applied the patches that he had there. The compilation errors remained. However, the definition of some functions in the kernel had changed, according to a comment in that post linking to here and the author didn’t replace all occurrences of the functions in the source. Doing that did the trick and I ended up with a .ko file — the kernel module.
The complete patchfile is available on the Pastebin.
I then copied the .ko file into /usr/lib/modules/(my kernel version)/kernel and did
sudo depmod -a
sudo modprobe ar5523
ifconfig -a then showed that a mysterious wlan0 interface appeared on the system. Doing sudo ifconfig wlan0 up then made the light on the dongle flash. Hooray!
Well, not really. Searching for networks (iwlist wlan0 scan) didn’t show anything useful. My next quest apparently had to be postponed.
I don’t really know much about minimalistic window managers: I use GNOME 3 (which is a story of its own), but have tinkered with xmonad (a window manager written in Haskell), so I decided to install in onto the Pi and set up a VNC server to be able to actually see what was going on from my laptop.
xmonad, however, wasn’t in the Arch ARM repository and I didn’t have any idea of how long compiling it would take. I therefore took the path of least resistance and installed openbox, a famous window manager (sudo pacman -S openbox obmenu obconf + a bunch of X libraries).
Setting up the VNC server was quite straightforward: I used the guide from the Arch wiki to install TightVNC (package name tightvnc).
I also copied a small script from here that would start and stop the VNC server with just one command (I didn’t register it as a service — Arch Linux uses init, a different way of managing services and starting the system, so the script sits in my home directory).
I then started the VNC server and connected to it from my laptop by installing tightvnc on it as well and typing
gvncviewer 192.168.1.161:1
(the IP address obviously is not constant) which gave me a completely empty screen with a cursor (standard X “desktop”).
I obviously forgot to start openbox, which could be easily fixed by adjusting the ~/.vnc/xstartup file:
#!/bin/sh
export XKL_XMODMAP_DISABLE=1
exec ck-launch-session openbox-session
which didn’t work since I forgot to install ConsoleKit. After I did, OpenBox launched normally (except for some strange graphical glitches).
I also decided to try out a more awesome window manager (couldn’t resist making that joke) called awesome by doing
sudo pacman -S awesome
and changing the line in xstart to say exec awesome.
(more awesome + some moire artifacts)
I didn’t play around more with awesome though (I did think of setting it up on my laptop eventually), since I never planned to connect my Pi to a screen and make it into a traditional computer with a desktop environment and VNCing to it over the network seems like a waste of bandwidth. I moved on to a different goal — setting up the wireless.
subject name here 
