1 算法原理及步骤
Wilson算法是一种用于生成完美迷宫的算法,它的主要特点是生成的迷宫无偏且随机。这意味着所有可能的迷宫结构生成的概率相等。它使用了“随机游走和环消除”的方法,确保每个单元格都被访问,并且没有循环路径。
算法流程
(1)初始化:
- 创建一个全是墙的网格。
- 随机选择一个单元格作为已访问的起点。
(2)随机游走:
- 从未访问的单元格中随机选择一个作为起点。
- 进行随机游走,直到游走路径到达已访问的单元格。
- 在游走过程中,记录经过的路径。
(3)环消除:
- 在随机游走的过程中,如果路径形成了环,删除环以确保路径简单。
- 通过检查路径中的重复单元格来实现环的消除,保留第一次出现的部分。
(4)路径连接:
- 将处理后的路径加到迷宫中,打通路径上的墙。
- 将路径中的所有单元格标记为已访问。
(5)重复: