70

N x Mグリッド上に、1つのパスがあり、行き止まりがたくさんある単純な迷路が必要だとしますが、それは「正しい」ように見えます（つまり、小さな行き止まりがあまり多くなく、誰かが手作業で作ったように見えます。 ）。これを行うための既知の方法はありますか？

4

9 に答える 9

63

「完璧な」迷路を生成するための 11 の古典的なアルゴリズムがあることが判明しました。迷路は、解が 1 つしかない場合に最適です。ここに、各アルゴリズムへのいくつかのリンクを、私の好みの大まかな順序で示します。

  1. クラスカルの
  2. プリムズ
  3. 再帰バックトラッカー
  4. オルダス ブローダー
  5. 成長する木
  6. ハント・アンド・キル
  7. ウィルソンズ
  8. エラーズ
  9. 再帰除算 (予測可能)
  10. サイドワインダー (予測可能)
  11. 二分木 (欠陥あり)

詳細については、GitHub のmazelibを確認してください。これは、すべての標準的な迷路生成/解決アルゴリズムを実装する Python ライブラリです。

于 2014-05-15T15:00:07.393 に答える
44

http://www.astrolog.org/labyrnth/algrithm.htmから

再帰的バックトラッカー：これは、以下で説明する再帰的バックトラッカー解決方法にいくらか関連しており、迷路のサイズまでスタックする必要があります。彫るときは、できるだけ貪欲になり、現在のセルの隣にある場合は、常に未完成のセクションに彫ります。新しいセルに移動するたびに、前のセルをスタックにプッシュします。現在の位置の横に未作成のセルがない場合は、スタックを前の位置にポップします。迷路は、スタックからすべてをポップすると完了します。このアルゴリズムにより、「川」係数が可能な限り高くなり、行き止まりは少なくなりますが、通常は非常に長くてねじれたソリューションの迷路が生成されます。プリムのアルゴリズムは少し高速ですが、非常に高速に実行されます。再帰的なバックトラックは壁の追加機能としては機能しませんが、

行き止まりはわずか10％です

その方法で生成された迷路の例です。

于 2008-09-01T22:04:39.747 に答える
28

非常に簡単な解決策は、グラフのエッジにランダムな重みを割り当て、Kruskal のアルゴリズムを適用して最小スパニング ツリーを見つけることです。

迷路生成アルゴリズムに関する最高の議論: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (数日前に HN で行われました)。

于 2011-09-30T14:31:57.810 に答える
5

不思議なことに、「正規の」ルールを少し変更し、ランダムな構成から始めることで、コンウェイのライフゲームはかなり素敵な迷路を生成しているようです！

（正確なルールは覚えていませんが、これは非常に単純な変更であり、細胞の集団を「高密度化」する傾向があります...）

于 2008-09-01T22:00:57.620 に答える
3

再帰バックトラッキングは、実装が最も簡単なアルゴリズムです。

Java の実装は次のとおりです。

ここで、 Cellは 2D グリッド内のセルを表すクラスであり、cellsはCellオブジェクトの 2D 配列です。セルには、セルの両側に壁があるかどうかを示すboolean 変数top、bottom、left、right 、セルを横断したかどうかを確認する boolean 変数、およびグリッド内の位置を示す2 つの整数変数rowとcolがあります。

Cell current = cells[0][0] , next;
    current.visited=true;
    do{
        next = getNeighbour(current);
        if(next!=null){
            removeWall(current , next);
            st.push(current);
            current = next;
            current.visited = true;
        }
        else {
            current = st.pop();
        }
    }
    while (!st.empty());


    private Cell getNeighbour(Cell cell){
    ArrayList<Cell> ara = new ArrayList<>();
    if(cell.col>0 && !cells[cell.col-1][cell.row].visited)
         ara.add(cells[cell.col-1][cell.row]);

    if(cell.row>0 && !cells[cell.col][cell.row-1].visited)
         ara.add(cells[cell.col][cell.row-1]);

    if(cell.col<col-1 && !cells[cell.col+1][cell.row].visited)
         ara.add(cells[cell.col+1][cell.row]);
    if(cell.row<row-1 && !cells[cell.col][cell.row+1].visited)
         ara.add(cells[cell.col][cell.row+1]); 


    if(ara.size()>0){
        return ara.get(new Random().nextInt(ara.size()));
    }else{
        return null;
    }
}
private void removeWall(Cell curr , Cell nxt){
    if((curr.col == nxt.col) && (curr.row == nxt.row+1)){/// top
        curr.top=nxt.botttom=false;
    }
    if(curr.col==nxt.col && curr.row == nxt.row-1){///bottom
        curr.botttom = nxt.top = false;
    }
    if(curr.col==nxt.col-1 && curr.row==nxt.row ){///right
        curr.right = nxt.left = false;
    }
    if(curr.col == nxt.col+1 && curr.row == nxt.row){///left
        curr.left = nxt.right = false;
    }
}
于 2020-05-07T20:08:00.227 に答える
2

迷路を生成する方法の 1 つは、Prim のアルゴリズムのランダム化バージョンです。

壁でいっぱいのグリッドから始めます。セルを選択し、迷路の一部としてマークします。セルの壁を壁リストに追加します。リストに壁がある場合:

リストからランダムな壁を選択します。反対側のセルがまだ迷路に入っていない場合:

(i) 壁を通路にし、反対側のセルを迷路の一部としてマークします。

(ii) セルの隣接する壁を壁リストに追加します。

反対側のセルが既に迷路内にある場合は、リストから壁を削除します。

于 2014-06-03T11:45:40.600 に答える