ALG 部屋付き迷路の自動作成 : プログラミング指南

ゲームでよく使われる迷路自動生成の考え方の解説です。今回はペンゴのゲーム開始で有名な穴掘り法と呼ばれる方法で解説します。あと、最後に部屋も配置してしまいましょうか。説明を簡単にするため、二次元配列を用います。-1 なら壁です。説明は C言語で進めます。では始めましょう！

初期化

最初に迷路のサイズを決めます。周囲を壁が囲む必要がありますので、迷路のサイズは必ず奇数になります。偶数を設定すると、右端と下端が無駄になります。迷路サイズは自由に後から変えられるようにdefineで定義します。あと、二次元配列はグローバルに配置することにします。

交差点から穴を掘り続ける^※後述ため、その交差点の位置を保存する配列も用意します。交差点から掘るので名称は起点とします。位置を示すのは Point構造体としたほうが便利なので、それも定義してしまいます。


// 迷路のサイズ
#define MAZE_WIDTH  39      // 迷路の幅　 ※奇数必須
#define MAZE_HEIGHT 25      // 迷路の高さ ※奇数必須
#define MAX_ORIGINS ((MAZE_WIDTH / 2) * (MAZE_HEIGHT / 2))  // 起点総数

// 穴掘り起点リスト
struct TPoint
{
    int X;  // X座標
    int Y;  // Y座標
};
typedef struct TPoint   Point;
Point Origins[MAX_ORIGINS];

// 迷路
int Maze[MAZE_HEIGHT][MAZE_WIDTH];

X列がY行存在するという意味で、配列は Y,X の順番とします。感覚的ではないのですが、メモリの配置順的にはこちらが順当ではないかと。以下の黄色の場所が起点となります。

起点位置の総数は迷路幅の半分×迷路高さの半分です。
※ 各方向毎に小数点以下を捨てる必要があるので define 定義に括弧が必要です。

グローバル変数の初期化がこちら。


void InitMaze(void)
{
    srand((unsigned)time(NULL));
    memset(Maze, -1, MAZE_WIDTH * MAZE_HEIGHT * sizeof(int));

    // 起点テーブルを作成
    int idx = 0;
    for (int x = 1; x < MAZE_WIDTH - 1; x += 2)
    {
        for (int y = 1; y < MAZE_HEIGHT - 1; y += 2)
        {
            Point pos = { x, y };
            Origins[idx++] = pos;
        }
    }

    // シャッフルする
    int max = MAX_ORIGINS / 2 + rand() % MAX_ORIGINS;
    for (int i = 0; i < max; ++i)
    {
        int a = rand() % MAX_ORIGINS;
        int b = rand() % MAX_ORIGINS;
        Point tmp = Origins[a];
        Origins[a] = Origins[b];
        Origins[b] = tmp;
    }
}

最初に時間で乱数を初期化します。迷路の状態を示す Maze 二次元配列を、memset を使って -1 で埋め尽くします。続いて起点の全て位置をテーブルに作成します。

最後に起点テーブルをシャッフルします。実はシャッフルしなくてもかなりランダムな迷路にはなるのですが、若干左上側に偏りが見られたので簡単にシャッフルしています。興味があればシャッフルをコメントアウトして違いを確認してみてください。
※ おそらく殆ど変わらないとは思います。

まとめます。

二次元配列を確保する
壁で配列を埋め尽くす
交差点部分を起点テーブルとして作成する

関数を作る

迷路作成の処理の前に必要となるだろう関数を先に作っておきます。まず、何はなくとも迷路の表示です。今回はコンソール出力で考えます。二次元配列で -1 なら赤色、 0 なら黒色で全角スペースを表示するだけで出来ます。途中経過も表示できるように、表示の際は毎回左上にカーソル位置が戻るようにします。


void DrawMaze(void)
{
    printf(LOCATE, 1, 1);
    for (int y = 0; y < MAZE_HEIGHT; ++y)
    {
        for (int x = 0; x < MAZE_WIDTH; ++x)
        {
            printf("%s　", Maze[y][x] < 0 ? BRED : BBLACK);
        }
        printf("\n");
    }
    printf(ATBCLEAR);
}

特に説明は要らないですよね。あと、その場所が掘れる場所か…つまりはそこは壁かという確認関数も用意します。二次元配列範囲外と最外周隣接箇所は穴を掘られると困るので、壁ではないと返却します。場所の引数は Point 構造体とします。


bool IsWall(Point pos)
{
    return true
        && pos.X > 0
        && pos.Y > 0
        && pos.X < MAZE_WIDTH - 1
        && pos.Y < MAZE_HEIGHT - 1
        && Maze[pos.Y][pos.X] < 0;
}

最初に掘れる範囲外なら false で返却します。続いてその場所の値が -1（壁）なら true で返却します。

最後に以下は自分の位置から方向に応じて座標を変化させる関数です。自分の周辺に穴が掘れるかどうかチェックする際に、方向を与えると座標が変化する関数があると便利です。


