生长树算法迷宫生成器

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

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

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

关于生长树算法

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

树形生长算法的工作原理

步骤 1：初始化

• 首先创建一个未访问单元格的网格。
• 随机选择一个起始单元格并将其添加到列表中。

步骤 2：迷宫生成循环

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

步骤三：终止

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

细胞选择策略（算法的灵活性）

生长树算法的关键特征在于如何选择接下来要处理的单元格。这一选择会极大地影响迷宫的外观：

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

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

随机单元格（随机化Prim算法）：

• 每次从列表中随机选择一个单元格。
• 形成一个分布更均匀、路径复杂交错的迷宫。
• 减少长走廊，增加分支道路。

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

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

混合方法：

针对不同迷宫特征，可以结合不同的策略。例如：

• 90% 最新，10% 随机：看起来主要像一个递归回溯迷宫，但偶尔会有分支打破长长的走廊。
• 50% 最新，50% 最旧：平衡长廊与茂密植被。

进一步阅读

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

• 递归回溯迷宫生成器
• 埃勒算法迷宫生成器
• Kruskal 算法迷宫生成器