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 が最終的にアクセス可能なセルが存在しない場所に到達すると、DFS は開始に戻ります。

これを修正して強制的に正しく動作させるにはどうすればよいですか?

ありがとう。

4

2 に答える 2

1

実際、生成したい迷路の目的が何であるかはまだわかりません。しかし、私はあなたにいくつかの提案があります：

  1. 迷路が単調にならないように、座標をランダム化して dfs アルゴリズムの開始点を 2 つまたは 3 つ作成します。

  2. アルゴリズムでは、各移動で 1 つのアクセス可能なセルのみを試行します。パスが一方通行のパスにならないように、各移動でよりアクセスしやすいセルにアクセスするようにしてください。(これは、アクセス可能なセルが見つからなかった後に dfs が開始に戻る理由でもあります)

上記の2番目のアイデアのコードは次のとおりです（上記のコードから編集）：

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 に答える