Hello! Since the last update I’ve made some major progress on a large number of major optimizations and improvements to the code and speed of the game, and in also in the development of new features, for URR 0.10. So, let’s have a look:
Field of view / map drawing optimizations
The first place I found to improve matters was in discovering that the fov computation was going significantly beyond the actual scope of the area the player can see. In URR you have a directional field of view, so what the player is able to see is dependent on which of eight directions (i.e. the eight main compass directions) they are facing, with a roughly 140 degree range of sight. Given the range of the sight coded into the game, this realistically meant that the player can see around 18 tiles in any direction at any given time. By this I mean they can actively see what is going on there, i.e. that area is lit up; of course if the player has previously explored some larger area they can see what buildings and terrain and so forth are there, but they are not actively seeing it, i.e. they are not seeing whether NPCs are moving around in it. Here are some examples of what this currently looks like:
So, even though the player cannot see things actively beyond eighteen tiles or so in any direction depending on what direction they are facing, I discovered that the fov calculation was using numbers more like 25 in each direction. So when the player is facing north, they can see a maximum of 18 tiles to the north and fractionally under 18 tiles to the west and east, meaning that the extra 7 or so in each direction are being unnecessarily calculated each turn. I recognise that I implemented this because we need a small buffer of tiles outside the player’s vision range to ensure that a tile which was visible the previous turn, but is now not visible, is correctly rendered not visible – but that needs to be only one tile (or two tiles to be absolutely confident), not seven. The initial and quite rapid improvement I was able to make was therefore really tightening the area around the player where these calculations are taking place, leaving only the slightest buffer of tiles which might have changed between this turn and the last. This saved a little bit of time on each calculation, but there was clearly more to be done.
The second optimisation was to notice that in the field of view code, a particular calculation was being done twice. There were some lines of code which in essence asked “if [calculation] < x, then do y”, and then if that was returned as a false, the next line was “else if [calculation] > x, then do y” – but it was doing the calculation again. This is a common mistake I made as an early programmer and lots of this code is literally a decade old or close to it, and was of some consequence here as this was a relatively computationally-demanding calculation that was definitely slowing things down by virtue of being unnecessarily run twice. It was therefore a trivial fix to just have a single calculation done for each tile and then have the outcome of that referenced twice, instead of doing the calculation anew each time. This again saved a handful of milliseconds on each fov calculation, but there was still more to be done.
The next optimisation was the realisation that there is actually a significant chunk of area which does not need calculating again each time. Take this diagram for instance (I’m doing all these diagrams in desert areas as they are the most devoid of stuff that gets in the way, and hence the clearest):
In this diagram imagine the red circle as being all the potential areas that the player might be able to see in (with a tile or two of buffer), and the green being the only area that needs to be calculated on this specific turn, i.e. the part of that red circle that the player is dealing with, as well as a small buffer on each side for any tiles which were visible and now should not be. My next big realization was that unless the player just changed height and some things might now be hidden over a hill that were previously visible, or the player has just entered a map tile for the very first time and hasn’t yet moved around within the map tile, or the player has just turned around and is looking at something that wasn’t in the green rectangle from the previous turn, then nothing within the blue square needs to be calculated each turn!
This seems a bit counter-intuitive, so let me explain. The player enters a new map grid and everything within the green rectangle is calculated and presented – all well and good. Then the player takes a step forward – whatever they might see has already been calculated within the green rectangle precisely because it has that 1-2 tile buffer around what the player is actually seeing that turn, and therefore it is the edges that need calculating again (as the green rectangle moves onto previously untouched tiles) – but not the middle. More broadly, generalising this to all directions, we could note that once the yellow rectangle is calculated on a given turn, anything within the blue rectangle does not need to be calculated on the following turn (again unless the player is changing height on the map, for example). This then looks like this…
…and all of this led to this realisation that because the buffer is always being calculated around the edge of what the player can see, whenever the player moves into those already-calculated areas (i.e. they become part of the blue rectangle), they’ve already been calculated! This was a big breakthrough, although it took a while to implement all the exception cases as mentioned above – the player first entering a map grid, the player changing height, and the player changing their facing direction, all require the blue rectangle to be calculated afresh. Nevertheless, this overall reduced by half the time it takes the time to calculate field-of-view stuff for the player! FOV calculations started at around ~15-18ms per turn; the previous optimizations had reduced it to something like 13-15ms/turn; and this reduced it down to around ~4-6ms/turn, and around ~10-11ms/turn when the player is, indeed, changing height.
With all of this done, it was then time to turn my attention to how the game prints this stuff on the console for the player, i.e. the actual playing of specific characters with specific colours. There was one obvious initial improvement to be made here – much like in the field-of-view context, the game was printing (and therefore re-printing) characters in slightly too wide an area compared to what might actually be changing on a player’s given turn. I reduced these numbers to just take in the barest of margins with a small buffer and this bought us a few extra milliseconds of grace on each calculation – but again, this was only the start. Looking over the code with a fresh eye I then noticed that there were a number of places where “player.z+1” and “player.z-1” were being calculated over and over and over, so I again just made that a pair of initial calculations, which between them maybe saved us a millisecond (but every little helps!).
I then discovered a piece of code that was actually completely superfluous under the new developments and improvements that I’d put in. There was a calculation being made for – I think (!??) – checking whether something was not in your fov but was a little bit outside of it and needed updating (I’m genuinely uncertain what this ancient code was for), but I discovered that disabling it changed absolutely nothing (I tested this at length!) and saved us another few milliseconds, so that mysterious line of code was out. I also then found that when the player was facing in a diagonal direction, i.e. northwest / northeast / southeast / southwest, a small optimization could be added by identifying the corner of the screen that is opposite from the direction you’re looking and automatically assessing that as an area that by definition must be out of vision, rather than doing a relatively complex calculation over every tile which would lead to the same conclusion. Again, removing this mysterious bit of ancient code another millisecond or two on average saved.
So: when I started work on this it was taking ~20ms to calculate the field of view each turn, and ~60ms to print what the player saw (and then on top of that it had to take the time to have all the NPCs in an area have their turns, etc). After about a week of work it now takes around ~5-10ms to calculate the field of view each turn and around ~30ms to print what the player is seeing. This is a more than 50% optimisation! I confess to being very, very happy about all this. My skill in programming is – to put it mildly – not to be found in this kind of deep optimisation / clean code sort of stuff, and I generally find it quite dull to work on this kind of deep-level stuff and it’s relatively unrewarding in m brain, as well as being the sort of programming that just doesn’t really resonate well in my mind compared to the more creative stuff. Given that general orientation to this kind of work, I’m actually pretty proud of myself for finding the brain space and energy to get this done; for finding so many solutions for improving the speed with which the game runs; and for the overall result and the > 50% saving of time in the fov calculations which the player has to encounter every time they take a movement. A lot of this release is about optimisation, about small improvements, smoothing off some of the rough corners and making the whole game just a smoother and easier experience to play and to navigate and to find your way around in, and the game really does run so much faster on the back of this. I’m very satisfied with all these improvements and all the workarounds I was able to find here, and I really think everyone will find the world a far more pleasant place to navigate as a result, especially when coupled with all the new options for fast-travel and all the new options for bookmarking and all the map generation optimisations I’ve also put in this week (see below!).
Map grid generation optimisation
My second main target for optimising the game’s speed came in the last week via working on map grid generation. To begin with we would note that this shares two main characteristics with the turn-by-turn rendering of the game world: this was code I generally wrote around a decade ago, and this is code that is incredibly slow for what it does. When I started work on this the average map grid took around 12-20 seconds to generate which is absolutely shocking for an ASCII game. Each map grid does admittedly consist of 40,000 tiles (200×200) but that should honestly barely take any time at all for a modern computer to create and fill with stuff according to some appropriately-scaled code. My goal was to get everything down to under five seconds and the lighter map grids – such as those which are just wilderness without buildings and NPCs and all this other stuff – to ideally maybe three or four seconds. I am unbelievably pleased to say that this has now almost been completed, with every map generation certainly now taking below eight seconds, and wilderness maps generally only taking five seconds – and there are certainly more optimisations for come. For now, though, I’ve managed to hugely speed up map generation in three major areas:
Terrain Dithering
Firstly, one area which I found was taking between two and five seconds (!!!) to generate for each map grid was the dithering of terrain on the edge of a map grid. What I mean by this is that if you enter a map grid which is savannah, for example, but the map grid next to it is a different type, such as tropical or desert or temperate, then the game will dither the terrain at the edge of that map grid in order to ensure a sense of a smooth and gradual blending between the two areas. This generally looks something like this, with the other terrain type becoming more and more pronounced closer to the edge of a map grid:
To my absolute horror I discovered that the method I developed for this when I was 22 and had barely finished the Python roguelike tutorial was to have the game go over the entire 40,000 tiles, calculate a random chance on every single one, calculate what possible terrains it should be on every single one, and then decide which of those terrains (if any) the existing default terrain for that map grid should be changed to. This is frankly atrocious and uses a staggering amount of wasted time engaging with tiles, and doing calculations on tiles, that don’t actually have anything to do with creating the intended dithering effect, especially if the dithering is only required on one side or even one corner of the current map grid. Instead, I have now created large sets of tile lists for each possible dither (each side, each corner, so eight in total) and if that side or corner needs to be dithered, the game goes through that set and dithers the tiles in that set. This means that no unnecessary tiles are touched by the algorithm, no calculations have to be performed over and over, and the final effect is literally indistinguishable from the earlier version. This has taken the time required to dither from potentially as long as 5 seconds (5000 milliseconds) all the way down to 0.1 second (100 milliseconds), with no loss of functionality! This is a massive improvement and I honestly can’t believe that such a catastrophically awful and time-consuming section of code has remained in there for so long – but either way, it’s good to be rid of it.
Spawning Plants
The next thing was to take a look at how plants were spawning. They had a similar method to what I’ve just described above and were carrying out a ludicrous number of calculations on every map tile, especially when we consider that relatively few map tiles actually end up having plants, especially in areas like deserts and tundra regions. These were therefore reworked in the same way as above, giving us a list of potential plant locations – where the list is of a sufficient size – in order to skip the tiles that don’t actually need to be addressed. This process took an unconscionable five seconds or so under the previous model, but now takes between 100 and 200 milliseconds (a tenth to a fifth of a second). Another huge improvement! Reworking how plants spawn also required me to interact with some other systems for spawning plants with certainty in specific places, such as gardens or other arrangements in upper class, middle-class or city centre districts, rather than (or as well as) just spawning them randomly. Some of these were actually fairly efficient already, but others needed a little bit of refactoring – again generally just changing them to a list of potential tiles, instead of iterating over every tile on the map – and this saved us a little bit of time here and there again.
Spawning Trees
The third area I’ve found so far for making huge time gains during map generation is in the placement of trees. The existing model was, again, alarmingly similar to the plants and dithering model – go over the entire map, do loads of calculations on each tile to decide whether a tree should be appearing there, and then eventually place the tree itself. Instead, therefore, I deployed a new model where the game now has a set of lists of potential locations for trees, and for plants. There’s a large enough number of these lists (and more than enough other stuff that varies with each map grid generation!) that I can’t imagine a player will ever spot when it’s repeating, but essentially it’s a long list of tuples – e.g. “(125,17)” – where trees or plants might spawn. A new map grid coming into existence selects one of these lists and then attempts to place some trees and some plants by looking at each tile according to the list (which totals only a small percentage of the total tiles on a map grid), rather than iterating over every tile on a map grid and running some randomization decision about whether or not some kind of plant should be appearing there. In other words, the old version tried to place a tree 40,000 times per map grid; the new version tries, at most, 1,500 times, and each of those attempts is more efficient than each attempt in the 40,000 attempt model. I think it’s not hard to see how much snappier this now is! The original version took 3-4 seconds while this new version is down to around 0.1 second, again with no change in the final effect or how things look when the player explores a given map grid.
Fast travel within a map grid
I’ve also been further refining the fast travel system. You can now fast travel to any of the important areas you find in a map grid (all the areas in your starting civilization being as pre-explored) but I’ve also now implemented a model whereby you can fast travel within a district. Pressing ‘T’ to travel, but then not moving outside your current district or town or whatever and just pressing enter instead, will again bring up the list of potential fast travel locations. You can then pick one and the game will quickly increment the required turns to get you there, and put you in the appropriate place, without having to reload the area. This again will help you get around faster (as I’ve said before, a lot of this release is about speeding everything up and making the whole game faster, easier, smoother, more user-friendly) and is a really nice improvement to assist in getting yourself around the map. Here’s are two gifs of me doing this in a town and in a city:
(If these gifs seem slightly “slow” given all that I’ve been hyping up speed improvements, don’t be alarmed – the gif recording slows things down, and there are debug messages playing in the background, but without both of these the in-district movement is genuinely *cracking* along!)
Farms, fences, hedges
With plants now fully implemented I want to start laying some early groundwork for animals. As such, I spent a couple of hours preparing some areas in the game’s generated farms. As well as plants and orchard areas, plants can also spawn with “blank” areas, i.e. fallow fields with nothing currently growing.
Half of these are now labelled instead as “livestock” areas instead of “blank” areas, and the first thing to do was to wrap a fence around them. A little bit of work quickly generated a system that could easily identify the limits of one of these farm quadrants:
And then a little bit more work enabled me to generate and place one of two new feature types, either fences or hedges. Here’s an example of a fence…
…and here’s an example of a series of fields enclosed by some hedges:
(And yes I know there’s a minor fov error in one of these screenshots, but it has since been fixed!). Each of these now finally implements the graphics for these that I’d generated during 0.9’s development cycle, so you can check those out as well:
This is all obviously just a very minor addition, but one that didn’t take up much time, adds some more variety, and prepares things for a later release as well once animals (wild animals, domesticated animals, horses the player can hire / ride, etc) come into being.
Bookmark fast travel returning
Lastly, in the previous release I described how the player could now place bookmarks of their own – up to five in a map grid – in order to then fast-travel back to custom locations such as the places that particular NPCs are, or a place where they think something might be buried and they need to come back with the appropriate equipment to dig it up, and so forth. I’ve done some more work on this and there are now a number of developments moving this feature closer to completion. Firstly, the actual act of placing the bookmark has now been limited substantially, ensuring that you cannot place a bookmark on a tile that you have not explored, and you also cannot place a bookmark on a building or some other structure. I immediately realised this would essentially be a tool that could be used to essentially teleport the player onto a rooftop or onto some previously-unseen part of the map, so this really needed resolving. As such, in the below screenshot, you can only place a bookmark on somewhere that has been explored, and somewhere which is the not a building (you will also see the two possible errors messages that can generate when you try to place a bookmark in an inappropriate location). I’ve marked excluded areas in red to illustrate what this looks like:
You also cannot place a bookmark on top of something like a tree trunk, a hedge, and so forth. The next thing was to not just have bookmarks appearing when you look at something on the world map, but also have them appear in the fast travel list as something you can warp to. The first part of this, however, was to rework part of the world map. Currently the game only shows you stuff that you’ve found if you’re in / hovering over looking at a city…
…but not if you’re doing the equivalent for a town or a fortress:
A few changes later, however, and the world map now gives you a proper description of what you’ve discovered in a town or a fortress (or anywhere else for that matter) and you can view these much as you would in a city:
There is still a minor bug in this screenshot – it should of course say that you have explored it! – but this screenshot nicely demonstrates how the map now looks, telling you both what is there and telling you at the same time what sorts of things you might be able to fast-travel to when you enter that area (town, fortress, later university, mine, etc). With this done the next step was to get the custom bookmarks appearing alongside the standard bookmarks whenever you enter an area that contains both. I will need some extra code for entering a wilderness area that contains no standard bookmarks but does have some custom bookmarks, but for now I focused this on cities, towns, and fortresses, which will always have the potential for standard bookmarks but can also include custom bookmarks as well. After some work, here’s what we have (with some silly bookmarks just for testing!):
You can now select any of these when you go back into an area you’ve placed bookmarks in, and much like the normal fast-travel locations, it will warp you to the place where you should be, and in doing so increment an appropriate amount of time. One thing did come up, however, which is that there is nothing visible which shows you where the bookmark is; if you were to mark out somewhere you want to dig, for instance, warp back to it, and then wander off to do something else just for a second (or even just leave the computer and come back!), it might not be immediately obvious where the spot is. So, to resolve this, I have also added a little feature that when you place a bookmark, the game prints a little message along the lines of “You have placed a bookmark with the label [XXXXXXXXX].”, and actually adds something new onto the tile where you placed the bookmark!
This is a “feature” on that tile like all other map objects (e.g. plants, trees, terrain types, doors, staircases, vases, shop stalls, tables, whatever) but can obviously be walked through and walked over since it isn’t really “there”, it’s just in the user interface, but can be looked at as a feature which just tells you that you placed a bookmark here, what it is called, and when you placed it.
The game will also place a ‘?’ on the world map if you place a bookmark in an area that doesn’t have anything else registered, i.e. is not a settlement or a farm or whatever, in order to aid in recalling things that might be far out in the wild.
I think these are nice little details and again, in such a vast world, should help the player to keep track of what’s going on and what they’re doing and when they did it. One of the next things to add is of course some way to see all of your bookmarks (this will probably be on ‘B’ whereas bookmarking is currently on ‘b’), and also a method to delete your bookmarks to free up room for others – I think these are all some very good additions to the fast travel system.
Ultimately it is clear to me that URR is, really, not very user-friendly at the moment, and so such a large portion of this release – speeding up every turn, speeding up generating every map, giving the player all these new options for fast-travel and custom fast-travel and everything else – is all in service to really trying to make the game a lot more approachable and a lot more accessible, and to give players all the facilities they might ever need for making sense of this vast world and its slowly coming-into-being mysteries
. I’m really happy with how all of this is coming along.
Bugs, miscellany, errata, etc
- Found a major issue with shops in towns sometimes not functioning correctly when you try to buy or sell something (unlike shops in cities which seem entirely unaffected by this) and causing a crash, but managed to resolve it after a fair bit of work.
- Fixed an issue where items that were not actually on stalls within shops were being counted as being “in” the shop and hence something you could purchase (and hence something the merchant would try to sell!).
- Pressing “P” now lets you press Tab to switch between information about the policies / culture of the nation you are currently in, and the policies / culture of your home nation, rather than just showing your home nation regardless of where you actually are in the game world. This now makes it a lot more useful.
- Fixed an issue with courts in appropriate civilizations not always generating correctly when the player tries to enter, and getting stuck in an infinite loop.
- Dealt with a bug whereby selecting unusual religion types in sufficient number during world generation could very, very, very rarely lead to a crash.
- General messages now accurately say “district”, “town” or “fortress” instead of (in some circumstances) always just saying “district” and assuming the player must be in a city.
- You can no longer just endlessly look at the same thing over and over – which tends to lag the game especially if you stack keyboard inputs – and instead you can only look at each thing once. This makes no gameplay difference except it stops some potentially quite significant lag if you press the same button repeatedly.
- Noticed that docks in towns were not correctly triggering with the new stuff in towns – i.e. intro messages didn’t mention them, they weren’t saving correctly as bookmarks, you couldn’t warp to them, etc – and resolved all of this.
- Resolved yet another bug that sometimes prevented docks from properly spawning in certain towns – docks should now always be able to appear no matter what.
- Fixed an issue with dock doors still sometimes spawning facing the ocean rather than facing the land – again, I was pretty sure this had been resolved before, but it has definitely (…?) been resolved now.
- Moving across a grid manually on foot, rather than with fast-travel, but not being in a city (so you’re moving through a gate between districts), now correctly handles things like calculating the initial field of view when you set foot for the first time in the next map grid rather than sometimes temporarily placing the player into a tiny shadow world for a few turns before allowing them to see the rest of the area.
What next?
My next tasks are essentially to continue working and finishing the systems already being implemented in 0.10 – fast travel, speed improvements, custom bookmarks, supplies and ailments, etc – and continue working through my list of known bugs, existing issues, small things that need polishing from earlier releases, and so on. I’m really happy with what I’m getting done here and enjoying the whole process just so much. As ever, if you enjoy this kind of detailed devlog, please do share it (
https://www.markrjohnsongames.com/2022/12/26/ultima-ratio-regum-0-10-update-5/) around on social media or with friends you know who you think might be interested! More soon!
Author
Topic: Dwarf Fortress meets The Outer Wilds? "Ultima Ratio Regum", v0.10.1 out Feb 2023 (Read 632182 times)