I’m more or less finished with cleaning up the dungeon. While I can direct the dungeon generation randomness and clean up as much as I can, it will still inevitably do something bad. I cannot fix every single corner case that could come up — I cannot preemptively avoid them until I see them. So I need a way to detect “likely bad” cases automatically some way. Now that I’m iterating dungeons, I can keep a sort of global “score” of the layout. Let’s start with an asset for scoring options that I can reference (in the dungeon layout options):

A simple rule would be failing to perform part of a generation step (for example, a step that needs 5 bridges only places 3):

As I mentioned, I can now specify how many iteration a full dungeon generation (comprised of multiple layout generations) should take:

Which results in something like this:

Naively, this is fine. But not all of my steps are even expected to succeed. Some are just nice to have, like forming additional shortcuts and connections. Some are critical though, like the very first branches without which the rest of the dungeon won’t really work out. So, for each step, I need to specify its importance for scoring:

Important step failure decreases score, bonus step success increases score, and unimportant steps are ignored. Then I can assign some values for this:

Now, I’ve designed my dungeon steps well enough that I am not getting a big score variation between iterations. That is, I’m never seeing some crazy -1000 score dungeons where everything failed. Mostly it’s just “almost as expected plus bonus”. So I need additional rules for scoring, because currently I’m only scoring hand-designed rules that have “success” built into them (especially the pattern clean-up), but no inherent “visual nice-ness” that I can directly score. So what I really want is to run the dungeon many, many times and see what sort of scenarios I want to avoid (or encourage). Then encode these into the scoring. So I’m just going to find a bunch of examples now and then write algorithms in a separate layout analysis pass.

For example, here is a obvious case of a garbage dead-end dungeon with three arenas that only have one entrance:

This doesn’t actually prevent the level from being completed or anything and everything is still connected. It’s just ugly and not something I can easily clean up without lots of work and additional rules and special cases. I never want this, because retracing steps this many times is not good gameplay. So I need to heavily penalize dead-end arenas, but allow an occasional one:

And this nicely finds such arenas with just one connection:

So now that I have both score increase and decrease, let’s generate a bunch of layouts and pick the best:

This is also surprisingly quick. Going from 1 to 30 iterations raises the time taken from 300 to some 550 ms and most of it is creating Unity scene stuff. So I have free time I can “spend” on this.

Now, my generation steps are fairly normalized and I actually don’t see these any big score variations between iterations. Most maps look fine as is. However, it does mean that I can now loosen up the generation step logic and let it create “crazier” dungeons. Then I can simply discard the bad ones. The hope is that the final chosen dungeon is randomly better. In other words, instead of generating average dungeons, I generate both bad and good dungeons, expect I can also choose what is “good”.

Another issue is when I end up with way too many tunnels that make no sense (pattern matching is disabled here — it would have removed all the red ones):

Occasional weird tunnels is okay, but this one is just tunnels for tunnels’ sake. I think I can apply similar logic to checking arena entrances. The areas formed by the connected tunnels must have a minimum amount of connections to (unique) arenas, otherwise they are just pointless labyrinths.

If I am going to analyze areas, I might as well add a generation step that collects all the inter-connected areas and any neighbours for easier later access (and for optimization):

So now I can encode the thresholds for bad tunnel detection:

And, after some tweaking, it works out nicely:

Another issue I considered, implemented and then scrapped is that I wanted to prevent dungeons that are too large or too small or just generally take the player too long to traverse. I extended my inter-node distance calculation logic to allow arbitrary requests, so I can look up and penalize things like this:

I thought this would make dungeons where the player can reach everything too quickly undesirable implying either bunched-up or too spread-out layout. But it turned out that I never even saw these issues and penalties. And the dungeon feels fine even with pretty extreme variations. Basically, it is local small things that catch your eye and not big global things. So I scraped this and will focus on small weird things instead.

Another issue is that I get too many halls next to each other (again, patterns would remove these, but not always and not really long ones):

