迷路の幅と高さをそれぞれ width, height として設定し、
その数値にしたがって壁伸ばし法で迷路を生成する。
※迷路の幅と高さは5以上の奇数とする。
using System;
using System.Collections.Generic;
using System.Linq;
public class Maze {
public const int PATH = 0;
public const int WALL = 1;
public int width;
public int height;
public int[,] maze;
public int[] start;
private Random random;
public Maze(int width, int height, int seed = 0) {
this.width = width;
this.height = height;
if (this.width < 5 || this.height < 5) {
Environment.Exit(0);
}
if (this.width % 2 == 0) {
this.width++;
}
if (this.height % 2 == 0) {
this.height++;
}
this.maze = new int[this.height,this.width];
for (int y = 0; y < this.height; ++y) {
for (int x = 0; x < this.width; ++x) {
this.maze[y,x] = Maze.PATH;
}
}
this.start = new int[] {1, 1};
this.random = new Random(seed);
}
public int[,] set_outer_wall() {
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[y,x] = Maze.WALL;
}
}
}
return this.maze;
}
public int[,] set_maze_kabenobashi() {
this.set_outer_wall();
int[] point;
Stack<int[]> stack = new Stack<int[]>();
for (int y = 2; y < this.height-1; y += 2) {
for (int x = 2; x < this.width-1; x += 2) {
stack.Push(new int[] {x, y});
}
}
while (true) {
if (stack.Count == 0) {
break;
}
stack = new Stack<int[]>(stack.OrderBy(i => random.Next(stack.Count)).ToArray());
point = stack.Pop();
if (this.maze[point[1],point[0]] == Maze.WALL) {
continue;
}
this.maze[point[1],point[0]] = Maze.WALL;
List<int[]> extend_wall = new List<int[]>();
extend_wall.Add(new int[] {point[0],point[1]});
while (true) {
List<int> directions = new List<int>();
CellComparer comparer = new CellComparer();
if (this.maze[point[1]-1,point[0]] == Maze.PATH && extend_wall.Contains(new int[] {point[0],point[1]-2}, comparer) != true) {
directions.Add(0);
}
if (this.maze[point[1],point[0]+1] == Maze.PATH && extend_wall.Contains(new int[] {point[0]+2,point[1]}, comparer) != true) {
directions.Add(1);
}
if (this.maze[point[1]+1,point[0]] == Maze.PATH && extend_wall.Contains(new int[] {point[0],point[1]+2}, comparer) != true) {
directions.Add(2);
}
if (this.maze[point[1],point[0]-1] == Maze.PATH && extend_wall.Contains(new int[] {point[0]-2,point[1]}, comparer) != true) {
directions.Add(3);
}
if (directions.Count == 0) {
break;
}
int direction = directions[random.Next(directions.Count)];
switch (direction) {
case 0:
if (this.maze[point[1]-2,point[0]] == Maze.WALL) {
this.maze[point[1]-1,point[0]] = Maze.WALL;
goto LOOPEND;
} else {
this.maze[point[1]-1,point[0]] = Maze.WALL;
this.maze[point[1]-2,point[0]] = Maze.WALL;
extend_wall.Add(new int[] {point[0],point[1]-2});
point = new int[] {point[0],point[1]-2};
break;
}
case 1:
if (this.maze[point[1],point[0]+2] == Maze.WALL) {
this.maze[point[1],point[0]+1] = Maze.WALL;
goto LOOPEND;
} else {
this.maze[point[1],point[0]+1] = Maze.WALL;
this.maze[point[1],point[0]+2] = Maze.WALL;
extend_wall.Add(new int[] {point[0]+2,point[1]});
point = new int[] {point[0]+2,point[1]};
break;
}
case 2:
if (this.maze[point[1]+2,point[0]] == Maze.WALL) {
this.maze[point[1]+1,point[0]] = Maze.WALL;
goto LOOPEND;
} else {
this.maze[point[1]+1,point[0]] = Maze.WALL;
this.maze[point[1]+2,point[0]] = Maze.WALL;
extend_wall.Add(new int[] {point[0],point[1]+2});
point = new int[] {point[0],point[1]+2};
break;
}
case 3:
if (this.maze[point[1],point[0]-2] == Maze.WALL) {
this.maze[point[1],point[0]-1] = Maze.WALL;
goto LOOPEND;
} else {
this.maze[point[1],point[0]-1] = Maze.WALL;
this.maze[point[1],point[0]-2] = Maze.WALL;
extend_wall.Add(new int[] {point[0]-2,point[1]});
point = new int[] {point[0]-2,point[1]};
break;
}
}
}
LOOPEND:;
}
return this.maze;
}
public void print_maze() {
for (int y = 0; y < this.maze.GetLength(0); ++y) {
for (int x = 0; x < this.maze.GetLength(1); ++x) {
if (this.maze[y,x] == Maze.WALL) {
Console.Write('#');
} else if (this.maze[y,x] == Maze.PATH) {
Console.Write(' ');
}
}
Console.WriteLine();
}
}
private class CellComparer : IEqualityComparer<int[]>
{
public bool Equals(int[] x, int[] y)
{
if(x[0] == y[0] && x[1] == y[1]) {
return true;
} else {
return false;
}
}
public int GetHashCode(int[] x)
{
return 0;
}
}
public static void Main() {
Maze maze1 = new Maze(15, 15);
maze1.set_maze_kabenobashi();
maze1.print_maze();
}
}
今回は、以下のように出力される。
###############
# # # # #
# ### # ### # #
# # # # # #
# # ### # #####
# #
# # ### # # # #
# # # # # # #
##### ##### ###
# # # #
# ##### # # # #
# # # # #
# ##### # ### #
# # # # #
###############
参考
迷路生成(壁伸ばし法) - Algoful
壁伸ばし法は迷路生成アルゴリズムの一種です。何もない状態から壁を生成することで迷路を作り上げます。シミュレーション機能で生成される過程を確認できます。C#の実装サンプルを用意しているのでUnityでのゲーム開発の参考にどうぞ。
[Python] 壁伸ばし法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路