5

我只是想使用最简单的算法生成一些迷宫，但我所有的迷宫都如下所示：

我的迷宫

这是一段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 最终到达没有可访问单元格的地方时，它只是重新开始。

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

谢谢。

4

2 回答 2

1

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

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

  2. 在您的算法中，您每次移动只尝试 1 个可访问的单元格。尝试在每次移动中访问更易于访问的单元格，这样路径就不会是一条完成的单向路径。（这也是您的 dfs 在找不到可访问的单元格后重新开始的原因）

这是我上面第二个想法的代码（从上面的代码编辑）：

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

希望这会有所帮助；）

于 2013-07-02T03:59:46.340 回答
1

每当你走到死胡同时，你似乎只是在跳伞并退出。相反，您应该回溯，直到找到仍然具有可访问邻居的单元格，然后从那里继续算法。执行此操作的常用方法是使用堆栈：在访问项目时推送项目，弹出以回溯。像这样的东西：

if (nextCell == null) { // You've reached a dead-end
  if (stack.empty()) // base-case, bail out
    return;

  dfs(stack.pop(), visited); // backtrack
} else {
  stack.push(nextCell);

  visited[start.y][start.x] = true;
  borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true;
  dfs(nextCell, visited);
}
于 2013-07-02T05:29:34.680 回答