迷路生成アルゴリズム(穴掘り法)

迷路を生成するアルゴリズムは以下のような種類があります。ここでは穴掘り法と呼ばれるアルゴリズムを解説します。穴掘り法は文字通り、穴(通路)を掘り進めることで迷路を生成します。壁を伸ばす壁伸ばし法と対照的なアルゴリズムです。

迷路の定義

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

1111111
1000001
1010111
1010001
1011101
1010001
1111111

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

壁壁壁壁壁壁壁
壁道道道道道壁
壁道壁壁壁壁壁
壁道道道道道壁
壁道壁道壁壁壁
壁道壁道道道壁
壁壁壁壁壁壁壁

禁止事項

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

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

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

壁壁壁壁壁
壁道壁道壁
壁道壁壁壁
壁道道道壁
壁壁壁壁壁
壁壁壁壁壁
壁道道道壁
壁道壁道壁
壁道道道壁
壁壁壁壁壁

穴掘り法

穴掘り法は以下の手順で迷路を生成します。

  1. 迷路全体を構成する2次元配列を、幅高さ5以上の奇数で生成します。
  2. 迷路の外周を通路とし、それ以外を壁とします。
  3. x, yともに奇数となる座標(任意)を穴掘り開始座標とします。
  4. 穴掘りを開始します。
    • 指定座標を通路とします。
    • 次に掘り進める方向(1セル先が通路かつ2セル先が壁の方向)をランダムで決定し、2セル先まで通路とします。掘り進められなくなるまで繰り返します。
    • 掘り進めた結果四方のどこにも進めなくなった場合、すでに通路となった座標(x, yともに奇数)をランダムに取得し、4. の穴掘り処理を再帰的に呼び出します。
  5. 外周を壁に戻します。

穴掘り法のシミュレーション

穴掘り法の特徴

穴掘り法は棒倒し法と比べ、実際に何もないところから通路を作っていくため、人が手書きで作る迷路に近いものが出来上がります。出来上がりもランダムで入り組んだ形になりやすいです。行き止まりになるまで通路を伸ばし続ける生成手法なので、割と長めの通路(短い行き止まりが少ない)で構成される傾向にあります。

先にゴールへの通路を伸ばしてから残りの穴掘りを行えば、任意の最短経路をもった迷路を生成することも可能です。

以下のURLで壁伸ばし法と穴掘り法を比較しているので参考にどうぞ。

迷路生成アルゴリズム比較サンプル

サンプルコード

C#

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1.Maze
{
    public class MazeCreateor_Dig
    {
        // 2次元配列の迷路情報
        private int[,] Maze;
        private int Width { get; set; }
        private int Height { get; set; }

        // 穴掘り開始候補座標
        private List<Cell> StartCells;

        // コンストラクタ
        public MazeCreateor_Dig(int width, int height)
        {
            // 5未満のサイズや偶数では生成できない
            if (width < 5 || height < 5) throw new ArgumentOutOfRangeException();
            if (width % 2 == 0) width++;
            if (height % 2 == 0) height++;

            // 迷路情報を初期化
            this.Width = width;
            this.Height = height;
            Maze = new int[width, height];
            StartCells = new List<Cell>();
        }

        // 生成処理
        public int[,] CreateMaze()
        {
            // 全てを壁で埋める
            // 穴掘り開始候補(x,yともに偶数)座標を保持しておく
            for (int y = 0; y < this.Height; y++)
            {
                for (int x = 0; x < this.Width; x++)
                {
                    if (x == 0 || y == 0 || x == this.Width - 1 || y == this.Height - 1)
                    {
                        Maze[x, y] = Path;  // 外壁は判定の為通路にしておく(最後に戻す)
                    }
                    else
                    {
                        Maze[x, y] = Wall;
                    }
                }
            }

            // 穴掘り開始
            Dig(1, 1);

            // 外壁を戻す
            for (int y = 0; y < this.Height; y++)
            {
                for (int x = 0; x < this.Width; x++)
                {
                    if (x == 0 || y == 0 || x == this.Width - 1 || y == this.Height - 1)
                    {
                        Maze[x, y] = Wall;
                    }
                }
            }
            return Maze;
        }

        // 座標(x, y)に穴を掘る
        private void Dig(int x, int y)
        {
            // 指定座標から掘れなくなるまで堀り続ける
            var rnd = new Random();
            while (true)
            {
                // 掘り進めることができる方向のリストを作成
                var directions = new List<Direction>();
                if (this.Maze[x, y - 1] == Wall && this.Maze[x, y - 2] == Wall)
                    directions.Add(Direction.Up);
                if (this.Maze[x + 1, y] == Wall && this.Maze[x + 2, y] == Wall)
                    directions.Add(Direction.Right);
                if (this.Maze[x, y + 1] == Wall && this.Maze[x, y + 2] == Wall)
                    directions.Add(Direction.Down);
                if (this.Maze[x - 1, y] == Wall && this.Maze[x - 2, y] == Wall)
                    directions.Add(Direction.Left);

                // 掘り進められない場合、ループを抜ける
                if (directions.Count == 0) break;

                // 指定座標を通路とし穴掘り候補座標から削除
                SetPath(x, y);
                // 掘り進められる場合はランダムに方向を決めて掘り進める
                var dirIndex = rnd.Next(directions.Count);
                // 決まった方向に先2マス分を通路とする
                switch (directions[dirIndex])
                {
                    case Direction.Up:
                        SetPath(x, --y);
                        SetPath(x, --y);
                        break;
                    case Direction.Right:
                        SetPath(++x, y);
                        SetPath(++x, y);
                        break;
                    case Direction.Down:
                        SetPath(x, ++y);
                        SetPath(x, ++y);
                        break;
                    case Direction.Left:
                        SetPath(--x, y);
                        SetPath(--x, y);
                        break;
                }
            }

            // どこにも掘り進められない場合、穴掘り開始候補座標から掘りなおし
            // 候補座標が存在しないとき、穴掘り完了
            var cell = GetStartCell();
            if (cell != null)
            {
                Dig(cell.X, cell.Y);
            }
        }

        // 座標を通路とする(穴掘り開始座標候補の場合は保持)
        private void SetPath(int x, int y)
        {
            this.Maze[x, y] = Path;
            if (x % 2 == 1 && y % 2 == 1)
            {
                // 穴掘り候補座標
                StartCells.Add(new Cell() { X = x, Y = y });
            }
        }

        // 穴掘り開始位置をランダムに取得する
        private Cell GetStartCell()
        {
            if (StartCells.Count == 0) return null;

            // ランダムに開始座標を取得する
            var rnd = new Random();
            var index = rnd.Next(StartCells.Count);
            var cell = StartCells[index];
            StartCells.RemoveAt(index);

            return cell;
        }

        // デバッグ用処理
        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();
            }
        }

        // 通路・壁情報
        const int Path = 0;
        const int Wall = 1;

        // セル情報
        private class Cell
        {
            public int X { get; set; }
            public int Y { get; set; }
        }

        // 方向
        private enum Direction
        {
            Up = 0,
            Right = 1,
            Down = 2,
            Left = 3
        }
    }
}