※この記事は、筑波大学のゲーム制作サークルAmusementCreatorsアドベントカレンダーの4日目の記事です。
はじめに
タイトルにあるように、この記事ではグラフ理論における概念の一つである最小全域木というものを用いて、迷路を作成する方法について記述しています。なお、筆者はグラフ理論をしっかり学んでいるわけではないため、最小全域木について誤解している部分があるかもしれませんがその際は進んでご指摘ください。
迷路の定義
この記事においては、迷路をグラフ理論における木であると定義します。下図のように、基本的に迷路は頂点と辺の組み合わせで表現することができ、かつ連結で頂点数-1の辺を持つため迷路を木で表現することは妥当であるといえます $^{[1]}$ 。
図1 迷路と木の関係
全域木
ところで、木には二分木や平衡木などいくつかの種類が存在します。その中に、全域木というものが存在します。数学的な定義は省きますが、簡単に言えば全域木とは、「あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木」です$^{[2]}$(図2参照)。
特に、元となるグラフの辺に正の数の重みが設定されている場合、全域木を構成する辺の重みの総和を計算することができ、この重みの総和が最小となるように構成された全域木を最小全域木といいます。
図2 全域木
先の迷路の定義から、迷路を作成するというのはグラフの全域木を求めることと同値であることがわかります。
迷路生成アルゴリズム
前項で示したように、迷路作成は全域木を求めることと同値であるため、全域木を求めるアルゴリズムが組めれば、迷路作成アルゴリズムが組めることになります。
そこで、今回はクラスカル法を用いて全域木を生成することにします$^{[3]}$。ただし、簡単のため次の前提条件を設定します。
- 元となるグラフは二次元配列$A[H][W]$で、$A[y][x]$は頂点$v_{x + yW}$を表す
- 辺集合は配列$E$で、要素としてタプル$t(v_a, v_b, w)$を持つ
- タプル$t$は、頂点$v_a, v_b$間の重みが$w$という意味を表す
- $w \geq 0$を満たし、$w = 0$は頂点$v_a, v_b$が隣接していないことを表す
- $w$は上の条件を満たす乱数
アルゴリズムの詳細は次の通りです。
- $A$の各要素を要素数1の木の集合$T$として、集合族$F$に保存する
- $E$が空集合となるまで、$E$から最小の$w$をもつ$t$を取り出す
- $t$の頂点$v_a, v_b$がそれぞれ$F$の異なる集合$T_a, T_b$に属していれば、$T_a, T_b$を合成し一つの木とする
- 2に飛ぶ
このアルゴリズムを実行することで、最終的に$A$のすべての頂点から構成される一つの木が生成されます。これが$A$の全域木、すなわち迷路となります。
実行結果
上記のアルゴリズムを実装したプログラムを実行した際の結果を下に示します。
図3 クラスカル法により生成された迷路1
図4 クラスカル法により生成された迷路2
おわりに
迷路の生成方法の一つとして、全域木を用いたアルゴリズムを紹介しましたが、他の有名な迷路生成方法である棒倒し法や穴掘り法と比べ、比較的アルゴリズムが複雑だと思います。
ですが、迷路が生成できる論理的な理由が最もわかりやすいアルゴリズムだと思うので、迷路生成方法の一つとしてぜひ検討してみてください。
迷路生成で用いたコードを見たいという方は、こちらのmasterブランチのmain.cppを見てください。かなり見にくいコードですが、実装の参考になれば幸いです。
参考文献
[1] 木(数学) - Wikipedia
URL->https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6)
[2] 全域木 - Wikipedia
URL->https://ja.wikipedia.org/wiki/%E5%85%A8%E5%9F%9F%E6%9C%A8
[3] クラスカル法 - Wikipedia
URL->https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AB%E3%83%AB%E6%B3%95