クラスカルのアルゴリズム迷路ジェネレータ

クラスカルのアルゴリズムは、迷路生成に応用できる最小全域木アルゴリズムです。特に完全迷路の作成に効果的です。クラスカルのアルゴリズムの代替として、同じく最小全域木アルゴリズムであるプリムのアルゴリズムがありますが、どちらも同じ迷路を生成すること、そしてクラスカルのアルゴリズムの方が実行速度が速いことから、私はプリムのアルゴリズムを実装していません。

完全な迷路とは、迷路のどの地点からどの地点へも、ちょうど1本の道がある迷路のことである。つまり、堂々巡りにはならないが、行き止まりにはしばしば遭遇し、引き返してくることを余儀なくされる。

ここで生成される迷路マップには、スタートとゴールの位置がないデフォルトバージョンも含まれています。迷路のどの地点からでも、他のどの地点からでも解があります。インスピレーションを得たい場合は、スタートとゴールの推奨位置を有効にし、その2つの間の解を見ることもできます。

クラスカルのアルゴリズムについて

クラスカルのアルゴリズムは、アメリカの数学者、統計学者、コンピュータ科学者であるジョセフ・バーナード・クラスカル・ジュニアによって考案されました。彼は1956年に論文「グラフの最短全域木と巡回セールスマン問題」の中でこのアルゴリズムを初めて説明しました。

このアルゴリズムは、グラフの最小全域木 (MST) を見つけるように設計されており、サイクルを回避しながら、すべての頂点が可能な限り最小の合計エッジ重みで接続されていることを保証します。

クラスカルのアルゴリズムが迷路生成にどのように機能するか

ステップ1: 初期化

• 迷路内の各セルを個別のセット (固有のコンポーネント) として扱います。
• 隣接するセル間のすべての壁を潜在的なエッジとしてリストします。

ステップ2：壁を分類する

• 壁をシャッフルするかランダムに並べます。真のクラスカルアルゴリズムとして実装する場合は、壁をランダムに並べます（迷路生成には重みは必要ないため）。

ステップ3：壁を処理する

• シャッフルされた壁を反復処理します。
• 壁で区切られた 2 つのセルが異なるセットに属している場合 (つまり、迷路内でまだ接続されていない場合)、壁を削除してセットを結合します。
• すでに同じセット内にある場合は、壁をスキップします (サイクルを回避するため)。

ステップ4: 完了するまで続ける

• すべてのセルが接続されて単一のスパニング ツリーが形成されるまで、このプロセスを繰り返します。
• 最後に、すべてのセルはループや分離されたセクションなしで他のセルに接続されます。

クラスカルのアルゴリズムは集合のマージに依存しているため、Union-Findアルゴリズムを使用することで最適化できます。Union-Findアルゴリズムは、迷路生成時に連結されたセルを効率的に追跡する方法を提供します。Union-FindアルゴリズムのPHP実装は、こちらでご覧いただけます：リンク

さらに読む

この投稿が気に入った場合は、次の提案も気に入るかもしれません:

• エラーのアルゴリズム迷路ジェネレーター
• 再帰バックトラッカー迷路ジェネレーター
• 成長木アルゴリズム迷路ジェネレータ