穴掘り法によるダンジョンの自動生成 (Unity2Dのサンプルコードつき)

はじめに

ダンジョンの自動生成では、最もお手軽と思われる穴掘り法を解説します。

サンプル

Unity2Dで実装したサンプルはこちらです。
http://2dgames.jp/unity/anahori/
プロジェクトファイルもついています。

メリットとデメリット

メリット

穴掘り法によるダンジョンのメリットは以下のとおりです

• 実装が簡単
• 通路のどこに入り口と出口を置いても必ずつながる
  • 袋小路が作られることがない

穴掘り法を使うメリットとしては「アルゴリズムが簡単」です。実装のためのプログラムコードとしては100行もかかりませんので、だいたい1時間もあれば実装できます。
また、通路がすべてつながっているので、通路内であれば入り口と出口をどこに置いても必ずつながります。

デメリット

サンプルを確認するとわかるのですが、穴掘り法は「不思議なダンジョンシリーズ」のように、大きな空間を持った「部屋」を作ることができません。そのため多くの敵に囲まれたりする、といったゲーム性を持つダンジョンには向いていません。そのため、穴掘り法を使う場合は、敵との戦闘はシンボルエンカウントやランダムエンカウントを採用して、ダンジョンと戦闘を切り離したゲームデザインにするとよいかもしれません。

穴掘り法の実装

穴掘り法の実装を箇条書きで記述すると以下のとおりです

1. 2次元配列を用意する
2. 配列の値はすべて「壁」に設定する
3. 開始地点を決める
4. 穴掘り開始
  ⅰ. 開始基準地点を「通路」に設定する
  ⅱ. 4方向をランダムな順番にチェックする
  ⅲ. チェックする方向の2マス先が「壁」であれば以下の処理を行う
    a. チェックした方向の1マス先を「通路」に設定する
    b. 2マス先を開始基準点として 『4. 穴掘り開始』を呼び出す

これでダンジョンが自動生成できます。「b.」の処理ですが、「4.」を再帰呼び出しするのがポイントとなります。

注意点

穴掘り法の注意点は以下の2つです

• ダンジョンの幅と高さは「奇数」にする
• 開始座標は「偶数」にする

これらのルールを守らなくてもダンジョンは作れますが、守らなかった場合は1マス分の余計な壁が作られることとなります。

C#での実装例

UnityのC#で実装した例は以下のようになります。

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

/// 穴掘りアルゴリズム
public class Anahori : MonoBehaviour
{

  /// 2次元レイヤー
  class Layer2D
  {
    int _width; // 幅.
    int _height; // 高さ.
    int _outOfRange = -1; // 領域外を指定した時の値.
    int[] _values = null; // マップデータ.
    /// 幅.
    public int Width {
      get { return _width; }
    }
    /// 高さ.
    public int Height {
      get { return _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;
    }
    /// 値の取得.
    // @param x X座標.
    // @param y Y座標.
    // @return 指定の座標の値（領域外を指定したら_outOfRangeを返す）.
    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;
    }

    /// 特定の値をすべてのセルに設定する.
    public void Fill (int v)
    {
      for (int y = 0; y < Height; y++) {
        for (int x = 0; x < Width; x++) {
          Set (x, y, v);
        }
      }
    }

    /// デバッグ出力.
    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);
      }
    }
  }

  /// チップ定数
  const int CHIP_NONE = 0; // 通過可能
  const int CHIP_WALL = 1; // 通行不可

  /// 穴掘り開始
  void Start ()
  {
    // ダンジョンを作る
    var layer = new Layer2D ();
    // ダンジョンの幅と高さは奇数のみ
    layer.Create (10 + 1, 8 + 1);
    // すべて壁を埋める
    layer.Fill(CHIP_WALL);

    // 開始地点を決める
    int xstart = 2; // 開始地点は偶数でないといけない
    int ystart = 4; // 開始地点は偶数でないといけない

    // 穴掘り開始
    _Dig (layer, xstart, ystart);

    // 結果表示
    layer.Dump ();
  }

  /// 穴を掘る
  void _Dig (Layer2D layer, int x, int y)
  {
    // 開始地点を掘る
    layer.Set(x, y, CHIP_NONE);

    Vector2[] dirList = {
      new Vector2 (-1, 0),
      new Vector2 (0, -1),
      new Vector2 (1, 0),
      new Vector2 (0, 1)
    };
    
    // シャッフル
    for (int i = 0; i < dirList.Length; i++) {
        var tmp = dirList [i];
        var idx = Random.Range (0, dirList.Length - 1);
        dirList [i] = dirList [idx];
        dirList [idx] = tmp;
    }

    foreach (var dir in dirList) {
      int dx = (int)dir.x;
      int dy = (int)dir.y;
      if (layer.Get (x + dx * 2, y + dy * 2) == 1) {
        // 2マス先が壁なので掘れる
        layer.Set(x+dx, y+dy, CHIP_NONE);

        // 次の穴を掘る
        _Dig(layer, x + dx*2, y + dy*2);
      }
    }
  }
}

サンプルでは開始位置をランダムにしていませんが、ランダムにすると生成のバリエーションが増えますので、ランダムにしておいたほうがよいです。また、Layer2Dというのは2次元配列管理用のクラスとなります。こういったクラスを用意しておくと領域外チェックが簡略化できます。

参考

• ActionScript入門Wiki - 迷路自動生成(穴掘り法編)
  • http://www40.atwiki.jp/spellbound/pages/284.html