Using A* to Create Procedurally Generated Rooms in Processing

Question

I've been working on this Processing project for a couple days and have a couple questions. First I'll show you where I started and how I got to where I am.

I first began by using a variation of the A* algorithm to randomly generate mazes as seen below.

A depiction of the maze:

I divide the window into even cells, and give each one four walls, and let the A* algorithm do its thing. it gives the result you see above.

Next I decided I wanted to have more dynamically shaped and placed rooms, so I took advantage of how all the cells are evenly spaced, and placed a room of random size, at least half the size of a cell, and at most the size of a cell. The result can be seen below.

Using the cells to make rooms:

For clarification, red lines indicate a solid wall, and green represents doorways. Now while I could generate hallways in-between each room, to connect them in the shape of the maze, I believe that this could create unnecessarily long walks in-between rooms.

I decided to add a section to the part of the algorithm that moves the random walker, so that when it creates a new room, it moves it closer to the room it moved from. Once again I present the results below.

Moving the rooms closer together:

As you can see this presented some obvious errors in the map generation. The arrows I drew point to two rooms that should be connected as you can see by their respective coordinates (7, 7) -> (7, 8). I then realized that when the walker moved up for example, not only would I have to move that room down, but I may also have to move left or right, after fixing this simple oversite everything was looking good, until I realized a couple of the rooms overlapped.

Rooms sometimes overlap:

In the image above I highlighted some of the overlap. I thought of a few ways I could solve this issue. Maybe I could have all the colliding rooms shrink their size little by little? but this would only work if they weren't intersecting over their position coordinate. Maybe I could move them away from each other? This might cause their partner rooms to become disconnected resulting in the whole thing needing to be moved around. Maybe even multiple times over. This dilemma is my first question.

Generator gen;

void setup() {
  size(1500, 900);
  background(0);
  
  int max = 100;
  gen = new Generator(floor(width/max), floor(height/max), max);
}

void draw() {
}

void keyPressed() {
    setup();
}

class Generator {
  ArrayList<PVector> stack = new ArrayList();
  Room rooms[][];
  PVector pos;
  
  float buffer = 20;
  float gap = 2;
  
  boolean done = false;
  
  int maxRoomSize;
  int columns;
  int rows;

  Generator(int col, int row, int max) {
    maxRoomSize = max;
    columns = col;
    rows = row;
    
    pos = new PVector(floor(random(columns)), floor(random(rows)));
    
    rooms = new Room[columns][rows];
    for (int x = 0; x < columns; x++) {
      for (int y = 0; y < rows; y++) {
        rooms[x][y] = new Room(x, y, maxRoomSize);
      }
    }
    
    generateMap();
    
    showRooms();
  }

  void generateMap() {
    while (!done) {
      ArrayList<String> dir = new ArrayList();
      int x = int(pos.x);
      int y = int(pos.y);
      if (x > 0 && !rooms[x-1][y].visited) {
        dir.add("Left");
      }

      if (x < columns-1 && !rooms[x+1][y].visited) {
        dir.add("Right");
      }

      if (y > 0 && !rooms[x][y-1].visited) {
        dir.add("Up");
      }

      if (y < rows-1 && !rooms[x][y+1].visited) {
        dir.add("Down");
      }

      int chance = round(random(1, dir.size()));
      String move = "";
      if (dir.size() > 0) {
        move = dir.get(chance-1);
      }

      if (!rooms[x][y].visited) {
        rooms[x][y].visited = true;
      }

      if (move == "Up") {
        up(x, y);
      } else if (move == "Right") {
        right(x, y);
      } else if (move == "Down") {
        down(x, y);
      } else if (move == "Left") {
        left(x, y);
      } else if (stack.size() > 0) {
        pos = stack.get(stack.size()-1);
        stack.remove(stack.size()-1);
      } else {
        done = true;
      }
    }
  }
  
