| ダンジョンの自動生成アルゴリズムを紹介します。 数あるダンジョンの中から、いわゆる「ローグ風ダンジョン」を取り上げます。 最初に基礎のアルゴリズムを解説し、その後に綺麗なダンジョンの作り方やゲームに必要な要素の組み込み例などを挙げたいと思います。 事前の定義として、 ・ダンジョンの広さは、横Ｗブロック×縦Ｈブロックとする ・縦横のみの２Ｄ座標とし、高さの概念を持たない とします。 ローグ風ダンジョンには、以下のような特徴があります。 ・部屋と通路で構成される ・すべての部屋が通路で結ばれている 要するに、すべての部屋を通路を通って行き来できる。言い換えると、孤立した部屋がない。ということです。 アルゴリズムの指針としては、すべての部屋を配置してからそれらの部屋を通路で結びたいと思います。 とはいえ、用意されたＷ×Ｈの空間にランダムに位置と大きさを決めて闇雲に部屋を作っていっても、部屋同士が重なったり、くっついたりして効率がよくありません。 そこでまずは、空間を分割して各部屋を作るためのスペースを決めます。 スペースが決まったら、各スペースの中に部屋をひとつずつ作ります。 イメージ的には、まず土地を分割してから、それぞれの土地に家を建てるような感じでしょうか。 こうすることで、部屋同士が重なることはもちろん、境界に接するように作らなければ、部屋同士がくっつくこともありません。 さて、肝心の空間分割の方法ですが、縦横交互に二分割していく方法が無難な方法です。 最初に縦（or横）に分割したら、次はそれぞれを横（or縦、最初とは異なる方向）に分割して、さらにそれぞれを今度は縦（横）に分割して…というのを繰り返します。 部屋が作れるだけの広さを確保できなくなったり、分割数が部屋の最大数に達したりしたら分割を終了します。 空間を二分割するということは、分割境界を挟んで二つの分割された空間が接触していることになります。 ただ分割するだけなら、縦→縦や横→横のように同じ方向に続けて分割してもいいのですが、縦横交互に分割することで便利な特徴が現れます。 それは、ひとつ前の分割境界にどちらの空間も必ず接触しているということです。 空間を縦境界でＡとＢの二つにわけて、 今度はＢを横境界でＢ１、Ｂ２にわけると、Ｂ１もＢ２もＡと境界を持ちますが、 続けて縦境界で分割すると、遠い方（Ｂ２）と近い方（Ｂ１）の二つに分割され、遠い方（Ｂ２）の空間はひとつ前の空間（Ａ）との境界を持ちません。 境界を挟んで接触している空間にある部屋同士は通路を引いて直接結ぶことができます。 途中に他の空間を経由しないので通路が他の部屋の中を通ったりする心配もありません。 同じ方向に続けて分割すると遠い方は近い方を通らないと行けないのでどちらが近い方かを認識しなければならず、ひと手間掛かります。 縦横交互分割ならばどちらにも直接行けるので気にする必要がありません。 空間の分割と部屋の配置が終わったら、部屋を結ぶ通路を引いていきます。 わかりやすくするために、部屋にＡ〜Ｅの名前をつけることにします。 さて、どの部屋を結ぶかですが、空間分割の前後の空間は接しているので、 Ａ−Ｂ、Ｂ−Ｃ、Ｃ−Ｄ、D−Ｅ は直接引けることがわかっています。 さらに、これらの部屋間に通路を引くとすべての部屋がつながるので、ダンジョンとしての必要条件も満たします。 通路を引くためにはまず、部屋の出口を決めます。 部屋を構成する壁のうち、分割境界に面している壁のどこかに出口を設けます。 例えば部屋ＡとＢを結ぶ通路の出口は上図の赤い壁のどこかになります。 出口の位置が決まったら、分割境界に向かってそれぞれの出口から通路を延ばします。 それぞれの出口から延ばした通路が分割境界と接触したら、接触した点同士を結びます。 これで部屋ＡとＢを結ぶ通路ができました。 同じ要領で残りの通路も引いていきます。 分割境界を消すとこんな感じのダンジョンになります ダンジョンの基礎工事は以上です。 しかし、これだけでは一本道でとても迷宮とは言えないので、次はダンジョンらしくする拡張工事をしたいと思います。 ■2011/03/21追記 サンプルプログラムを作りました。 |