はじめに
前回の「穴掘り法」は、どちらかというと迷路の生成アルゴリズムだったのですが、今回は「不思議のダンジョン」のような部屋が存在するダンジョンを自動生成するアルゴリズムの実装方法を紹介します。
サンプル
実装サンプルはこちらで確認できます。
「もう１回」ボタンを押すごとに、ダンジョンが自動生成されます。こちらのページからUnity2Dで実装したプロジェクトがダウンロードできます。なおソースコードは自由に使って頂いて問題ありません。
実装方法
アルゴリズムのフロー
アルゴリズムのフローとしては以下のようになります。
1. 初期化 (2次元配列作成・区画リスト作成)
2. すべてを壁にする
3. マップサイズで最初の区画を作る
4. 区画を分割していく
5. 区画内に部屋を作る
6. 部屋同士をつなげる通路を作る
図にすると以下のようになります。
データ構造
データ構造は以下のように設計しました
- 自動生成管理クラス DgGenerator
- 2次元配列 Layer2D
- 区画情報管理 : DgDivision
- 外周情報(矩形) : Outer(DgRect)
- 部屋情報(矩形) : Room(DgRect)
DgGeneratorがすべての管理をしていて、それにLayer2Dや区画情報であるDgDivisionがぶら下がるイメージです。DgRectは単なる矩形情報を保持したクラスです。
2次元配列 (Layer2D)
まずは2次元配列管理クラスであるLayer2Dです。
using UnityEngine;
using System.Collections;
/// 2次元レイヤー
public class Layer2D
{
int _width; // 幅
int _height; // 高さ
int _outOfRange = -1; // 領域外を指定した時の値
int[] _values = null; // マップデータ
/// 幅
public int Width
{
get { return _width; }
}
/// 高さ
public int Height
{
get { return _height; }
}
/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="width"></param>
/// <param name="height"></param>
public Layer2D(int width = 0, int height = 0)
{
if (width > 0 && height > 0)
{
Create(width, height);
}
}
/// 作成
public void Create(int width, int height)
{
_width = width;
_height = height;
_values = new int[Width * Height];
}
/// 座標をインデックスに変換する
public int ToIdx(int x, int y)
{
return x + (y * Width);
}
/// 領域外かどうかチェックする
public bool IsOutOfRange(int x, int y)
{
if (x < 0 || x >= Width) { return true; }
if (y < 0 || y >= Height) { return true; }
// 領域内
return false;
}
/// <summary>
/// 値の取得
/// </summary>
/// <param name="x">X座標</param>
/// <param name="y">Y座標</param>
/// <returns>指定の座標の値（領域外を指定したら_outOfRangeを返す）</returns>
public int Get(int x, int y)
{
if (IsOutOfRange(x, y))
{
return _outOfRange;
}
return _values[y * Width + x];
}
/// 値の設定
// @param x X座標
// @param y Y座標
// @param v 設定する値
public void Set(int x, int y, int v)
{
if (IsOutOfRange(x, y))
{
// 領域外を指定した
return;
}
_values[y * Width + x] = v;
}
/// <summary>
/// すべてのセルを特定の値で埋める
/// </summary>
/// <param name="val">埋める値</param>
public void Fill(int val)
{
for (int j = 0; j < Height; j++)
{
for (int i = 0; i < Width; i++)
{
Set(i, j, val);
}
}
}
/// <summary>
/// 矩形領域を指定の値で埋める
/// </summary>
/// <param name="x">矩形の左上(X座標)</param>
/// <param name="y">矩形の左上(Y座標)</param>
/// <param name="w">矩形の幅</param>
/// <param name="h">矩形の高さ</param>
/// <param name="val">埋める値</param>
public void FillRect(int x, int y, int w, int h, int val)
{
for (int j = 0; j < h; j++)
{
for (int i = 0; i < w; i++)
{
int px = x + i;
int py = y + j;
Set(px, py, val);
}
}
}
/// <summary>
/// 矩形領域を指定の値で埋める（4点指定)
/// </summary>
/// <param name="left">左</param>
/// <param name="top">上</param>
/// <param name="right">右</param>
/// <param name="bottom">下</param>
/// <param name="val">埋める値</param>
public void FillRectLTRB(int left, int top, int right, int bottom, int val)
{
FillRect(left, top, right - left, bottom - top, val);
}
/// デバッグ出力
public void Dump()
{
Debug.Log("[Layer2D] (w,h)=(" + Width + "," + Height + ")");
for (int y = 0; y < Height; y++)
{
string s = "";
for (int x = 0; x < Width; x++)
{
s += Get(x, y) + ",";
}
Debug.Log(s);
}
}
}
生の2次元配列を使ってもいいのですが、管理を楽にするためこのようなクラスを用意しました。
区画情報 / 矩形情報 (DgDivision / DgRect)
次に区画情報であるDgDivisionクラスと、矩形であるDgRectクラスです。DgRectは単なる矩形です。DgDivisionは、DgRectをメンバ変数に持つデータクラスです。外周（区画）情報と、その内部に作成する部屋を矩形情報として保持しています。
using UnityEngine;
using System.Collections;
/// <summary>
/// ダンジョン区画情報
/// </summary>
public class DgDivision
{
/// <summary>
/// 矩形管理
/// </summary>
public class DgRect
{
public int Left = 0; // 左
public int Top = 0; // 上
public int Right = 0; // 右
public int Bottom = 0; // 下
/// <summary>
/// コンストラクタ
/// </summary>
public DgRect()
{
// 特に何もしない
}
/// <summary>
/// 値をまとめて設定する
/// </summary>
/// <param name="left">左</param>
/// <param name="top">上</param>
/// <param name="right">右</param>
/// <param name="bottom">左</param>
public void Set(int left, int top, int right, int bottom)
{
Left = left;
Top = top;
Right = right;
Bottom = bottom;
}
/// <summary>
/// 幅
/// </summary>
public int Width
{
get { return Right - Left; }
}
/// <summary>
/// 高さ
/// </summary>
public int Height
{
get { return Bottom - Top; }
}
/// <summary>
/// 面積 (幅 x 高さ)
/// </summary>
public int Measure
{
get { return Width * Height; }
}
/// <summary>
/// 矩形情報をコピーする
/// </summary>
/// <param name="rect">コピー元の矩形情報</param>
public void Copy(DgRect rect)
{
Left = rect.Left;
Top = rect.Top;
Right = rect.Right;
Bottom = rect.Bottom;
}
/// <summary>
/// デバッグ出力
/// </summary>
public void Dump()
{
Debug.Log(string.Format("<Rect l,t,r,b = {0},{1},{2},{3}> w,h = {4},{5}",
Left, Top, Right, Bottom, Width, Height));
}
}
/// <summary>
/// 外周の矩形情報
/// </summary>
public DgRect Outer;
/// <summary>
/// 区画内に作ったルーム情報
/// </summary>
public DgRect Room;
/// <summary>
/// コンストラクタ
/// </summary>
public DgDivision()
{
Outer = new DgRect();
Room = new DgRect();
}
/// <summary>
/// デバッグ出力
/// </summary>
public void Dump()
{
Outer.Dump();
Room.Dump();
}
}
ダンジョン生成 (DgGenerator)
最後にダンジョン生成クラスです。
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
/// <summary>
/// ダンジョンの自動生成モジュール
/// </summary>
public class DgGenerator : MonoBehaviour
{
/// <summary>
/// 2次元配列情報
/// </summary>
Layer2D _layer = null;
/// <summary>
/// 区画リスト
/// </summary>
List<DgDivision> _divList = null;
}
このクラスはいくつか定数を持たせているのですが、必要なデータのみに省略してコードを乗せました。2次元配列のLayer2Dを持たせ、区画情報であるDgDivisionをListで保持するようにしています。
アルゴリズム説明
データ構造の説明が終わったので、アルゴリズムの説明です。
フローは以下のようになっていました。
1. 初期化 (2次元配列作成・区画リスト作成)
2. すべてを壁にする
3. マップサイズで最初の区画を作る
4. 区画を分割していく
5. 区画内に部屋を作る
6. 部屋同士をつなげる通路を作る
これらを細かく説明します。
1〜3. の説明
DgGenerator.csのStart関数は以下のようになっています。
void Start()
{
// ■1. 初期化
// 2次元配列初期化
_layer = new Layer2D(WIDTH, HEIGHT);
// 区画リスト作成
_divList = new List<DgDivision>();
// ■2. すべてを壁にする
_layer.Fill(CHIP_WALL);
// ■3. 最初の区画を作る
CreateDivision(0, 0, WIDTH - 1, HEIGHT - 1);
// ■4. 区画を分割する
// 垂直 or 水平分割フラグの決定
bool bVertical = (Random.Range(0, 2) == 0);
SplitDivison(bVertical);
// ■5. 区画に部屋を作る
CreateRoom();
// ■6. 部屋同士をつなぐ
ConnectRooms();
1と2はそのままですね。3 (CreateDivision関数)では区画情報を作成し、リストの先頭に登録しています。幅と高さから「-1」して引数として渡しているのは、実際の右や下の位置は「-1」された値となるためです。
void CreateDivision(int left, int top, int right, int bottom)
{
DgDivision div = new DgDivision();
div.Outer.Set(left, top, right, bottom);
_divList.Add(div);
}
4. 区画の分割
大きな区画ができたので、この区画を分割していきます。
分割は以下のルールで行います。
- 分割した2つの区画のどちらかをさらに分割する
- 水平方向・垂直方向の分割を交互に行う
具体的には以下の手順となります。
まず区画を分割する方向をランダムで決めます。今回は垂直から始めることにしました。その場合は区画の左(a)と右(b)の間から、分割するポイント(p)をランダムで決めます。ただし分割の最小単位となる部屋サイズや余白などの制限を考慮します。この制限は後々のステップとなる「部屋」や「通路」の作成に必要となるためです。
ソースコードだと以下の部分ですね。
// ▼縦方向に分割する
if (CheckDivisionSize(parent.Outer.Height) == false)
{
// 縦の高さが足りない
// 親区画を戻しておしまい
_divList.Add(parent);
return;
}
// 分割ポイントを求める
int a = parent.Outer.Top + (MIN_ROOM + OUTER_MERGIN);
int b = parent.Outer.Bottom - (MIN_ROOM + OUTER_MERGIN);
// AB間の距離を求める
int ab = b - a;
// 最大の部屋サイズを超えないようにする
ab = Mathf.Min(ab, MAX_ROOM);
// 分割点を決める
int p = a + Random.Range(0, ab + 1);
// 子区画に情報を設定
child.Outer.Set(
parent.Outer.Left, p, parent.Outer.Right, parent.Outer.Bottom);
// 親の下側をp地点まで縮める
parent.Outer.Bottom = child.Outer.Top;
分割ルールでは「分割した2つの区画のどちらかをさらに分割する」とあるので、以下のように分割します。
ここでは右側の区画を分割することにしました。また分割方向は交互に行うので、横分割となっています。ソースコードでは、分割対象となる区画を divList の末尾にある要素としています。これにより、最後に分割した区画をさらに分割する、という動作となります。
/// <summary>
/// 区画を分割する
/// </summary>
/// <param name="bVertical">垂直分割するかどうか</param>
void SplitDivison(bool bVertical)
{
// 末尾の要素を取り出し
DgDivision parent = _divList[_divList.Count - 1];
_divList.Remove(parent);
そうして分割を繰り返した結果が以下のような図となります。
そして区画リストの末尾が分割できなくなったら、分割処理は終了となります。
5. 区画内に部屋を作る
部屋を作る処理は、区画のサイズから余白（通路をつくるためのサイズ）を引いて、そこからランダムのサイズを決定して、左上をずらしているだけです。
// 基準サイズを決める
int dw = div.Outer.Width - OUTER_MERGIN;
int dh = div.Outer.Height - OUTER_MERGIN;
// 大きさをランダムに決める
int sw = Random.Range(MIN_ROOM, dw);
int sh = Random.Range(MIN_ROOM, dh);
// 最大サイズを超えないようにする
sw = Mathf.Min(sw, MAX_ROOM);
sh = Mathf.Min(sh, MAX_ROOM);
// 空きサイズを計算 (区画 - 部屋)
int rw = (dw - sw);
int rh = (dh - sh);
// 部屋の左上位置を決める
int rx = Random.Range(0, rw) + POS_MERGIN;
int ry = Random.Range(0, rh) + POS_MERGIN;
int left = div.Outer.Left + rx;
int right = left + sw;
int top = div.Outer.Top + ry;
int bottom = top + sh;
// 部屋のサイズを設定
div.Room.Set(left, top, right, bottom);
// 部屋を通路にする
FillRoom(div.Room);
6. 部屋同士をつなげる通路を作る
最後に部屋同士をつなげます。
これは以下の手順で行います。
1. 隣接する部屋を選ぶ
2. 部屋から通路を伸ばす場所をランダムで決める
3. それぞれの部屋から、通路を外周の位置まで伸ばす
4. 伸ばした先を外周にそって接続する通路を作る
1については、divListの前後は隣接していることが保証されています。なのでdivListの前後となる区画を選ぶようにしています。
/// <summary>
/// 部屋同士を通路でつなぐ
/// </summary>
void ConnectRooms()
{
for (int i = 0; i < _divList.Count - 1; i++)
{
// リストの前後の区画は必ず接続できる
DgDivision a = _divList[i];
DgDivision b = _divList[i + 1];
// 2つの部屋をつなぐ通路を作成
CreateRoad(a, b);
}
}
2はそれぞれの部屋のサイズから通路を伸ばす位置を決めます。
決まったら、区画の外周まで通路を伸ばします。そして外周にそって通路を接続すれば、2つの部屋を接続する通路ができあがります。
課題
これでダンジョンの自動生成は完了しましたが 通路が一本道となってしまっている という課題があります。解決法としては、子だけでなく、孫の区画にも接続します。孫の区画は隣接していれば、必ず子の区画と同じ方向から接続できます。そして孫へ接続する場合は、親の通路は引かずに、孫の区画のみ通路を作成する、などの工夫をします。
サンプルコード・改良版
一本道とならないようにしたサンプルコードを作成しました
プロジェクトファイルもこちらからダウンロードできます。
部屋をより多く作る方法
分割する区画は、分割した区画からランダムで選ぶとしましたが、区画の面積を比較して大きい方を次の分割対象とすると、より多くの部屋が作られやすくなります。