5
\$\begingroup\$

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): enter image description here

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Not an answer, but a great resource and sounds exactly like what you're searching for: journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes \$\endgroup\$ – William Mariager Jan 13 '16 at 2:47
  • \$\begingroup\$ @WilliamMariager I did see that, but I was unsure how to implement the flood fill algorithm. \$\endgroup\$ – mattrick Jan 13 '16 at 2:51
  • 2
    \$\begingroup\$ This question is unanswerable; as you've seen there are lots of algorithms each with different pros and cons, and many with great explanations already, and yet you're saying you can't understand most of them. We can't help you there. If you can pick out one algorithm and explain where you're having trouble, that's a better question. \$\endgroup\$ – congusbongus Jan 13 '16 at 3:47
  • \$\begingroup\$ It's easy to spot that you want to find a way to connect your rooms, but the question is still too broad since we know little about the set up of your application. I suggest you edit it with more details on your application, how you implemented the procedural generation, maybe a picture for us to understand how the rooms are fit in a grid. For instance, are the rooms regularly shaped or are they irregular? Do they need to have a space between them or can they "touch" each other and them connect? \$\endgroup\$ – MAnd Jan 13 '16 at 6:18
  • 1
    \$\begingroup\$ Slightly related: Algorithm for procedural 2D map with connected paths \$\endgroup\$ – Roflo Jan 13 '16 at 19:15
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ It's a bit too cave-like for my taste, but thanks anyway :) \$\endgroup\$ – mattrick Jan 14 '16 at 2:37
  • \$\begingroup\$ Yep, it's my idea of a "dungeon", but you can make it just change direction after 10 or 20 tiles has been setted, so the path will be random but straight (no cave generation, just kind of random road) and then spawn your rooms all along the way. \$\endgroup\$ – PRDeving Jan 14 '16 at 9:08
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.