# P5.js Prim's Algorithm Maze Generation: Stuck in Infinite Loop

Note: Posted this question on StackOverflow and received answers there: https://stackoverflow.com/questions/54613229/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/54621408#54621408

I’m trying on implementing randomized Prim’s algorithm to generate a maze. However, the program keeps getting stuck in an infinite loop as the length of the list of walls ( `wallList` ) is always in the thousands. Currently, I am using an if statement that stops the maze generation after 11500 iterations to prevent an infinite loop.

My pseudocode is based on Wikipedia’s description of the algorithm (https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim’s_algorithm)

HTML:

``````<!doctype html>
<html>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<script src="https://ajax.aspnetcdn.com/ajax/jQuery/jquery-3.3.1.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.6.0/p5.js"></script>
</script>
<body>
<div id="game-wrapper">
<div id="canvas-wrapper">
</div>
</div>

</div>
<script type="text/javascript" src="maze.js"></script>
</body>
</html>
``````

JavaScript:

``````    var numIterations = 0; // Just for debugging purposes (stop at 1000 iterations otherwise the program goes into
// an infinite loop

// The directions and vectors arrays correspond to each other
// For example, the first element of directions is "N" and the first element of vectors also represents a
// north vector
var directions = ["N", "E", "S", "W"]

var vectors = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1]
];

var wallList = {}; // Structure of a wall [rol (num), col (num), direction (string)]

function Maze(numRows, numColumns) {
/*
Defines a maze given the number of rows and the number of columns in the maze
*/
this.numColumns = numColumns;
this.numRows = numRows;
this.numCells = numRows * numColumns;
this.cellGraph = [];

for (var i = 0; i < numRows; i++) { // For every single row
this.cellGraph.push([]); // Start out with an empty row
}
}

Maze.prototype.computeFrontierWalls = function (cellRow, cellColumn) {
/*
The frontier walls of a cell is defined as all the walls of the adjacent cells
*/

/*
Coordinates of adjacent cells:
Up [cellRow - 1, cellColumn]
Down [cellRow + 1, cellColumn]
Right [cellRow, cellColumn + 1]
Left [cellRow, cellColumn - 1]
*/
var coordinates = [
[cellRow - 1, cellColumn],
[cellRow + 1, cellColumn],
[cellRow, cellColumn + 1],
[cellRow, cellColumn - 1]
];

var computedFrontier = []; // List of frontier cells

var originalCell = this.cellGraph[cellRow][cellColumn]; // We want to calculate the frontier of the original cell

for (var i = 0; i < coordinates.length; i++) {
// Get the coordinates of the adjacent cell
var coordinate = coordinates[i];
var row = coordinate[0];
var col = coordinate[1];

// See if a cell exists at that area
// If there is a cell that exists, add all of the walls of the cell to the computedFrontier array
if (row >= 0 && row < this.cellGraph.length && col >= 0 && col < this.cellGraph[0].length) {
var cell = this.cellGraph[parseInt(row)][parseInt(col)];

for (var j = 0; j < directions.length; j++) {
computedFrontier.push([cell.row, cell.column, directions[j]]);
}
}
}

return computedFrontier;
}

function Cell(cellSize, row, column) {
this.cellSize = cellSize; // The width and height of the cell

this.column = column;
this.row = row;

this.xPos = column * cellSize;
this.yPos = row * cellSize;

this.walls = [true, true, true, true]; // 0 = top, 1 = right, 2 = bottom, 3 = left
this.visited = false; // Whether the cell has been traversed or not
}

function getRandomPos(widthCells, heightCells) {
var row = Math.floor(Math.random() * heightCells); // Generate a random row
var column = Math.floor(Math.random() * widthCells); // Generate a random column

return [row, column];
}

