递归回溯迷宫生成器

递归回溯算法实际上是一种通用的深度优先搜索算法。当用于迷宫生成时，它会稍作修改，随机选择路径；而用于实际搜索时，通常会按线性顺序逐层搜索。这种算法往往会生成具有长而蜿蜒的走廊以及非常长且曲折的解的迷宫。

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

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

递归回溯算法是一种深度优先搜索方法，用于生成完美迷宫（无环且任意两点之间只有一条路径的迷宫）。它简单高效，能够生成具有蜿蜒长廊且视觉效果极佳的迷宫。

尽管名称中带有“递归”二字，但迷宫算法并非必须使用递归来实现。它通常采用迭代的方式，并使用后进先出（LIFO）队列（即栈）来实现。对于非常大的迷宫，使用递归更容易导致调用栈溢出，具体情况取决于编程语言和可用内存。LIFO队列更容易适应处理大量数据，即使内存不足，也可以将队列保存在磁盘或数据库中。

工作原理

该算法采用基于堆栈的深度优先搜索方法。以下是详细步骤：

1. 选择一个起始单元格并将其标记为已访问。
2. 当存在未访问的单元格时：查看尚未访问的相邻单元格。如果至少存在一个未访问的相邻单元格：随机选择一个未访问的相邻单元格。移除当前单元格与所选相邻单元格之间的隔墙。移动到所选相邻单元格并将其标记为已访问。将当前单元格压入栈中。如果不存在未访问的相邻单元格：回溯，从栈中弹出最后一个单元格。
3. 重复此过程，直到堆栈为空。

这个算法的一个有趣之处在于它既可以作为迷宫生成器，也可以作为迷宫求解器。如果你在一个已经生成的迷宫上运行它，并在到达预设的终点时停止，那么堆栈中就会包含迷宫的解。

实际上，我在这个网站上使用了两个版本的算法：一个是基于后进先出队列的算法，用于生成本页上的迷宫；另一个是基于递归的算法，用于求解迷宫，以及其他算法生成的迷宫（这就是带有解的地图的生成方式）。使用两个不同的版本纯粹是为了好玩，因为我是一个技术宅，觉得这很有趣，其实任何一个版本都足以满足需求 ;-)

进一步阅读

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

• 威尔逊算法迷宫生成器
• 生长树算法迷宫生成器
• Kruskal 算法迷宫生成器