威尔逊算法迷宫生成器

威尔逊算法是一种循环消除随机游走方法，它生成均匀生成树用于迷宫生成。这意味着给定大小的所有可能迷宫的生成概率均等，因此它是一种无偏的迷宫生成技术。威尔逊算法可以看作是奥尔德斯-布罗德算法的改进版本，因为它生成的迷宫具有相同的特征，但运行速度更快，所以我在这里没有实现奥尔德斯-布罗德算法。

完美迷宫是指从迷宫中的任何一点到其他任何一点都只有一条路径的迷宫。这意味着你不会兜圈子，但你会经常遇到死胡同，不得不掉头回去。

这里生成的迷宫地图包括一个没有起点和终点位置的默认版本，因此您可以自行决定起点和终点位置：从迷宫中的任何一点到其他任何一点都有解法。如果你想获得灵感，可以启用建议的起点和终点位置，甚至可以查看两者之间的解法。

关于威尔逊算法

威尔逊算法（Wilson's algorithm）是一种利用循环消除随机墙生成均匀生成树的算法，由大卫·布鲁斯·威尔逊（David Bruce Wilson）创建。

威尔逊最初于 1996 年在研究概率论中的随机生成树和马尔可夫链时提出了这种算法。尽管他的研究主要集中在数学和统计物理领域，但由于该算法能够生成完全均匀的迷宫，因此已被广泛应用于迷宫生成。

威尔逊算法如何生成迷宫

威尔逊算法通过使用随机游走，从未访问的单元格中迭代地开辟路径，从而确保最终的迷宫完全连通且没有任何回路。

步骤 1：初始化

• 首先画一个布满墙壁的网格。
• 定义所有可能的通道单元格列表。

步骤 2：选择一个随机起始单元格

• 随机选择一个单元格并将其标记为已访问。这将作为迷宫生成过程中的起点。

步骤 3：带循环消除的随机游走

• 选择一个未访问过的单元格，开始随机游走（向随机方向移动）。
• 如果路径到达已访问过的单元格，则删除路径中的任何循环。
• 一旦路径连接到已访问区域，则将路径上的所有单元格标记为已访问。

步骤 4：重复此步骤直至访问所有细胞：

• 继续选择未访问过的单元格并进行随机游走，直到每个单元格都成为迷宫的一部分。

进一步阅读

如果您喜欢这篇文章，您可能还会喜欢这些建议：

• 狩猎与杀戮迷宫生成器
• 生长树算法迷宫生成器
• Kruskal 算法迷宫生成器