var mazeIntro = function (p) {

var maze = new Maze(20, 35); // Generate a new maze with 20 rows and 35 columns

Maze.prototype.createMaze = function () { // Build an empty maze
for (var i = 0; i < this.numRows; i++) { // Iterate through every row
for (var j = 0; j < this.numColumns; j++) { // Iterate through every column
var cell = new Cell(20, i, j); // Create a new size at row i and column j with size 20
maze.cellGraph[i].push(cell); // Add the cell to the row
}
}
}

maze.createMaze(); // Build the maze

p.setup = function () {
var canvas = p.createCanvas(700, 400);
p.background(255, 255, 255);

p.smooth();
p.noLoop();

// Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list
var pos = getRandomPos(maze.cellGraph[0].length, maze.cellGraph.length);
;
var row = pos[0];
var column = pos[1];

maze.cellGraph[row][column].visited = true;

for (var k = 0; k < directions.length; k++) {
var key = row.toString() + column.toString() + directions[k].toString();

if (!wallList[key]) {
wallList[key] = [row, column, directions[k]];
}
}
}

Cell.prototype.display = function () {
/*
For each wall:
1. Check if it is on the border of the maze:
2. If it is on the border: don't draw the wall
3. If it isn't on the border: draw the wall
*/

p.stroke(0, 0, 0);
if (this.walls[0] && this.row != 0) { // Top
p.line(this.xPos, this.yPos, this.xPos + this.cellSize, this.yPos);
}
if (this.walls[1] && this.column != maze.widthCells - 1) { // Right
p.line(this.xPos + this.cellSize, this.yPos, this.xPos + this.cellSize, this.yPos + this.cellSize);
}
if (this.walls[2] && this.row != maze.heightCells - 1) { // Bottom
p.line(this.xPos + this.cellSize, this.yPos + this.cellSize, this.xPos, this.yPos + this.cellSize);
}
if (this.walls[3] && this.column != 0) { // Left
p.line(this.xPos, this.yPos + this.cellSize, this.xPos, this.yPos);
}

p.noStroke();
}

Cell.prototype.toString = function () {
/*
Mainly used for debugging purposes, converts the object into a string containing the row and the column of the cell
*/
return this.row + "|" + this.column;
}

function deleteWall(current, neighbor) {
/*
Deletes two walls separating two cells: current and neighbor

Calculates if neighbor is to the left, right, top, or bottom of cell
Removes the current's wall and the corresponding neighbor's wall
*/
var deltaX = current.column - neighbor.column;
var deltaY = current.row - neighbor.row;

if (deltaX == 1) { // Current is to the right of the neighbor
current.walls[3] = false;
neighbor.walls[1] = false;
}
if (deltaX == -1) { // Current is to the left of the neighbor
current.walls[1] = false;
neighbor.walls[3] = false;
}
if (deltaY == 1) { // Current is to the bottom of the neighbor
current.walls[0] = false;
neighbor.walls[2] = false;
}
if (deltaY == -1) { // Current is to the top of the neighbor
current.walls[2] = false;
neighbor.walls[0] = false;
}
}

function isWall(cellA, cellB) {
// Whether there's a wall or not depends on the orientation of the blocks
// If it's vertical, it has to be false between even numbers
// If it's horizontal, it has to be false between odd numbers
for (var j = 0; j < cellA.walls.length; j++) {
for (var k = 0; k < cellB.walls.length; k++) {
if (Math.abs(j - k) == 2 && !cellA.walls[j] && !cellB.walls[k]) {
var rA = cellA.row;
var cA = cellA.column;
var rB = cellB.row;
var cB = cellB.column
if ((rA - rB) == 1 && j == 0 || (rA - rB) == -1 && j == 2 || (cA - cB) == 1 && j == 3 || (cA - cB) == -1 && j == 1) {
return false;
}
}
}
}
return true;
}

function calculateCellDivision(wall) {
// Calculate the two cells that the wall divides
// For example:
// If the wall is [10, 11, "N"]
// The two cells that the wall divides are (10, 11) and (9, 11)

var row = wall[0];
var col = wall[1];

var cell1 = maze.cellGraph[row][col]; // Get the cell of the wall

// Get the corresponding vector based upon the direction of the wall
var vectorIndex = directions.indexOf(wall[2]);

// Add the vector to the position of cell1
var cell2Row = parseInt(cell1.row) + vectors[vectorIndex][0];
var cell2Column = parseInt(cell1.column) + vectors[vectorIndex][1];

if (cell2Row < 0 || cell2Row >= maze.cellGraph.length || cell2Column < 0 || cell2 >= maze.cellGraph[0].length) {
return -1;
}

var cell2 = maze.cellGraph[cell2Row][cell2Column]; // Get the corresponding cell

var cellsVisited = 0;
var unvisitedCell;

if (cell1.visited) {
cellsVisited += 1;
unvisitedCell = cell2;
}

if (!cell2) { // This means that the wall is a border wall
return -1;
}

if (cell2.visited) {
cellsVisited += 1;
unvisitedCell = cell1;
}

if (cellsVisited == 1) {
return [cell1, cell2, cellsVisited, unvisitedCell];
}

return -1;
}

function getCellWalls(row, col) {
// Gets a cell's walls
var cellWalls = [];

for (var i = 0; i < directions.length; i++) {
cellWalls.push(row + col + directions[i]);
}

return cellWalls;
}

p.draw = function () {
while (Object.keys(wallList).length > 0) { // While there are still walls in the list
console.log("Object.keys(wallList).length = " +

// Pick a random wall of the list
var wallListKeys = \$.map(wallList, function (value, key) {
return key;
});

var randomKey = wallListKeys[Math.floor(Math.random() * wallListKeys.length)];

var randomWall = wallList[randomKey];

var components = calculateCellDivision(randomWall);

if (components != -1) {

var numVisited = components[2];

var cell1 = components[0];
var cell2 = components[1];

// If only one of the two cells that the wall divides is visited, then:
//  1. Make the wall a passage and mark the unvisited cell as part of the maze.
//  2. Add the neighboring walls of the cell to the wall list.
//     Remove the wall from the list.

if (numVisited == 1) {
deleteWall(cell1, cell2);

var unvisitedCell = maze.cellGraph[components[3].row][components[3].column];
unvisitedCell.visited = true;

var unvisitedString = unvisitedCell.row + "|" + unvisitedCell.column;

// Add the neighboring walls of the cell to the wall list
// Format of the walls (by index):
// 0 = top, 1 = right, 2 = bottom, 3 = left
var computedFrontierWalls = maze.computeFrontierWalls(unvisitedCell.row, unvisitedCell.column);

for (var k = 0; k < computedFrontierWalls.length; k++) {
var computedWall = computedFrontierWalls[k];
var keyString = computedWall[0].toString() + computedWall[1].toString() + computedWall[2];

if (!wallList[keyString]) {
wallList[keyString] = computedWall;
}
}

// Delete randomKey from the list of walls, and then delete the same wall from the corresponding cell
delete wallList[randomKey];

// Calculate the corresponding cell
var direction = randomWall[2];
var directionIndex = directions.indexOf(direction);
var oppositeDirectionIndex = -1;

if (directionIndex == 0) {
oppositeDirectionIndex = 2;
}
if (directionIndex == 2) {
oppositeDirectionIndex = 0;
}
if (directionIndex == 1) {
oppositeDirectionIndex = 3;
}
if (directionIndex == 3) {
oppositeDirectionIndex = 1;
}

var vector = vectors[directionIndex];

var correspondingString = (randomWall[0] + vector[0]).toString() + (randomWall[1] + vector[1]).toString() + directions[oppositeDirectionIndex];

delete wallList[correspondingString];
}
}

numIterations += 1;

if (numIterations == 11500) { // Prevents infinite loop
break;
}
}

p.clear();

// Draw the maze
for (var i = 0; i < maze.cellGraph.length; i++) { // Iterate through row
for (var j = 0; j < maze.cellGraph[i].length; j++) { // Iterate through every column
maze.cellGraph[i][j].display(); // Display the cell
}
}

p.line(0, 400, 400, 400);
}
};

var myp5 = new p5(mazeIntro, "canvas-wrapper"); // Initialize the graphics engine for the canvas
``````

The generation does work, as shown in the screenshot below. But I’m pretty sure my implementation is not correct as the wall list shouldn’t contain thousands of walls.