サカトマのゲーム設計ノート
ランダムな部分矩形格子グラフ型MAPの作り方 その２
「じじまごRPGmini」では，図AのようなMAPが使われています．
図A．じじまごRPGminiのMAP例 ※実際に存在するMAPだとは限りません
「このMAPをランダムに作れないのか」というお話を，こちらにてしましたね．
その方法だと，実は「演習問題」に当たる部分の実装が難しくてですね……．
ということで，もう１つ．比較的簡単に実装できそうなものを提案します．
図B．MAPの初期状態
前回と同じく，図Bのような状態から図AのようなMAPを作る方法を紹介します．
まず，図AのMAPのようなものを「部分矩形格子グラフ」といいます．
グラフっていうのは，図Cのような「点と線の集合」のことだったね．
数学用語を使うと，点のことを「頂点」，線のことを「辺」というのが一般的．
図C．一般的なグラフ
作りたいグラフの条件として，図Dのように離れているものじゃ嫌だということ．
図D．非連結なグラフ
いくつかの辺をたどることで，どの頂点にも行けるようなグラフを連結なグラフといって，
図Dのように，行けない頂点があるグラフを非連結なグラフという．
ここでは連結なものを作っていきましょう，という流れでした．
結論を言うと，今回紹介するのは
「ランダムな重みをつけたグラフの最小木から生成する」という方法です．
ここからは数学用語の定義です．ちょっとお付き合いください．
「連結」で「ループを含まない」グラフを木といいます．
図E．ループがあるから木ではない
図F．連結でループがないから，これは木
さらに，グラフGに対して，それに含まれる部分的な木を部分木といいます．
つまり，部分木に含まれる頂点と辺は，すべて元のグラフに入っているということね．
（図Fは図Cの部分木となります．）
そして，部分木TがGのすべての頂点を持つとき，全域木といいます．
（図Fは図Cの頂点すべてを含むので，全域木となります．）
なぜ全域木を説明したかったかというと，ですね．
MAPを作るということは，
「矩形格子グラフ（図G）の全域木を得ること」として認識すればよいからです．
図G．矩形格子グラフ
ま，木だとループがなくてつまらないので，実際には数本付け加えるんですけれどね．
とりあえず全域木を作るということにします．
さて，そんな全域木をどのように作るか，ですがね．
その前に，元のグラフの各辺にランダムに「重み」をつけます．
図Gのようになったとしましょう．
図G．矩形格子グラフの辺に重みをつけたよ
このグラフの全域木を見つければよいのですが，「重みが最小となる」木を見つけることにします．
その木のことを，元のグラフの「最小木」といいます．
整理しましょう．
１．矩形格子グラフ（図G）からランダムに全域木をとることが目標．
２．ランダムに全域木をとるため，各辺にランダムに重みをつけることで，
重み最小の木を求めることにする．
ということです．
※全域木を作るなら「幅優先探索」を利用してもいいと思ったんだけれど，
生成されるグラフが偏ってしまうんだな……．
最小木を求める方法は，ググればいくつか出てきます．
ここではR.G.Primさんに考案された方法を紹介します．
まず，矩形格子グラフを用意します．各辺にランダムに重みをつけます（図G-1）．
また，すべての頂点の色を「白」，辺の色を「黒」とします．
図G-1．矩形格子グラフの辺に重みをつけたよ
ランダムに点を1個選びます．それを「赤く」します（図H）．
図H．ランダムに1個選んで赤くする
辺のうち，「辺の両端の色が異なるもの」を候補にあげます
（図I 赤丸つきの重みを持つ辺）．（※）
図I．ランダムに1個選んで赤くする
それらのうち，「辺の重みが最小のもの」を「赤く」します．
そして，その辺の両端の頂点をどちらも「赤く」します．（図J）
図J．重み最小の辺とその両端を赤くする
そしたら，（※）に戻ってループです．つまり，
１．「辺の両端の色が異なるもの」を候補にあげ
２．「辺の重みが最小のもの」を「赤く」し
３．その辺の両端の頂点をどちらも「赤く」するんです．
図K．2回目の繰り返し
図L．3回目の繰り返し
図M．4回目の繰り返し
この作業を繰り返し繰り返し，「どの頂点も赤くなった状態」になれば，
そのときの赤い辺が，最小木を構成しています！
以上をまとめると，アルゴリズムはこんな感じです．
for all edge(辺):
重みをランダムにつける
end of for
ランダムに1点を赤くする
while (赤くない頂点が存在する):
辺 e = (両端の頂点が異なる色である辺のうち，重みが最小のもの)
e とその両端を赤くする
end of while
辺の数が足りないなぁ，と思ったときは，辺のないところに確率で追加しちゃってください．
25%くらいで充分だと思います．
当然ですが，計算機上では文字通りに赤く塗ることはできません．
フラグなどをつけましょう．
１．最小木を求める方法として最も有名なのは「クラスカル法」というものですが，
今回，この方法を採用するのは良くないと思います．なぜでしょう？
（ヒント：「重みをランダムにつけている」がネック）
２．グラフが木であるとき，「接続する辺が１つだけ」の点を取り除くと，それも木です．なぜでしょう？
３．グラフが木であるとき，その辺の数は点の数よりも１小さいです．なぜでしょう？
（ヒント：「数学的帰納法」を使う）＝＝＞つまり，繰り返しの回数はたかだか「頂点の数-1」となります．
広告