  void up(int x, int y) {
    Room currentRoom = rooms[x][y];
    Room nextRoom = rooms[x][y-1];

    nextRoom.worldPos.y += currentRoom.worldPos.y - (nextRoom.worldPos.y+nextRoom.roomHeight) - gap;
    
    if (currentRoom.worldPos.x - (nextRoom.worldPos.x+nextRoom.roomWidth) > -buffer) {
      nextRoom.worldPos.x += currentRoom.worldPos.x - (nextRoom.worldPos.x+nextRoom.roomWidth) - gap + buffer;
    }
    
    if (nextRoom.worldPos.x - (currentRoom.worldPos.x+currentRoom.roomWidth) > -buffer) {
      nextRoom.worldPos.x -= nextRoom.worldPos.x - (currentRoom.worldPos.x+currentRoom.roomWidth) - gap + buffer;
    }

    currentRoom.t = false;
    nextRoom.b = false;

    pos.y -= 1;
    stack.add(pos.copy());
  }

  void right(int x, int y) {
    Room currentRoom = rooms[x][y];
    Room nextRoom = rooms[x+1][y];
    
    nextRoom.worldPos.x -= nextRoom.worldPos.x - (currentRoom.worldPos.x+currentRoom.roomWidth) - gap;
    
    if (currentRoom.worldPos.y - (nextRoom.worldPos.y+nextRoom.roomHeight) > -buffer) {
      nextRoom.worldPos.y += currentRoom.worldPos.y - (nextRoom.worldPos.y+nextRoom.roomHeight) - gap + buffer;
    }
    
    if (nextRoom.worldPos.y - (currentRoom.worldPos.y+currentRoom.roomHeight) > -buffer) {
      nextRoom.worldPos.y -= nextRoom.worldPos.y - (currentRoom.worldPos.y+currentRoom.roomHeight) - gap + buffer;
    }

    currentRoom.r = false;
    nextRoom.l = false;

    pos.x += 1;
    stack.add(pos.copy());
  }

  void down(int x, int y) {
    Room currentRoom = rooms[x][y];
    Room nextRoom = rooms[x][y+1];

    nextRoom.worldPos.y -= nextRoom.worldPos.y - (currentRoom.worldPos.y+currentRoom.roomHeight) - gap;
    
    if (currentRoom.worldPos.x - (nextRoom.worldPos.x+nextRoom.roomWidth) > -buffer) {
      nextRoom.worldPos.x += currentRoom.worldPos.x - (nextRoom.worldPos.x+nextRoom.roomWidth) - gap + buffer;
    }
    
    if (nextRoom.worldPos.x - (currentRoom.worldPos.x+currentRoom.roomWidth) - buffer > -buffer) {
      nextRoom.worldPos.x -= nextRoom.worldPos.x - (currentRoom.worldPos.x+currentRoom.roomWidth) - gap + buffer;
    }

    currentRoom.b = false;
    nextRoom.t = false;

    pos.y += 1;
    stack.add(pos.copy());
  }

  void left(int x, int y) {
    Room currentRoom = rooms[x][y];
    Room nextRoom = rooms[x-1][y];

    nextRoom.worldPos.x += currentRoom.worldPos.x - (nextRoom.worldPos.x+nextRoom.roomWidth) - gap;
    
    if (currentRoom.worldPos.y - (nextRoom.worldPos.y+nextRoom.roomHeight) > -buffer) {
      nextRoom.worldPos.y += currentRoom.worldPos.y - (nextRoom.worldPos.y+nextRoom.roomHeight) - gap + buffer;
    }
    
    if (nextRoom.worldPos.y - (currentRoom.worldPos.y+currentRoom.roomHeight) > -buffer) {
      nextRoom.worldPos.y -= nextRoom.worldPos.y - (currentRoom.worldPos.y+currentRoom.roomHeight) - gap + buffer;
    }

    currentRoom.l = false;
    nextRoom.r = false;

    pos.x -= 1;
    stack.add(pos.copy());
  }
  
