Hello everyone! We have a bit of a different entry this fortnight. I don’t normally talk too extensively about how things are coded in detail since I prefer to focus on design questions, but I decided to do so this week. While working on a few edge cases and bugs and the like for the world map clues since last fortnight’s entry I ran into a somewhat interesting challenge involving resolving an obscure, but problematic, edge case. Specifically, this edge case involved the possibility for the damage spread organically across a world map clue to leave part of the clue floating in the middle of a sea of damage without anything else surrounding it. If it’s not clear what I mean by that, I mean something like this:
This is a real problem from a suspension-of-disbelief point of view, for obvious reasons. How could the player character possibly know where the important part should be positioned? And, to be clear, the fact that the all-important “X” happened to be the lone floating part here is totally coincidental; I’ve had examples with any element of the map being left floating as damage is done all around it, or indeed several tiles of the map floating as a larger island. This needed resolving, but was surprisingly non-trivial to deal with. The reasons for this were several – firstly, I needed something that added the smallest possible amount of time to the damage generation. The obvious solution would be some kind of flood-fill algorithm, where we keep testing whether or not all the non-damaged parts of the map are connected, and if they suddenly aren’t, we remove / undo the last added damage section. That’s pretty obvious, but comes with issues. As the technique’s Wikipedia page very nicely outlines, this is a surprisingly computationally hard problem to optimise, as there’s a lot of ways it can take up a surprising amount of time. This was a problem because generating the higher-level maps, which I rate as being in the “Hard” or “Ultra” difficulty, is already much harder for the game than the “Easy” or “Normal” level maps, simply because the game has to discard some of its attempts because they don’t meet the required parameters that I’ve set. This meant I really, really didn’t want another computationally intensive element of the generation system here, particularly because whatever the computation was, it would have to be run after every single additional of a damage tile (okay, yes, strictly speaking it wouldn’t, you wouldn’t need to run it for the first seven additions to the damage set because it takes eight to create a full loop, but you get my point).
The second challenge was that the damage is populated in quite an organic way – the game selects a number of start points on the grid (more for higher difficulties, fewer for lower difficulties) and then has some spread out in various directions (more for higher difficulties, fewer for lower difficulties) for a set number of iterations (again – more for higher difficulties, fewer for lower difficulties). This works really well for creating really rich, organic-looking damage to the maps and I was very reluctant to change it, especially since I’d spent a lot of time optimizing that code and making sure it yielded the outcomes I wanted in both aesthetic and gameplay terms – but I couldn’t see an obvious non-flood-fill way to use this existing code to check whether islands are being created or not. If one block of damage touches another block of damage, that’s not inherently a problem, and doesn’t automatically create a floating island. The best alternative would seem to be that each time you add damage to tile a, you look at the tiles to each side and above and below, and then from those tiles you look at the tiles above and below them, and if they’re at 3/4 damage tiles already, then you don’t add the damage you just added. That’s quicker than flood-fill, no doubt, but still decently computationally intensive – for a lot of damage you might be running that 50 or so times, and that’s 16 checks 50 times, which is 800, each of which requires checking two different grids (the map grid and the damage grid) – and even then it doesn’t actually totally solve the problem, as it wouldn’t prevent 2-tile or 3-tile islands from appearing! Now, there is already some code to ensure that the entire map cannot be split in half, i.e. only one tile at the map’s edge is allowed to damage (which itself doesn’t always happen, but occurs more on smaller maps than larger maps because the edge becomes a larger percentage of the map’s overall size), and that helps a lot, but that code doesn’t prevent these islands. So, given all this, I had to find another solution – and the logical / mental process of finding and refining that solution is what this blog post is all about :).
So, I began to consider other alternatives, and one immediately leapt into mind that was computationally extremely simple, requiring only a single fleeting check of something when the game was considering adding in a damage tile. The idea would be to have a hidden grid lying underneath the map grid which the player never sees, but which has a particular set of tiles that cannot be made into damage, and that these are geometrically ordered in such a way that it becomes impossible for an island to ever be formed. I realised, then, that if a given tile on the map could never become a damage tile, then all the tiles around it would be, in a sense, “safe” from becoming an island tile themselves, because they would be guaranteed to be next to a tile that can never become damage. Once this realisation came to be, I opened up Paint and made a basic 9×9 grid – recognizing that the largest world map clues would be the hardest to do this on, of course, and so I started there – and experimented with what the smallest number of tiles could possibly be which would have this effect successfully. My initial experiment, predicated solely on the logic I’ve just outlined, wound up looking like the below, and I was very happy with this for about 10 seconds, thinking that as long as the red tiles were always non-damage tiles then we could never get an island, because every other tile is next to a red tile… right? Well, no, obviously not, and immediately my brain pointed out that this did nothing to prevent multi-tile islands, even if it would indeed successfully prevent one-tile islands. Whoops.
The next option, then, was to find a model where no tile on the entire grid would not be touching a red tile (i.e. a tile that I would, in this model, disallow from every becoming a damage tile), and make sure that there were no possible loops. What I realised that meant, in practice, was that the cannot-be-damaged tiles (the red ones) would all have to connect to the edge of the map in some way, otherwise it would be possible for the game – in extremely rare edge cases, let’s be clear, but still possible – to generate a larger loop of damage around them that would yield a larger floating island of note in the centre rather than a single tile. However, I naturally didn’t want to disrupt the overall shaping of the note damage too much and wanted to find the largest possible spaces that could remain devoid of the cannot-be-damaged tiles, while still ensuring every tile would touch one. After some consideration, I decided that parallel diagonal lines would probably be the best way to do this, since parallel horizontal or vertical lines enabled only 2×2 blocks of other tiles to exist between them, whereas here we could have almost 3×3 blocks of damage-valid tiles, each just having a single tile taken out by a red tile to ensure that every possible tile is grounded by a cannot-be-damaged tile, thus preventing the islands. I then also thought at the time that the edge tiles would have to often have red tiles as well, so that tiles further in couldn’t be turned into islands by having a loop built via edge damage (at this moment I hadn’t forgotten the “only one tile at the map’s edge can be damaged” rule I’d already implemented in the earlier version of the generator, but I hadn’t realised the implication of this yet for this system). After some consideration and trying to minimize the number of cannot-be-damaged tiles, I came up with this, as a possible hidden grid that would indeed, entirely prevent note islands from occurring:
I was quite please with this, but disappointed by how limiting it was – so much of the potential space on a note that could be damaged was being taken out of consideration here! Now, there could be permutations of this, of course, where we invert it along the x or oy axis to produce another possibility, and the diagonals could be placed in different locations to still achieve the same goals… but even so, a rather significant portion of a map note was – in this model – not valid for potential damage. Nevertheless, this seemed to be the best I could come up with, so I spent some time exploring other geometries to maximize the range of possible cannot-be-damaged tile layouts, so that even if in the above version certain areas couldn’t be damaged, in other versions those tiles could be damaged – and since these would be hidden, obscured things that the player never saw, the player shouldn’t ever really notice or be aware of one of these grids having had a secret, shaping hand, over the final appearance of the damage distribution on a higher-difficulty world map clue. This was, in fact, a really interesting intellectual and geometric exercise, since I was always trying to ensure that there were the smallest possible number of cannot-be-damaged tiles, while making sure that every tile was connected to one of them, and they all reached the edge of the map grid, and they did so in a variety of interesting ways in order to ensure that as many possible variations for damage would still be allowed to spawn on the clues, without being too limited by these hidden grids that prevented islands from appearing. After a bit of effort, then, I’d come up with something like this, and started to internally learn what some of the “rules” were for this specific geometric problem:
(There is actually a mistake in two of these – see whether you can spot the two places in these grids where, actually, an island could spawn!).
There were doing the job, but I was really getting worried at this point about how these simply were going to limit the possible shapes for damage that could appear. If you look back at last week’s entry, some of the “Hard” and “Ultra” difficulty maps have genuinely large areas removed by damage and in a variety of shapes, and no matter how I tried, these were going to end up limiting that. What I realised here was that a lot of the cannot-be-damaged tiles are actually going to be totally unnecessary in most damage generations, but will nevertheless prevent damage generation, at least a lot of the time, from coming out as interesting as I’d like it to be. This was a bit of a quandary, but then I had an idea, and a realisation. The idea was this – what if we group cannot-be-damaged tiles into groups, and the damage generator counts how many in a group have been damaged, and only if they have all been damaged, and thus a loop becomes possible, does the game then say “no!” and prevent damage from being added. As I refined that idea though, I realised that wouldn’t work since you could still have smaller damage loops before reaching the main size, so instead I thought about a system whereby some tiles can only have damage if other tiles do / don’t – this is sketched out, roughly, in the left-hand image in the picture below. The realisation, meanwhile, was that the entire outer loop of tiles on each map, and the second loop instead there, cannot be turned into islands anyway! In all cases it would require multiple outer loop tiles to be turned into damage, and a rule against that already existed, so that simplified things considerably. With both of these, I tried to figure out a model – the right-hand picture below – whereby we could have a small number of grouped tiles where only one can be damaged and we have only a handful of absolutely cannot-be-damaged tiles… but it was all getting rather complicated, and a bit more computationally demanding than I wanted, with loads of conditionals being required to make such a system work.
However, having realised the two outermost loops are immune to the problem anyway, it’s then only the inner parts that are bothersome, and we just have to connect these to the outermost loops. This then became again a very interesting little geometric and mathematical problem – what’s the most efficient way you can do this so that all cannot-be-damaged tiles are connected in some way to the second most outer loop or another cannot-be-damaged tile, and every other tile (aside from the outermost and second most outer loop) is connected orthogonally or diagonally to a cannot-be-damaged tile, and we have the smallest number of cannot-be-damaged tiles possible in order to ensure the largest possibility space we can get for generating visual damage onto the world map clues? Below were two of my early experiments, with the left one requiring only nine tiles to satisfy this condition for everywhere in a 9×9 world map clue grid, and the right one requiring ten tiles to satisfy the same condition. While playing around with these I didn’t find one requiring only eight tiles, though it may well exist? If you can find one that satisfies these rules (assuming the rules are understandable from what I’ve written here…) do let me know as I would be interested to see it. Anyway, these two I was very happy with since they still allowed tremendous variety in how the damage visuals on maps would end up looking, while again making sure that it was impossible for any one-tile islands to come into being. It was at this point that I was beginning to feel like I was actually making progress here – some of the earlier versions were so busy with cannot-be-damaged tiles that I was getting worried about a potentially very deleterious effect on the final outcome, but here, I was feeling pretty confident about how things were going to end up looking.
However, the diagonal parts of these really stood out to me as elements it would be good to try to lose. Some map clues do indeed generate with a piece of the map just sort of “hanging on” to the rest of the map diagonally, and it genuinely looks fine, but it doesn’t look visually as nice as the other ways maps can generate (i.e. with connections between pieces of the map being orthogonal). As such, I went back to my grids in Paint and tried to find some nice grids of cannot-be-damaged tiles were instead wholly or primarily orthogonal in their connections, in order to again make sure we’re getting nicer-looking generations out of it. This was a little bit tricky, since orthogonal lines simply don’t cover as much “distance” on a flat plane as diagonal lines so – hence why of course lots of strategy games go with hexagonal tiles in order to prevent diagonal movement simply being objectively stronger than orthogonal movement – but soon I was able to find three examples I really that were completely orthogonal in their use of the cannot-be-damaged tiles, and one which was a mix of both possibilities. I did decide to keep this fourth one because having some rare damage or non-damage cutting across diagonal lines is completely okay, but overall I thought it would generate stronger and more visually compelling maps if we did try to make sure this was a mostly orthogonal thing. As such, once I had these four, I quickly implemented them into the game in all possible rotations and reflections as well, of course, and did the same for the 7×7 possibilities and the 5×5 possibilities, which as you might imagine were far simpler. The 5×5 was particularly interesting as each one only needed a single cannot-be-damaged tile somewhere in the second most outer loop, either corner or edge, to prevent any islands from ever spawning, so that was about as simple as it comes.
With these in place, I then of course did lots of playtesting, and I’m pleased to report genuinely no difference in the final generation of high-damage maps, especially in the “Hard” and “Ultra” categories. They’re looking great! And you really can’t notice in the slightest that there’s a sort of secret thread, or set of threads, running through the notes that subtly shape the creation of the organic damage during the note’s generation. Indeed, there are certainly plenty of other things in the game which actually use comparable ideas (though not in the same context) where a few particular points or elements of something are more fixed, and other generative outcomes are constructed around that, since that often ensures the outcomes are closer to what I want in nature – but no less varied – than complete freedom (the latter being a bit less suitable for a game like URR where we cannot, for instance, have a world map gen with only one nation that has conquered the entire world). As for notes though, the key point is that nothing is changed visually, but islands now cannot spawn, and thus the design objective of this little geometric and mathematical adventure has been achieved – and in a way that is computationally trivial, and at most adds around 1/1000th of a second to a note’s generation, rather than potentially an actually meaningful portion of a second (these might seem like the same, but remember the game is doing nothing else while generating any given thing – so we need those speeds to be as rapid as humanly possible). What’s also great as well is that these insights can be easily applied to the local map clues once I get to generating them – and indeed the exact same 20 hidden grids for the 9×9 size, the 16 hidden grids for the 7×7 size, and the 8 hidden grids for the 5×5 size, will work just as well in that context as they do in this context to ensure that floating islands of paper can never be generated.
So there we have it – this obviously wasn’t the fortnight’s entire work (this whole process was roughly a half-day of pretty focused attention and planning) but I thought it was an interesting insight into the coding process from problem, to bad solutions, to okay solutions, to good solution, to optimised solution, to implemented solution, and could therefore make for a bit of a novel read about how I actually go about approaching a problem and trying to balance the various needs – computational speed, outcome quality, etc – that one always faces here. These are some of the most interesting things in programming, I think, where you’re developing a genuinely novel solution to a genuinely novel problem, and besides, I and I really don’t post much stuff of this sort on the blog anyway. If you’d like to see more under-the-hood entries like this, please let me know! I’m happy to write them and I’m sure there will be plenty of really interesting problems like this coming up in the foreseeable future. And of course, the opposite also applies – if you really don’t want blog entries like this, I certainly won’t be offended in the least, and I’ll always appreciate that kind of honest feedback as well. And, please do let me know your thoughts in the comments – I’d be keen to read what you think about the solution, and whether you can think of a more mathematically elegant way to get the job done! Not that I plan on changing it now, of course, since it’s working perfectly at no noticeable negative impact to the visual flair of the maps generated – but I’d still be interested in other ideas about how else one might have solved this particular quandary. And lastly, of course, none of this is to discount that in the future I would expect note clues that are split in half and you find two halves in separate places, but that’ll be a separate generator with separate code, where the player is putting them together – not the character somehow figuring out where pieces are meant to join together with one floating, tattered part. This needed fixing, and needed fixing in a smooth way, and I’m very happy with how it all came out.
As for next time, of course, we’ll be back to a more usual “here’s a bunch of new stuff I’ve done” update (which of course is other stuff I’ve been working on while doing this, and will be continuing to work on for the next fourteen days as well), so I’ll see you all then :). Thanks for reading, everybody!
