p5.js Prim 的算法迷宫生成：陷入无限循环

Question

注意：我也在 p5.js' 论坛上发布了这个问题： https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277

我正在尝试实施随机 Prim 算法来生成迷宫。但是，由于墙列表 (wallList) 的长度总是以千计，程序一直陷入无限循环。目前我正在使用 if 语句在 11500 次迭代后停止生成迷宫以防止无限循环。

我的伪代码是基于维基百科对算法的描述：

Start with a grid full of walls.

Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.

While there are walls in the list:

Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:

Make the wall a passage and mark the unvisited cell as part of the maze.

Add the neighboring walls of the cell to the wall list.

Remove the wall from the list.

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 (maze.js):

// Note to self: JavaScript variables have function scope, not block scope

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

生成确实有效，如下面的截图所示。但我很确定我的实现不正确，因为墙列表不应包含数千面墙。

Answer 1

根据Wikipedia article的规定，无论分析结果如何，随机抽取一堵墙进行分析就必须拆除。在您的代码中，行 delete wallList[randomKey]; 和 delete wallList[correspondingString]; 必须在要从列表中删除的墙的条件之外。

删除上述行后，替换为：

numIterations += 1;

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

有了这个：

delete wallList[randomKey];
delete wallList[correspondingString];

你可以开始了。（免责声明：我对其进行了测试并且它有效；但是你那里有大量代码，所以我不确定是否还有其他问题）。

我想尝试让它更具可读性，以便我能更好地理解并想出了这个。希望对你有帮助。

// 1. Start with a grid full of walls.

const _WALL = '█';
const _PATH = ' ';
const _COLS = 60;
const _ROWS = 60;

let maze = [];
for(let i = 0; i < _COLS; i++){
  maze.push([]);
  for(let j = 0; j < _ROWS; j++)
    maze[i][j] = _WALL;
}

// 2. Pick a cell, mark it as part of the maze. 

let cell = {x:Math.floor(Math.random()*_COLS), y:Math.floor(Math.random()*_ROWS)};
maze[cell.x][cell.y] = _PATH;

// 2.1 Add the walls of the cell to the wall list.

let walls = [];
if(cell.x+1 < _COLS)  walls.push({x:cell.x+1, y:cell.y});
if(cell.x-1 >= 0)     walls.push({x:cell.x-1, y:cell.y});
if(cell.y+1 < _ROWS)  walls.push({x:cell.x, y:cell.y+1});
if(cell.y-1 >= 0)     walls.push({x:cell.x, y:cell.y-1});

// 3. While there are walls in the list:

while(walls.length > 0){

 // 3.1 Pick a random wall from the list.

  let wallIndex = Math.floor(Math.random() * walls.length);
  let wall = walls[wallIndex];

  // 3.2 If only one of the two cells that the wall divides is visited, then:

  let uc = []; // uc will be short for 'unvisited cell'

  if(wall.x+1 < _COLS && maze[wall.x+1][wall.y] === _PATH) uc.push({x:wall.x-1, y:wall.y});
  if(wall.x-1 >= 0  && maze[wall.x-1][wall.y] === _PATH) uc.push({x:wall.x+1, y:wall.y});
  if(wall.y+1 < _ROWS && maze[wall.x][wall.y+1] === _PATH) uc.push({x:wall.x, y:wall.y-1});
  if(wall.y-1 >= 0  && maze[wall.x][wall.y-1] === _PATH) uc.push({x:wall.x, y:wall.y+1});

  if(uc.length === 1){

  // 3.2.1 Make the wall a passage and mark the unvisited cell as part of the maze.

    maze[wall.x][wall.y] = _PATH;
    if(uc[0].x >=0 && uc[0].x <_COLS && uc[0].y >=0 && uc[0].y<_ROWS){
      maze[uc[0].x][uc[0].y] = _PATH;

      // 3.2.2 Add the neighboring walls of the cell to the wall list.

      if(uc[0].x+1 < _COLS  && maze[uc[0].x+1][uc[0].y] === _WALL) walls.push({x:uc[0].x+1, y:uc[0].y});
      if(uc[0].x-1 >= 0     && maze[uc[0].x-1][uc[0].y] === _WALL) walls.push({x:uc[0].x-1, y:uc[0].y});
      if(uc[0].y+1 < _ROWS  && maze[uc[0].x][uc[0].y+1] === _WALL) walls.push({x:uc[0].x, y:uc[0].y+1});
      if(uc[0].y-1 >= 0     && maze[uc[0].x][uc[0].y-1] === _WALL) walls.push({x:uc[0].x, y:uc[0].y-1});
      }
    }

 // 3.3 Remove the wall from the list.

  walls.splice(wallIndex, 1);
}

console.table(maze);

function setup(){
  createCanvas(400, 400);
  fill(0);
  let widthUnit = width / _COLS;
  let heightUnit = height / _ROWS;

  for(let i = 0; i < _COLS; i++)
    for(let j = 0; j < _ROWS; j++)
    if(maze[i][j] === _WALL){
    //rect(i*widthUnit, j*heightUnit, widthUnit, heightUnit);
      if(i-1 >= 0 && i+1 < _COLS){
        if(maze[i-1][j] === _WALL) line((i+0.5)*widthUnit, (j+0.5)*heightUnit, i*widthUnit, (j+0.5)*heightUnit);
        if(maze[i+1][j] === _WALL) line((i+0.5)*widthUnit, (j+0.5)*heightUnit, (i+1)*widthUnit, (j+0.5)*heightUnit);
      }
      if(j-1 >= 0 && j+1 < _ROWS){
        if(maze[i][j-1] === _WALL) line((i+0.5)*widthUnit, (j+0.5)*heightUnit, (i+0.5)*widthUnit, j*heightUnit);
        if(maze[i][j+1] === _WALL) line((i+0.5)*widthUnit, (j+0.5)*heightUnit, (i+0.5)*widthUnit, (j+1)*heightUnit);
      }
    }
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.3/p5.min.js"></script>

p5.js Prim 的算法迷宫生成：陷入无限循环

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

javascript

algorithm

p5.js