生长树算法迷宫生成器

生长树算法很有趣，因为它可以模拟其他几种算法的行为，具体取决于生成过程中如何选择下一个单元格。本页上的实现使用广度优先、类似队列的方法。

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

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

关于生长树算法

生长树算法是一种灵活而强大的生成完美迷宫的方法。该算法很有趣，因为它可以模拟其他几种迷宫生成算法的行为，例如 Prim 算法、递归回溯和递归除法，具体取决于您如何选择要处理的下一个单元格。

生长树算法的工作原理

步骤 1：初始化

• 从未访问过的单元格网格开始。
• 选择一个随机的起始单元格并将其添加到列表中。

第 2 步：迷宫生成循环

• 当单元格列表不为空时：
  • 根据特定策略从列表中选择一个单元格（如下所述）。
  • 从选定的单元格开辟一条通道到其未访问的邻居之一（随机选择）。
  • 将邻居添加到列表中，因为它现在是迷宫的一部分。
  • 如果选定的单元格没有未访问的邻居，则将其从列表中删除。

步骤 3：终止

• 当列表中不再有单元格时，算法结束，这意味着整个迷宫已被雕刻。

小区选择策略（算法的灵活性）

生长树算法的决定性特征是如何选择下一个要处理的单元格。这一选择极大地影响了迷宫的外观：

最新单元（类似堆栈的行为）——递归回溯器：

• 始终选择最近添加的单元格。
• 产生长而曲折的走廊，其中有许多死胡同（就像深度优先搜索迷宫一样）。
• 迷宫通常通道较长，容易解决。

随机细胞（随机原始算法）：

• 每次从列表中随机挑选一个单元格。
• 创建一个分布更均匀、路径复杂且蜿蜒的迷宫。
• 长廊减少，分支增多。

最老的单元（类似队列的行为）：

• 始终选择列表中最旧的单元格。
• 生成分布更均匀的迷宫，类似于广度优先搜索模式。
• 短而茂密的通道，连接紧密。
• （这是此处实现的版本）

混合方法：

结合不同迷宫特征的策略。例如：

• 90％ 最新，10％ 随机：看起来大部分像递归回溯迷宫，但偶尔会有分支打破长廊。
• 50％ 最新，50％ 最旧：平衡长廊与灌木丛生长。