サカトマのゲーム設計ノート
「じじまごRPGmini」では，図AのようなMAPが使われています．
図A．じじまごRPGminiのMAP例 ※実際に存在するMAPだとは限りません
このようなものを，数学では「部分格子グラフ」とかいうんですけれども．
当ゲームでは，このMAPは定型であり，常に同じ形をとっています．
ここで，きっとローグライクゲームが好きな方は思うでしょう．
「このMAPをランダムに作れないのか」と．
じゃあ，作る方法を考えてみましょう．
図B．MAPの初期状態
ここでは，図Bのような状態から図AのようなMAPを作る方法を紹介します．
まず，図AのMAPのようなものを「部分矩形格子グラフ」といいます．
そもそもグラフっていうのは，図Cのような「点と線の集合」のことね．
図C．一般的なグラフ
んで，矩形格子グラフっていうのは，図Dのように方眼のように張られたグラフね．
図D．矩形格子グラフ
「矩形」っていうのは，点が長方形のように並んでいるということ．
（矩形じゃない格子グラフもあるのでね．）
さっき「点と線の集合」って書いたけれど，数学用語を使うと，
点のことを「頂点」，線のことを「辺」というのが一般的．
で，矩形格子グラフからいくつか辺を取り除いたグラフが部分矩形格子だ．
つまり，さっきのMAPのこと．
図A-1．部分矩形格子グラフ
ところで，せっかくMAPを作るんだし，どの頂点にも行けるようにしたいよね？
どういうことかって，図Eのようなものは作りたくないということ．
図E．非連結なグラフ
いくつかの辺をたどることで，どの頂点にも行けるようなグラフを連結なグラフといって，
図Eのように，行けない頂点があるグラフを非連結なグラフという．
ここでは連結なものを作っていきましょう．
まず，初期状態を用意します．辺が１つもない状態です．
図B-1．MAPの初期状態
ランダムに点を1個選びます．それをpとします(図F)．
図F．pを選ぶ
pに，「チェック」を入れます（図Gでは黄色にしました）．
図G．pを「チェック」する
で，pの上下左右に存在する頂点からランダムに1つ選びます．それをqとします．
pとqの間に辺を追加しましょう（図H）．
図H．qを決定して辺を加える
そうしたら，qをpと置き換えます．過去のpは忘れましょう(図I)．
図I．pを更新
あとはこの繰り返しです．
pに「チェック」を入れ，qを選び，辺を加えます(図J)．
ここでポイントですが，qは，直前に選んでいたpを選ばないようにすると効率が良いですよ．
図J．チェックして辺をランダムに追加
6回目の繰り返しで，図Kまで来たとします．
図K．6回目の繰り返し
おっと，qには「チェック」が入っていますね．
そしたら，いったんここで繰り返しを中止します．
しかし，これではだめですね．だって連結じゃないもん．
じゃあ，どうするか．ここまでで，どの辺もつながっていない頂点は
未チェックであるはずです．
そこで，未チェックの点をランダムに選んで，pとしましょう．
すると，さっきの繰り返しをもう一度行うことができます．図Lのような感じになります．
図L．いったん中止
この作業を繰り返し繰り返し，「どの頂点にもチェックが入った状態」になれば，完成です！
図A-2．完成
アルゴリズムは，こんな感じです．
while (未チェックの頂点が存在する):
p = ランダムな未チェックの頂点
while:
pをチェックする
pの上下左右に存在する頂点からランダムにqを選ぶ
pとqを辺でつなげる
if (qがチェック済) ==> break while
q = p
end of while
end of while
辺の数が足りないなぁ，と思ったときは，辺のないところに確率で追加しちゃってください．
25%くらいで充分だと思います．
実は，この方法だけでは図Mのような「非連結な」グラフができてしまうおそれがあります．
どうにかして，この問題を解決してください．
（ヒント：チェックをいったんリセットし，頂点を1個決めて，そこから行ける頂点をあぶりだしてみよう．）
図M．出力されうる非連結なグラフ
広告