100种算法【Python版】第21篇——Wilson算法

1 算法原理及步骤

Wilson算法是一种用于生成完美迷宫的算法，它的主要特点是生成的迷宫无偏且随机。这意味着所有可能的迷宫结构生成的概率相等。它使用了“随机游走和环消除”的方法，确保每个单元格都被访问，并且没有循环路径。

算法流程
（1）初始化:

• 创建一个全是墙的网格。
• 随机选择一个单元格作为已访问的起点。

（2）随机游走:

• 从未访问的单元格中随机选择一个作为起点。
• 进行随机游走，直到游走路径到达已访问的单元格。
• 在游走过程中，记录经过的路径。

（3）环消除:

• 在随机游走的过程中，如果路径形成了环，删除环以确保路径简单。
• 通过检查路径中的重复单元格来实现环的消除，保留第一次出现的部分。

（4）路径连接:

• 将处理后的路径加到迷宫中，打通路径上的墙。
• 将路径中的所有单元格标记为已访问。

（5）重复: