我的递归除法算法中的错误(随机生成迷宫)

Question

我在生成随机迷宫时遇到问题。我的算法创建了迷宫所在的初始框。但我似乎无法在这个框内生成任何墙。我正在尝试使用递归除法算法。这是我的代码：

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>

正如您在运行代码时所看到的，墙是生成的，但位置不对。所以有些人互相接触(所以你不能在他们之间移动(，我无法解决这个问题。我不能得到这个">递归除法"；算法正常工作。

Answer 1

我在您的代码中至少看到了以下问题：

• 墙是在一个随机的位置建造的，没有考虑到你的细胞在潜在的墙/非墙细胞中的奇数/偶数分裂(这就是你在构造函数中使用this.COLS = this.width*2+1的原因(。因此，你的墙可能会相邻，没有空间容纳开放的细胞。应仅将水平墙放置在偶数Y坐标处，将垂直墙放置在偶数X坐标处。

• 墙中的门总是在墙的最末端制作，而算法应该随机制作墙中的间隙。

• 只有一个递归调用，这意味着算法没有意识到一堵墙通常将房间划分为两个分区，每个分区(通常(都应该通过递归进一步划分。因此，您需要两个递归调用，而不是一个。

如果你纠正了这些点，它可能会起作用。然而，我更喜欢这样的数据结构，其中真正的每个内部数组元素表示一个单元，并且壁是由这些单元的属性推断的。所以，没有细胞会起到壁的作用。然后，每个小区可以跟踪哪些是它的邻居(最多4个(。然后，可以通过从小区中删除邻居来实现墙(并在相反的方向上执行同样的操作(。然后可以使用borderCSS样式对墙进行可视化。

这里有一个实现：

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>