MIS.W 公式ブログ

早稲田大学公認、情報系創作サークル「早稲田大学経営情報学会」(MIS.W)の公式ブログです!

ランダムダンジョンのアルゴリズム【アドベントカレンダー2015冬9日目】

49代のkeyです。

文才も書く内容も無いのにアドベントカレンダーに指名されました。困りましたね。

僕は早稲田祭にて、ローグライクのゲームを作る企画に携わっており、その中の仕事の1つでランダムマップ生成のコードを担当しました。受けた時は「まあ、ネットに落ちてるやろW」みたいな軽い気持ちだったのですが、探しても「ランダムダンジョン生成のコードはとても複雑」という記述やら示してあっても概略のようなものばかり。

「うわ これ難しいんだろうな」と思って面倒くさがりな僕は理解することを放棄していました。しかし、早稲田祭の日にちが迫ってきてしまい、逃げていた仕事と向き合わなければならなくなりました。必死に概略のサイトを見て回って何とか早稲田祭直前に2日くらいで考えて作ったアルゴリズムを説明したいと思います。


 

さて、ここから本題です。

コードは基本的なC/C++で作成しました。

用いた各クラスはこんな感じです。

class Point{//座標を表すクラス
public:
 int x, y;
};

class Root{//通路を表すクラス 通路よりも分割に用いる線とした方が適切かも
public:
 Point start, end;//startは左端もしくは上端、endは右端もしくは下端の座標
};

class Area{//領域を表すクラス
public:
 Point start, end;//startは左上、endは右下の座標

 int sizeX(){
  return end.x - start.x + 1;
 }
 int sizeY(){
  return end.y - start.y + 1;
 }
 int size(){
  return sizeX() * sizeY();
 }
};

class Room{//部屋のクラス  各Areaに1つのRoomを作るようにする
public:
 Point start, end;//startは左上、endは右下の座標

 int sizeX(){
  return end.x - start.x + 1;
 }
 int sizeY(){
  return end.y - start.y + 1;
 }
 int size(){
  return sizeX() * sizeY();
 }

 Point random;//通路を繋げるときに使う座標 部屋内からランダムに1点をとる
 Point cross[4];//部屋から通路を伸ばすときに使う交点の座標 後述
 bool gateexist[4];//部屋から見て方向に通路を作るかどうか
 int maxamountgate;//部屋から伸びている通路の最大数
 int amountgate;//部屋から伸びている通路の数
};

class Map{//マップのクラス 関数は色々あるが省略
private:
 int x, y;

public://適当にそれぞれ20個の配列を用意 実際に使いそうな数に応じて増減させると良い
 Area area[20];
 Room room[20];
 Root root[20];
};

 

これらのクラスを用いてアルゴリズムを説明していきます。

まず概略から。

①マップ全体をarea[0]とする

b0ffa0680d202735c95a5ee6e07d202f

area[0]root[0]で分割してarea[1]を作る

37b445d4adb40f5507bc67b667f1f35a

 

area[n]をrootでどんどん分割してareaを増やしていく(nはランダム)

49802a76de5f1f3b0812d1bc214bb741

④各area内にroomを作る

767df0949560d78b507b9640ef1e8a0e

⑤各roomから分割に用いたrootへと直線を伸ばし、交点をcrossとして保存

62d59d445e95ced3e147e7f21a4bf6d0

⑥各rootstartから交点の部分まで消す endについても同様

ここでの消し方は2通り考えられます。

・交点をrootとrootの交点とcrossどちらも含める

・crossだけ

前者は画像左、後者は画像右の形になります。

16205eadec321c8b8e7568236298a4f3

 ⑦完成

 

概略だけで終わろうと思ったのですが、これだけだとググれば簡単に見つかる他のサイトでも書いてあります。なので、せっかくだし上の各手順についても少し詳しく説明します。

最初にイメージしやすいように、マップ全体の大きさを40*40とします。

・手順⓪ マップの初期化

マップをint map[40][40]みたいに置いておいて、全てのマスを初期化しておきます。

便宜上map[a][b]=0は通行不可、map[a][b]=1は通行可のマスとします。

