I’m going to implement an iterative dungeon generator, that is, a generator that can run multiple times and decide “okay, this dungeon is garbage, try again.” In fact, I could fail and retry early before I spend time on further generation steps, especially expensive world object spawning. So a layout can define something like:
As the name implies, for that I will need some sort of scoring, but I will discuss that later (technically, I’m working on the two features in parallel, but I will separate the blog posts). For now, I want to get rid of any predictable bad layouts that I can reliably “clean up”.
First, now that I can iterate the generation, I can do something I wanted for a while and that is to extend my goal-placing step to have an actual restriction for not spawning way too close to the player spawn, which happens way too much:
This now means that the step can fail, even if it happens in 1/1000 cases. But since this is not acceptable (since it will crash the game or at best make the dungeon uncompletable), I need an additional rule for what to do when the step fails:
And then I can re-run the generation if any of the failed steps requests a restart. I should rarely see such a restart and pretty much never see multiple in a row.
Here’s a bunch of loops I see all the time:
These are essentially 8-part tunnel loops with random connections. This is a very specific problem that has a specific solution. And I can just add an extra dungeon generation step to remove them altogether:
This is pretty finicky though. Firstly, I need to detect them, which means checking all looping nodes for being tunnels and being inter-connected in a loop and not having any middle nodes. Then deciding which of the four possible nodes to remove that doesn’t have other connections. And this works out pretty well for removing the odd loops:
I only remove a single node, so these can leave behind a dead-end. But the dead-end removal step would get rid of those, so it’s fine.
Another annoying thing I see too often is parallel entrances into an arena (it’s a connection that technically passes the minimum neighboring node limit, and then gets extra inter-connected with stuff):
However, at this point, I have to wonder how many of these layouts am I going to define? It’s very tedious and error-prone to do this by hand in code: trying to shift every coordinate, check all the connections, all the designations, etc. Debugging is also really time-consuming if I get something wrong and if something silently fails. And it’s not modular or reusable — I’m writing custom code and cases for every one. So I think what I need is a way to define pattern and I can put it in an editor with not too much trouble but with much better readability:
It can request a specific tile, any tile, no tile, or anything at a location. Similarly, it can request a connection, no connection, or either from that node. So it’s pretty much any combination I could possibly need. It took me about the same amount of time to make this editor as another hard-coded scenario would have (like the removal of loops above). Now I can implement this as a new dungeon generation step:
So this took about another amount of time of making another step. But it detects patterns now through the whole dungeon at any location, including the correct connections and all that. Now I have to tell it what actions to take when it matches a pattern:
Actions here is whatever I want, really. For this example, I can get rid of one of the tunnel tiles. And implementing this is about another half a hard-coded step time’s worth. And it works great (dark purple node was removed):
Of course, that’s just the direction I manually specified. I want all four rotations to do the same. And I don’t want to manually specify each direction, which means having an algorithm that can rotate my pattern. I had to extend my rotation logic and even add unit tests to make sure it works:
But the working result is very satisfying to see (270° rotated here):
There is another transformation though and that is symmetry — flipping the pattern. I only need to flip it either horizontal or vertical — the other one will get covered by rotation+flip. This is much simpler to write and works out nicely:
And the transforms took probably another amount of writing a custom rule.
In total, this took the time to write something like four new hard-coded rules. So that means that the fifth pattern I encode for adjustment is going to be faster than if I had hard-coded them all. Efficiency! And I also have to account for the fact that I would be royally tired of hard-coding finicky cases by that point. In contrast, this was actually fun!
I can add the two above problematic cases as patterns: the loops and the parallel tunnels (three long). And these all work out nicely, also in combination with dead-end removal (purple – pattern removals; red – dead-end removals):
Besides removing nodes, there are occasional patterns where I would want to alter the connections, like this scenario:
So I added the action for connections (connect/disconnect):
And now I can basically just run the game a bunch of time and watch for bad patterns that occur the most and then add them to my pattern list. Here are some more examples (purple wire stuff are the removed rooms and connections; purple connector — added connection):
-> 
In fact, as I’m running these patterns, I realize that occasionally several of them can overlap (that is, one runs only because the other created something new):
The question though is the order in which they should run then. After all, if #2 here ran before #1, then it would never get fixed. So I am just not going to bother with ordering my patterns and simply run the step as many times as needed until it can find no more patterns. It takes like 30 ms to generate a dungeon, so I don’t really care if it take 5 ms more or some such. And this can create lots of removals:
The best part is that the patterns are “hard-coded” and thus make sense. I’m also surprised by just how often these patterns match. I guess part of the reason is because everything is so tightly packed, it’s inevitable that I get a lot of repeating patterns. But I also usually notice the problems only when they are more or less obvious. But with patterns, it will match them even if I were to glance over it. Occasionally, I look at something that was adjusted and go, “oh, yeah, that does actually match”. Which is a good thing — it’s “smarter” than me at detecting patterns.
There is one problem here and that is endless loops where one pattern creates something another pattern can “fix” and the fix itself just creates the same thing the first pattern was fixing (or some sort of variation of this):
It’s near impossible for me to design patterns than never do this — they will. So the best I can do is just stop iterating after a few runs and call it “good enough”. In fact, I can count this as a step failure. This doesn’t happen often — may be 2/300 individual dungeon generations. It still only takes 500 ms for 30 iterations.
For example, here a pattern resulted in a “symmetric” case where the arena wants it’s extra exit moved away around the corner away from an adjacent exit — but it just moved it adjacent to an exit on the other side of the corner. Rinse and repeat from the other side:
For cases like this, I can just further tweak my pattern so it won’t try to move the exit if it will just end adjacent to another one, In fact, I’m starting to add comments to my patterns so I can recall what exactly things are supposed to do:
But the bottom line is that these happen and I need a safety termination for the potentially endless loop. None of my patterns break gameplay (the layout was technically playable before).
So that about wraps it up: I can now prevent arbitrary (small) layout issues easily whenever I see them. This will make my next task — scoring — significantly easier since I don’t have to worry about these cases that I can just fix before they ever get scored.