ランダムダンジョン生成

Posted

phaser

ランダムダンジョン生成

※ これはほぼ備忘録です。参考になるのかはわかりません。

ランダムダンジョン生成は男のロマン。

手順

大まかな手順は以下の通り。

  1. 空間をパーティションで仕切る
  2. 各パーティションについて、必要なマージンを取って部屋になる空間を1つ配置
  3. 各パーティションについて、自身と隣接しているパーティションの情報をまとめる(隣接しているパーティションと、接している領域の座標)
  4. ‘3'の情報から、各部屋について、自身と直接通路で繋げることができる部屋を互いに把握させる
  5. ‘3'の情報から、各部屋について、通路を繋げる時に必ず経由する地点を把握させる
  6. ‘5'までの情報をもって、部屋同士を通路で繋げる

順に見ていく。

1. 空間をパーティションで仕切る

空間を複数のパーティションで仕切るのは、まずマップ全体を半分に(等分ではない)、さらに半分にされた領域を半分に…としていく。これをする際、最大分割深さを決めてランダムで分割していく。

draw1

この時、縦に分割するか横に分割するかもランダムで決めると、長細い領域が頻繁に出来てしまう(たまにそういう領域が出来るのは構わないが)。これを防ぐには、アスペクト比(短辺と長辺の比)を使ったりして縦長の領域はより水平に分割されやすくすれば良い。

ちなみに、パーティションの最小値を、次に配置する部屋の最小値と必要なマージンが取れるように設定する必要がある。

2. 各パーティションについて、必要なマージンを取って部屋になる空間を1つ配置

次に各パーティションで分けられた領域の中に部屋を配置していく。

部屋の幅、逆さの最小値をあらかじめ決めて、ランダムで部屋の大きさを決める。

しかし、ここでも純粋なランダムにすると、長細い部屋が頻繁に出来てしまうので、以下のようなルールを設けることでこれを防ぐ。

  1. 先にパーティションの短辺側の部屋の幅、または高さになる辺を決める。
  2. 次に、正規分布に従ってアスペクト比を決める(平均 : 1, 分散: 適当) ※アスペクト比の平均1ということは正方形に近い形の部屋ができやすくなるということ
  3. アスペクト比に従って決まっていない方の部屋の辺の長さを決める。

上記のルールで部屋の大きさを決めて、残った領域の中で部屋の位置をランダムで決める。ここは一様なランダムが良い。

draw2

3. 各パーティションについて、自身と隣接しているパーティションの情報をまとめる

マップを作る手順としては部屋ができればあとはそれらの部屋を通路で繋げば終了なのだが、ランダムでペアを決めて通路で繋ぐとあまりにも規則性のないマップが出来上がってしまう。しかし期待しているのはある部屋から次の部屋に、さらに次の部屋に…と進んでいけるダンジョンマップだろう。そのための準備をこれからしていかないといけない。

draw3

要点としては、部屋と部屋を繋いだ通路の途中に別の部屋があったりするとマップの規則性がなくなってしまうということなので、ここでほしいのが この部屋の近隣にある部屋はどれとどれなのか という情報である。

部屋の情報を使うと近隣の部屋を見つけるのが大変になるので、ここでその部屋が所属しているパーティションの位置情報から近隣の部屋を探す。各パーティションに1つ部屋があるのだから、その隣接しているパーティションに所属している部屋同士は近隣の部屋同士ということになる。

パーティションが隣接しているかどうかは、それらのパーティションが占めているx,y座標上の領域について重なりをみれば分かる。大雑把に書けば以下のようにして分かる。

// それぞれの長さの合計と、それぞれの値の最大値、最小値から、重なっている領域の長さが分かる
getOverlapRange(startA: number, endA: number, startB: number, endB: number): number {
  const max = Math.max(startA, startB, endA, endB);
  const min = Math.min(startA, startB, endA, endB);
  const lenA = Math.abs(endA - startA);
  const lenB = Math.abs(endB - startB);
  return (lenA + lenB) - (max - min);
}

isFacing(a: Area, b: Area): boolean {
  const overlapRangeX = getOverlapRange(a.left, a.right, b.left, b.right);
  const overlapRangeY = getOverlapRange(a.top, a.bottom, b.top, b.bottom);

  // yに重なっている領域があり、かつ、xの重なりが0であれば、左右に隣接する
  if (overlapRangeY > 0 && overlapRangeX === 0) return true;
  // xに重なっている領域があり、かつ、yの重なりが0であれば、上下に隣接する
  if (overlapRangeX > 0 && overlapRangeY === 0) return true;

  return false;
}

このパーティションが接触している領域は、後々使うので情報を部屋のペアとセットで取っておく。

4. 各部屋について、自身と直接通路で繋げることができる部屋を互いに把握させる

上記でも書いたが、1つのパーティションにつき1つの部屋がある時、パーティション同士が隣接していれば部屋同士も近隣同士になるということである。これを部屋に把握させる。

5. 各部屋について、通路を繋げる時に必ず経由する地点を把握させる

近隣する部屋が分かれば、あとはそこに向かって通路を伸ばせば良いとなるが、ここで一つ問題が発生する。

まず、ダンジョンの通路は斜めになってほしくない。最終的にマップに落とす時に描写が大変になるし、そもそもダンジョンのマップの通路は直角に進行すると相場で決まっている。そのため、スタート地点とゴール地点を結ぶ線が直角になるように後々ルートを補正することになるのだが、補正したがために関係のない部屋に侵入してしまう可能性があるのだ。

draw4

これを防ぐために、絶対他の部屋が存在しないルートを作るための 中継地点を作成する。この中継地点は、3で調べたパーティション同士が接している領域からランダムで決めれば良い。

中継地点が決まったら、最後に部屋を通路で繋げる(先に書いておくとこれが大変)

6. 部屋同士を通路で繋げる

いよいよ部屋同士を通路で繋げる。おおまかな手順としては以下の通り。

  1. これから通路で繋ぐ部屋の中からランダムで位置を取る
  2. 中継地点と合わせてスタートとゴールが決まったので、それが通路になる
  3. 通路が水平、垂直のみで構成されるように、ルートを補正する地点を加える

draw5

通路が水平、垂直のみで構成されるようにルートを補正するには、各ポイント同士のx,yが交わるところを新たな中継地点として加えてやればよい。これには水平方向優先と、垂直方向優先の2通りのパターンがあるが、 ある場合を除いて ランダムで良い。(あとで説明する)

これで通路がつながる。…のだが、これだけだといくつか問題が起きる。

問題1. 2マスの通路が生まれる

通路同士がくっついて幅2マスの通路が生まれることがある。これは個人的にはそこまで問題でない(特徴として許容できる)ので、今回は無視したが、気になるのであればパース時に埋めてしえば済むかもしれない。

問題2. 通路が部屋の壁を破壊する

これは許容できない問題。補完された通路が部屋と間隔を開けずに通った場合、本来は1マスは確保しておきたい部屋の壁が通路によって破壊されることがたまに起きる。

これを防ぐためには、ルートを補完する時に部屋のすぐ隣を中継地点としないようにすれば良い。

draw6

これら、書けば簡単にできそうだが、“問題を避けるための中継地点を一つ増やせばOK!” などと簡単に済む話ではない(すぐスパゲッティーになる)。