mapのすべてのマスの値を0にしておきましょう。

値が2の箇所に階段を設置したり、3の箇所に罠を設置したりするとよりダンジョンらしくなりますが、今回は0と1の2値だけでの生成を行います。

・手順① マップ全体をarea[0]とする

ここで行うことはarea[0]をマップの大きさに合わせてstartを(1,1)、endを(40,4o)にするだけです。

・手順② area[0]root[0]で分割してarea[1]を作る

縦分割・横分割の2通りの処理を書くことになります。

(1)縦分割の場合

分割がy=Yで行われたとします。

(例:Y=10 + rand()%21 とすると Y=[10,30]でランダムになる)

その時のarea[0],area[1],root[0]は

area[0].start=(1,1) area[o].end=(40,Y-1)

area[1].start=(1,Y+1) area[0].end=(40,40)

root[0].start=(1,Y) root[0].end=(40,Y)

(2)横分割の場合

分割がx=Xで行われたとします。

その時のarea[0],area[1],root[0]は

area[0].start=(1,1) area[o].end=(X-1,40)

area[1].start=(X+1,1) area[0].end=(40,40)

root[0].start=(X,1) root[0].end=(X,40)

「?」ってなった方は概略の②で使った画像を見て頂ければ多分分かります。

・手順③ area[n]をrootでどんどん分割してareaを増やしていく(nはランダム)

一般化してroot[k]でarea[n]を分割し、area[k]を生成するとしましょう。

(1)縦分割の場合

分割がy=Yで行われたとします。

(例:Y=area[n].start.y + area[n].sizeY()/2 + rand()%4 -2 とすると、Y=[area[n].start.y+area[n].sizeY()/2-2, area[n].start.y+area[n].sizeY()/2+1]つまり部屋の真ん中くらいで分割されるようになる)

その時のarea[n],area[k],root[k]は

area[k].end=(area[n].end.x, area[n].end.y)

area[n].start=(area[n].start.x, area[n].start.Y) 変化なし

area[n].end=(area[n].end.x, Y-1)

area[k].start=(area[n].start.x, Y+1)

root[k].start=(area[n].start.x, Y)

root[k].end=(area[n].end.x, Y)

area[k].endは分割前のarea[n].endに一致するので、area[n].endを弄る前に値を決める必要があります。その他の順番は適当で大丈夫です。

(2)横分割の場合

分割がx=Xで行われたとします。

その時のarea[n],area[k],root[k]は

area[k].end=(area[n].end.x, area[n].end.y)

area[n].start=(area[n].start.x, area[n].start.y) 変化なし

area[n].end=(X-1, area[n].end.y)

area[k].start=(X+1, area[n].start.y)

root[k].start=(X, area[n].start.y)

root[k].end=(X, area[n].end.y)

この手順③の処理は部屋の元を作るため、何度も繰り返す訳ですが、同じ部屋ばかりを分割してしまうと、極端に小さい部屋が出来たりしてしまうので、area[n]を選ぶときに、「sizeX()<5またはsizeY()<5なら部屋を選ぶ直す」「部屋の辺の長い方を分割」みたいな条件を入れるとわりと綺麗なマップになります。

多分。

・手順④ 各area内にroomを作る

手順③でいっぱいareaを作りましたね。各areaにroomを1つずつ作っていきましょう。

部屋に壁が欲しいので、areaの外周1マスは必ず壁になるようにしましょう。

room[n].start=(area[n].start.x+1, area[n].start.y+1)

room[n].end=(area[n].end.x-1, area[n].end.y-1)

こうするととりあえず必ず壁はできますが、壁の厚さが固定されてしまいますね。

部屋が大きい場合→+1/-1を+1+rand()%7/-1-rand()%7

部屋が小さい場合→+1/-1を+1+rand()%3/-1-rand()%3

みたいにすると壁の厚さもある程度ランダムになり、よりダンジョンらしくなると思います。

この処理の後、ひとまず各roomとrootの範囲の値をmap[x][y]=1にしましょう。手順⑤でこの値を使います。

