迷路生成アルゴリズム(壁伸ばし法)
迷路を生成するアルゴリズムは以下のような種類があります。ここでは壁伸ばし法と呼ばれるアルゴリズムを解説します。壁伸ばし法は文字通り、全面が通路の状態から壁を生成し伸ばしていくことで、迷路を作り上げるアルゴリズムです。
迷路の定義
まずは迷路の定義を行います。ここで生成される迷路とは、2次元配列に 0 と 1 で構成されます。1 が通れない壁部分で 0 が通れる通路部分を意味します。
1111111
1000001
1010111
1010001
1011101
1010001
1111111上記のような 7*7 の2次元配列のデータがあったとして、これは次のような迷路を意味します。
| 壁 | 壁 | 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 道 | 道 | 道 | 道 | 道 | 壁 |
| 壁 | 道 | 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 道 | 道 | 道 | 道 | 道 | 壁 |
| 壁 | 道 | 壁 | 道 | 壁 | 壁 | 壁 |
| 壁 | 道 | 壁 | 道 | 道 | 道 | 壁 |
| 壁 | 壁 | 壁 | 壁 | 壁 | 壁 | 壁 |
禁止事項
迷路は次のような状況にならないように生成します。
- 外の通路につながらない死に領域(閉じた領域)
- 通路がループになる
1.の閉じた領域は到達できない領域になってしまい無駄なのでこれは許可しません。2.は同じ場所まで複数の方法で到達できてしまい、難易度が下がるのでこれも許可しない方向で考えます。ループしないなら最短経路も一意に決まります。それぞれの状況は以下のような場合に発生します。
| 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 道 | 壁 | 道 | 壁 |
| 壁 | 道 | 壁 | 壁 | 壁 |
| 壁 | 道 | 道 | 道 | 壁 |
| 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 道 | 道 | 道 | 壁 |
| 壁 | 道 | 壁 | 道 | 壁 |
| 壁 | 道 | 道 | 道 | 壁 |
| 壁 | 壁 | 壁 | 壁 | 壁 |
壁伸ばし法
壁伸ばし法は以下の手順で迷路を生成します。
- 迷路全体を構成する2次元配列を、幅高さ5以上の奇数で生成します。
- 迷路の外周を壁とし、それ以外を通路とします。
- x, yともに偶数となる座標を壁伸ばし開始座標(候補)としてリストアップします。
- 壁伸ばし開始座標からランダムで座標を取り出し、通路の場合のみ 5. の壁伸ばし処理を行います。すべての候補座標が壁になるまで繰り返します。
- 壁伸ばし処理を行います。
- 指定座標を壁とします。
- 次に掘り進める方向(隣のセルが通路の方向かつ2セル先が現在拡張中の壁ではない方向)をランダムで決定しします。
- 拡張する方向2セル先が壁の場合(既存の壁に接続された場合)、壁の拡張を終了します。
- 通路の場合、そのセルから続けて拡張します。(5. の処理を再帰的に呼び出す。)
- 四方がすべて現在拡張中の壁の場合、拡張できる座標が見つかるまで、現在拡張中の壁をバックして、壁の拡張を再開します。
- すべての候補座標が壁(拡張済)になれば完了です。
壁伸ばし法は棒倒し法で棒となる座標から壁を伸ばして行きます。壁は必ず外周4辺のいずれか一つにのみ接続されなければなりません。したがって既存の壁と繋がるまで拡張を続けてやればよいのです。ただし注意点として必ず、既存の壁(外周の壁含む)に接続しなければなりません。現在拡張中の壁に接続してしまうと、到達できない領域が生成されてしまいます。
壁の拡張を続け赤のセルから先には拡張できまぜ。よって赤のセルから前のセル(青のセル)に戻って再開を目指すように対処します。
| 壁 | 壁 | 壁 | 壁 | 壁 |
| 壁 | 道 | 道 | 道 | 壁 |
| 壁 | 道 | 壁 | 道 | 壁 |
| 壁 | 道 | 壁 | 道 | 壁 |
| 壁 | 道 | 壁 | 壁 | 壁 |
拡張中の壁への接続を避けるため、拡張時には現在の壁(x, yともに偶数となる座標のみ)をスタックに積んで管理しておきましょう。周りが拡張済の壁のみで進めなくなった場合は、スタックから取り出した座標で拡張を再開してやれば、この状態を回避できます。
壁伸ばし法のシミュレーション
現在拡張中の壁が、必ず既存の壁に接続され、自分自身には接続しないことが確認できます。
壁伸ばし法の特徴
壁伸ばし法は棒倒し法と比べ、複雑な迷路が生成されます。ランダムな位置から壁を伸ばしていくため、それなりに入り組んだ見た目になっているはずです。割とゴールへすんなりいく場合も少ないようで、ゲームなどに応用する場合、穴掘り法と比較して検討してみるとよいでしょう。
以下のURLで壁伸ばし法と穴掘り法を比較しているので参考にどうぞ。
サンプルコード
C#
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1.Maze
{
public class MazeCreator_Extend
{
// 2次元配列の迷路情報
private int[,] Maze;
public int Width { get; }
public int Height { get; }
// 乱数生成用
private Random Random;
// 現在拡張中の壁情報を保持
private Stack<Cell> CurrentWallCells;
//private Stack<int> CurrentWallIndex;
// 壁の拡張を行う開始セルの情報
private List<Cell> StartCells;
// コンストラクタ
public MazeCreator_Extend(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>();
CurrentWallCells = new Stack<Cell>();
this.Random = new Random();
}
public int[,] CreateMaze()
{
// 各マスの初期設定を行う
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)
{
this.Maze[x, y] = Wall;
}
else
{
this.Maze[x, y] = Path;
// 外周ではない偶数座標を壁伸ばし開始点にしておく
if (x % 2 == 0 && y % 2 == 0)
{
// 開始候補座標
StartCells.Add(new Cell(x, y));
}
}
}
}
// 壁が拡張できなくなるまでループ
while (StartCells.Count > 0)
{
// ランダムに開始セルを取得し、開始候補から削除
var index = Random.Next(StartCells.Count);
var cell = StartCells[index];
StartCells.RemoveAt(index);
var x = cell.X;
var y = cell.Y;
// すでに壁の場合は何もしない
if (this.Maze[x, y] == Path)
{
// 拡張中の壁情報を初期化
CurrentWallCells.Clear();
ExtendWall(x, y);
}
}
return this.Maze;
}
// 指定座標から壁を生成拡張する
private void ExtendWall(int x, int y)
{
// 伸ばすことができる方向(1マス先が通路で2マス先まで範囲内)
// 2マス先が壁で自分自身の場合、伸ばせない
var directions = new List<Direction>();
if (this.Maze[x, y - 1] == Path && !IsCurrentWall(x, y - 2))
directions.Add(Direction.Up);
if (this.Maze[x + 1, y] == Path && !IsCurrentWall(x + 2, y))
directions.Add(Direction.Right);
if (this.Maze[x, y + 1] == Path && !IsCurrentWall(x, y + 2))
directions.Add(Direction.Down);
if (this.Maze[x - 1, y] == Path && !IsCurrentWall(x - 2, y))
directions.Add(Direction.Left);
// ランダムに伸ばす(2マス)
if (directions.Count > 0)
{
// 壁を作成(この地点から壁を伸ばす)
SetWall(x, y);
// 伸ばす先が通路の場合は拡張を続ける
var isPath = false;
var dirIndex = Random.Next(directions.Count);
switch (directions[dirIndex])
{
case Direction.Up:
isPath = (this.Maze[x, y - 2] == Path);
SetWall(x, --y);
SetWall(x, --y);
break;
case Direction.Right:
isPath = (this.Maze[x + 2, y] == Path);
SetWall(++x, y);
SetWall(++x, y);
break;
case Direction.Down:
isPath = (this.Maze[x, y + 2] == Path);
SetWall(x, ++y);
SetWall(x, ++y);
break;
case Direction.Left:
isPath = (this.Maze[x - 2, y] == Path);
SetWall(--x, y);
SetWall(--x, y);
break;
}
if (isPath)
{
// 既存の壁に接続できていない場合は拡張続行
ExtendWall(x, y);
}
}
else
{
// すべて現在拡張中の壁にぶつかる場合、バックして再開
var beforeCell = CurrentWallCells.Pop();
ExtendWall(beforeCell.X, beforeCell.Y);
}
}
// 壁を拡張する
private void SetWall(int x, int y)
{
this.Maze[x, y] = Wall;
if (x % 2 == 0 && y % 2 == 0)
{
CurrentWallCells.Push(new Cell(x, y));
}
}
// 拡張中の座標かどうか判定
private bool IsCurrentWall(int x, int y)
{
return CurrentWallCells.Contains(new Cell(x, y));
}
// デバッグ用処理
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 struct Cell
{
public int X { get; set; }
public int Y { get; set; }
public Cell(int x, int y)
{
this.X = x;
this.Y = y;
}
}
// 方向
private enum Direction
{
Up = 0,
Right = 1,
Down = 2,
Left = 3
}
}
}