GoKawiilHello 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.
... continue reading