不思議のダンジョン（ローグライク）の自動生成（AS3版）
＝追記＝
画像埋め込み版を追加。
＝状況＝
とりあえず、パラメータ調整とバグつぶしをして、「AS3で不思議のダンジョン的な迷路を生成する」というところまではできた。はず。
＝迷路作成の解説＝
Racanhack コード解説をもとに作成。アルゴリズムは読んだけど、コードは読んでないので、実装は異なっているかもしれない。
基本方針
最初は全体を一つの領域とみなし、それを分割していって、複数の領域にする。その領域ごとに内部に部屋を作り、「どこで分割したか」をもとに部屋をつないでいく。
実装
コードは「Room.as」にまとめてある。すでに「床と壁を配列で指定したら、グラフィックなどは自動的に生成される」ところまではできているので、「最初は全部"壁"で埋めておいて、部屋と通路だけ"床"を置く」という処理だけ入れれば良い状態。
おおまかな流れはRoomのReset()で行っていて、以下のような感じ。
- 「全体を現す領域(Room)」を一つ作り（Reset()内のInit部分）、
- 分割する関数「Divide」で分割して（Reset()内のDivide部分）、
- それによってできた複数のRoom内に床を敷き（Reset()内のRoom -> ...の部分）、
- そして通路を作って完成（Reset()内のPath部分）。
領域は、上下左右の端をm_Boundとして持っている。分割の際は、これをコピーして、境界部分だけ設定しなおせば良い。また、m_Boundは通路を引く際の軸にもなっている。（分割した両方のRoomから、この境界線に垂線をひき、その垂線をつないで通路を作る感じ）
実際に床を敷く範囲はm_Walkableとして保持。注意すべきは「領域の端から必ず一定マス以上離すこと」。そうしないと、通路を作るときに通路と部屋が隣接してしまい、部屋がいびつな形に削られてしまう。
Room同士はリスト構造のようにつながっている。このリスト構造は分割時に作成される。たとえば「A」という部屋を分割して「A」と「B」を作る場合、「A→B」というような親と子の関係ができる（実際には例外もあるが）。４つの分割方向それぞれに子を持つことができ、先ほどの例では「Aの左の子はB」というような感じになる。複数の子を持つという意味では木構造と呼んだ方が良い（実際、最初に作る部屋(m_Root)を根とする木構造になっている）。
このリスト構造がそのまま「どの部屋とどの部屋がつながっているか」を表し、「根」から再帰的に「葉」の方に向かうことで通路を作成することができる（Room2Room_Recursive()の処理）。
＝その他＝
どうにも、C++のクセで配列などの巡回に「for構文」を使ってしまう。AS3だと、たしかもっと別に良い方法があったはずなんだけど。（eachとか）
解説はできればコードに埋め込みたいんだけども。「全体の解説」はどこに書けばよいかわからん。
今回わかった「ゲームデザインに使えそうなネタ」としては、「部屋は木構造でできている」ということ。例えば、「根」をスタート地点にすることで、「この葉にいたるまでの経路」が確定できるため、「ここでコレしてゲートを開かないと、階段まで行けない」というギミックが仕込めそう。
不思議迷宮録シレン-絶望の谷-にあるような、「モンスターが横穴に気付かない」というのは、このアルゴリズムのような「分割時のリンクで作られた通路」じゃないからなんだろうな。分割時にできた通路なら生成時に記録しておけるのでモンスターの移動経路として使いやすいけど、あとから作られた通路は通路としての認識が困難。
はてダに埋め込むとグラフィックが表示されない問題は、Loaderまわりをどうにかすれば良いような気がするので、そっちも調べたいところ。
