C#实现4种经典迷宫生成算法和迷宫寻路算法(三)
使用深度优先算法生成迷宫
后面讲述的三种生成算法,都用到了一个中间矩阵。所以我们把对中间矩阵的处理放在了一个虚类里。中间矩阵是一个三维矩阵,前面两维还是行和列,而最后一维则表示:左、上、右、下的墙是否存在,以及本格子是否访问过。
/// <summary>
/// 迷宫接口2
/// </summary>
public abstract class IMaze2 : IMaze
{
/// <summary>
/// 中间矩阵
/// </summary>
protected int[,,] M;
/// <summary>
/// 初始化中间矩阵
/// </summary>
protected void InitM()
{
int[,,] M = new int[room_row, room_col, 5];
for (int i = 0; i < room_row; i++)
{
for (int j = 0; j < room_col; j++)
{
for (int k = 0; k < 5; k++)
{
M[i, j, k] = 0;
}
}
}
}
/// <summary>
/// 解析中间矩阵
/// </summary>
protected void ParseM()
{
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if (i == 0 || i == ROW - 1 || j == 0 || j == COL - 1)
{
maze[i, j] = 1;
}
else
{
if (i % 2 == 0)
{
if (j % 2 == 0)
{
maze[i, j] = 1;
}
else
{
maze[i, j] = M[i / 2 - 1, (j - 1) / 2, 3] == 1 ? 0 : 1;
}
}
else
{
if (j % 2 == 0)
{
maze[i, j] = M[(i - 1) / 2, j / 2 - 1, 2] == 1 ? 0 : 1;
}
else
{
maze[i, j] = 0;
}
}
}
}
}
}
}
深度优先算法是很好理解的,其算法思路是:
(1)把起点S放到一个堆栈里。
(2)从堆栈里弹出一个格子,然后随机选择一个相邻并且没有访问过的格子。打通本格子与相邻格子的墙。
(3)把相邻的格子放入堆栈。重复第二步。
代码如下:
public override void Build()
{
InitM();
int r = 0;
int c = 0;
Stack<Position> history = new Stack<Position>();
history.Push(GetPosition(r, c));
Random rand = new Random();
while (history.Count != 0)
{
M[r, c, 4] = 1;
List<char> directions = new List<char>();
if (c > 0 && M[r, c - 1, 4] == 0)
{
directions.Add('L');
}
if (r > 0 && M[r - 1, c, 4] == 0)
{
directions.Add('U');
}
if (c < room_col - 1 && M[r, c + 1, 4] == 0)
{
directions.Add('R');
}
if (r < room_row - 1 && M[r + 1, c, 4] == 0)
{
directions.Add('D');
}
if (directions.Count != 0)
{
history.Push(GetPosition(r, c));
int direction_index = rand.Next(directions.Count);
char direction = directions[direction_index];
switch (direction)
{
case 'L':
M[r, c, 0] = 1;
c = c - 1;
M[r, c, 2] = 1;
break;
case 'U':
M[r, c, 1] = 1;
r = r - 1;
M[r, c, 3] = 1;
break;
case 'R':
M[r, c, 2] = 1;
c = c + 1;
M[r, c, 0] = 1;
break;
case 'D':
M[r, c, 3] = 1;
r = r + 1;
M[r, c, 1] = 1;
break;
}
}
else
{
Position pos = history.Pop();
r = pos.row;
c = pos.col;
}
}
ParseM();
}
算法结束之后,所有格子都是相通的。生成的迷宫如下图所示:
用深度优先算法生成的迷宫特点是:路径几乎唯一,很好走,但特别长。