java - 使用DFS回溯算法生成迷宫的问题

Question

我正在尝试实现 DFS 回溯算法，该算法涉及利用维基百科上找到的堆栈(而不是递归算法)。我试图生成一个由 0 和 1 组成的迷宫，其中 1 代表一堵墙，0 代表一条可用路径。对于迷宫中任何不是墙的给定空间，必须始终存在一条可以从任何其他非墙单元到达的有效路径。

我从一个大小为 maze[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]被墙壁包围，因此它是一个无法到达的区域。通过多次执行，这也非常一致。

如有任何帮助，我们将不胜感激。

Answer 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;
    }

}