ダンジョンのランダム生成のアルゴリズム

gistfile1.txt

1. ダンジョンを生成する領域をランダムにNxNの領域に分ける（これはx、y軸それぞれで、N-1の区分座標を選ぶことで行う）ただし、サイズが3x3以上になるようにする
2. それぞれの領域に収まる範囲で部屋を作る
   2-1. 部屋の左上の座標を選ぶ
   2-2. 領域に収まる範囲で幅と高さを選択する（部屋は3x3以上のサイズになるようにする）

3. NxNの部屋ができる。これを左上から右＝＞下の順でA1, A2, ..., A9とよぶ
4. NxNつの部屋を通路でつなげる
   4-1. それぞれの部屋から以下の方向にジグザグな通路を引く
    A1:左上隅 => 右下（右壁）
    A2:上端 => 右下（右壁） 左下（下壁）
    A3:右上隅 左下（下壁）
    A4:左端 右上（上壁）、右下（右壁）
    A5:中央 => 右上（上壁）、右下（右壁）、左上（左壁）、左下（下壁）
    A6:右端 => 左上（左壁）、左下（下壁）
    A7:左下隅 => 右上（上壁）
    A8:下端 => 右上（上壁）、左上（左壁）
    A9:右下隅 => 左上（左壁）
   4-2. 通路の引き方は以下の通り
    4-2-1. 例：右下
     以下のA-Eをどこかの部屋につくか、すでに通路になっているマスにつくまで繰り返す
　　　A. 右下なら、部屋の右の壁の上端と下端をのぞいた所から１つ選んで始点とする
     B. 右にランダムで１〜１０回通路を延ばしていく。
     C. 下にランダムで１〜１０回通路を延ばしていく。
     D. B,Cでダンジョンの領域外にでてなければBへ戻る。出ていればEへ
     E. 領域外に出る直前の通路延ばしをキャンセルして、それが右方向であれば下、下方向であれば右に通路を延ばしたときにどこかの部屋につくか、通路につながらないか調べる。つながるのであれば、その方向につないで終了。つながらないのであればさらにキャンセルして繰り返す
     (右上と左下はBとCの順は逆になる）
   
   4-3. これで全ての部屋が相互につながるはずなので、全ての部屋を処理し終わったら完了。