使用深度优先算法生成迷宫

后面讲述的三种生成算法，都用到了一个中间矩阵。所以我们把对中间矩阵的处理放在了一个虚类里。中间矩阵是一个三维矩阵，前面两维还是行和列，而最后一维则表示：左、上、右、下的墙是否存在，以及本格子是否访问过。

/// <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();
}

算法结束之后，所有格子都是相通的。生成的迷宫如下图所示：

用深度优先算法生成的迷宫特点是：路径几乎唯一，很好走，但特别长。