威尔逊算法迷宫生成器

Wilson 算法是一种循环擦除随机游走方法，可生成均匀生成树来创建迷宫。这意味着给定大小的所有可能迷宫都有同等的可能性生成，使其成为一种无偏迷宫生成技术。Wilson 算法可以被认为是 Aldous-Broder 算法的改进版本，因为它可以生成具有相同特征的迷宫，但运行速度要快得多，因此我在这里没有费心实现 Aldous-Broder 算法。

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

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

关于威尔逊算法

使用循环擦除随机墙生成均匀生成树的 Wilson 算法由 David Bruce Wilson 创建。

Wilson 最初于 1996 年在研究概率论中的随机生成树和马尔可夫链时引入了该算法。尽管他的工作主要在数学和统计物理学领域，但该算法后来被广泛用于迷宫生成，因为它能够生成完美均匀的迷宫。

威尔逊算法如何生成迷宫

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

步骤 1：初始化

• 从布满墙壁的网格开始。
• 定义所有可能的传代细胞的列表。

第 2 步：选择随机起始单元格

• 选取任意一个单元格并将其标记为已访问。这在生成过程中用作迷宫的起点。

步骤 3：循环擦除随机游走

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

步骤4：重复，直到访问所有单元格：

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