Interesting Map Geometry and Mathematics

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.

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.

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 and then has some spread out in various directions for a set number of iterations. I was very reluctant to change it, 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.

So, I began to consider other alternatives, and one immediately leapt into mind that was computationally extremely simple. 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. After some consideration, I decided that parallel diagonal lines would probably be the best way to do this, since they enabled larger blocks of damage-valid tiles while ensuring every possible tile is grounded by a cannot-be-damaged tile, thus preventing the islands.