Procedural Dungeon Generation Connect Rooms With Passageways

Question

I've been working on a simple procedural generation class which currently places rooms on a x, y grid and selects a starting room. Each room needs to be connected with passageways so the player will be able to access them. The part that I am having issues with is how to actually connect the rooms.

There's a number of algorithms I've seen online, but I am unsure how to implement most of them.

As for my implementation of placing the rooms, the code tries placing them randomly on the grid until I get the desired density of rooms. After each room is placed, it is added to a list which stores the dimensions of the room. A room is them randomly selected to be the starting room.

Edit

Here's an example of the generated dungeons (the room with the "S" is the starting room):

Preferably, the rooms should be connected with their nearest neighbor. I'm not sure what the best way to go about this is.

Answer 1

I would make it little different, i would make a procedural path builder and then spawn floor tiles randomly all over the map, so the rooms will be more "natural created" and them will be linked at least for 1 tile, i can't code in java but i'll code the example in javascript, i think it's clear enough.

var c = document.getElementsByTagName("canvas")[0];
c.width = 600;
c.height = 600;
var ctx = c.getContext("2d");

//We gonna format a map of 300x300 tiles with 2px each
var mapSize = 300;
var tileSize = 2;
var _map = new Int8Array(mapSize*mapSize).fill(0);

var pathLength = 20000;

//Here we draw our path with a length of 20000 tiles randomly from the entry point [150,150]

var currentPos = [150,150];
_map[currentPos[0]+(currentPos[1]*mapSize)] = 1;

for(var p = 0; p < pathLength; p++){
	var dir = [
  	Math.floor(Math.random()*3)-1,
    Math.floor(Math.random()*3)-1
  ]
 
  currentPos[0] += dir[0];
  currentPos[1] += dir[1];
  
  if(currentPos[0] >= mapSize) currentPos[0]--;
  if(currentPos[0] < 0) currentPos[0]++;
  if(currentPos[1] >= mapSize) currentPos[1]--;
  if(currentPos[1] < 0) currentPos[1]--;
  
	_map[currentPos[0]+(currentPos[1]*300)] = 1;
}

//We now has an array of 0 and 1 that makes paths and rooms randomly

//We gonna draw our map
var r = 0;
var c = 0;
for(var t of _map){
	if(r == mapSize){
  	c++;
    r=0;
  };
	
  ctx.save();
  switch(t){
  	case 0:
    	ctx.fillStyle = "black";
  	break;
    case 1:
    	ctx.fillStyle = "grey";
    break;
  }
  ctx.fillRect(c*tileSize,r*tileSize,tileSize,tileSize);
  ctx.restore();
  r++;
}

<canvas style="border: 1px solid grey"></canvas>

Answer 2

I'm going to drop this alternative into the mix. Its one that I really liked and used myself, with some changes.

https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/

Roughly speaking the steps are:

1. Generate a bunch of squares of various sizes, save them to an array (you probably want a class for these objects: x, y, width, height, doesOverlap(other), etc).
2. Loop through the set of rooms and jiggle them around until they "lay flat" (that is, they no longer overlap). This will be a tricky part to get right, to avoid edge-case infinite loop problems. The simple solution is that if two rooms overlap, randomly pick between them and move the selected room away from the other in the direction that will make it not-overlap the most quickly (so if the overlap size is 2 along X and 5 along Y, then shift it 1 along X away from the other room's center (this may be negative!)).
3. Perform a Delaunay Triangulation on the room's centers. Finding some code that does this is pretty easy, although you may have to do some translation into Java. Try to use native types where possible.
4. Categorize rooms into "small" and "large." Large rooms are like what you have now. Small ones will not be added until step 6.
5. Find the triangulation's MST. This will create a minimally connected map. Add a few more edges (say 15% of the remainder, although personally I looked for connections that would create interesting loops, ignoring any edge that would make a triangle). Draw dog-leg hallways for these edges, drawing along one axis first, then turning to draw along the other. I choose a random point within the room to start drawing from, and a random target point within the destination to connect to. I also check that this path will not cross other hallways or rooms, but depending on your needs you may be OK with this.
6. Any small rooms that a hallway passes through are added to the map, any that aren't are ignored. This gives the hallways some definition and quirks.

It might also be worth making your cell data structure hold informational values, such as "this is a room, this is the wall around a room, this is dead space, this is a hallway, here's a corner, there's where a hallway meets a room (e.g. "door") so that these features can be easily located later, even if functionally a "hallway" cell and a "room" cell are the same thing.

Answer 3

It´s hard without seeing the code, but I think I can give you an asnwer.

• You can check which rooms are next to which rooms using the rows and columns of the file you created.

• The pathfinding is a bit harder, once you have your current room and the objetive room (the one next to the current room, I guess), all you need to do is define exact point for "doors" in each room.

  (You can do this by selecting a random point of the wall of each room, for example).

  Once you have the two points you want to connect, run a pathfinding algorithm.

I have a very basic implementation of A* (or AStar) algorithm in java, you can use it as a waypoint.

import java.util.*;


public class AStar {


  public static class PriorityList extends LinkedList {

    public void add(Comparable object) {
      for (int i=0; i<size(); i++) {
        if (object.compareTo(get(i)) <= 0) {
          add(i, object);
          return;
        }
      }
      addLast(object);
    }
  }

  protected List constructPath(AStarNode node) {
    LinkedList path = new LinkedList();
    while (node.pathParent != null) {
      path.addFirst(node);
      node = node.pathParent;
    }
    return path;
  }

  public List findPath(AStarNode startNode, AStarNode goalNode) {

    PriorityList openList = new PriorityList();
    LinkedList closedList = new LinkedList();

    startNode.costFromStart = 0;
    startNode.estimatedCostToGoal =
      startNode.getEstimatedCost(goalNode);
    startNode.pathParent = null;
    openList.add(startNode);

    while (!openList.isEmpty()) {
      AStarNode node = (AStarNode)openList.removeFirst();
      if (node == goalNode) {
        // construct the path from start to goal
        return constructPath(goalNode);
      }

      List neighbors = node.getNeighbors();
      for (int i=0; i<neighbors.size(); i++) {
        AStarNode neighborNode =
          (AStarNode)neighbors.get(i);
        boolean isOpen = openList.contains(neighborNode);
        boolean isClosed =
          closedList.contains(neighborNode);
        float costFromStart = node.costFromStart +
          node.getCost(neighborNode);

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if ((!isOpen && !isClosed) ||
          costFromStart < neighborNode.costFromStart)
        {
          neighborNode.pathParent = node;
          neighborNode.costFromStart = costFromStart;
          neighborNode.estimatedCostToGoal =
            neighborNode.getEstimatedCost(goalNode);
          if (isClosed) {
            closedList.remove(neighborNode);
          }
          if (!isOpen) {
            openList.add(neighborNode);
          }
        }
      }
      closedList.add(node);
    }

    return null;
  }

}

Please, ask if you have any question.

Answer 4

A very neat technique I stumbled upon a long time ago for mapping shortest path for an enemy to take was for an invisible block to be copied along in all directions, not including walls, until it hit your base (This technique was used in a tower-defense game).

To implement this in your game, you could create another character, say &, that would be copied throughout the map from all points on your room. It would be copied such that it would go off into different paths at each point that there was more than one way for it to go. In your case, it will be able to spread however it wants until it hits another room.

Those path would be tracked, and whichever path encountered a room first would thus be the path you use.

If you do end up using this method (highly doubtful considering how long ago this was, but for future readers), make sure that paths do not take all routes possible. Overall this is just food for thought, as it is a highly impractical technique to code on a larger scale, but could work quite well in a smaller game.