Point GetNextPosition(Point pos, int dir, int len = 1)
{
    // 右を起点に時計方向回り
    switch (dir)
    {
    case 0: pos.X += len; break;
    case 1: pos.Y += len; break;
    case 2: pos.X -= len; break;
    case 3: pos.Y -= len; break;
    }
    return pos;
}

交差点まで距離は 2 ですが、穴を開ける祭は隣りのマスとなるので、引数で移動量を指定できるようにしてみました。方向は右方向を基準として、右回りに右下左上という順としています。

【Amazon】
8BitDo Lite 2 Switch、Switch Lite、Android、Raspberry Pi（ピンク）用のBluetoothゲームパッド

8Bitdo

※ 女性にオススメの小さなSwitch Liteっぽいデザインのコントローラ。使い勝手はとても良さそうです。

通路を掘る
通路はランダムな閉鎖空間から始めて、最後に閉鎖空間以外に繋がったら、次の閉鎖空間を求めて、最後に閉鎖空間が無くなるまで堀り続けます。通路を掘る関数の全体がこちら。


void CreatePass(void)
{
    Maze[Origins[0].Y][Origins[0].X] = 0;
    for (int idx = 0; idx < MAX_ORIGINS; ++idx)
    {
        Point pos = Origins[idx];
        if (IsWall(pos)) continue;

        while (true)
        {
            int dir = rand() % 4;
            int cnt = 0;
            while (cnt < 4)
            {
                Point chkPos = GetNextPosition(pos, dir, 2);
                if (IsWall(chkPos)) break;
                dir = (dir + 1) % 4;
                ++cnt;
            }
            if (cnt >= 4) break;

            pos = GetNextPosition(pos, dir);
            Maze[pos.Y][pos.X] = 0;

            pos = GetNextPosition(pos, dir);
            Maze[pos.Y][pos.X] = 0;

            idx = 0;
        }
    }
}

初期化時に、交差点座標をシャッフルして格納した起点テーブルを作っています。そのため、起点テーブルの一番最初がスタートとなります、スタート地点は無条件で穴を空けます。


    Maze[Origins[0].Y][Origins[0].X] = 0;