・手順⑤ 各roomから分割に用いたrootへと直線を伸ばし、交点をcrossとして保存

Roomで定義した各変数を使って部屋と通路を繋げていきます。

  Point random;//通路を繋げるときに使う座標 部屋内からランダムに1点をとる   Point cross[4];//部屋から通路を伸ばすときに使う交点の座標   bool gateexist[4];//部屋から見て方向に通路を作るかどうか   int maxamountgate;//部屋から伸びている通路の最大数   int amountgate;//部屋から伸びている通路の数

まず、randomの座標を取得します。

random.x=[start.x, end.x] (random.x = rand()%sizeX() + start.x)

random.y=[start.y, end.y] (random.y = rand()%sizeY() + start.Y)

この範囲で座標を決めると、randomの座標は部屋内で1点ランダムに選ぶことができます。

次に、部屋から4つの各方向にrootが存在しているかを調べます。

例:部屋の下方向についてrootがあるかを調べる場合

x=room[n].end.x + 1; y=room[n].random.y + 1;//x,yを(部屋の一つ下,random.y)にセット

while (true){
 if (map[x][y] == 1){//map[x][y]=1となっているのはroot
  room[n].gateexist[i] = true;//i(1≦i≦4)は4方向に対応
  room[n].cross[i].x = x;//rootがあったらその座標を取得
  room[n].cross[i]].y = y;
  break;
 }
 x++;
 if (x == 40){//マップの右端に到達
  room[n].gateexist[i] = false;
  break;
 }
}

4方向について調べ終わったらgateexist[i]=trueとなっている数をmaxamountgateの値とします。(1≦maxamountgate≦4)

さて、この後通路を伸ばす訳ですが、通路の数は最低1本、最大maxamountgateですよね。

全ての部屋で通路を最大数作ってしまうと通路が多すぎてダンジョン感が薄れてしまいます。そこで、amountgate = 1 + rand()%maxamountgate のようにして、作る通路の数を減らしましょう。

そして、通路を繋げる処理です。通路が出来る位置もランダムにしたいですよね。

方向iを1つランダムに取得して、gateexistがtrueなら通路生成。そこからiの値を変えてamountgateの数だけ通路が出来るように繰り返す処理が下みたいな感じになります。

while (amountgate != 0){
 if (gateexist[i]){
  通路を作成;//random~crossの座標の値を1にする
  amountgate--;
 }
 if(i==3) i=0;
 else i++;
}

iの増え方を変則的にするのも面白いと思います。

・手順⑥ 各rootstartから交点の部分まで消す endについても同様

いよいよ最後の処理です。各rootの両端から「通路の周囲の座標の値が0なら通路のマスを消去」という考えで処理しました。画像にするとこんな感じです。

advent-300x122

 

赤いマスは通路を、黒いマスがstart,endを、黄色いマスが今調べているマスを表します。

例えば、黄色いマスをmap[x][y]として、map[x-1][y](上)・map[x][y-1](左)・map[x][y+1](右)が全て値が0なら黄色いマスの下側にしか通路は伸びていないですよね。逆にこの3方向のどれかの値が1なら下側以外にも通路が繋がっていることを表します。

前者なら黄色いマスを値を0にしてx++して下のマスを調べる、後者ならそこで終了して次のstart,endについて調べる。このような処理を繰り返せば、通路の無駄な部分が消え、概略⑥の画像左のようなマップが完成します。


完成マップ例(図は42*42として外周1マスを必ず壁にしてるもの)

result-268x300

図は半角表記での出力をしているため、縦長に見えますが多分ちゃんと42*42になってると思います。

部屋をたまに迷路の形にしたりすると面白いかもしれませんね。

改善点としては

・各部屋の通路が時計回りの順で出来てしまう

・大きい部屋なのに通路が1つしか繋がってなくて不便

・部屋同士が直線で繋がることが無い

このあたりですかね。

全く推敲してないので、間違ってる箇所があるかもしれませんがご了承を。

長々と書きましたが、ダンジョン生成を考えている人が全く見当もつかないという人の参考になればと思います。

ありがとうございました。