1

I’m working on my own dungeon generation system (akin to old school dungeon crawlers).

Here’s how I have it building:
A central point, which runs the script on Active, builds a path in a random direction (North, South, East, West). When it reaches the end of the path (length determined randomly, within variable set bounds), it adds the end point to a list. Then a random end point in the list is picked (including the base starting point) and another path is built off of that. It repeats this until a certain amount are built (determined randomly by variable set bounds). Then, it builds rooms based on all of the end points, of varying size. Anywhere that already has a block in place will not build a new one on top of it, preventing overlap.

The problem is this: When two path endpoints are near each other, it will result in two rooms being built on top of each other. This is expected, and in fact wanted. The problem is that occasionally, the second room is built too long and is cut off by the walls of the other room that was built there. The end result is small sections of a room being completely cut off from the rest of the dungeon.

I realize this is what happens. The problem is that I’m not sure what to do about it.

An example: There are two end points adjacent to each other vertically. The top one has a room 5x5 built off of it. The bottom one creates a room 3x9. If there are no previously existing paths going north or south of either room (so, the paths meet from the East or West), the end result is that the bottom and/or top of the second room is built behind the walls of the first room, cutting it off from the rest of the dungeon.

I do not want the second room to destroy the walls created by the first room, except so that it can be entered. A wanted effect of the generation is that there can be rooms inside of rooms, or rooms connected to half of another room and branches out, sort of like a T. The unwanted effect is sections being completely cut off by previously existing rooms.

Below is an example of what I am talking about (pardon the texture-less…everything).

14160-generationfail.png
14160-generationfail.png1366×728 96.4 KB

In this picture, 4 paths either build from the room or in to it. As a result at least two rooms were built in the same general location. The second room was built tall, and as a result it builds outside of the first room and there is no way to access the lower portion of it because there is no south bound path.

Any suggestions on fixing this problem would be greatly appreciated.

2

This question might not have a simple enough solution to give here at UA, I could imagine. You could post this question on the forums to bounce ideas off others, discuss and get suggestions. Post a link here if you do decide to make a forum post.

I do have a solution, though it might not be possible in this case. You could map the area of the dungeon to a grid while it’s being generated, then do a flood fill of it to see if the two areas match. If they don’t, you’ll need to punch through the blocking walls.

Another thought that came to me was to use box colliders (on a separate physics layer) to mark the space within rooms. If any two box colliders intersect, you have overlapping rooms and need to do some wall-smashing. Not the cheapest solution but could work.

3

So I think I ironed out this problem, but not by anything I did intentionally.

When I was considering how to do ceiling tiles (So that the outside of the dungeon didn’t look like an abyss of nothingness), I realized that I also may want to eventually do a “Digging” system where you can destroy walls and build out. In some games that have inspired this dungeon generator, there are monsters and weapons that are able to destroy the walls, and I always liked that concept so I wanted to give myself the ability to implement such a system. To do that, my current wall system was inadequate. I changed all walls generated to full-fledged blocks, instead of slabs connected to floor blocks. By doing this, I have caused the generation of the corner segments to, so far, no longer occur. I think it is because the problem had dealt with very small sections of blocks remaining (usually single wall blocks). Because walls are now full fledged blocks, there’s no longer these tiny segments to be left unattached, and the problem seems to have gone away.

There is probably still a potential for this to occur again, if I were to work with large enough dungeon rooms, however if it does I will have to look back at this situation and attempt to solve it all over again. After about 100 test dungeons since my change, I have not seen an occurrence since.

I want to thank those who commented for the suggestions, it got me thinking about other things I can do to not only improve the dungeon generation, but also how to solve other problems in the future. Although I didn’t solve this particular problem with anything mentioned here, it has opened my mind to possible methods to do other things, and for that I appreciate the input.