目次
はじめに
ダンジョンの自動生成をするということで、前回はルームの作成を行いました。
今回は
①エリアの分割
②ルームの作成
③ドアの設置←←
④廊下（コリドー、Corridor）の作成←←
③④をやりましょう。
※後述にもありますが、③は考えた結果別に必要ないということで④が中心です。
ドアの設置の準備
ドアを設置するにあたって、ルームにドアをつけるだけならまだ簡単なんです。（簡単なんですよ。）大切なのはちゃんとコリドーを通すことを見通したドアの位置決定なんです。ドアを生成してコリドーを通した結果、すべてのルームに行けるようにしなければせっかく作ったルームがかわいそうですので、ちゃんと全部のルームに行けるようにドアを生成したいのです。
そのために、どの順番でどの方向でドアを生成していくかを確定させていきます。
各エリアに必ず１ルーム存在するので、すべてのエリアに行けるようになれば良いわけです。そのためにこのような考え方でドアを生成する順番を確定させていきたいと思います。
エリア０からスタートして隣接する最も大きなエリア番号のところへと向かう。それを繰り返して最終的にすべてつながれば終了。もしまだ行っていないエリアがあるのにもう次に進めるエリアがなくなってしまった場合には、ひとつ前に行ったエリアに戻ってそこで隣接する最も大きなエリア番号のところへ向かうことによってすべてのエリアに行こう。やってみた結果すべてエリアに行けないパターンがあったので、それはもう仕方ありません。いけないパターンにぶち当たったら、なかったことにしてもう一度順番を決めなおします。
これをorderRoom関数で行います。
以下、orderRoom関数。
ただし、グローバル変数として
int order[AREA_MAX]; //ルームをつなげる順番 int orderIndex = 0; //order[]の添え字 int connectErrorCount = 0; //エラー発見用
を準備していて、AREA_t構造体に
int check; //0:まだ 1:チェックされた
の項目を追加しています。
void orderRoom(int areaIndex) { int x, y; int neighborAreaNum[2] = { -1, 0 }; //areaIndex番目のエリアに隣接するエリア番号の最大値をneiborAreaNum[0]に格納できる int nextDirection; //1:上 2:下 3:左 4:右 //areaIndex番目のエリアに隣接するエリアを見つける //上側 if (areas[areaIndex].y != 0){ for (x = areas[areaIndex].x; x < areas[areaIndex].x + areas[areaIndex].w; x++){ if (areas[areaNumber[areas[areaIndex].y - 1][x]].check == 1) continue; neighborAreaNum[1] = areaNumber[areas[areaIndex].y - 1][x]; if (neighborAreaNum[0] < neighborAreaNum[1]){ neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 2; } } } //下側 if (areas[areaIndex].y != FIELD_HEIGHT-1){ for (x = areas[areaIndex].x; x < areas[areaIndex].x + areas[areaIndex].w; x++){ if (areas[areaNumber[areas[areaIndex].y + areas[areaIndex].h][x]].check == 1) continue; neighborAreaNum[1] = areaNumber[areas[areaIndex].y + areas[areaIndex].h][x]; if (neighborAreaNum[0] < neighborAreaNum[1]){ neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 3; } } } //左側 if (areas[areaIndex].x != 0){ for (y = areas[areaIndex].y; y < areas[areaIndex].y + areas[areaIndex].h; y++){ if (areas[areaNumber[y][areas[areaIndex].x - 1]].check == 1) continue; neighborAreaNum[1] = areaNumber[y][areas[areaIndex].x-1]; if (neighborAreaNum[0] < neighborAreaNum[1]) neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 } } //右側 if (areas[areaIndex].x != FIELD_WIDTH){ for (y = areas[areaIndex].y; y < areas[areaIndex].y + areas[areaIndex].h; y++){ if (areas[areaNumber[y][areas[areaIndex].x + areas[areaIndex].w]].check == 1) continue; neighborAreaNum[1] = areaNumber[y][areas[areaIndex].x +areas[areaIndex].w]; if (neighborAreaNum[0] < neighborAreaNum[1]){ neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 4; } } } //次のエリアが見つからない場合、 if (neighborAreaNum[0] == -1) { connectErrorCount++; if (connectErrorCount >= 10) return; orderRoom(order[orderIndex - 1]); //ひとつ前のエリアに戻ってチェックされていないエリアを探す } //次のエリアが見つかった場合、 if (neighborAreaNum[0] != -1){ areas[neighborAreaNum[0]].check = 1; //次のエリアにチェックを入れる order[orderIndex + 1] = neighborAreaNum[0]; orderIndex++; } if (orderIndex+1 == areaCount) return; orderRoom(neighborAreaNum[0]); }
コリドーの生成
作ってる途中で「あれ、ドアって要らなくね？」ってなったので、もう一気にコリドーを通します（冒頭の宣言通り）。ドアをいちいち考えているとめんどくさかったのでそのまま作成しようと思います。
接続されるルーム内にそれぞれ任意に点(d1x,d1y),(d2x,d2y)を取って、繋げたいルームの方向へその点を移動していきます。移動していく度に穴を掘っていくようなイメージでコリドーを生成していきたいと思います。移動の方法としては、ｘ、ｙ座標のどちらかのみを動かしていって、そのどちらかが一致するまで続けます。
一致したら後はもう片方の座標が一致するまで動かしていけば晴れてコリドー完成というわけです。
orderRoom関数の次のエリアが見つかった場合の箇所を書き換えていきます。
以下、orderRoom関数内
//次のエリアが見つかった場合、 if (neighborAreaNum[0] != -1){ areas[neighborAreaNum[0]].check = 1; //次のエリアにチェックを入れる order[orderIndex + 1] = neighborAreaNum[0]; orderIndex++; //ここからコリドーを伸ばしていく int d1x, d1y, d2x, d2y; //d1:移動前のドアの座標 d2:移動後のドアの座標 //両ルーム内の適当な点を１つずつ取る d1x = random(areas[order[orderIndex - 1 -connectErrorCount]].room.x, areas[order[orderIndex - 1 - connectErrorCount]].room.x + areas[order[orderIndex - 1 - connectErrorCount]].room.w - 1); d1y = random(areas[order[orderIndex - 1 - connectErrorCount]].room.y, areas[order[orderIndex - 1 - connectErrorCount]].room.y + areas[order[orderIndex - 1 - connectErrorCount]].room.h - 1); d2x = random(areas[order[orderIndex]].room.x, areas[order[orderIndex]].room.x + areas[order[orderIndex]].room.w - 1); d2y = random(areas[order[orderIndex]].room.y, areas[order[orderIndex]].room.y + areas[order[orderIndex]].room.h - 1); connectErrorCount = 0; //各ルームからコリドーを伸ばしていって同じ位相まで行く //その際に進んだ経路は穴を掘るようになるので、CELL_TYPE_NONEを代入 switch (nextDirection){ case 1: while (d1y!=d2y){ if (abs(d1y - d2y) == 1){ d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } else{ d1y--, d2y++; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1y == d2y) { while (d1x != d2x) { if (d1x < d2x) d1x++; else d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 2: while (d1y != d2y){ if (abs(d1y - d2y) == 1){ d1y++; field[d1y][d1x] = CELL_TYPE_NONE; } else{ d1y++, d2y--; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1y == d2y) { while (d1x != d2x) { if (d1x < d2x) d1x++; else d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 3: while (d1x != d2x){ if (abs(d1x - d2x) == 1){ d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } else{ d1x--, d2x++; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1x == d2x) { while (d1y != d2y) { if (d1y < d2y) d1y++; else d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 4: while (d1x != d2x){ if (abs(d1x - d2x) == 1){ d1x++; field[d1y][d1x] = CELL_TYPE_NONE; } else{ d1x++, d2x--; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1x == d2x) { while (d1y != d2y) { if (d1y < d2y) d1y++; else d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; default: break; } }
ここまでの全体のソースコード、実行結果例
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<conio.h> #define FIELD_HEIGHT 64 #define FIELD_WIDTH 64 #define AREA_MAX 64 //エリアの最大個数 #define AREA_SIZE_MIN 16 //エリア #define CELL_COUNT 2 #define ROOM_SIZE_MIN (AREA_SIZE_MIN-4-4) enum { CELL_TYPE_NONE, //0 CELL_TYPE_WALL //1 }; //ルームの座標・横幅・高さをひとまとめに管理するために構造体ROOM_tで定義 typedef struct { int x; int y; int w; int h; int doorX; int doorY; }ROOM_t; /* エリアの座標・横幅・高さをひとまとめに管理するために構造体AREA_tで定義 また、エリア内にルームを作成するのでルームもここで管理します。 orderRoom関数用にチェック項目を追加 */ typedef struct { int x; int y; int w; //width int h; //height ROOM_t room; int check; //0:まだ 1:チェックされた }AREA_t; AREA_t areas[AREA_MAX]; //各エリアの座標・横幅・高さの情報をしまっておける int areaCount; //エリアの個数 int field[FIELD_HEIGHT][FIELD_WIDTH]; //座標毎のフィールドの状態 int areaNumber[FIELD_HEIGHT][FIELD_WIDTH]; //座標に対応するエリア番号をしまっておける char cellSymbol[CELL_COUNT][3] = { "・", //CELL_TYPE_NONE(0)番目の配列 "■" //CELL_TYPE_WALL(1)番目の配列 }; int order[AREA_MAX]; //ルームをつなげる順番 int orderIndex = 0; //order[]の添え字 int connectErrorCount = 0; //エラー発見用 int random(int, int); void spritArea(int); void generateField(void); void orderRoom(int); int main(void) { int x, y, i; srand((unsigned int)time(NULL)); while (1) { //フィールドの生成 generateField(); //座標に対応するエリア番号を取得 for (i = 0; i < areaCount; i++) { for (y = areas[i].y; y < areas[i].y + areas[i].h; y++) { for (x = areas[i].x; x < areas[i].x + areas[i].w; x++) { areaNumber[y][x] = i; } } } //すべてのエリアのチェックを0で初期化 for (i = 0; i < areaCount; i++) areas[i].check = 0; areas[0].check = 1; //最初のエリアのみ、チェックを打っておく orderIndex = 0; //orderRoom関数で使用するために初期化 order[0] = 0; //順番の最初はルーム0 orderRoom(0); //0番目のエリアからどんどん隣接させる //エラー回避 if (connectErrorCount >= areaCount) { connectErrorCount = 0; continue; } system("cls"); //フィールドの描画 for (y = 0; y < FIELD_HEIGHT; y++) { for (x = 0; x < FIELD_WIDTH; x++) { /* field[y][x]でフィールドの情報を数字で取り出し、 その数字に応じて対応した記号をcellSymbolで取り出し、 それを描画 fieldにはenumで定義したものしか入っていないので */ printf("%s", cellSymbol[field[y][x]]); } printf("\n"); } for (i = 0; i < areaCount; i++) printf("%d\n", order[i]); //移動するエリアの順番確認用 _getch(); } return 0; } int random(int start, int end) { return rand() % (end - start + 1) + start; } //エリアを分割して、エリア毎に座標・横幅・高さを取得する関数 //oldAreaIndex : 分割前のエリア番号 //newAreaIndex : 分割後のエリア番号 void spritArea(int oldAreaIndex) { int flag = 0; int newAreaIndex = areaCount; //分割をキャンセルする時に戻せるようにする(再帰処理なので、終了条件を満たしたときに直前の分割をキャンセルしたい) int w = areas[oldAreaIndex].w; //保存用 int h = areas[oldAreaIndex].h; //保存用 //縦切り if (rand() % 2 == 0) { areas[oldAreaIndex].w /= 2; //半分 areas[newAreaIndex].x = areas[oldAreaIndex].x + areas[oldAreaIndex].w; //新しいエリアのx座標 areas[newAreaIndex].y = areas[oldAreaIndex].y; //新しいエリアのy座標 areas[newAreaIndex].w = w - areas[oldAreaIndex].w; //新しいエリアの横幅 areas[newAreaIndex].h = areas[oldAreaIndex].h; //新しいエリアの高さ } //横切り else { flag = 1;//横切りのサイン areas[oldAreaIndex].h /= 2; //半分 areas[newAreaIndex].x = areas[oldAreaIndex].x; //新しいエリアのx座標 areas[newAreaIndex].y = areas[oldAreaIndex].y + areas[oldAreaIndex].h; //新しいエリアのy座標 areas[newAreaIndex].w = areas[oldAreaIndex].w; //新しいエリアの横幅 areas[newAreaIndex].h = h - areas[oldAreaIndex].h; //新しいエリアの高さ } //分割後の二つのエリアがエリアの条件(AREA_SIZE_MINの範囲内かどうか)を満たしているか if ((areas[oldAreaIndex].w < AREA_SIZE_MIN) || (areas[oldAreaIndex].h < AREA_SIZE_MIN) || (areas[newAreaIndex].w < AREA_SIZE_MIN) || (areas[newAreaIndex].w < AREA_SIZE_MIN)) { areas[oldAreaIndex].w = w; areas[oldAreaIndex].h = h; return; //void型関数を終了させたいときは、単にreturnと書けばよい } areaCount++; spritArea(newAreaIndex); //新エリアの分割 spritArea(oldAreaIndex); //旧エリアの分割 } void generateField(void) { int i, x, y; //最初のエリアの情報 //つまり、エリアの初期化 areaCount = 0; areas[0].x = 0; areas[0].y = 0; areas[0].w = FIELD_WIDTH; areas[0].h = FIELD_HEIGHT; areaCount++; spritArea(0); //まず、フィールドをすべて壁(1)で埋める。あとで部屋の部分に穴をあけていく。 for (y = 0; y < FIELD_HEIGHT; y++) { for (x = 0; x < FIELD_WIDTH; x++) { field[y][x] = CELL_TYPE_WALL; } } //ここでルームを作成している！ for (i = 0; i < areaCount; i++) { //まずは元となるルームを作成 areas[i].room.x = areas[i].x + 2; areas[i].room.y = areas[i].y + 2; areas[i].room.w = areas[i].w - 4; areas[i].room.h = areas[i].h - 4; //ここからルームをランダムに小さくします。 int r1 = random(0, areas[i].room.w - ROOM_SIZE_MIN); int r2 = random(0, areas[i].room.h - ROOM_SIZE_MIN); areas[i].room.x += r1; areas[i].room.y += r2; areas[i].room.w = random(ROOM_SIZE_MIN, areas[i].room.w - r1); areas[i].room.h = random(ROOM_SIZE_MIN, areas[i].room.h - r2); //ルームの上から下まで for (y = areas[i].room.y; y < areas[i].room.y + areas[i].room.h; y++) { //ルームの左から右まで for (x = areas[i].room.x; x < areas[i].room.x + areas[i].room.w; x++) { field[y][x] = CELL_TYPE_NONE; //ルームの部分だけ穴が空く(ルームでのfieldが0になった) } } } } void orderRoom(int areaIndex) { int x, y; int neighborAreaNum[2] = { -1, 0 }; //areaIndex番目のエリアに隣接するエリア番号の最大値をneiborAreaNum[0]に格納できる int nextDirection; //1:上 2:下 3:左 4:右 //areaIndex番目のエリアに隣接するエリアを見つける //上側 if (areas[areaIndex].y != 0) { for (x = areas[areaIndex].x; x < areas[areaIndex].x + areas[areaIndex].w; x++) { if (areas[areaNumber[areas[areaIndex].y - 1][x]].check == 1) continue; neighborAreaNum[1] = areaNumber[areas[areaIndex].y - 1][x]; if (neighborAreaNum[0] < neighborAreaNum[1]) { neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 1; } } } //下側 if (areas[areaIndex].y + areas[areaIndex].h != FIELD_HEIGHT - 1) { for (x = areas[areaIndex].x; x < areas[areaIndex].x + areas[areaIndex].w; x++) { if (areas[areaNumber[areas[areaIndex].y + areas[areaIndex].h - 1][x]].check == 1) continue; neighborAreaNum[1] = areaNumber[areas[areaIndex].y + areas[areaIndex].h][x]; if (neighborAreaNum[0] < neighborAreaNum[1]) { neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 2; } } } //左側 if (areas[areaIndex].x != 0) { for (y = areas[areaIndex].y; y < areas[areaIndex].y + areas[areaIndex].h; y++) { if (areas[areaNumber[y][areas[areaIndex].x - 1]].check == 1) continue; neighborAreaNum[1] = areaNumber[y][areas[areaIndex].x - 1]; if (neighborAreaNum[0] < neighborAreaNum[1]) { neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 3; } } } //右側 if (areas[areaIndex].x + areas[areaIndex].w != FIELD_WIDTH) { for (y = areas[areaIndex].y; y < areas[areaIndex].y + areas[areaIndex].h; y++) { if (areas[areaNumber[y][areas[areaIndex].x + areas[areaIndex].w]].check == 1) continue; neighborAreaNum[1] = areaNumber[y][areas[areaIndex].x + areas[areaIndex].w]; if (neighborAreaNum[0] < neighborAreaNum[1]) { neighborAreaNum[0] = neighborAreaNum[1]; //一番大きな番号を[0]に格納 nextDirection = 4; } } } //次のエリアが見つからない場合、 if (neighborAreaNum[0] == -1) { connectErrorCount++; if (connectErrorCount >= 10) return; orderRoom(order[orderIndex - 1]); //ひとつ前のエリアに戻ってチェックされていないエリアを探す } //次のエリアが見つかった場合、 if (neighborAreaNum[0] != -1) { areas[neighborAreaNum[0]].check = 1; //次のエリアにチェックを入れる order[orderIndex + 1] = neighborAreaNum[0]; orderIndex++; //ここからコリドーを伸ばしていく int d1x, d1y, d2x, d2y; //d1:移動前のドアの座標 d2:移動後のドアの座標 //両ルーム内の適当な点を１つずつ取る d1x = random(areas[order[orderIndex - 1 - connectErrorCount]].room.x, areas[order[orderIndex - 1 - connectErrorCount]].room.x + areas[order[orderIndex - 1 - connectErrorCount]].room.w - 1); d1y = random(areas[order[orderIndex - 1 - connectErrorCount]].room.y, areas[order[orderIndex - 1 - connectErrorCount]].room.y + areas[order[orderIndex - 1 - connectErrorCount]].room.h - 1); d2x = random(areas[order[orderIndex]].room.x, areas[order[orderIndex]].room.x + areas[order[orderIndex]].room.w - 1); d2y = random(areas[order[orderIndex]].room.y, areas[order[orderIndex]].room.y + areas[order[orderIndex]].room.h - 1); connectErrorCount = 0; //各ルームからコリドーを伸ばしていって同じ位相まで行く //その際に進んだ経路は穴を掘るようになるので、CELL_TYPE_NONEを代入 switch (nextDirection) { case 1: while (d1y != d2y) { if (abs(d1y - d2y) == 1) { d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } else { d1y--, d2y++; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1y == d2y) { while (d1x != d2x) { if (d1x < d2x) d1x++; else d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 2: while (d1y != d2y) { if (abs(d1y - d2y) == 1) { d1y++; field[d1y][d1x] = CELL_TYPE_NONE; } else { d1y++, d2y--; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1y == d2y) { while (d1x != d2x) { if (d1x < d2x) d1x++; else d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 3: while (d1x != d2x) { if (abs(d1x - d2x) == 1) { d1x--; field[d1y][d1x] = CELL_TYPE_NONE; } else { d1x--, d2x++; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1x == d2x) { while (d1y != d2y) { if (d1y < d2y) d1y++; else d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; case 4: while (d1x != d2x) { if (abs(d1x - d2x) == 1) { d1x++; field[d1y][d1x] = CELL_TYPE_NONE; } else { d1x++, d2x--; field[d1y][d1x] = CELL_TYPE_NONE; field[d2y][d2x] = CELL_TYPE_NONE; } } if (d1x == d2x) { while (d1y != d2y) { if (d1y < d2y) d1y++; else d1y--; field[d1y][d1x] = CELL_TYPE_NONE; } } break; default: break; } } if (orderIndex + 1 == areaCount) return; orderRoom(neighborAreaNum[0]); }
おわりに
ダンジョン自動生成はもうほぼ完成となりましたが、まあなんとも難しかったです。特に再帰処理でバグが酷かったのでバグを取り除くのにとても苦労しました。今は頭の中に思い描いたことを直感的にプログラムにしただけなので効率的かと言われれば恐らくそうではないと思います。本場のゲームプログラマーは最高効率で動くような工夫を凝らしているので、改めて凄いなあと感じます。まあそこまで追い求めるつもりはないので、余力があれば。。。
とにかく！大切なのは思いついたことをプログラムに直す力です。これまでに書いたプログラムを参考にしつつ考え方及びそれに対応するプログラムの書き方を知れば発展の余地は沢山あると思います。
疲れました。お疲れ様でした。
