我的递归除法算法中的错误（随机生成迷宫）
Bug in my recursive division algorithm (to generate maze randomly)
我在生成随机迷宫时遇到问题。我的算法创建了迷宫所在的初始框。但我似乎无法在这个盒子内生成任何墙壁。我正在尝试使用递归除法算法。这是我的代码：
class Maze {
constructor(COLS,ROWS) {
this.width = COLS;
this.height = ROWS;
this.COLS = this.width*2+1; // *2 To account for blocks which are replaced by walls,
this.ROWS = this.height*2+1; // so the hollow blocks will be half of the total blocks, and there
//will be +1 wall (because the border of the maze will be a wall on either side on both x and y axies.)
this.dimentions = [this.COLS, this.ROWS];
this.maze = this.initArray([]);
// This will palce the border walls (the ones on the outside of the maze)
this.maze.forEach((currentRow, index) => {
if(index === 0 || index === this.ROWS-1) {
currentRow.forEach((_, cellIndex) => {
this.maze[index][cellIndex] = ["BLACK_WALL"];
});
} else {
this.maze[index][0] = ["BLACK_WALL"];
this.maze[index][currentRow.length-1] = ["BLACK_WALL"];
}
});
// Now do the "recursive division" method to generate the maze
const randomWallStart = [[2,2], [this.COLS-3, this.ROWS-3]][this.randInt(0,2)]; // Picks top left or bottom right
const randomWallEnd = [[this.COLS-3, 2], [2, this.ROWS-3]][this.randInt(0,2)]; // Picks the other corner
this.recursiveDivision(randomWallStart, randomWallEnd);
}
randInt(min, max) { // Used in random generation of maze
return Math.floor(Math.random()*(max-min))+min;
}
initArray(value) {
return new Array(this.ROWS).fill().map(() => new Array(this.COLS).fill(value));
}
recursiveDivision(wallStart, wallEnd, its=0) {
this.maze[wallStart[1]][wallStart[0]] = ["FLAG1"];
this.maze[wallEnd[1]][wallEnd[0]] = ["FLAG2"];
const randXpoint = this.randInt(wallStart[0], wallEnd[0]); // Doesn't matter which way round the max and min are.
const randYpoint = this.randInt(wallStart[1], wallEnd[1]);
const directionToBuildWall = wallStart[0] === wallEnd[0] ? 0 : 1; // 0 = x-axis 1 = y-axis
const newWallStart = [randXpoint, randYpoint];
let forwardsOrBackwards = 1;
if(newWallStart[directionToBuildWall] > this.dimentions[directionToBuildWall]/2) {
forwardsOrBackwards = -1;
}
let currentPosition = newWallStart;
currentPosition[directionToBuildWall] += forwardsOrBackwards * 1;
while(this.maze[currentPosition[1]][currentPosition[0]] != "BLACK_WALL") {
this.maze[currentPosition[1]][currentPosition[0]] = ["BLACK_WALL"];
currentPosition[directionToBuildWall] += forwardsOrBackwards*1;
}
if(its > Math.min(this.COLS-2)) {
return;
}
const beginningPos = currentPosition.slice();
beginningPos[directionToBuildWall] = 1;
this.recursiveDivision(currentPosition,beginningPos,its+1);
}
posToSpace(x) {
return 2 * (x-1) + 1;
}
posToWall(x) {
return 2 * x;
}
inBounds(r, c) {
if((typeof this.maze[r] == "undefined") || (typeof this.maze[r][c] == "undefined")) {
return false; // out of bounds
}
return true;
}
isGap(...cells) {
return cells.every((array) => {
let row, col;
[row, col] = array;
if(this.maze[row][col].length > 0) {
if(!this.maze[row][col].includes("door")) {
return false;
}
}
return true;
});
}
countSteps(array, r, c, val, stop) {
if(!this.inBounds(r, c)) {
return false; // out of bounds
}
if(array[r][c] <= val) {
return false; // shorter route already mapped
}
if(!this.isGap([r, c])) {
return false; // not traversable
}
array[r][c] = val;
if(this.maze[r][c].includes(stop)) {
return true; // reached destination
}
this.countSteps(array, r-1, c, val+1, stop);
this.countSteps(array, r, c+1, val+1, stop);
this.countSteps(array, r+1, c, val+1, stop);
this.countSteps(array, r, c-1, val+1, stop);
}
display() {
this.parentDiv = document.getElementById("maze-container");
while(this.parentDiv.firstChild) {
this.parentDiv.removeChild(this.parentDiv.firstChild);
}
const container = document.createElement("div");
container.id = "maze";
container.dataset.steps = this.totalSteps;
this.maze.forEach((row) => {
let rowDiv = document.createElement("div");
row.forEach((cell) => {
let cellDiv = document.createElement("div");
if(cell?.join) {
cellDiv.className = cell.join("");
}
rowDiv.appendChild(cellDiv);
});
container.appendChild(rowDiv);
});
this.parentDiv.appendChild(container);
return true;
}
}
const myMaze = new Maze(5,5);
myMaze.display();
body, html {margin: 0;}
#maze-container {
position: absolute;
top: 50%; left: 50%;
transform: translate(-50%, -50%);
}
#maze {
position: relative;
background-color: #a7c53f;
background-size: 8em 8em;
}
#maze div {
display: flex;
}
#maze div div {
position: relative;
width: 1.2rem;
height: 1.2rem;
}
#maze div div::after {
position: absolute;
left: -3px;
top: -4px;
text-align: center;
text-shadow: 0 0 1px black;
font-size: 1.2em;
z-index: 10;
}
.FLAG1 {
background-color: #a00;
}
.FLAG2 {
background-color: #0a0;
}
#maze div div.BLACK_WALL, #maze div div.nubbin.BLACK_WALL, #maze div div.door.exit {
background-color: #000;
background-size: 0.5em 0.5em;
}
#maze div div.nubbin.BLACK_WALL::after {
content: "";
}
#maze div div:nth-child(odd) {
width: 1em;
}
#maze div:nth-child(odd) div {
height: 1em;
}
<div id="maze-container"></div>
正如您在 运行 代码中看到的那样，墙壁已生成，但位置错误。所以有些相互接触（所以你不能在它们之间移动），我无法解决这个问题。
我无法让这个“递归除法”算法正常工作。
我在您的代码中至少看到了这些问题：
墙是在随机位置建造的，没有考虑 odd/even 你的细胞在潜在壁/非壁细胞中的划分（这就是你有 this.COLS = this.width*2+1 在构造函数中）。因此，您的墙壁最终可能彼此相邻，没有空间容纳开放式单元格。您应该只在 even Y 坐标处放置水平墙，在 even X 坐标处放置垂直墙。
墙中的门总是在墙的最末端制作，而算法应该随机在墙中制作缝隙。
只有一个递归调用，这意味着算法不知道一堵墙通常将房间分成两个分区，每个分区（通常）应该通过进一步划分递归。所以你需要两次递归调用而不是一次。
如果您纠正这些问题，它可能会起作用。但是，我更喜欢这样一种数据结构，其中真正的 each 内部数组元素代表一个单元格，并且墙壁是由这些单元格的属性推断出来的。所以，没有细胞会起到墙的作用。然后每个单元格可以跟踪哪些是它的邻居（最多 4 个）。然后可以通过 从单元格中移除 一个邻居（并在相反的方向上做同样的事情）来实现一堵墙。然后可以使用 border CSS 样式来完成墙的可视化。
这是一个实现：
class Maze {
static Cell = class {
constructor(x, y, left, above) {
this.x = x;
this.y = y;
this.neighbors = [left ?? null, above ?? null, null, null];
// Also set link in opposite direction
if (left) left.neighbors[2] = this;
if (above) above.neighbors[3] = this;
}
block(direction) {
// Place a wall by clearing neighbor link
if (this.neighbors[direction]) this.neighbors[direction][direction ^ 2] = null;
this.neighbors[direction] = null;
}
}
constructor(parent, numCols, numRows) {
this.parentDiv = parent;
let above = [];
this.maze = Array.from({length: numRows}, (_, y) => {
let left = null;
return above = Array.from({length: numCols}, (_, x) => left = new Maze.Cell(x, y, left, above[x]));
});
this.recursiveDivision(0, 0, numCols, numRows);
}
recursiveDivision(left, top, right, bottom, its=0) {
const randInt = (min, max) => Math.floor(Math.random() * (max - min)) + min;
const width = right - left;
const height = bottom - top;
// Base case: cannot be divided further:
if (width < 2 || height < 2) return;
let choice = randInt(0, (width - 1) + (height - 1));
if (choice >= width - 1) { // Place horizontal wall
const y = top + choice - (width - 2);
const gap = randInt(left, right);
for (let x = left; x < right; x++) {
if (x != gap) this.maze[y][x].block(1);
}
this.recursiveDivision(left, top, right, y, its+1);
this.recursiveDivision(left, y, right, bottom, its+1);
} else { // Place vertical wall
const x = left + choice + 1;
const gap = randInt(top, bottom);
for (let y = top; y < bottom; y++) {
if (y != gap) this.maze[y][x].block(0);
}
this.recursiveDivision(left, top, x, bottom, its+1);
this.recursiveDivision(x, top, right, bottom, its+1);
}
}
display() {
this.parentDiv.innerHTML = "";
const container = document.createElement("div");
container.className = "maze";
for (const row of this.maze) {
const rowDiv = document.createElement("div");
for (const cell of row) {
const cellDiv = document.createElement("div");
cellDiv.className = ["left", "top", "right", "bottom"].filter((_, i) => !cell.neighbors[i]).join(" ");
rowDiv.appendChild(cellDiv);
}
container.appendChild(rowDiv);
}
this.parentDiv.appendChild(container);
}
}
const myMaze = new Maze(document.getElementById("maze-container"), 30, 10);
myMaze.display();
body, html { margin: 0 }
#maze-container {
position: absolute;
top: 50%;
left: 50%;
transform: translate(-50%, -50%);
}
.maze {
position: relative;
background-color: #a7c53f;
background-size: 8em 8em;
}
.maze div {
display: flex;
}
.maze div div {
box-sizing: border-box;
position: relative;
width: 1.2rem;
height: 1.2rem;
}
.left { border-left: 1px solid black }
.right { border-right: 1px solid black }
.top { border-top: 1px solid black }
.bottom { border-bottom: 1px solid black }
<div id="maze-container"></div>
我在生成随机迷宫时遇到问题。我的算法创建了迷宫所在的初始框。但我似乎无法在这个盒子内生成任何墙壁。我正在尝试使用递归除法算法。这是我的代码：
class Maze {
constructor(COLS,ROWS) {
this.width = COLS;
this.height = ROWS;
this.COLS = this.width*2+1; // *2 To account for blocks which are replaced by walls,
this.ROWS = this.height*2+1; // so the hollow blocks will be half of the total blocks, and there
//will be +1 wall (because the border of the maze will be a wall on either side on both x and y axies.)
this.dimentions = [this.COLS, this.ROWS];
this.maze = this.initArray([]);
// This will palce the border walls (the ones on the outside of the maze)
this.maze.forEach((currentRow, index) => {
if(index === 0 || index === this.ROWS-1) {
currentRow.forEach((_, cellIndex) => {
this.maze[index][cellIndex] = ["BLACK_WALL"];
});
} else {
this.maze[index][0] = ["BLACK_WALL"];
this.maze[index][currentRow.length-1] = ["BLACK_WALL"];
}
});
// Now do the "recursive division" method to generate the maze
const randomWallStart = [[2,2], [this.COLS-3, this.ROWS-3]][this.randInt(0,2)]; // Picks top left or bottom right
const randomWallEnd = [[this.COLS-3, 2], [2, this.ROWS-3]][this.randInt(0,2)]; // Picks the other corner
this.recursiveDivision(randomWallStart, randomWallEnd);
}
randInt(min, max) { // Used in random generation of maze
return Math.floor(Math.random()*(max-min))+min;
}
initArray(value) {
return new Array(this.ROWS).fill().map(() => new Array(this.COLS).fill(value));
}
recursiveDivision(wallStart, wallEnd, its=0) {
this.maze[wallStart[1]][wallStart[0]] = ["FLAG1"];
this.maze[wallEnd[1]][wallEnd[0]] = ["FLAG2"];
const randXpoint = this.randInt(wallStart[0], wallEnd[0]); // Doesn't matter which way round the max and min are.
const randYpoint = this.randInt(wallStart[1], wallEnd[1]);
const directionToBuildWall = wallStart[0] === wallEnd[0] ? 0 : 1; // 0 = x-axis 1 = y-axis
const newWallStart = [randXpoint, randYpoint];
let forwardsOrBackwards = 1;
if(newWallStart[directionToBuildWall] > this.dimentions[directionToBuildWall]/2) {
forwardsOrBackwards = -1;
}
let currentPosition = newWallStart;
currentPosition[directionToBuildWall] += forwardsOrBackwards * 1;
while(this.maze[currentPosition[1]][currentPosition[0]] != "BLACK_WALL") {
this.maze[currentPosition[1]][currentPosition[0]] = ["BLACK_WALL"];
currentPosition[directionToBuildWall] += forwardsOrBackwards*1;
}
if(its > Math.min(this.COLS-2)) {
return;
}
const beginningPos = currentPosition.slice();
beginningPos[directionToBuildWall] = 1;
this.recursiveDivision(currentPosition,beginningPos,its+1);
}
posToSpace(x) {
return 2 * (x-1) + 1;
}
posToWall(x) {
return 2 * x;
}
inBounds(r, c) {
if((typeof this.maze[r] == "undefined") || (typeof this.maze[r][c] == "undefined")) {
return false; // out of bounds
}
return true;
}
isGap(...cells) {
return cells.every((array) => {
let row, col;
[row, col] = array;
if(this.maze[row][col].length > 0) {
if(!this.maze[row][col].includes("door")) {
return false;
}
}
return true;
});
}
countSteps(array, r, c, val, stop) {
if(!this.inBounds(r, c)) {
return false; // out of bounds
}
if(array[r][c] <= val) {
return false; // shorter route already mapped
}
if(!this.isGap([r, c])) {
return false; // not traversable
}
array[r][c] = val;
if(this.maze[r][c].includes(stop)) {
return true; // reached destination
}
this.countSteps(array, r-1, c, val+1, stop);
this.countSteps(array, r, c+1, val+1, stop);
this.countSteps(array, r+1, c, val+1, stop);
this.countSteps(array, r, c-1, val+1, stop);
}
display() {
this.parentDiv = document.getElementById("maze-container");
while(this.parentDiv.firstChild) {
this.parentDiv.removeChild(this.parentDiv.firstChild);
}
const container = document.createElement("div");
container.id = "maze";
container.dataset.steps = this.totalSteps;
this.maze.forEach((row) => {
let rowDiv = document.createElement("div");
row.forEach((cell) => {
let cellDiv = document.createElement("div");
if(cell?.join) {
cellDiv.className = cell.join("");
}
rowDiv.appendChild(cellDiv);
});
container.appendChild(rowDiv);
});
this.parentDiv.appendChild(container);
return true;
}
}
const myMaze = new Maze(5,5);
myMaze.display();
body, html {margin: 0;}
#maze-container {
position: absolute;
top: 50%; left: 50%;
transform: translate(-50%, -50%);
}
#maze {
position: relative;
background-color: #a7c53f;
background-size: 8em 8em;
}
#maze div {
display: flex;
}
#maze div div {
position: relative;
width: 1.2rem;
height: 1.2rem;
}
#maze div div::after {
position: absolute;
left: -3px;
top: -4px;
text-align: center;
text-shadow: 0 0 1px black;
font-size: 1.2em;
z-index: 10;
}
.FLAG1 {
background-color: #a00;
}
.FLAG2 {
background-color: #0a0;
}
#maze div div.BLACK_WALL, #maze div div.nubbin.BLACK_WALL, #maze div div.door.exit {
background-color: #000;
background-size: 0.5em 0.5em;
}
#maze div div.nubbin.BLACK_WALL::after {
content: "";
}
#maze div div:nth-child(odd) {
width: 1em;
}
#maze div:nth-child(odd) div {
height: 1em;
}
<div id="maze-container"></div>
正如您在 运行 代码中看到的那样，墙壁已生成，但位置错误。所以有些相互接触（所以你不能在它们之间移动），我无法解决这个问题。 我无法让这个“递归除法”算法正常工作。
我在您的代码中至少看到了这些问题：
墙是在随机位置建造的，没有考虑 odd/even 你的细胞在潜在壁/非壁细胞中的划分（这就是你有
this.COLS = this.width*2+1在构造函数中）。因此，您的墙壁最终可能彼此相邻，没有空间容纳开放式单元格。您应该只在 even Y 坐标处放置水平墙，在 even X 坐标处放置垂直墙。墙中的门总是在墙的最末端制作，而算法应该随机在墙中制作缝隙。
只有一个递归调用，这意味着算法不知道一堵墙通常将房间分成两个分区，每个分区（通常）应该通过进一步划分递归。所以你需要两次递归调用而不是一次。
如果您纠正这些问题，它可能会起作用。但是，我更喜欢这样一种数据结构，其中真正的 each 内部数组元素代表一个单元格，并且墙壁是由这些单元格的属性推断出来的。所以，没有细胞会起到墙的作用。然后每个单元格可以跟踪哪些是它的邻居（最多 4 个）。然后可以通过 从单元格中移除 一个邻居（并在相反的方向上做同样的事情）来实现一堵墙。然后可以使用 border CSS 样式来完成墙的可视化。
这是一个实现：
class Maze {
static Cell = class {
constructor(x, y, left, above) {
this.x = x;
this.y = y;
this.neighbors = [left ?? null, above ?? null, null, null];
// Also set link in opposite direction
if (left) left.neighbors[2] = this;
if (above) above.neighbors[3] = this;
}
block(direction) {
// Place a wall by clearing neighbor link
if (this.neighbors[direction]) this.neighbors[direction][direction ^ 2] = null;
this.neighbors[direction] = null;
}
}
constructor(parent, numCols, numRows) {
this.parentDiv = parent;
let above = [];
this.maze = Array.from({length: numRows}, (_, y) => {
let left = null;
return above = Array.from({length: numCols}, (_, x) => left = new Maze.Cell(x, y, left, above[x]));
});
this.recursiveDivision(0, 0, numCols, numRows);
}
recursiveDivision(left, top, right, bottom, its=0) {
const randInt = (min, max) => Math.floor(Math.random() * (max - min)) + min;
const width = right - left;
const height = bottom - top;
// Base case: cannot be divided further:
if (width < 2 || height < 2) return;
let choice = randInt(0, (width - 1) + (height - 1));
if (choice >= width - 1) { // Place horizontal wall
const y = top + choice - (width - 2);
const gap = randInt(left, right);
for (let x = left; x < right; x++) {
if (x != gap) this.maze[y][x].block(1);
}
this.recursiveDivision(left, top, right, y, its+1);
this.recursiveDivision(left, y, right, bottom, its+1);
} else { // Place vertical wall
const x = left + choice + 1;
const gap = randInt(top, bottom);
for (let y = top; y < bottom; y++) {
if (y != gap) this.maze[y][x].block(0);
}
this.recursiveDivision(left, top, x, bottom, its+1);
this.recursiveDivision(x, top, right, bottom, its+1);
}
}
display() {
this.parentDiv.innerHTML = "";
const container = document.createElement("div");
container.className = "maze";
for (const row of this.maze) {
const rowDiv = document.createElement("div");
for (const cell of row) {
const cellDiv = document.createElement("div");
cellDiv.className = ["left", "top", "right", "bottom"].filter((_, i) => !cell.neighbors[i]).join(" ");
rowDiv.appendChild(cellDiv);
}
container.appendChild(rowDiv);
}
this.parentDiv.appendChild(container);
}
}
const myMaze = new Maze(document.getElementById("maze-container"), 30, 10);
myMaze.display();
body, html { margin: 0 }
#maze-container {
position: absolute;
top: 50%;
left: 50%;
transform: translate(-50%, -50%);
}
.maze {
position: relative;
background-color: #a7c53f;
background-size: 8em 8em;
}
.maze div {
display: flex;
}
.maze div div {
box-sizing: border-box;
position: relative;
width: 1.2rem;
height: 1.2rem;
}
.left { border-left: 1px solid black }
.right { border-right: 1px solid black }
.top { border-top: 1px solid black }
.bottom { border-bottom: 1px solid black }
<div id="maze-container"></div>