Avoid unreachable rooms in duengons

Question

Good evening.

Im currently trying to create a Dungeon Generator . First I place randomly some rooms. Right after that I dig in a randomized maze.

But sometimes it happens that some rooms or even some maze paths are unreachable.

Is there any way to avoid that ? Are there any good Methods for avoiding that ? Any ideas or examples?

Im currently doing it like so (pseudocode) :

1. Pick a random Number of rooms

2. Create an arraylist for those rooms

3. Pick random Positions with random sizes

4. Try to place all those rooms without overlapping and add them to the list.

-- Room placement Done --

-- Maze Generation Begins --

1. Loop over the whole Map, if Theres an empty tile ( No wall, No floor and No paths) than Beginn to grow the maze .

2. When the Statement above ist true, than create a 'Cell arraylist' and put the 'start' cell into it with the coords of the empty tile above . ( A cell just contains x and y coords) .

3. While the cell list isnt empty, Pick the latest cell (cellsList.Size()-1) and Check the possible direction it Can move. If Theres just empty space in that direction ( No wall, No floor and No paths) than the direction is true.

4. Pick a random Number and Check for every direction if the assigned Number fits with the random one. If it fits, then dig into that direction and create a new cell at the End . If Not redo this step until one paths ist diged Out.

5. At least kill 'Dead ends'. Those path tiles which are surounded by 3 empty tiles or those which are completly isolated.

I Hope I mentioned everything . Im currently at my phone and cant acess my Files at my Home PC :/ im gonna Update this later when im Back Home.

Answer 1

It depends on what algorithm you are using to generate your dungeon. There are algorithms which by their very nature ensure that everything is reachable:

• Algorithms which start with one room and then keep attaching new rooms at random to already existing rooms
• Algorithms which use recursive division (you start with a huge, empty room and keep subdividing by creating horizontal and vertical walls with a doorway in a random position)

But when you have already implemented an algorithm you like and you don't want to start from scratch, you can just check which parts of its output are walkable by performing a flood fill and then just delete everything not covered by the flood-fill. The main problem with this approach is that you can randomly end up with really tiny dungeons.

Answer 2

I once ran into a similar situation on a proof of concept, and this is how I solved it.

My dungeon was simulated as a single mesh, with different nodes which held a boolean state (floor or wall; walkable or unwalkable). I picked the center node of the largest room, then used Dijkstra's algorithm to find the shortest path between each other room to the largest room. I also weighted the values of the nodes such that a walkable node cost significantly less than an unwalkable tile. I can not remember the exact values, but it was like 1 vs 100. This was done to make sure I didn't accidentally create a duplicate path. Once the path had been found, it made all nodes in that path walkable, thus connecting all the rooms.