ダンジョン等を毎回違うマップにするために迷路を自動生成するプログラムを作ってみました。
迷路の自動生成アルゴリズムは何種類かありますが、その中で「壁伸ばし法」を採用しました。
理由は大体以下の通りです。
・縦横共に5マス以上の奇数であれば大きさは自由に設定可能
・複雑なものから単純なものまで多彩な迷路が出来る
・生成前に壁で囲って中の起点を取り除くと小部屋にすることが可能
※起点とは壁を伸ばし始める点
・生成前に全体マップを壁で分割しておくと区画分けが可能
等々、使い勝手が非常に良さそうなんです。
他のアルゴリズムでも実現は可能なのかも知れませんが「壁伸ばし法」では簡単な改修で実現可能です。
ソースはGoogleドキュメントに載せてあります。
壁伸ばし法の解説
壁伸ばし法による迷路生成は以下の手順で行います。
1.迷路のサイズを決定します。
迷路の縦幅と横幅を決めますが、この縦幅と横幅には外周の壁も含まれます。
例えば、縦5マス×横5マスと設定すると上下左右に壁が作られるので中身は縦3マス×横3マスになります。
また縦幅と横幅には5マス以上の奇数という制限があるので、その範囲で設定します。
2.全体の座標を管理する迷路マップリストを作成し、外周の座標に「壁」を、その他に「通路」を設定します。
3.起点リストを作成し、左上の座標を(y,x)=(0,0)としてyとxが共に偶数の座標を起点リストに登録します。
例：縦9マス×横11マスの場合、以下の青い四角の座標を全て起点リストに登録
※上記の例では(2,2),(4,2),(6,2),(2,4),(4,4),(6,4),(2,6),(4,6),(6,6),(2,8),(4,8),(6,8)の12か所を登録
4.起点リストのデータをシャッフルして順番をランダムに入れ替えます。
※3の例を使用してシャッフルすると…
ランダムなので実際はどうなるかは分からないが、例えば上記の様に3で使用したデータ
(2,2),(4,2),(6,2),(2,4),(4,4),(6,4),(2,6),(4,6),(6,6),(2,8),(4,8),(6,8)
が、以下の様な感じに順が入れ替わる
↓↓↓
(2,8),(6,6),(4,8),(4,6),(6,2),(6,4),(4,2),(2,6),(2,4),(2,2),(4,4),(6,8)
5.シャッフル後の起点リスト内の起点をfor文で先頭から順に抜き出して、その起点の座標から壁作りを行います。これを起点リスト内の全ての起点に行います。但し、壁の延長中に現在の起点から伸ばしている壁に繋がらない様にします。もし延長中の壁に囲まれて壁を伸ばせなくなった場合は、延長中の壁を全て破棄して最初の座標から再度壁作りを行います。
※延長不可になった時の延長中の壁が作り直しの対象で、既に壁として確定している箇所を作り直す必要はない
壁作りの詳細
5-1.起点の座標が既に壁の場合は何もせずに次の起点を抜き出します。
5-2.起点の座標を通常の壁とは別の「作成中の壁」として迷路マップリストに設定します。
5-3.延長可能リストを作成します。
5-4.起点の座標から上下左右に2マス離れた座標をチェックし、「作成中の壁」でない場合は延長可能リストに追加します。
※上下左右が全て「作成中の壁」の場合は「作成中の壁」を全て「通路」に戻して5-2から作り直します。
5-5.延長可能リストの中からランダムにひとつ選択して壁を延長する方向を決定します。
5-6.決定された方向に1マス「作成中の壁」を設定します。
5-7.決定された方向の2マス目の設定状況に応じて以下のどちらかの処理に分岐します。
5-7-1.「壁」の場合は「作成中の壁」を全て「壁」に設定して、この起点からの延長を終了して次の起点を抜き出します。
5-7-2.「通路」の場合はこの座標を起点として5-2から繰り返します。
この5-1～5-7の処理を起点リストの全ての起点に行うと迷路が完成します。
4でシャッフルした起点リストを使用して壁作りの具体的な進行例を挙げます。
※少々長いです
起点リスト：(2,8),(6,6),(4,8),(4,6),(6,2),(6,4),(4,2),(2,6),(2,4),(2,2),(4,4),(6,8)
※0～11の計12か所
1.起点リスト(0)の(2,8)を起点とし、「作成中の壁」(緑のマス)とする。
2.上下左右の2マス先を調査し、「作成中の壁」でない場合は延長可能リストに追加する。
※(0,8),(4,8),(2,6),(2,10)を延長可能リストに追加
3.延長可能リストからランダムで延長方向を選択する。
※(4,8)が選択されたことにする
4.選択した方向1マス(3,8)を「作成中の壁」にする。
5.延長先(4,8)が「通路」なので、(4,8)を起点とし「作成中の壁」とする。
6.上下左右の2マス先を調査し、「作成中の壁」でない場合は延長可能リストに追加する。
※(6,8),(4,6),(4,10)を延長可能リストに追加
7.延長可能リストからランダムで延長方向を選択する。
※(4,10)が選択されたことにする
8.選択した方向1マス(4,9)を「作成中の壁」にする。
9.延長先(4,10)が「壁」なので、「作成中の壁」を全て「壁」にする。
10.起点リスト(1)の(6,6)を起点とし、「作成中の壁」とする。
11.同様の流れで矢印の順に「壁」まで進む。
12.延長先(6,10)が「壁」なので、「作成中の壁」を全て「壁」にする。
13.起点リスト(2)の(4,8)は既に「壁」なので、何もしない。
14.起点リスト(3)の(4,6)を起点とし、「作成中の壁」とする。
15.同様の流れで矢印の順に進むと、「作成中の壁」に囲まれて延長不可になる。
16.今回作成した「作成中の壁」を全て「通路」に戻し、再度(4,6)を「作成中の壁」とする。
17.(4,6)から作り直して、矢印の順に「壁」まで進む。
18.「作成中の壁」を全て「壁」にする。
19.起点リスト(4),(5),(6)はいずれも既に「壁」なので、何もしない。
20.起点リスト(7)の(2,6)を起点とし、「作成中の壁」とする。
21.矢印の順に「壁」まで進む。
22.「作成中の壁」を全て「壁」にする。
23.起点リスト(8),(9),(10),(11)はいずれも既に「壁」なので、何もしない。
24.全ての起点を処理し終えたので迷路が完成！
この様な流れで迷路が作成されます。
Googleドキュメントに載せてあるソースには迷路の再作成が簡単に行える様に、右クリックで新規の迷路を作る様にしてあります。
以上です。