Connecting Rooms in a Dungeon Map Generator

Processing Coding Questions
1

Hello!
I am currently working on a project to generate 2D dungeon maps (like in Binding of Isaac, or similar games) but I am having difficulty finding a way to automatically connect rooms. I currently can generate a random map of “rooms” but I need to find a way to connect some rooms together. I was thinking of writing a function that connects rooms that are a certain distance apart, but the way I would implement that would be to draw a line that connects the starting positions of rooms, then checks which open cells that line intersects, then fills in those cells. However, this method seems inefficient and clunky. Thanks in advance!


ArrayList Rooms;
public int[][] floorGrid;
public Cell[][] cellGrid;
int startX, startY;
int gridSize;
int margin;
ArrayList<PVector> doors;
int numRooms;
color[] cols;

int xNext, yNext;
int x1, y1;
int currentID;

int xmax, xmin, ymax, ymin;

void setup() {

  size(600, 600);
  stroke(255);
  rectMode(CENTER);

  numRooms = 8000;
  gridSize = 20;
  startX = 10;
  startY = 10;
  margin = 2*gridSize;
  currentID = 1;
  doors = new ArrayList<PVector>();
  cols = new color[numRooms + 10];
  cols[0] = color(255);
  for (int i = 1; i< numRooms; i++) {
    cols[i] = color(int(random(20, 230)), int(random(20, 230)), int(random(20, 230)));
  }

  xmin = 3;
  xmax = 10;
  ymin = 2;
  ymax = 7;

  xNext = 1;
  yNext = 1;

  floorGrid = new int[(width-margin)/gridSize][(height-margin)/gridSize];
  cellGrid = new Cell[floorGrid.length][floorGrid[1].length];
  println(cellGrid.length + ", " + cellGrid[0].length);
  cellGrid[0][0] = new Cell(0, 0, -1); 

  // int div = int((cellGrid[0].length)/3);

  for (int i = 0; i< cellGrid.length; i++) {
    for (int j = 0; j< cellGrid[0].length; j++) {
      // if (i == 0 || j == 0 || i == cellGrid.length-1 || j == cellGrid[0].length-1 || (j)%div == 0) {
      if (i == 0 || j == 0 || i == cellGrid.length-1 || j == cellGrid[0].length-1) {
        cellGrid[i][j] = new Cell(i, j, -1);
      } else {
        cellGrid[i][j] = new Cell(i, j, 0);
      }
    }
  }


  cellGrid[xNext][yNext].changeID(-2);
  xNext = xNext+int(random(2, 6));

  int xstep = int(random(xmin, xmax));
  int ystep = int(random(ymin, ymax));
  println("steps: " + xstep + ", " + ystep);

  x1 = 1;
  y1 = 1;
  boolean markx = true;
  boolean marky = true;
  int tt = 0;
  while (marky) {
    markx = true;
    while (markx) {
      xstep = int(random(3, 7));
      ystep = int(random(2, 5));
      for (int xx = x1; xx< x1+xstep; xx++) {
        for (int yy = y1; yy< y1+ystep; yy++) {
          if (xx >0 && xx< cellGrid.length && yy > 0 && yy<cellGrid[0].length) {
            if (cellGrid[xx][yy].ID == 0) {
              cellGrid[xx][yy].changeID(currentID);
            }
          } else {
            markx = false;
          }
        }
      }

      for (int i = 1; i< cellGrid.length-1; i++) {
        for (int j = 1; j< cellGrid[0].length-1; j++) {
          if (cellGrid[i][j].ID == currentID) {
            if (cellGrid[i-1][j].ID == 0) cellGrid[i-1][j].changeID(-1);
            if (cellGrid[i+1][j].ID == 0) cellGrid[i+1][j].changeID(-1);
            if (cellGrid[i-1][j+1].ID == 0) cellGrid[i-1][j+1].changeID(-1);
            if (cellGrid[i-1][j-1].ID == 0) cellGrid[i-1][j-1].changeID(-1);
            if (cellGrid[i+1][j+1].ID == 0) cellGrid[i+1][j+1].changeID(-1);
            if (cellGrid[i+1][j-1].ID == 0) cellGrid[i+1][j-1].changeID(-1);
            if (cellGrid[i][j+1].ID == 0) cellGrid[i][j+1].changeID(-1);
            if (cellGrid[i][j-1].ID == 0) cellGrid[i][j-1].changeID(-1);
          }
        }
      }
      currentID++;
      //  cellGrid[x1][y1].changeID(-3);
      x1 += xstep +int(random(1, 3));
      // y1 += int(random(-2,2));
    }

    x1 = int(random(1, 5));
    y1 += int(random(ystep, ystep + 3));

    if ( y1 > cellGrid[0].length) marky = false;

    tt++;
  }

  for (int i = 1; i< cellGrid.length-1; i++) {
    for (int j = 1; j< cellGrid[0].length-1; j++) {
      if (cellGrid[i][j].ID == 0) cellGrid[i][j].changeID(-1);
    }
  }

  println("SZ" + doors.size());
}



void draw() {
  background(0);

  for (int i = gridSize; i<= width-gridSize; i+= gridSize) {
    for (int j = gridSize; j <= height-gridSize; j+= gridSize) {
      line(i, gridSize, i, height-gridSize);
      line(gridSize, j, width-gridSize, j);
    }
  }

  for (int i = 0; i< cellGrid.length; i++) {
    for (int j = 0; j< cellGrid[0].length; j++) {
      cellGrid[i][j].display();
    }
  }
}


class Room {
  int xloc, yloc, xSize, ySize;
  public Room(int xloc, int yloc, int xSize, int ySize) {
    this.xloc = xloc;
    this.yloc = yloc;
    this.xSize = xSize;
    this.ySize = ySize;
  }
}

class Cell {
  float xpos, ypos;
  int x, y;
  int ID;
  color f;
  boolean isDoor;
  public Cell(int x, int y, int ID) {
    this.x = x;
    this.y = y;
    this.ID = ID;
    colorChange(ID);
    isDoor = false;

    xpos = 1.5* gridSize + x*gridSize;
    ypos = 1.5* gridSize + y*gridSize;
  }

  void colorChange(int IDin) {
    color retCol = 255;
    if (IDin == -1) {
      f = color(155, 155, 155);
    } else if (IDin == -3) {
      f = color(#6F1B5D);
    } else if (IDin == -2) {
      f = color(255, 0, 0);
    } else {
      f = cols[IDin];
    }
  }



  void display() {
    if (ID != 0 && ID != -1) {
      fill(f);
      stroke(f);
      rect(xpos, ypos, gridSize, gridSize);

      if (isDoor) {
        stroke(255);
        fill(0);
        // text("D", xpos, ypos);
      } else {
        fill(0);
        //   text(ID, xpos, ypos);
      }
    } else {
      fill(f);
      stroke(0);
      rect(xpos, ypos, gridSize, gridSize);
    }
  }

  void changeID(int newID) {
    this.ID = newID;
    colorChange(newID);
  }
}
1 Like
2

Thanks for sharing this interesting generative map prototype.

  • What are your connectivity goals?
  • Is there a designated “last room” that should be the farthest from the first room?
  • Should there be multiple ways to traverse the map, or should they all be strung together in one big snake?
  • How long can a passage be – can it be 2, 4, 10 units long?
  • Can paths bend?

There are ways to solve these kinds of problems, but the goal is underspecified.

3 Likes
3

There seems to be an article on procedural generation of worlds/levels similar to the ones found in the game you mentioned (“Binding of Isaac”). It might be worth checking.

2 Likes
4

Thanks Jeremy,
You’re right! I should specify further. Ideally, I will be able to determine passage length, and in so doing determine which rooms connect. I don’t want it to be a single linear path, but rather rooms that are a certain distance apart should connect. Paths can bend, but not in incredible ways. The path will take the quickest route but does not need to be linear. The last room will be decided at random. Thanks for your input- I will try a new implementation tonight or tomorrow.

5

Thanks Solub,
I will check it out! To be honest, I didn’t do a ton of research into the project before I dived in, and that’s on me. I’ll work on developing an algorithm based on the one the article recommends in conjunction with this one, and compare them at the end to see how they differ. Thanks for taking the time to help!

1 Like
6

It sounds like the easiest implementation of “the quickest route but does not need to be linear” is either a straight line or an L. Are paths allowed to cross such that they make a T or a + ? If so then you don’t have to check for paths when you add new ones…

1 Like
7

Good idea. For simplicity and also since there’s more rooms than spaces for paths, I think I will stick to lines and Ls, and avoid Ts and +s. Thanks again!

1 Like