Prim’s Algorithm as a Maze in javascript

I’ve gone over Eller’s Algorithm in a previous blogpost, which is great for making rectangular mazes. However, if you want to create mazes in other shapes, a spanning tree algorithm like Prim’s is more appropriate.

Rendered isometrically, so still a rectangle.

I’m using basically the same set up for rendering that I used in my last blogpost.

Pseudocode

1. Start with a grid of unvisited cells.
2. Create two empty sets, marking visited cells, and what we’ll call frontier cells.
3. Choose a random cell as the starting point, and add it to the visited set.
4. Add all unvisited cells that are adjacent to the current cell to the frontier set.
5. Choose a cell randomly from the frontier set and make it the current cell, removing it from the frontier set and adding it to the visited set.
6. Remove the wall between the current cell and a random adjacent cell that belongs to the visited set.
7. Repeat steps 4 through 6 until there are no more frontier cells.

Actual Code

First make a 2D array with cells that know what their adjacent cells are:

//Prim's Algorithm - spanning tree
function generatePrimMaze(e) {
  let cells = [];
  let mazeHeight = 20;
  let mazeWidth = 20;
  //Generate grid template
  for (let y = 0; y < mazeHeight; y++) {
    //Step 1: Initialize empty row
    cells[y] = [];
    // mazeWidth = y+1;
    for (let x = 0; x < mazeWidth; x++) {
      //Step 2: create each cell in this row
      let cell = {
        x: x,
        y: y,
        index: [x, y],
        status: "unvisited",
        adjacents: [],
        connections: []
      };
      cells[y][x] = cell;
      //add to unvisited set
      // unvisited.add(cell);
      //add adjacents
      if (cells[y - 1]) {
        if (cells[y - 1][x]) {
          let up = cells[y - 1][x];
          cell.adjacents.push(up);
          up.adjacents.push(cell);
        }
      }
      if (cells[y][x - 1]) {
        let left = cells[y][x - 1];
        cell.adjacents.push(left);
        left.adjacents.push(cell);
      }
    }
  }

Create the sets and choose a random starting point. I found the code to be a bit cleaner if the starting cell starts in the frontier set:

//initialize empty visited set and frontier set
  let visited = new Set();
  let frontier = new Set();
  //get random index pair as starting point and add it to visited set
  let startY = Math.floor(Math.random() * cells.length);
  let startX = Math.floor(Math.random() * cells[startY].length);
  let start = cells[startY][startX];
  //Initialize starting cell as frontier
  frontier.add(start);
  //Set start as current
  let current = start;

Next we’ll write the recursive function to create a spanning tree, altering the drawing grid at each step to create an animation. First step is to remove the current cell from the frontier set and add it to the visited set.

  recursiveSpanningTree();
  function recursiveSpanningTree() {
    //remove current from frontier and add it to visited
    frontier.delete(current);
    visited.add(current);
    current.status = "visited";
    grid[current.y * 2 + 1][current.x * 2 + 1].color = "transparent";

Add adjacent cells to frontier set. Add the current cell as a possible connection to each frontier cell.

    //add unvisited adjacent cells to frontier
    function addToFrontier(adjCells) {
      for (let c of adjCells) {
        if (c.status === "unvisited") {
          // unvisited.delete(c);
          frontier.add(c);
          c.status = "frontier";
          //make current cell the frontier cell's connection
          c.connections.push(current);
        } else if (c.status === "frontier") {
          c.connections.push(current);
        }
      }
    }
    addToFrontier(current.adjacents);

Choose a random frontier cell.

    //choose random cell from frontier
    let iteratable = [...frontier.values()];
    let randomIndex = Math.floor(Math.random() * iteratable.length);
    let frontierCell = iteratable[randomIndex];

Open a wall between the frontier cell and a random connected cell. Alter the drawing grid as well.

    //open wall between frontier cell and choose its connection
    if (frontierCell) {
      let randomConn = Math.floor(
        Math.random() * frontierCell.connections.length
      );
      let connectX = frontierCell.x + frontierCell.connections[randomConn].x;
      let connectY = frontierCell.y + frontierCell.connections[randomConn].y;
      grid[connectY + 1][connectX + 1].color = "transparent";
    }

Make that cell the current cell

    //make the frontier cell the new current
    current = frontierCell;

Clear the canvas and redraw the maze, then call the recursive function until there are no more frontier cells.

    //make the frontier cell the new current
    current = frontierCell;
    bgCtx.clearRect(0, 0, bgw, bgh);
    drawMaze();
    //while there are still unvisited cells, repeat
    if (frontier.size > 0) {
      window.setTimeout(recursiveSpanningTree, 1);
    }
  }
}