  void showRooms() {
    for (int x = 0; x < columns; x++) {
      for (int y = 0; y < rows; y++) {
        if (x == pos.x && y == pos.y) {
          Room room = rooms[x][y];

          push();
          fill(1, 50, 32);
          noStroke();
          rect(room.worldPos.x+2, room.worldPos.y+2, room.roomWidth-2, room.roomHeight-2);
          pop();
          
          rooms[x][y].showRooms();
        } else if (rooms[x][y].visited) {
          rooms[x][y].showRooms();
        }
      }
    }
  }
  
  void showMaze() {
    for (int x = 0; x < columns; x++) {
      for (int y = 0; y < rows; y++) {
        if (x == pos.x && y == pos.y) {
          Room room = rooms[x][y];
          
          rooms[x][y].showMaze();
          push();
          fill(200, 0, 0);
          noStroke();
          rect(room.pos.x*maxRoomSize+1, room.pos.y*maxRoomSize+1, maxRoomSize-1, maxRoomSize-1);
          pop();
        } else if (rooms[x][y].visited) {
          rooms[x][y].showMaze();
        }
      }
    }
  }
}

class Room {
  PVector pos;

  Boolean t = true;
  Boolean r = true;
  Boolean b = true;
  Boolean l = true;

  Boolean visited = false;
  
  int maxRoomSize;
  int roomWidth;
  int roomHeight;
  PVector worldPos;

  PVector moved = new PVector();

  Room(int x, int y, int max) {
    pos = new PVector(x, y);

    maxRoomSize = max;
    roomWidth = floor(random(maxRoomSize/2, maxRoomSize));
    roomHeight = floor(random(maxRoomSize/2, maxRoomSize));


    worldPos = new PVector(floor(random(pos.x*maxRoomSize, pos.x*maxRoomSize+(maxRoomSize-roomWidth))), floor(random(pos.y*maxRoomSize, pos.y*maxRoomSize+(maxRoomSize-roomHeight))));
  }

  void showRooms() {
    push();
    noFill();
    stroke(1, 200, 32);
    rect(worldPos.x, worldPos.y, roomWidth, roomHeight);

    stroke(255);
    text(int(pos.x) + ", " + int(pos.y), worldPos.x+1, worldPos.y + 10);
    pop();

    push();
    noFill();
    stroke(255, 0, 0);

    float x = worldPos.x;
    float y = worldPos.y;

    float w = roomWidth;
    float h = roomHeight;

    if (t) {
      line(x, y, x+w, y);
    }

    if (r) {
      line(x+w, y, x+w, y+h);
    }

    if (b) {
      line(x+w, y+h, x, y+h);
    }

    if (l) {
      line(x, y+h, x, y);
    }
    pop();
  }
  
  void showMaze() {
    float x = pos.x*maxRoomSize;
    float y = pos.y*maxRoomSize;

    float w = maxRoomSize;
    float h = maxRoomSize;

    push();
    noStroke();
    fill(0, 200, 0);
    rect(x, y, w, h);
    pop();

    push();
    noFill();
    strokeWeight(3);
    stroke(1, 50, 32);

    if (t) {
      line(x, y, x+w, y);
    }

    if (r) {
      line(x+w, y, x+w, y+h);
    }

    if (b) {
      line(x+w, y+h, x, y+h);
    }

    if (l) {
      line(x, y+h, x, y);
    }
    pop();
  }
}

If you see any way for me to optimize this please let me know, I am open to any and all suggestions. Especially suggestions related to writing code in a way that's easier to understand from outside eyes, and easier to make sense of. Do keep in mind I am entirely self taught and it is likely I don't know things that I probably should by the time I'm attempting a project like this, so I apologize if the answer should be obvious.

To all those who read this far and answer: Seriously - Thank You! I've been stuck on this for a while and haven't been able to make any progress and I can't get it out of my mind.

Answer 1