These are occasionally okay, but usually they are not great, indicating weird hall layouts. So I can penalize them:

And as far as I can tell from my observations, these seem to pop up much less now.

Another rare scenario is where the whole dungeon is split in two by a single node/room:

In a more generic formulation of the issue is that I would like a way to detect “hot” nodes that “connect too much stuff”, even when they are not as an extreme case as above. Unfortunately, I cannot run a perfect algorithm (in that it always find the correct answer), because that would be way too slow. I cannot flood fill from every node to see if it cuts off some section of a dungeon. I cannot find paths between every node. Basically, I need a heuristic algorithm.

I think it will be sufficient for me to run a flood fill path-finding from every arena and count how many times each room is traversed. This way I can potentially see which rooms definitely exceed the threshold (doodle of me imagining how it would look):

(I can probably use this information for something else as well. This actually tells me the “wear” of the paths. This can be used for decoration, patrol routes, signs, etc. Not that I am doing any of it, but it’s an idea.)

So this becomes another analytical pass for my dungeon generation. Surprisingly, it doesn’t take any real time to flood fill the map from every arena and then find a path to (technically, from) every other arena. I guess my map is small enough and the structure organized enough that it lends itself to quick parsing. Anyway, I have to set up some debug for this (darker opaque blue — higher usage):

It’s great to see an idea come to life! And I just want to point out how many different map overlays I now have for debugging purposes:

Activating individual or multiple of them draws the Unity scene gizmos that are the debug things you see in screenshots:

It’s a bunch of work to set these up, of course. But these have helped me immensely in debugging issues and just quickly seeing whatever I am trying to examine, especially when the underlying data is not something that directly translates into in-game things, like deleted nodes or content spots or whatever. Without being able to visualize things like this, it would take me way longer to adjust certain things. With these I can just click refresh over and over and instantly see the result. Yay for pretty debug!

Anyway, the traversal map reveals two types of areas: “too much traffic” and “not enough traffic”. The first is a problem when a certain spot becomes the only hall to go around the map. The latter means that certain “shortcuts” are pointless and are likely not shortcuts at all. So I can penalize both types of halls:

And this scores the layout nicely (red-wired: too much traffic, blue-wired: too little):

There are generally more tunnels that are not actually shorter paths between anything, but that’s fine in small amounts so they get a tiny penalty. A node that hosts a lot of traffic gets a massive penalty though, since it splits the dungeon parts too aggressively. (I should probably account for how many connections such a node has, because a 4-way crossroad is more acceptable as a high-traffic node than a 2-way tunnel. But that’s just extra work and many extra parameters.)

Another visually annoying occurrence in the generation is either overly bunched up or overly empty spots:

It’s okay to have both of these, but it tends to feel bad when it approaches extremes, so I will penalize both when they get too large. To do this, I need yet another analytical pass that can tell me the density of each location based on its neighbour count. Basically, every node adds a little “I’m near” score to all its close-by nodes. The more nodes there are, the higher the scores will get. This way I can detect “cold” and “hot” areas:

Hot nodes is fine as is — I can just set a threshold. The problem is cold nodes — I don’t actually care about the nodes outside the play area, so I need to trim them so they don’t get detected as “empty areas”. I can do a flood-fill pass to remove all the nodes that are “outside” the dungeon:

So now I can assign actual values for thresholds and penalties for these nodes:

And this nicely detect any overly dense/sparse areas (outlines spheres are the ones scoring decided are bad):

Yay, another debug layer!

I’m sure I can think of many other (overly complex) ways to score my dungeon. But I think this is sufficient for immediate means. Majority of my generated dungeon look very decent. Rarely are there strange layouts. I can generate dungeons for ages and not see anything that strikes me as anything but “well, this is slightly off”. And I’ve already spent a lot of time on this, so I need to go back to some more gameplay.

MicroRogue DevDiary #28 – Dungeon scoring

Leave a Reply
