[解決済み] 迷路の生成に適したアルゴリズムとは？[クローズド］

質問

例えば、N×Mのグリッドに、1本の道と行き止まりがあり、でも見た目は正しい（つまり、小さな行き止まりなどがあまりなく、誰かが手作業で作ったような）単純な迷路が欲しいとします。このような方法をご存じですか？

解決方法は？

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

Recursive backtracker: 後述の再帰的バックトラッカーの解法と多少関係があり、Mazeの大きさまで積み上げる必要があります。刻むときは、できるだけ貪欲に、現在のマスの隣に未作成の部分があれば、そこに刻みます。新しいマスに移動するたびに、前のマスをスタックに押し込んでください。現在のマスの隣に未作成のマスがない場合、スタックを前の位置にポップします。スタックからすべてを取り出したら、「迷路」は終了です。このアルゴリズムでは、行き止まりは少ないが長く、通常は非常に長く曲がりくねった解答となり、できるだけ高いquot;river"係数を持つ迷路が得られます。プリムのアルゴリズムの方が少し速いですが、かなり高速に実行できます。再帰的バックトラックは壁の加算器としては機能しません。なぜなら、そうすると、解答経路が外縁に沿うようになり、迷路の内部全体が1本の茎で境界線に接続されてしまう傾向があるからです。

10％しか行き止まりを作らない

は、その方法で生成された迷路の例である。