p5.j s Prim的算法迷宫生成：陷入无限循环
问题描述 投票：4回答：1
注意：我也在p5.js'论坛上发布了这个问题：https://discourse.processing.org/t/p5-js-prims-algorithm-maze-generation-stuck-in-infinite-loop/8277
我正在尝试实现一个随机的Prim算法来生成迷宫。然而，由于墙壁列表（wallList）的长度始终为数千，因此程序不断陷入无限循环。目前我使用if语句在11500次迭代后停止迷宫生成以防止无限循环。
我的伪代码基于维基百科对算法的描述：
- 从充满墙壁的网格开始。
- 选择一个单元格，将其标记为迷宫的一部分。将单元格的墙添加到墙列表中。
- 虽然列表中有墙： 从列表中选择一个随机墙。如果只访问了墙划分的两个单元格中的一个，则： 使墙成为通道，并将未经检查的细胞标记为迷宫的一部分。 将单元格的相邻墙添加到墙列表中。 从列表中删除墙。
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
这一代确实有效，如下面的截图所示。但我很确定我的实施不正确，因为挂牌列表不应包含数千个墙。
1个回答
3
投票
投票
根据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>最新问题
- Angular 可访问性并跳至导航链接
- 当软键盘可见时不会调用onBackPressed
- 如何去除联系表 7 中的跨度包装纸？
- 如何使用 JMX 导出器从 hazelcast JMX mbean 获取 hazelcast 指标
- 如何在nextjs中导入SVG
- 如何在 Android Studio 中更改 android vd 的路径
- 如何编写 xpath 来使用标签名称获取标签的值，该标签名称分别有 2 个桌面实例和移动实例
- 如何在Jupyter笔记本中显示带有文本和图像的表格？
- 我该如何解决这个问题：app = Flask(_name_) NameError: name '_name_' is not Defined
- Athena - 案例陈述计数
- 如何为 Lazygit 启用键盘映射？
- 动态树数据结构和HTML表格
- 在cmake中，如何将多个列表作为args传递
- Firefox - iframe - 即使在同源上，“跨源对象上的属性“文档”访问权限也被拒绝
- Media Foundation 如何支持多 GPU 系统？
- 如何在Keycloak管理API中进行身份验证？
- 限制 Electron webContents.findInPage() 搜索特定页面元素
- 如何为单一存储库设置 GitLab 管道，其中管道仅在文件更改时触发？
- 如何检查neo4j cypher中是否存在索引
- 如何使用 NOT IN 函数在 Top 10 列表中查找#10？
© www.soinside.com 2019 - 2024. All rights reserved.