我正在尝试实现DFS回溯算法，该算法涉及利用Wikipedia上的堆栈（而非递归算法）。我正在尝试生成0和1的迷宫，其中1代表墙，0代表可用路径。对于迷宫中不是墙壁的任何给定空间，必须始终存在可以从任何其他非墙壁单元到达的有效路径。
我从一个迷宫开始，该迷宫是一个二维数组，大小为迷宫[15] [20]，并按照算法标记需要适当标记为已访问的单元格。最初，所有单元（不包括外部边界）都标记为“未访问”。所有单元格均初始化为值“ 1”，并且期望该算法将在整个迷宫中挖掘唯一路径。
链接到算法（使用堆栈的递归回溯器第二实现）：
https://en.wikipedia.org/wiki/Maze_generation_algorithm
我写的代码：
public void innerMaze() {
List<Coordinate> listOfCoordinates = new ArrayList<>();
List<Coordinate> coordinatesToBeRemoved = new ArrayList<>();
Stack<Coordinate> DFS_Stack = new Stack();
Coordinate initialCell = new Coordinate(1, 1);
checkIfVisited.put(initialCell, true);
DFS_Stack.push(initialCell);
int randomInteger = 0;
int cx = 0;
int cy = 0;
int gx = 0;
int gy = 0;
while (!DFS_Stack.empty()) {
Coordinate currentCoordinate = DFS_Stack.pop();
cx = currentCoordinate.getX();
cy = currentCoordinate.getY();
if ((cx - 2) >= 1) {
Coordinate up = findCoordinate((cx - 2), cy);
up.setDirection('N');
listOfCoordinates.add(up);
}
if ((cx + 2) <= MAX_ROW) {
Coordinate down = findCoordinate((cx + 2), cy);
down.setDirection('S');
listOfCoordinates.add(down);
}
if ((cy - 2) >= 1) {
Coordinate left = findCoordinate(cx, (cy - 2));
left.setDirection('W');
listOfCoordinates.add(left);
}
if ((cy + 2) <= MAX_COL) {
Coordinate right = findCoordinate(cx, (cy + 2));
right.setDirection('E');
listOfCoordinates.add(right);
}
for (Coordinate s : listOfCoordinates) {
if (checkIfVisited.get(s) == true) {
coordinatesToBeRemoved.add(s);
}
}
listOfCoordinates.removeAll(coordinatesToBeRemoved);
if (!listOfCoordinates.isEmpty()) {
DFS_Stack.push(currentCoordinate);
randomInteger = ThreadLocalRandom.current().nextInt(0, listOfCoordinates.size());
Coordinate temp = listOfCoordinates.get(randomInteger);
char direction = temp.getDirection();
Coordinate newWall;
if (direction == 'N') {
newWall = findCoordinate((cx - 1), cy);
} else if (direction == 'S') {
newWall = findCoordinate((cx + 1), cy);
} else if (direction == 'W') {
newWall = findCoordinate(cx, (cy - 1));
} else {
newWall = findCoordinate(cx, (cy + 1));
}
System.out.println(newWall);
gx = newWall.getX();
gy = newWall.getY();
completeMaze[gx][gy] = 0;
checkIfVisited.put(temp, true);
checkIfVisited.put(newWall, true);
listOfCoordinates.clear();
DFS_Stack.push(temp);
}
}
}
在我目前的实现中，每个像元要么代表一堵墙，要么代表一条路径，因此我对算法进行了些微改动，以至于移除两个像元之间的墙成为移除两个像元的壁，将中间的一个像元更改为一个像元。壁。我的输出示例如下：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1
1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0
1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0
1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0
1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
乍看之下，二维数组索引[1] [1]被包裹在墙壁中，因此这是一个无法到达的区域。通过多次执行，这也是非常一致的。
任何帮助将不胜感激。
我强烈建议您使用其他算法。我在迷宫生成算法编码方面有丰富的经验，而递归回溯总是会导致漫长的路径，几乎没有任何选择。我看不到您的代码中的问题，但是这是我自己的递归回溯的Java实现（很抱歉，如果代码不好，它已经使用了几年）。
public class Maze {
private int sizeX, sizeY;
private Cell[][] cells;
private List<Cell> backtracker = new ArrayList<>();
public Maze(int sizeX, int sizeY) {
this.sizeX = sizeX;
this.sizeY = sizeY;
this.cells = new Cell[sizeX][sizeY];
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++)
cells[i][j] = new Cell(this, i, j);
}
generate();
}
private void generate() {
Cell current = cells[0][0];
current.visit();
boolean hasUnvisited = hasUnvisited();
while (hasUnvisited) {
current = current.pickNext();
if (!current.isVisited()) {
current.visit();
backtracker.add(current);
hasUnvisited = hasUnvisited();
}
}
}
private boolean hasUnvisited() {
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
if (!cells[i][j].isVisited()) {
return true;
}
}
}
return false;
}
public Cell backtrack() {
if (backtracker.size() == 0) return null;
Cell cell = backtracker.get(backtracker.size() - 1);
backtracker.remove(cell);
return cell;
}
public Cell getCell(int x, int y) {
return cells[x][y];
}
}
public class Cell {
private Maze maze;
private int x, y;
private boolean visited = false;
// top, right, bottom. left
private boolean[] walls = new boolean[]{true, true, true, true};
public Cell(Maze maze, int x, int y) {
this.maze = maze;
this.x = x;
this.y = y;
}
public Cell pickNext() {
List<Cell> neighbors = new ArrayList<>();
if (y != maze.sizeY - 1) neighbors.add(maze.getCell(x, y + 1));
else neighbors.add(null);
if (x != maze.sizeX - 1) neighbors.add(maze.getCell(x + 1, y));
else neighbors.add(null);
if (y != 0) neighbors.add(maze.getCell(x, y - 1));
else neighbors.add(null);
if (x != 0) neighbors.add(maze.getCell(x - 1, y));
else neighbors.add(null);
boolean hasUnvisitedNeighbor = false;
for (Cell c : neighbors) {
if (c == null) continue;
if (!c.isVisited()) hasUnvisitedNeighbor = true;
}
if (hasUnvisitedNeighbor) {
int random = (int) Math.floor(Math.random() * 4);
Cell next = neighbors.get(random);
while (next == null || next.isVisited()) {
random = (int) Math.floor(Math.random() * 4);
next = neighbors.get(random);
}
this.breakWall(random);
next.breakWall((random + 2) % 4);
return next;
} else return maze.backtrack();
}
public void breakWall(int wall) {
walls[wall] = false;
}
public void visit() {
visited = true;
}
public boolean isVisited() {
return visited;
}
}