迷路の話

　このブログは、実は「迷路　自動生成」なんてキーワードで検索されることも多い。マジで。ついでに検索キーワードにはCとかC++とかC#とかが追加される場合もある。大学生だか専門学校生だか知らんがその程度のこと自力でできてくれと思わないでもない。
　まあ、ついでに迷路について色々考えたことをいくつか。

迷路の種類の分類

　迷路はその生成アルゴリズムによって使用目的が決まってくる。ごく原始的なアルゴリズムで生成したダンジョンは、確かに迷路ではあるがしかしファイナルファンタジーのようなゲームで使うには不適格だ。（ドラクエ１ならまだわかるが……）せいぜいが使えてローグタイプゲームであろう。
　ここでは、そういうアルゴリズムと目的を対にしてまとめてみる。

棒倒し法による迷路

参考:http://uk.geocities.com/sugar777pe/arugo/maze1.html
　外壁を作成し、その内部に格子状に基準点を並べる。基準点から一定のルールに従ってランダムな方向に棒を倒す＝壁を伸ばす方法。
　棒倒し法による迷路を作るさい、基準点の取り得る行動に「棒を倒さない」を追加すると、正解路が複数の迷路ができる可能性が生じる。その比率を高めれば高めるほど、壁が少なくなり、迷路と言うよりも障害物と呼べるようなものが出来上がる。こう言った迷路は、「ボンバーマン」「ドルアーガの塔」などで使えるだろう。ドラクエ系でも、廃墟を表現するのに使える。
※プログラム的に最も簡単で最もメモリーを食わない。

穴掘り法による迷路

参考:穴掘り法
　穴掘り法による迷路は、機械的な完全さが特徴であり、こういう迷路の用途はかつて流行った「機械鼠による迷路脱出コンテスト」みたいなものに限られる。人間に解かせる場合は、俯瞰にするか、3Dダンジョンにしてウィザードリィ的な苦行めいた楽しみのどちらかだろう。ただし、3Dダンジョンにした場合、通路の形に人間的な癖がないため人間が記憶するのは至難の業になってしまう。
※穴掘り法をゲーム的に応用する：コブラで、ダンジョンの正解路がナスカの地上絵の「鳥」と同じ形、と言うギミックがあった。正解路をあらかじめ描いておいて、そこから穴掘り法によって拡張すれば、そのようなマップが作成できる。
※プログラム的にはスタックかそれに類する機構を必要とするため、ちょっと慣れた人間向け。

壁伸ばし法による迷路

参考:http://www.saoyagi.net/piece/maze.html
　外壁を作り、その外壁の一点以上から、木が生長するように壁を伸ばしていく方法。木は他の木や外壁とは決して交わらないようにすれば、正解路が一本の迷路がする。
　たとえば、上辺中央にスタート地点、下辺中央にゴール地点がある方形の外壁の場合、右辺と左辺にそれぞれ1ないし2の木の「根」を設定するといい。
　壁伸ばし法による迷路の特徴は穴掘り法とほぼ重なるが、大まかな正解路の形を指定できる分、こちらの方が使い勝手がいいかも知れない。たとえば、上辺中央左側にスタート地点、右側にゴール地点があったとすると、その中間地点に「根」を設定すれば、そこから壁が延びるため正解路を長くすることができる。ドラクエでよく使われた手法で、ゴール地点がスタート地点から見えているにも関わらず、そこに至るまでは長々と移動しなければならない構造がこれである。ゴール地点を宝箱に置き換えてもこれは成立する。
※プログラム的にはスタックかそれに類する機構を複数必要とするため、さらに慣れた人間向け。

配置法による迷路

参考:http://racanhack.sourceforge.jp/rhdoc/codemaze.html
　ローグタイプの、いかにもダンジョン然とした部屋と通路から成る迷路を作る方法。もちろん用途はローグタイプのゲームに適用できる。FF的なゲームにも使える。

迷路表現

　迷路はキャラクターが存在できないところを「壁」、そうでないところを「通路」と呼んで来た訳だが、グラフィックを変えることでダンジョンを様々な状況に見せることができる。ドラクエシリーズでは「壁」を「床のないところ」、「通路」を「ロープ」にして綱渡りを演出したりもした。

まとめ

　迷路は目的を考えてアルゴリズムを選ぼう、と言う当たり前の話。
　部屋を漁っていたらウォーロック誌が発掘されたので、後日ウォーロック誌に掲載されたファイティングファンタジー用ダンジョン生成システムをレポートしてみたい。