【ゲームプログラミング】その5. マップ自動生成のアルゴリズム
こんばんは、てぃってぃ(嫁)の夫です。
「スマホでローグライク開発」第5回です。
今回の記事は「マップ自動生成のアルゴリズム」の実装です。不思議のダンジョンなどで定番の、入る度に地形が変わるマップです。
目次
実際に出力したマップ
先に成果物をお見せします。その方が読んでくれる気が起きると思うのでｗ
出力結果をテキストファイルに落としました。
後ほどの説明の為に、マップに記号を付けています。
・☆★ … 区域の頂点
・△▲ … 部屋の頂点
方針
「区域分割法」という方法を用います。
全体マップの分割を繰り返して、「区域」を作成し、その区域内で「部屋」を作成して、部屋同士を接続する感じです。
ネットにもたくさんヒントがあったのですが、頭の悪い私には理解できず（笑）、参考にするのはあきらめて自作しちゃいました。2日程度でぱぱーっと作ったので、色々とクオリティに突っ込みどころはあるかと思いますが、誰かの参考になればと思いますので、載せておきたいと思います。
実装
以下、実装方法のメモ書きです。
注意）ほんとーーに、2日程度で仕事終わりの状態で家で仕上げた、テスト不十分の完全オリジナルソースなので、参考程度にしてください。バグっていても責任とれませんw
① 全体マップを区域分割する
全体マップを複数の区域に分割していきます。１つの区域を「Rect」と呼びます。イメージはこんな感じです。
処理としては、全体マップのサイズ定義、マップ実体の定義、区域クラスの定義が必要です。
(注)ちなみにdefineは「X_RECT_MIN」「Y_RECT_MIN」を変えるとややおかしくなったかも。部屋の最小幅を「4」から変えたい場合は調整必要。(そのうちやるかも、やらないかも…)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
/// <summary> /// 制御パラメータ(設定可能) /// </summary> private const int X_MAX = 40; // MAP最大X private const int Y_MAX = 30; // MAP最大Y private const int X_RECT_MIN = 7; // 部屋の最小X = 4 private const int Y_RECT_MIN = 7; // 部屋の最小Y = 4 private const int X_LOAD_MAX = 2; // 部屋と接続するX通路最大数 private const int Y_LOAD_MAX = 2; // 部屋と接続するY通路最大数 private const int FLOOR_MAX = 6; // 最大部屋数 private const int FLOOR_PADDING = 2; // 壁との余白 public enum TYPE { NONE, WALL, FLOOR, LOAD_UP, LOAD_DOWN, LOAD_RIGHT, LOAD_LEFT, LOAD_UP_ALONE, LOAD_LEFT_ALONE, ETC1, ETC2, ETC3, ETC4, ETC5, } public TYPE[,] mapData = new TYPE[X_MAX, Y_MAX]; private List<Rect> rectData = new List<Rect>(); /// <summary> /// 区域クラス /// </summary> public class Rect { public int _r_sx, _r_sy, _r_ex, _r_ey; // 区域の開始,終了座標 public int r_X, r_Y; // 区域のX,Y幅 public int f_sx, f_sy, f_ex, f_ey; // 部屋の開始,終了座標 /// <summary> /// コンストラクタ /// </summary> /// <param name="r_sx">区域の開始x座標</param> /// <param name="r_sy">区域の開始y座標</param> /// <param name="r_ex">区域の終了x座標</param> /// <param name="r_ey">区域の終了y座標</param> public Rect(int r_sx, int r_sy, int r_ex, int r_ey) { this._r_sx = r_sx; this._r_sy = r_sy; this._r_ex = r_ex; this._r_ey = r_ey; this.f_sx = r_sx + FLOOR_PADDING; this.f_sy = r_sy + FLOOR_PADDING; this.f_ex = r_ex - FLOOR_PADDING; this.f_ey = r_ey - FLOOR_PADDING; // 区域幅を計算する this.r_X = r_ex - r_sx; this.r_Y = r_ey - r_sy; } public int r_sx { get { return _r_sx; } set { _r_sx = value; f_sx = value + FLOOR_PADDING; r_X = _r_ex - _r_sx; } } public int r_sy { get { return _r_sy; } set { _r_sy = value; f_sy = value + FLOOR_PADDING; r_Y = _r_ey - _r_sy; } } public int r_ex { get { return _r_ex; } set { _r_ex = value; f_ex = value - FLOOR_PADDING; r_X = _r_ex - _r_sx; } } public int r_ey { get { return _r_ey; } set { _r_ey = value; f_ey = value - FLOOR_PADDING; r_Y = _r_ey - _r_sy; } } } |
そして、実際に分割する処理です。綺麗（偏りなく）に分割していく方法として、以下を入れてみました。
・分割対象は「最も面積が広い区域」
・分割方向は「長さが長い辺」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/// <summary> /// 区域分割 /// </summary> /// <param name="rectData">区域データ</param> private static void MakeRectData(List<Rect> rectData) { // 区域分割 System.Random r; int target = 0; int rect_type = 0; int end_flg = 0; int seed = 0; // 全体区域の作成 rectData.Add(new Rect(0, 0, X_MAX - 1, Y_MAX - 1)); // 区域分割ループ while (true) { r = new System.Random(seed++); // 縦分割 if (rect_type == 0) { if (rectData[target].r_sx + X_RECT_MIN < rectData[target].r_ex - X_RECT_MIN) { int c_x = r.Next(rectData[target].r_sx + X_RECT_MIN, rectData[target].r_ex - X_RECT_MIN); rectData.Add(new Rect(c_x + 1, rectData[target].r_sy, rectData[target].r_ex, rectData[target].r_ey)); rectData[target].r_ex = c_x; } else { end_flg++; } } // 横分割 else { if (rectData[target].r_sy + Y_RECT_MIN < rectData[target].r_ey - Y_RECT_MIN) { int c_y = r.Next(rectData[target].r_sy + Y_RECT_MIN, rectData[target].r_ey - Y_RECT_MIN); rectData.Add(new Rect(rectData[target].r_sx, c_y + 1, rectData[target].r_ex, rectData[target].r_ey)); rectData[target].r_ey = c_y; } else { end_flg++; } } // 分割終了 if ((rectData.Count >= FLOOR_MAX) || (end_flg >= 2)) { break; } // 面積が1番広い部屋を次の分割対象にする int max = 0; for (int i = 0; i < rectData.Count; i++) { int size = rectData[i].r_X * rectData[i].r_Y; if (max < size) { max = size; target = i; // 縦or横分割どちらか判定する if (rectData[i].r_X > rectData[i].r_Y) { // 縦分割 rect_type = 0; } else { // 横分割 rect_type = 1; } } } } } |
② 区域内に部屋を作成する
区域毎に、区域頂点から乱数だけずらした位置に、新たに部屋頂点を作成します。イメージはこんな感じ。
処理イメージもそのまんまです。簡単。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/// <summary> /// 部屋の作成 /// </summary> /// <param name="rectData"></param> /// <param name="mapData"></param> private static void MakeFloorData(List<Rect> rectData, TYPE[,] mapData) { System.Random r; int seed = 0; // 区域毎に部屋頂点を作成する foreach (Rect rect in rectData) { int length_x = rect.r_X - 3; int length_y = rect.r_Y - 3; int expire = 0; int expire_1, expire_2; r = new System.Random(System.DateTime.Now.Millisecond + (++seed)); expire = (length_x > length_y) ? r.Next(0, length_x - 4) : r.Next(0, length_y - 4); // 減少分をどちらから分配するか乱数にする expire_1 = expire - r.Next(0, expire); expire_2 = expire - expire_1; if (length_x > length_y) { rect.f_sx += expire_1; rect.f_ex -= expire_2; } else { rect.f_sy += expire_1; rect.f_ey -= expire_2; } // 部屋を設定する for (int y = rect.f_sy; y <= rect.f_ey; y++) { for (int x = rect.f_sx; x <= rect.f_ex; x++) { mapData[x, y] = TYPE.FLOOR; } } } } |
③ 部屋から区域の境界へ線を伸ばす
部屋毎に、区域の境界線に向かって線を伸ばします。イメージはこんな感じ。
部屋頂点を結んだ線上の任意の点（乱数でずらす）から、区域の境界線に線を伸ばします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
/// <summary> /// 通路作成 /// </summary> /// <param name="rectData"></param> /// <param name="mapData"></param> private static void MakeLoadData(List<Rect> rectData, TYPE[,] mapData) { System.Random r; int seed = 0; // 部屋から区域に向けて線を伸ばす foreach (Rect tmp in rectData) { int load_x = 0, load_y = 0; int load_x_num = 0, load_y_num = 0; // 上方向 load_x = tmp.f_sx + 1; load_x_num = 0; while ((load_x < (tmp.f_ex - 1)) && (load_x_num < X_LOAD_MAX) && (tmp.r_sy != 0)) { r = new System.Random(seed++); load_x = r.Next(load_x, tmp.f_ex - 1); load_x_num++; for (int y = tmp.r_sy; y < tmp.f_sy; y++) mapData[load_x, y] = TYPE.LOAD_UP; load_x += 2; } // 下方向 load_x = tmp.f_sx + 1; load_x_num = 0; while ((load_x < (tmp.f_ex - 1)) && (load_x_num < X_LOAD_MAX) && (tmp.r_ey != Y_MAX - 1)) { r = new System.Random(seed++); load_x = r.Next(load_x, tmp.f_ex - 1); load_x_num++; for (int y = tmp.f_ey + 1; y < tmp.r_ey; y++) mapData[load_x, y] = TYPE.LOAD_DOWN; load_x += 2; } // 左方向 load_y = tmp.f_sy + 1; load_y_num = 0; while ((load_y < (tmp.f_ey - 1)) && (load_y_num < Y_LOAD_MAX) && (tmp.r_sx != 0)) { r = new System.Random(seed++); load_y = r.Next(load_y, tmp.f_ey - 1); load_y_num++; for (int x = tmp.r_sx; x < tmp.f_sx; x++) mapData[x, load_y] = TYPE.LOAD_LEFT; load_y += 2; } // 右方向 load_y = tmp.f_sy + 1; load_y_num = 0; while ((load_y < (tmp.f_ey - 1)) && (load_y_num < Y_LOAD_MAX) && (tmp.r_ex != X_MAX - 1)) { r = new System.Random(seed++); load_y = r.Next(load_y, tmp.f_ey - 1); load_y_num++; for (int x = tmp.f_ex + 1; x < tmp.r_ex; x++) mapData[x, load_y] = TYPE.LOAD_RIGHT; load_y += 2; } } ： |
④ 区域の境界線上の通路を結ぶ
区域の境界線をなめていき、通路が存在する場合、通路から通路へと線を結びます。
処理としては、区域頂点を順番に見て、通路が隣接している場合には、通路と通路の間も通路に変える感じです。（イミフ）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
// 通路と通路を結ぶ foreach (Rect tmp in rectData) { // X方向の精査(下側境界) if (tmp.r_ey != Y_MAX - 1) { int start_x = -1; int end_x = -1; int count_x1 = 0, count_x2 = 0; for (int x = tmp.r_sx; x<tmp.r_ex; x++) { // 上もしくは下に通路があれば処理開始 if (mapData[x, tmp.r_ey - 1] == TYPE.LOAD_DOWN) { count_x1++; end_x = x; } if (mapData[x, tmp.r_ey + 1] == TYPE.LOAD_UP) { count_x2++; end_x = x; } if ((count_x1 > 0 || count_x2 > 0) && (start_x == -1)) { start_x = x; } } if (start_x != -1) { if (count_x1* count_x2 == 0) { mapData[start_x, tmp.r_ey] = TYPE.LOAD_LEFT_ALONE; } else { for (int x = start_x; x <= end_x; x++) mapData[x, tmp.r_ey] = TYPE.LOAD_LEFT; } } } // Y方向の精査(右側境界) if (tmp.r_ex != X_MAX - 1) { int start_y = -1; int end_y = -1; int count_y1 = 0, count_y2 = 0; for (int y = tmp.r_sy; y<tmp.r_ey; y++) { // 左もしくは右に通路があれば処理開始 if (mapData[tmp.r_ex - 1, y] == TYPE.LOAD_RIGHT) { count_y1++; end_y = y; } if (mapData[tmp.r_ex + 1, y] == TYPE.LOAD_LEFT) { count_y2++; end_y = y; } if ((count_y1 > 0 || count_y2 > 0) && (start_y == -1)) { start_y = y; } } if (start_y != -1) { if (count_y1* count_y2 == 0) { mapData[tmp.r_ex, start_y] = TYPE.LOAD_UP_ALONE; } else { for (int y = start_y; y <= end_y; y++) mapData[tmp.r_ex, y] = TYPE.LOAD_UP; } } } } ： |
これでほぼ完成なのですが、画像でいうRect[0]のように、接続する区域の通路がなく、行き止まりになることもあります。行き止まりを許容する場合はここで終わりですが、許容しない場合は次の「⑤」の処理が必要になります。
⑤ 行き止まりの点から他の通路へ接続する
行き止まりの点があれば、行き止まりの通路と垂直方向の直線上に存在する他の通路に接続します。
処理としては、区域頂点を走査していき、行き止まりの点があれば、そこから垂直方向の直線を走査し、通路が見つかれば接続する、という感じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// 行き止まりの場合、伸ばした先に通路があれば伸ばす for (int y = 0; y < Y_MAX; y++) { for (int x = 0; x < X_MAX; x++) { // 左右方向に道がない if (mapData[x, y] == TYPE.LOAD_LEFT_ALONE) { int flg = 0; // 左に伸ばしてみる for (int x2 = x - 1; x2 > 0; x2--) { if (mapData[x2, y] == TYPE.LOAD_LEFT || mapData[x2, y] == TYPE.LOAD_RIGHT) { // そこまでを通路に変える for (int x3 = x2; x3<x; x3++) mapData[x3, y] = TYPE.LOAD_LEFT_ALONE; flg = 1; x2 = 0; break; } } if (flg == 1) continue; // 右に伸ばしてみる for (int x2 = x + 1; x2<X_MAX; x2++) { if (mapData[x2, y] == TYPE.LOAD_LEFT || mapData[x2, y] == TYPE.LOAD_RIGHT) { // そこまでを通路に変える for (int x3 = x; x3<x2; x3++) mapData[x3, y] = TYPE.LOAD_LEFT_ALONE; x2 = X_MAX; break; } } } // 上下方向に道がない if (mapData[x, y] == TYPE.LOAD_UP_ALONE) { int flg = 0; // 上に伸ばしてみる for (int y2 = y - 1; y2 > 0; y2--) { if (mapData[x, y2] == TYPE.LOAD_UP || mapData[x, y2] == TYPE.LOAD_DOWN) { // そこまでを通路に変える for (int y3 = y2; y3<y; y3++) mapData[x, y3] = TYPE.LOAD_UP_ALONE; flg = 1; y2 = 0; break; } } if (flg == 1) continue; // 右に伸ばしてみる for (int y2 = y + 1; y2<Y_MAX; y2++) { if (mapData[x, y2] == TYPE.LOAD_UP || mapData[x, y2] == TYPE.LOAD_DOWN) { // そこまでを通路に変える for (int y3 = y; y3<y2; y3++) mapData[x, y3] = TYPE.LOAD_UP_ALONE; y2 = Y_MAX; break; } } } } } |
これでめでたく、全ての処理が終了になります。お疲れ様でした。
あとがき
っったのしぃっっ
アルゴリズムを作るのは読むより作る方が断然面白いですね。
次はいよいよこのマップデータを組み込んで、実際のマップチップを描画するところまでいこうと思います。それでかなりゲームらしくなりそう。そして凄く順調で良い感じである！年内にゲームできちゃうかも？ｗ
ご購読、ありがとうございました。