この起点位置全てに穴が開けば迷路は完成したことになります。起点テーブル Origins の 0 から MAX_ORIGINS - 1 までをループして、穴があればその穴からさらに掘り進めることが出来るかどうかを確認していきます。起点テーブルを参照するインデックス変数は idx としました。


    for (int idx = 0; idx < MAX_ORIGINS; ++idx)
    {
        Point pos = Origins[idx];
        if (IsWall(pos)) continue;

idx を添え字として起点テーブル Origins から座標 pos を取得して、それを IsWall 関数で穴が空いているかどうかを確認します。壁なら次の添字とします。アルゴリズム的には穴を伸ばしていく処理なので、壁に新規に穴を開けるとおかしくなってしまうためです。


    int dir = rand() % 4;

方向は右下左上の 4種類です。偏りをなるべく防ぎたいので最初に確認する方向はランダムで決めています。for でループを回しても良かったんですが、ループ終了時に cnt の値をチェックしたいので、while ループとしました。


    int cnt = 0;
    while (cnt < 4)
    {
        Point chkPos = GetNextPosition(pos, dir, 2);
        if (IsWall(chkPos)) break;
        dir = (dir + 1) % 4;
        ++cnt;
    }
    if (cnt >= 4) break;

現在の位置 pos から dir の方向に 2 マスズレた位置を取り出します。この場所が壁なら掘るのでループを終了します。穴なら、次の方向を確かめるため dir を更新します。 +1 してから 4 の余りを求めることで 0,1,2,3 の繰り返しループとなっています。ループ終了時に cnt が 4 以上（実際には 4 しかこない）なら、全ての方向に穴があるので、次の起点チェックに移行するため、穴掘りループを脱出します。

これで穴を掘る方向がわかったので、実際に掘っていきます。


    pos = GetNextPosition(pos, dir);
    Maze[pos.Y][pos.X] = 0;

    pos = GetNextPosition(pos, dir);
    Maze[pos.Y][pos.X] = 0;

現在地から指定方向に 1マス移動して 0 を入れて穴を掘ります。もう一度指定方向に移動して、もう一度穴を掘ります。これで通路が延長されました。新たな延長となったので、起点テーブル参照を 0 に戻します。


    idx = 0;

ここを 0 に戻さないと、時々掘り残しが起きます。0 に戻さないと掘り残しが起きる可能性がある代わりに、迷路作成（穴掘り）はとても高速になります。今時のマシンなら全く問題にならないのですが、1980年代のマシンだと、あえて掘り残しを許容するのもありかもしれません。

あとは、穴掘り延長と、新たな分岐穴掘りを続けて、
起点テーブルを参照して新た

全ての起点位置に穴が空いたら迷路作成の完成となります。
全ての起点に穴が空いたので

事前に便利関数を用意したので、迷路作成の処理がとても簡易化されたのが分かるかと思います。

まとめます。

最初の起点位置に穴を開ける
ランダムな方向に通路を延長する
通路が延長できなくなったら次の起点位置を確認する
全ての起点位置に穴が空いていたら迷路作成を終了する

【Amazon】
JUTOSU Free McBoot FMCB PS2 メモリーカード 64MB Sony Playstation 2用v1.966 64MB 収納カードゲーム起動メモリカードポータブル PS2 Playstation 2 専用メモリーカード

JUTOSU

※ FMCBは自分でメモカに焼けば作りますが、64MBの容量はなかなか持ってないと思います。このサイズならセーブデータはかなり沢山入るので一つ持っていると良いかと。ちなみに256MBタイプを持っていますが、使えませんでした…

部屋を作る

部屋の作成ですが、部屋同士が重なる事を許すか許さないかで、少々話が変わります。部屋同士が重なる場合は、特に意識せず全体サイズより小さい部屋サイズを指定すれば良いですが、重なりを禁止する場合は指定の仕方によっては、延々と配置できる場所を探し続けて無限ループを引き起こす可能性があります。今回は、部屋の重なりは重要ではないので、重なってもOKとします。
※ タイムアウトを設けるなどして、基本的には無限ループを起こさないコードを記述するクセを付けましょう。

部屋の大きさは、最小サイズと最大サイズを引数で与えましょうか。あと、部屋の個数も指定します。折角(?)なので、これもランダムにしてしまいます。まずは呼び出し側から


    int roomMinimum   = MAZE_WIDTH  / 10;
    int roomMaxWidth  = MAZE_WIDTH  / 4;
    int roomMaxHeight = MAZE_HEIGHT / 4;
    int roomCount     = rand() % 6 + 3;
    CreateRoom(roomMaxWidth, roomMaxHeight, roomMinimum, roomCount);

部屋の最大サイズは全体サイズの 1/4、一番小さいサイズが 1/10、部屋の数は 3～8 としました。これを部屋作成の関数 CreateMaze に引数を入れて呼び出します。CreateMaze は指定の数だけループして部屋を作っていくことになります。


    for (int i = 0; i < count; ++i)
    {
        int w = (rand() % (width - min) + min)  / 2 * 2 + 1;
        int h = (rand() % (height - min) + min) / 2 * 2 + 1;
        int x = rand() % (MAZE_WIDTH - w)  / 2 * 2 + 1;
        int y = rand() % (MAZE_HEIGHT - h) / 2 * 2 + 1;
        for (int yy = y; yy < y + h; ++yy)
        {
            for (int xx = x; xx < x + w; ++xx)
            {
                Maze[yy][xx] = 0;
            }
        }
    }

ポイントとしては、ランダムに決定される左上の座標と部屋のサイズも、必ず奇数になるように調整することです。偶数が出ると壁を崩すことになるので好ましくありません。
※ 偶数混じりの部屋があったほうが楽しいかもしれません…

まとめます。

適切な部屋のサイズと個数を決める
ランダムな位置にランダムなサイズで四角く穴を開ける

あとがき

これで広場がある全てが繋がった迷路を作ることが出来ました。部屋の作成はオマケみたいなものですから、実装はあってもなくても構いません。今回の部屋の配置では、折角作った通路を分断しますので、ループする通路が出来ます。私はループはあっても良いと思ってる派ですが、それが許せないヒトもいるのではないでしょうか。その場合は部屋を先に作ってから通路を伸ばす作り方が良いです。

ただ、今回紹介したアルゴリズムのまま部屋を先に作ってしまうと、各部屋毎に独立した空間となる可能性が高いので、このままのアルゴリズムでは作れません。最初に部屋を作るのであれば、その後に部屋通しの連絡通路を専用で掘って、各部屋を確実に繋げてから、新規に穴を空けずに迷路の通路掘りを実行すると良いでしょう。この処理に関しては皆様への宿題とします。

今回次の方向を決定する際にランダムからの右回り固定となっていますが、ここは右回りだけではなく左回りもあったほうが偏りは減るかもしれません。今回はアルゴリズム説明用に極力処理を簡素化しています。進行方向に対して左右判定とか、少しだけ拘ると微妙な違いが出るかもです。

迷路作成は今まで多くの人が様々なアルゴリズムを開発してきました。それぞれには代表的なアルゴリズムの名前がついています。私が今回紹介した方法は穴掘り法と呼ばれているようです。他には壁伸ばし法であるとか、棒倒し法であるとか。迷路作成もなかなか奥が深いと思いますので、たまにチャレンジすると面白いかもしれません。

あと、今回は純然たる C言語で記述してみました。さほど難しい書き方をしていないので、C言語022 三項演算子までを読み解ける人であれば、サンプルも読めると思いますので参考にしてみてください。
※ memset は調べる必要はあるかも…

サンプルのダウンロード

ProjectMaze

2022.03.16