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

**URL:** <https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277>\
**Category:** Coding Questions\
**Created:** [February 10, 2019, 6:39pm UTC](https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277 "2019-02-10T18:39:58Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![henrydavidzhu](https://avatars.discourse-cdn.com/v4/letter/h/87869e/32.png) [@henrydavidzhu](https://discourse.processing.org/u/henrydavidzhu)\
**Post date:** [February 10, 2019, 6:39pm UTC](https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277/1 "2019-02-10T18:39:59Z")

</div>

**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](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](https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim's_algorithm))

HTML:

```auto
<!doctype html>
<html>
   <head>
      <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>
   </head>
   <body>
      <div id="game-wrapper">
            <div id="canvas-wrapper">
            </div>
         </div>

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

```

JavaScript:

```auto
    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.

 ![Capture](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/1/18c11c05256e23c686ca14a7028f24517ae5b097.png)

---

<div class="post-metadata">

**Author:** ![Kevin](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kevin/32/2297_2.png) [@Kevin](https://discourse.processing.org/u/Kevin)\
**Post date:** [February 11, 2019, 12:09am UTC](https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277/2 "2019-02-11T00:09:23Z")

</div>

If you post to multiple sites, please link between those posts so we know what help you’ve already received. This question has already been asked (and answered) here:

> <https://stackoverflow.com/questions/54613229/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop>

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [February 15, 2019, 9:05pm UTC](https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277/3 "2019-02-15T21:05:59Z")

</div>

There is also a p5.js video tutorial on Prim’s

[![](https://img.youtube.com/vi/BxabnKrOjT0/hqdefault.jpg "9.9: Minimum Spanning Tree (Prim's Algorithm) - p5.js Tutorial") ](https://www.youtube.com/watch?v=BxabnKrOjT0)