【数据结构01】

迷宫生成算法

现在的迷宫生成主要有三种算法：DFS算法，随机Prim算法，Kruskal算法

DFS算法：即深度优先搜索算法，这种方法生成的迷宫具有较为明显的通路
Prim算法：这种算法生成的迷宫岔路较多，整体看上去也较为自然
Kruskal算法：这种算法同样不会产生明显的主路，岔路也较多

本篇主要采用Prim算法生成完美迷宫

完美迷宫

完美迷宫是指符合以下条件的迷宫：

迷宫中任意两点之间存在通路
任意两点见的通路是唯一的
迷宫中不存在回路

Prim完美迷宫生成算法

以下讲述中使用的代码大部分是伪码

主要步骤

设置一个二维数组，用于记录地图信息
- 地图尺寸为 奇数×奇数
- 地图最外侧一周是墙
- 将坐标为（奇数，奇数）的点先看做路点（坐标从0开始）
- 这里用0表示路，用1表示墙
1
2
3
#define Width 11
#define Height 11
int roadOrWall[Width][Height] = 0;
初始化地图信息
- 将所有地图块标记为墙，即数组所有元素的值都为1
1
2
3
4
5
6
7
8
9
for (int i = 0; i < Width; i++)
{
for (int j = 0; j < Height; j++)
{
roadOrWall[i][j] = 1;
}
}
或
memset(roadOrWall,1,sizeof(roadOrWall));
将路点用蓝色表示，墙用橙色表示，路用白色表示

会得到下面的“迷宫”（11×11）
现在在图的边缘部分选择一个路点，如图所示，选择（1,1）点，将其变成路
1
roadOrWall[1][1]=0;
再将其周围的两个路点，加入待选路点列表中
- 待选路点用绿色表示，得到以下图像
- 待选路点在地图信息中用2表示
1
2
roadOrWall[1][3]=2;
roadOrWall[3][1]=2;
创建路线备选池
- 之后要变成路的地图块要从路线备选池中随机选择
初始工作准备完毕，现在进入循环
- 循环条件
1
while(待选路点的个数>0)
- 在待选路点列表中随机选取一个路点A
  - 如选中了路点A(1,3)
- 清空路线备选池
  - 进入路线备选池的路点将会形成迷宫的路线
- 将A周围的四个路点中的已经变成路的路点加入路线备选池
- 从路线备选池中再随机选出一个路点B
  - 如选中了B(1,1)
- 将AB两个路点打通，即路点A，路点B及其中间的部分全部变成路，得到下图迷宫
  1
  2
  3
  4
  //将A变成路
  roadOrWall[A->y][A->x] = 0;
  //将AB中间的方块变成路
  roadOrWall[(A->y + B->y) / 2][(A->x + B->x) / 2] = 0;
- 将路点A周围还不是路的路点加入待选路点列表中（不可重复添加），如下图
- 从待选路点列表中删除路点A
- 重复进行以上操作，直到待选路点列表为空为止