I decided to work a bit more on dungeon generation and improve the layouts. I have made all the generation steps be random besides the parameters I set. Now I am adjusting logic to avoid bad results and produce more nice results. In other words, I am fighting with randomness, which sort of is what developing procedurally generated content is all about. I guess I am working somewhat backwards here — creating something very random and then restricting it rather than having hard-coded rules and then adding randomness to them.
One thing that is bugging me is that my super-grid-based dungeon cannot yet connect rooms more organically. So the solution I am going for is marking certain walls and doors as “removable”:
Then, if two rooms that connect and overlap on those tiles both agree they can have a removable tile, then I can just place a floor tile there instead of walls or doors. So now my “tunnel” rooms can convert from
to 
And now my rooms feel way too big. I think some of that might be fixed when I add more props and enemies or whatnot.
Anyway, The first step to improving layouts is to further improve my debug so I can quickly see why different rooms where placed:
One of the biggest issues my layout generation has is that the randomness can create extreme values. And while larger dungeons are not a big issue, small ones not only look relatively tiny, but can also fail to provide enough points to follow the layout plan successfully. For example, these two dungeons have identical generation rules, but one randomly picked very few branches with fewest segments of very short lengths:
If I were to need 4 hubs to place more branches but the small can only provide 3, then the smaller size will cascade and exaggerate through the rest of the generation.
The way I am solving this is by specifying “how many of something” I need for the dungeon. Firstly, I have to extend my existing counters to include the count selection method and use a “random” version by default (which is what it currently is):
Then I can extend it with various other value-obtaining methods:
Here, my branch count target is to reach a certain number of primary hubs in the dungeon. In other words, the generator will continue placing this layout step until the total number of primary hubs reaches the given value. For example:
The green hubs were placed by the initial snake branches from the start room. It happens to be 6 here. The blue hubs were then placed from existing hubs until the total number reaches the goal, which is 12 here.
(I can technically just have all my random values be constants. Then all my dungeons will have a guaranteed “size”. The problem is that they will look very similar, such as the start room always having X exits instead of being random. This method, on the other hand, lets me “counteract” randomness and append additional areas in the way I see fit. For instance, the above example uses straight branches to append while the first pass used snake branches.)
This means the dungeon never looks the same, even though the total important constituent elements do:
(Oh look, I found an excuse to make another GIF!)
There are many fancy and not so fancy extra steps I could do. For example, I can try to connect hubs that are next to each other. This will end up creating circular paths, which is fine and actually desired. A very simple way is to just add various hubs connecting to similar hubs:
This results in occasional connection like this:
This is fine for “patching up” generator’s deficiencies where it just looks wrong when two rooms don’t connect. However, we can go a step further and introduce a “bridge” step:
As I was writing as simple L shape generator between two coordinates, I realized there’s a bunch of cases there (including, whether it is L or actually Γ). So I wrote some unit tests to check that all my cases work in all directions, including straight lines:
Anyway, the result is that I can pick a hub room and then find a nearby hub room and try to connect them:
In fact, I still don’t have enough debug information to clearly see what the generator is doing (cyan connection are branches, green ones are bridges):
Sure, this means I’m doing a bunch of extra debug code. But I am also regenerating my level about 30 times every time I change something (I even bound F5 key to regenerate). Quickly seeing issues and understanding reasons for issues is a must for me. In fact, at this point I’m just regenerating the dungeon endlessly and seeing what sort of patterns I see most and what patterns I don’t. Then I can add additional logic to improve the generation — avoid bad stuff, encourage good stuff, implement new stuff. Rinse and repeat.
For example, occasionally, hubs would appear next to each other:
Just connecting them like I am doing is not good enough. So I made my branches fail if they happen to want to place a hub next to an existing hub. It means a few more iterations, but that’s fine as it’s all pretty fast anyway.
Another issue with purely random node selection for bridging is that sometimes the whole dungeon can get split in two:
The nodes that got connected were already very close together, some from the same branch. So I added a rule where bridges have to connect nodes from different steps, in this case, snake branches won’t form additional connection as they are already connected closely.
But this didn’t actually achieve what I wanted it to. In fact, what I want is to connect nodes that are otherwise far away from each other. And “far away” means the distance the player has to travel, not just naive visual distance. For that I need a whole another algorithm that can find the distance between arbitrary nodes. In fact, I added a generation step to test this:
And this creates a nice flood-filled distance map from the start node:
So now I can use this logic to not only do the immediate bridge thing I want, but make a lot of other decisions, such as not making nodes that are too far or too close to start or goal or whatever. In fact, knowing relative distances is a very powerful tool to “combat” the randomness.
But anyway, for the bridges I added this as a potential restriction when making bridges (mainly because I want to quickly change the minimum distance number to iterate):
And this works great, for example:
The green bridge here got formed (technically, chosen from available ones), because a distance of 9 is acceptable for a bridge. But the red bridge did not (technically, was not even considered), because a distance of 5 is not acceptable. I don’t even need any restriction on bridge length, because they can form (and should form) connections between far-away nodes with just a single hall:
In fact, now that my bridges connect more logical spots, I might as well have different restrictions on their length (it was hard-coded to 6 before and made me wonder why some obvious nodes didn’t form bridges):
Funnily enough, this may result in a bridge being same distance that it tries to “shorten”. But that’s fine.
Another issue that often happens and that I am not sure I want is occasional dead-end hubs:
In fact, these formed because I placed bridges after I placed these hubs. This just looks weird. But I can extend my connect hubs logic and make them connect to any neighbouring halls:
This makes these dead-ends into more hall inter-connections (orange lines (I’m glad I added the debug)):
Of course, it pretty much always does so:
Every feature I add that relies on randomness will inevitably seek to occasionally create the worst possible scenario. So my job is 20% building houses and 80% putting up fences. I think I can solve such weirdness by making a hub not only never end adjacent to a hub but also never diagonally next to two or more hubs (which is how the above formed). So now it cannot make any chains like above, but at most something like this:
Which is sort of fine, but not really. In fact, I need special rule here to never form “connection squares” like the above. In other words, it will connect on of the hubs, but leave the other be. This result in this:
Much better. I know this is borderline nitpicky, but I really don’t want areas in the dungeon that are basically 4 neighbouring rooms in a circle. It just feels broken.
I am at a point of refactoring my code. I’ve added a lot of different logic steps and they are starting to do many extra checks and validations, etc. My class is huge now. So I want to organize it all, separate into classes, have common base classes, common utilities, better pipeline, etc. Much better:
Now I think I need to do some work on dungeon rooms and which kinds of rooms I even want. This will tie together with more generation options and steps, but will be because gameplay needs it and not because I like making pretty layouts. The above is all primary or now big halls and hubs, so I need to think about how I am approaching medium/small and such, if at all.
To conclude, here is a random dungeon (and I mean I ran the game and screenshot the first thing it generated rather than trying to cherry-pick a nice layout to post):