I think that the "feel" you want to have of the room layout should really dictate the generation procedure. But, I will try and approach this as close to the later room layouts you showed - and hopefully this approach would get you further down your path.

Instead of generating a maze and trying to "group together" rooms from the cells I thought you could start with a large "room" and subdivide it in a recursive way and get a perfect "cover" of rooms the original area.

Here is a basic P5*js code to do that (hopefully close enough to the processing env you are using)

const minWidth = 40
const minHeight = 40
const maxLevels = 10

function setup() {
  createCanvas(400, 400);
  background(255);
  randomSeed(101)
  const rootNode = {
    id: 'z',
    x1: 0, y1: 0,
    x2: 400, y2: 400
  };
  divide(rootNode, 0)
  
  noLoop()
}

function draw() {
  
}

function aboutHalf(size, irregularityFactor) {
  return round(size/2 + size * (random() - 0.5) / irregularityFactor);
}

function divide(currNode, level) {
  if (level > maxLevels) return;
  
  const { x1, x2, y1, y2 } = currNode;
  let width = x2 - x1
  let height = y2 - y1
  
  let horizontal = false;
  if (width <= minWidth && height < minHeight) {
    return;
  } else if (width <= minWidth) {
    horizontal = true
  } else if (height < minHeight) {
    horizontal = false
  } else {
    horizontal = level % 2 == 0//random() > 0.5
  }
  
  if (horizontal) {
    let yPos = y1 + constrain(aboutHalf(height, 2), 10, height - 10)
    line(x1, yPos, x2, yPos)
    
    const topNode = {
      id: `${currNode.id}t`,
      x1, y1,
      x2, y2: yPos
    }
    const bottomNode = {
      id: `${currNode.id}b`,
      x1, y1: yPos,
      x2, y2
    }
    divide(topNode, level + 1)
    divide(bottomNode, level + 1)
  } else {
    let xPos = x1 + constrain(aboutHalf(width, 2), 10, width - 10)
    line(xPos, y1, xPos, y2)
    //print(`${horizontal}, ${level}, ${xPos}, ${y1}, ${xPos}, ${y2}`)
    
    const leftNode = {
      id: `${currNode.id}l`,
      x1, y1,
      x2: xPos, y2
    }
    const rightNode = {
      id: `${currNode.id}r`,
      x1: xPos, y1,
      x2, y2
    }  
    divide(leftNode, level + 1)
    divide(rightNode, level + 1)
  }
}

In the above code I refer to "rooms" as "nodes" represented by an id, and the two x,y coords of the room corners. The reason for the "node" term is that later, I use nodes and edges to traverse paths across the rooms layout. (see below)

This will produce layouts like this (which resemble treemap charts):

And playing with the irregularity factor (as I called it) will tweak how "square" rooms are. Can also play with max sub division levels, and min room size.

This could be extended to have more complex generation logic, forming corridors, mega rooms and so on. As long as the generation is based on subdividing areas, this will support the next stage.

Next up, we will make sure each room (node) has and edge (path) to every adjacent room. This will produce a graph that maps the possible passages between rooms.

Here is the updated code, it marks each room node as a red dot in the center of the room, and each edges as a green line.

const minWidth = 40
const minHeight = 40
const maxLevels = 4
  let nodes = []
  let edges = []

function setup() {
  createCanvas(400, 400);
  background(255);
  randomSeed(101)
  const rootNode = {
    id: 'z',
    x1: 0, y1: 0,
    x2: 400, y2: 400
  };
  nodes.push(rootNode)
  divide(rootNode, 0)
  
  strokeWeight(6)
  stroke(color('red'))
  for (const node of nodes) {
    const [nX, nY] = nodeCenter(node);
    point(nX, nY)
  }
  strokeWeight(1)
  stroke(color('green'))
  drawEdges(edges)
  
  noLoop()
}

function draw() {
  
}

function nodeCenter(node) {
  return [(node.x1 + node.x2) / 2, (node.y1 + node.y2) / 2];
}

function aboutHalf(size, irregularityFactor) {
  return round(size/2 + size * (random() - 0.5) / irregularityFactor);
}

function divide(currNode, level) {
  if (level > maxLevels) return;

  const { x1, x2, y1, y2 } = currNode;
  let width = x2 - x1
  let height = y2 - y1

  let horizontal = false;
  if (width <= minWidth && height < minHeight) {
    return;
  } else if (width <= minWidth) {
    horizontal = true
  } else if (height < minHeight) {
    horizontal = false
  } else {
    horizontal = level % 2 == 0//random() > 0.5
  }

  if (horizontal) {
    let yPos = y1 + constrain(aboutHalf(height, 2), 10, height - 10)
    line(x1, yPos, x2, yPos)
    //print(`${horizontal}, ${level}, ${x1}, ${yPos}, ${x2}, ${yPos}`)

    const topNode = {
      id: `${currNode.id}t`,
      x1, y1,
      x2, y2: yPos
    }
    const bottomNode = {
      id: `${currNode.id}b`,
      x1, y1: yPos,
      x2, y2
    }

    const currNodeEdges = edges.filter(e => e[0] === currNode.id || e[1] === currNode.id);
    edges = edges.filter(e => e[0] !== currNode.id && e[1] !== currNode.id)

    nodes = nodes.filter(n => n !== currNode)
    nodes.push(topNode)
    nodes.push(bottomNode)
    for (const currEdge of currNodeEdges) {
      const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
      const otherNode = nodes.find(n => n.id === otherNodeId)

      // Overlapping wall with old neighbours?
      if (otherNode.y1 < topNode.y2) {
        edges.push([topNode.id, otherNode.id])
      }
      if (otherNode.y2 > bottomNode.y1) {
        edges.push([bottomNode.id, otherNode.id])
      }
    }

    // two sub nodes are neighbours
    edges.push([topNode.id, bottomNode.id])

    divide(topNode, level + 1)
    divide(bottomNode, level + 1)
  } else {
    let xPos = x1 + constrain(aboutHalf(width, 2), 10, width - 10)
    line(xPos, y1, xPos, y2)
    //print(`${horizontal}, ${level}, ${xPos}, ${y1}, ${xPos}, ${y2}`)

    const leftNode = {
      id: `${currNode.id}l`,
      x1, y1,
      x2: xPos, y2
    }
    const rightNode = {
      id: `${currNode.id}r`,
      x1: xPos, y1,
      x2, y2
    }

    const currNodeEdges = edges.filter(e => e[0] === currNode.id || e[1] === currNode.id);
    edges = edges.filter(e => e[0] !== currNode.id && e[1] !== currNode.id)

    nodes = nodes.filter(n => n !== currNode)
    nodes.push(leftNode)
    nodes.push(rightNode)
    for (const currEdge of currNodeEdges) {
      const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
      const otherNode = nodes.find(n => n.id === otherNodeId)

      // Overlapping wall with old neighbours?
      if (otherNode.x2 > rightNode.x1) {
        edges.push([rightNode.id, otherNode.id])
      }
      if (otherNode.x1 < leftNode.x2) {
        edges.push([leftNode.id, otherNode.id])
      }
    }

    // two sub nodes are neighbours
    edges.push([leftNode.id, rightNode.id])

    divide(leftNode, level + 1)
    divide(rightNode, level + 1)
  }
}

function drawEdges(edgesToDraw) {
  for (const edge of edgesToDraw) {
    const fromNode = nodes.find(n => n.id == edge[0]);
    const toNode = nodes.find(n => n.id == edge[1]);
    const [fromX, fromY] = nodeCenter(fromNode);
    const [toX, toY] = nodeCenter(toNode);
    line(fromX, fromY, toX, toY)
  }
}

The way this algorithm works, in essence, is that with each subdivision of a room, the old room node is removed, along with it's edges, and replaced with the new (two) room nodes, and edges to rooms that still share at least some of the original wall. (based on the edges of the removed node).

Note, the diagonal lines just like two room centers, in practice the location of "the door" may not fall exactly on the line, but anywhere the two room share a wall.

Finally, we can use this graph, to create passages across the rooms. Here I used a simple graph walk to produce a DFS spanning tree so every room is accessible from any other room, and there are no "loops". But many other graph walk strategies could be deployed to connect the rooms.

Final code looks like this:

const minWidth = 40
const minHeight = 40
const maxLevels = 5
  let nodes = []
  let edges = []

function setup() {
  createCanvas(400, 400);
  background(255);
  randomSeed(101)
  const rootNode = {
    id: 'z',
    x1: 0, y1: 0,
    x2: 400, y2: 400
  };
  nodes.push(rootNode)
  divide(rootNode, 0)
  
  strokeWeight(6)
  stroke(color('red'))
  for (const node of nodes) {
    const [nX, nY] = nodeCenter(node);
    point(nX, nY)
  }
  strokeWeight(1)
  stroke(color('green'))
  drawEdges(edges)
  
  strokeWeight(2)
  stroke(color('blue'))
  walkGraph(nodes[0]);
  drawEdges(walkedEdges)
  
  noLoop()
}

function draw() {
  
}

function nodeCenter(node) {
  return [(node.x1 + node.x2) / 2, (node.y1 + node.y2) / 2];
}

function aboutHalf(size, irregularityFactor) {
  return round(size/2 + size * (random() - 0.5) / irregularityFactor);
}

function divide(currNode, level) {
  if (level > maxLevels) return;

  const { x1, x2, y1, y2 } = currNode;
  let width = x2 - x1
  let height = y2 - y1

  let horizontal = false;
  if (width <= minWidth && height < minHeight) {
    return;
  } else if (width <= minWidth) {
    horizontal = true
  } else if (height < minHeight) {
    horizontal = false
  } else {
    horizontal = level % 2 == 0//random() > 0.5
  }

  if (horizontal) {
    let yPos = y1 + constrain(aboutHalf(height, 2), 10, height - 10)
    line(x1, yPos, x2, yPos)
    //print(`${horizontal}, ${level}, ${x1}, ${yPos}, ${x2}, ${yPos}`)

    const topNode = {
      id: `${currNode.id}t`,
      x1, y1,
      x2, y2: yPos
    }
    const bottomNode = {
      id: `${currNode.id}b`,
      x1, y1: yPos,
      x2, y2
    }

    const currNodeEdges = edges.filter(e => e[0] === currNode.id || e[1] === currNode.id);
    edges = edges.filter(e => e[0] !== currNode.id && e[1] !== currNode.id)

    nodes = nodes.filter(n => n !== currNode)
    nodes.push(topNode)
    nodes.push(bottomNode)
    for (const currEdge of currNodeEdges) {
      const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
      const otherNode = nodes.find(n => n.id === otherNodeId)

      // Overlapping wall with old neighbours?
      if (otherNode.y1 < topNode.y2) {
        edges.push([topNode.id, otherNode.id])
      }
      if (otherNode.y2 > bottomNode.y1) {
        edges.push([bottomNode.id, otherNode.id])
      }
    }

    // two sub nodes are neighbours
    edges.push([topNode.id, bottomNode.id])

    divide(topNode, level + 1)
    divide(bottomNode, level + 1)
  } else {
    let xPos = x1 + constrain(aboutHalf(width, 2), 10, width - 10)
    line(xPos, y1, xPos, y2)
    //print(`${horizontal}, ${level}, ${xPos}, ${y1}, ${xPos}, ${y2}`)

    const leftNode = {
      id: `${currNode.id}l`,
      x1, y1,
      x2: xPos, y2
    }
    const rightNode = {
      id: `${currNode.id}r`,
      x1: xPos, y1,
      x2, y2
    }

    const currNodeEdges = edges.filter(e => e[0] === currNode.id || e[1] === currNode.id);
    edges = edges.filter(e => e[0] !== currNode.id && e[1] !== currNode.id)

    nodes = nodes.filter(n => n !== currNode)
    nodes.push(leftNode)
    nodes.push(rightNode)
    for (const currEdge of currNodeEdges) {
      const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
      const otherNode = nodes.find(n => n.id === otherNodeId)

      // Overlapping wall with old neighbours?
      if (otherNode.x2 > rightNode.x1) {
        edges.push([rightNode.id, otherNode.id])
      }
      if (otherNode.x1 < leftNode.x2) {
        edges.push([leftNode.id, otherNode.id])
      }
    }

    // two sub nodes are neighbours
    edges.push([leftNode.id, rightNode.id])

    divide(leftNode, level + 1)
    divide(rightNode, level + 1)
  }
}

function drawEdges(edgesToDraw) {
  for (const edge of edgesToDraw) {
    const fromNode = nodes.find(n => n.id == edge[0]);
    const toNode = nodes.find(n => n.id == edge[1]);
    const [fromX, fromY] = nodeCenter(fromNode);
    const [toX, toY] = nodeCenter(toNode);
    line(fromX, fromY, toX, toY)
  }
}

const walkedEdges = [];
function walkGraph(currNode) {
  const currEdges = edges.filter(e => e.includes(currNode.id))
  const adjNodeIds = [];
  for (const currEdge of currEdges) {
    const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
    if (!adjNodeIds.includes(otherNodeId)) {
      adjNodeIds.push(otherNodeId)
    }
  }
  for (const adjNodeId of adjNodeIds) {
    const adjNode = nodes.find(n => n.id === adjNodeId);
    if (!adjNode.visited) {
      const nextVisitNode = adjNode;
      nextVisitNode.visited = true;
      walkedEdges.push([currNode.id, nextVisitNode.id])
      walkGraph(nextVisitNode)
    }
  }
}

Produced output might look like this:

Here is how punching room doors following a sub-graph might look like:

function punchDoors(pathEdges) {
  strokeWeight(2)
  stroke(color('blue'))
  for (const currNode of nodes) {
    const doorEdges = pathEdges.filter(e => e.includes(currNode.id))
    for (const currEdge of doorEdges) {
      const otherNodeId = currEdge[0] === currNode.id ? currEdge[1] : currEdge[0];
      const adjNode = nodes.find(n => n.id === otherNodeId);
      
      // Which wall is shared?
      const {x1,y1,x2,y2} = currNode;
      const {x1: ax1,y1: ay1,x2: ax2,y2: ay2} = adjNode;
      
      if (x2 === ax1 || x1 === ax2)  {// horizontal adj.
        const sharedYtop = max(y1, ay1);
        const sharedYbottom = min(y2, ay2);
        const doorPosY = sharedYtop + (sharedYbottom - sharedYtop) / 2;
        if (x2 === ax1) { // room to the left
          square(x2, doorPosY, 2);
        } else { // room to the right
          square(x1, doorPosY, 2);
        }  
      } else { // vertical adj.
        const sharedXleft = max(x1, ax1);
        const sharedXright = min(x2, ax2);
        const doorPosX = sharedXleft + (sharedXright - sharedXleft) / 2;
        if (y1 === ay2) { // room to the top
          square(doorPosX, y1, 2);
        } else { // room to the bottom
          square(doorPosX, y2, 2);
        }
      }
    }
  }
}

Here is a visual result:

Final thoughts:

• The subdivision approach ensures there are no adjacency / overlapping problems.

• Tracking room adjacency as a graph allows room passage generation using common graph traversing algorithms.

• Procedural generation based on random seed is very limited and unstable (the order in which random numbers are pulled, affects the result). In a more realistic approach, the random decisions in each part of the algorithm would derive from the seed in a more deterministic fashion - for example, a subdivision axis could randomize based on level, divided room area, etc.