java - 使用 DFS 生成迷宫失败，我不知道为什么

Question

我只是想用最简单的算法生成一些迷宫，但我所有的迷宫看起来都像下面这样:

这是一段Java代码(一个whatVisit函数是正确的，不要看它):

private void dfs(Point start, boolean[][] visited) {
    Point nextCell = whatVisit(start, visited);
    if(nextCell == null)        // if there's nothing to visit
        return;

    // mark current cell as visited
    visited[start.y][start.x] = true;
    // destroy the wall between current cell and the new one
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true;

    // start a new search from found cell
    dfs(nextCell, visited);
}

private Point whatVisit(Point p, boolean[][] visited) {
    Vector<Point>cells = new Vector<Point>();   // to store acessible cells

    // lookaround
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2])
        cells.add(new Point(p.x - 2, p.y));
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2])
        cells.add(new Point(p.x + 2, p.y));
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x])
        cells.add(new Point(p.x, p.y - 2));
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x])
        cells.add(new Point(p.x, p.y + 2));

    // instead of Random
    Collections.shuffle(cells);

    // returns null if there are no acessible cells around
    if(cells.size() > 0)
        return cells.get(0);
    else return null;
}

而且我知道为什么它不起作用!当 DFS 最终到达没有可访问单元格的地方时，它只是返回开始。

如何解决这个问题并强制正常工作？

谢谢。

Answer 1

其实我还是不明白你要生成的迷宫的目的是什么。但我有一些建议给你:

1. 通过随机化坐标创建 2 或 3 个 dfs 算法的起点，这样迷宫就不会单调。

2. 在您的算法中，您每次移动只尝试 1 个可访问的单元格。尝试在每次移动中访问更易于访问的单元格，以便路径不会是单向路径来完成。 (这也是为什么你的dfs在找不到可访问的cell后又回到start的原因)

这是我上面第二个想法的代码(根据你上面的代码编辑):

private void dfs(Point start, boolean[][] visited) {
    ArrayList<Point> nextCell = whatVisit(start, visited);
    if(nextCell == null)        // if there's nothing to visit
        return;

    // mark current cell as visited
    visited[start.y][start.x] = true;

    for (Point next : nextCell) // try new accessible cells
    {
        // destroy the wall between current cell and the new one
        borders[(start.y + next.y)/2][(start.x + next.x)/2] = true;    
        // start a new search from found cell
        dfs(next, visited);
    }
}

private ArrayList<Point> whatVisit(Point p, boolean[][] visited) {
    Vector<Point>cells = new Vector<Point>();   // to store acessible cells

    // lookaround
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2])
        cells.add(new Point(p.x - 2, p.y));
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2])
        cells.add(new Point(p.x + 2, p.y));
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x])
        cells.add(new Point(p.x, p.y - 2));
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x])
        cells.add(new Point(p.x, p.y + 2));

    // returns null if there are no accessible cells around
    if(cells.size() > 0)
    {
        ArrayList<Point> tmp = new ArrayList<Point>();
        // randomize how many cell that will be returned
        int x = (int)(Math.random()*cells.size()) + 1;
        if (x > cells.size())
            x = cells.size();
        Collections.shuffle(cells);
        for (int i = 0; i < x; i++)
            tmp.add(cells.get(i));
        return tmp;
    }
    else return null;
}

希望这会有所帮助；)