2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ well we'd need to see your algorithm for generating the dungeon, and then we can suggest fixes. not necessarily even code, just at least describe what you are doing \$\endgroup\$ – jhocking Jan 2 '17 at 21:43
  • \$\begingroup\$ It seems like you could solve this by running a quick graph search to identify connected components. If a part of your dungeon is unreachable, find the closest tile in one of the other components, and tunnel from there until you reach the disconnected piece. Repeat until no more pieces are disconnected. Is there a reason a simple fix like this won't work for your case? \$\endgroup\$ – DMGregory Jan 2 '17 at 21:57
  • \$\begingroup\$ @jhocking I added some pseudocode :) \$\endgroup\$ – genaray Jan 2 '17 at 22:01
  • \$\begingroup\$ @DMGregory If im running a Flood Film Algorithm to determine the isolated Part . How im gonna Connect it ? Should I Just Take a random Point in that isolated Part and run an Pathfinder The nearest reachable path ? \$\endgroup\$ – genaray Jan 2 '17 at 22:03
  • \$\begingroup\$ A fixing round sounds reasonable. Determine unreachable rooms and path systems and then try to connect these to some existing path which is connected to an entry or exit. \$\endgroup\$ – mvw Jan 3 '17 at 7:34
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.