49代のkeyです。
文才も書く内容も無いのにアドベントカレンダーに指名されました。困りましたね。
僕は早稲田祭にて、ローグライクのゲームを作る企画に携わっており、その中の仕事の１つでランダムマップ生成のコードを担当しました。受けた時は「まあ、ネットに落ちてるやろ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]とする
②area[0]をroot[0]で分割してarea[1]を作る
③area[n]をrootでどんどん分割してareaを増やしていく（ｎはランダム）
④各area内にroomを作る
⑤各roomから分割に用いたrootへと直線を伸ばし、交点をcrossとして保存
⑥各rootのstartから交点の部分まで消す endについても同様
ここでの消し方は2通り考えられます。
・交点をrootとrootの交点とcrossどちらも含める
・crossだけ
前者は画像左、後者は画像右の形になります。
⑦完成
概略だけで終わろうと思ったのですが、これだけだとググれば簡単に見つかる他のサイトでも書いてあります。なので、せっかくだし上の各手順についても少し詳しく説明します。
最初にイメージしやすいように、マップ全体の大きさを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通りの処理を書くことになります。
（１）縦分割の場合
分割が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)
（２）横分割の場合
分割が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を増やしていく（ｎはランダム）
一般化してroot[k]でarea[n]を分割し、area[k]を生成するとしましょう。
（１）縦分割の場合
分割が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を弄る前に値を決める必要があります。その他の順番は適当で大丈夫です。
（２）横分割の場合
分割が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を１つずつ作っていきましょう。
部屋に壁が欲しいので、areaの外周１マスは必ず壁になるようにしましょう。
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の座標は部屋内で１点ランダムに選ぶことができます。
次に、部屋から４つの各方向に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)は４方向に対応
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)
さて、この後通路を伸ばす訳ですが、通路の数は最低１本、最大maxamountgateですよね。
全ての部屋で通路を最大数作ってしまうと通路が多すぎてダンジョン感が薄れてしまいます。そこで、amountgate = 1 + rand()%maxamountgate のようにして、作る通路の数を減らしましょう。
そして、通路を繋げる処理です。通路が出来る位置もランダムにしたいですよね。
方向iを１つランダムに取得して、gateexistがtrueなら通路生成。そこからiの値を変えてamountgateの数だけ通路が出来るように繰り返す処理が下みたいな感じになります。
while (amountgate != 0){
if (gateexist[i]){
通路を作成;//random～crossの座標の値を1にする
amountgate--;
}
if(i==3) i=0;
else i++;
}
iの増え方を変則的にするのも面白いと思います。
・手順⑥ 各rootのstartから交点の部分まで消す endについても同様
いよいよ最後の処理です。各rootの両端から「通路の周囲の座標の値が0なら通路のマスを消去」という考えで処理しました。画像にするとこんな感じです。
赤いマスは通路を、黒いマスがstart,endを、黄色いマスが今調べているマスを表します。
例えば、黄色いマスをmap[x][y]として、map[x-1][y]（上）・map[x][y-1]（左）・map[x][y+1]（右）が全て値が０なら黄色いマスの下側にしか通路は伸びていないですよね。逆にこの3方向のどれかの値が１なら下側以外にも通路が繋がっていることを表します。
前者なら黄色いマスを値を０にしてx++して下のマスを調べる、後者ならそこで終了して次のstart,endについて調べる。このような処理を繰り返せば、通路の無駄な部分が消え、概略⑥の画像左のようなマップが完成します。
完成マップ例（図は42*42として外周1マスを必ず壁にしてるもの）
図は半角表記での出力をしているため、縦長に見えますが多分ちゃんと42*42になってると思います。
部屋をたまに迷路の形にしたりすると面白いかもしれませんね。
改善点としては
・各部屋の通路が時計回りの順で出来てしまう
・大きい部屋なのに通路が１つしか繋がってなくて不便
・部屋同士が直線で繋がることが無い
このあたりですかね。
全く推敲してないので、間違ってる箇所があるかもしれませんがご了承を。
長々と書きましたが、ダンジョン生成を考えている人が全く見当もつかないという人の参考になればと思います。
ありがとうございました。
