アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

迷路生成アルゴリズム(棒倒し法)

迷路生成アルゴリズムの一種で比較的実装の容易な棒倒し法と呼ばれるアルゴリズムを解説します。迷路を生成するアルゴリズムは以下のような種類があります。

• 棒倒し法
• 壁伸ばし法
• 穴掘り法

迷路の定義

まずは迷路の定義を行います。ここで生成される迷路とは、2次元配列に 0 と 1 で構成されます。1 が通れない壁部分で 0 が通れる通路部分を意味します。

1111111
1000001
1010111
1010001
1011101
1010001
1111111

上記のような 7*7 の2次元配列のデータがあったとして、これは次のような迷路を意味します。

禁止事項

迷路は次のような状況にならないように生成します。

1. 外の通路につながらない死に領域(閉じた領域)
2. 通路がループになる

1.の閉じた領域は到達できない領域になってしまい無駄なのでこれは許可しません。2.は同じ場所まで複数の方法で到達できてしまい、難易度が下がるのでこれも許可しない方向で考えます。ループしないなら最短経路も一意に決まります。それぞれの状況は以下のような場合に発生します。

棒倒し法

棒倒し法は以下の手順で迷路を生成します。

1. 迷路全体を構成する2次元配列を、幅高さ5以上の奇数で生成します。
2. 迷路の外周を壁とし、それ以外を通路とします。
3. 外周の内側に基準となる壁(棒)を1セルおき(x, y ともに偶数の座標)に配置します。
4. 内側の壁(棒)を走査し、ランダムな方向に倒して壁とします。(ただし以下に当てはまる方向以外に倒します。)
   • 1行目の内側の壁以外では上方向に倒してはいけない。
   • すでに棒が倒され壁になっている場合、その方向には倒してはいけない。

棒倒し法のシミュレーション

棒倒し法の特徴

棒倒し法で生成された迷路は、必ず上2段の通路で左右両端への通路がつながります。これは上に倒せるのが1段目の壁のみという制約のためです。ほかにもこの上に倒せないという制約が原因で一度下がってから上がるということもあり得ません。また短い行き止まりの通路も多くなってしまいます。

上記のような特徴により、棒倒し法はあまり複雑な迷路は生成できません。何回か生成してみると同じような迷路パターンが見つかるはずです。

サンプルコード

C#

using System;

namespace ConsoleApplication1
{
    public static class MazeGenerator_Bar
    {
        // 通路・壁情報
        const int Path = 0;
        const int Wall = 1;

        // 棒倒し法による迷路生成
        public static int[,] GenerateMaze(int width, int height)
        {
            // 5未満のサイズでは生成できない
            if (height < 5 || width < 5) throw new ArgumentOutOfRangeException();
            if (width % 2 == 0) width++;
            if (height % 2 == 0) height++;

            // 指定サイズで生成し外周を壁にする
            var maze = new int[width, height];
            for (int x = 0; x < width; x++)
                for (int y = 0; y < height; y++)
                    if (x == 0 || y == 0 || x == width - 1 || y == height - 1)
                        maze[x, y] = Wall; // 外周はすべて壁
                    else
                        maze[x, y] = Path;  // 外周以外は通路

            // 棒を立て、倒す
            var rnd = new Random();
            for (int x = 2; x < width - 1; x += 2)
            {
                for (int y = 2; y < height - 1; y += 2)
                {
                    maze[x, y] = Wall; // 棒を立てる

                    // 倒せるまで繰り返す
                    while (true)
                    {
                        // 1行目のみ上に倒せる
                        int direction;
                        if (y == 2)
                            direction = rnd.Next(4);
                        else
                            direction = rnd.Next(3);

                        // 棒を倒す方向を決める
                        int wallX = x;
                        int wallY = y;
                        switch (direction)
                        {
                            case 0: // 右
                                wallX++;
                                break;
                            case 1: // 下
                                wallY++;
                                break;
                            case 2: // 左
                                wallX--;
                                break;
                            case 3: // 上
                                wallY--;
                                break;
                        }
                        // 壁じゃない場合のみ倒して終了
                        if (maze[wallX, wallY] != Wall)
                        {
                            maze[wallX, wallY] = Wall;
                            break;
                        }
                    }
                }
            }
            return maze;
        }

        // デバッグ用メソッド
        public static void DebugPrint(int[,] maze)
        {
            Console.WriteLine($"Width: {maze.GetLength(0)}");
            Console.WriteLine($"Height: {maze.GetLength(1)}");
            for (int y = 0; y < maze.GetLength(1); y++)
            {
                for (int x = 0; x < maze.GetLength(0); x++)
                {
                    Console.Write(maze[x, y] == Wall ? "■" : "　");
                }
                Console.WriteLine();
            }
        }
    }
}