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


#1

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>
   <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:

    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.


#2

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:


#3

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