三种迷宫生成算法概述
2018-11-11 本文已影响0人
M_lear
1. Randomized Prim's algorithm（随机Prim算法）
随机Prim算法属于打通墙壁生成迷宫的算法，下面以集合的角度来描述此算法。
-
首先是初始化，建立一个所有单元格都被墙隔开的迷宫。
以8*8的迷宫为例，将每个单元格进行编号。使用集合表示路径，集合中的元素就是单元格的编号，表示这条路径经过了哪些单元格。
假设我们从1开始，按从左到右从上到下的顺序依次对单元格进行编号。又假设迷宫的入口为左上角的单元格，编号为1，出口为右下角的单元格，编号为64。
初始化迷宫
- 所以最开始有64条路径，每条路径只有一个单元格。我们用
表示路径i的集合，其中i为集合中元素的最小值(这个约定对编程来讲意义不大，只是方便后面的描述)。初始时有：
- 然后随机选择一个内部的墙壁，假设墙壁两边的单元格编号为
若，表示墙壁两边的单元格属于同一路径，则没必要打通该墙壁，之后重复步骤3.
若，表示两单元格不在同一路径，则打通该墙壁，连通相邻的两路径，连通路径对应为集合的合并。
之后重复步骤3。
- 直至最终合并为一个集合
，就将所有的单元格纳入到一个可达路径中，即对于入口单元格1来说其它任意单元格都是可达的。不过我们并不需要一定合并到一个集合为止，只要当
时，表明入口和出口之间已有可达路径，就可以停止合并了。
全连通迷宫
如果编程实在没思路可以参考下面的伪码描述，否则可以跳过。
- 建立单元格矩阵，下标对应编号，元素值对应集合，值相同单元格代表属于同一集合，初始时所有值都不同。
- 建立两个向量，分别表示所有单元格的右上（也可是左下等等）墙壁，下标对应单元格，值表示墙是否被打通，初始时所有墙未被打通。
- 随机选择两个向量中的一堵未被打通的墙（非边缘），找到矩阵中此墙邻接的两单元格。判断元素值是否相等，相等则不打通，然后重复当前步骤；若元素值不等，则打通该墙壁，将矩阵中两集合的元素值统一，然后重复当前步骤。
知道并查集这个数据结构的同学，在看到前面说的集合合并和判断两元素是否属于同一集合的操作时，肯定能自然而然的联想到并查集。不错！并查集确实是一种刚好能够用到随机 Prim 算法中的高效的数据结构，我们可以用并查集进一步改造上面所描述的伪代码。
2. Recursive backtracker ( 递归回溯）
同样是属于打通墙壁生成迷宫的算法，也叫深度优先算法（不撞南墙不回头，哈哈）。
- 首先是初始化，建立一个所有单元格都被墙隔开的迷宫。
- 随机选择一个单元格作为起始点，以此单元格开始打通墙壁。
- 以当前单元格为基准，随机选择一个方向，若此方向的邻接单元格没有被访问过，则打通这两个单元格之间的墙壁，并将此邻接单元格作为当前单元格，重复步骤3。
- 若当前单元格的四个邻接单元格都已经被访问过，则退回到进入当前单元格的邻接单元格，且以此单元格为当前当前单元格，重复步骤3，4。
- 直到起始点单元格被退回，则算法结束。
3. Recursive division（递归分割法）
属于构造墙壁生成迷宫的算法。
在空白空间随机生成十字墙壁，将空间分割为四个子空间，然后在三面墙上各自选择一个随机点挖洞，保证四个子空间的连通。之后继续对子空间做分割，直至空间不足以继续分割为止。
引用一下别人的总结：这三种算法分别适合不同的迷宫情况，递归回溯适合于那种主线支线明显的游戏（如RPG），而递归分割则适合转角较少的游戏（如FPS和ACT），至于Prim，似乎适合最标准的迷宫游戏（随机Prim算法生成的迷宫分支较多，整体上更复杂也更自然）。
