递归回溯迷宫生成器

递归回溯算法实际上是一种通用的深度优先搜索。当用于迷宫生成时，它会略微修改以随机选择路径，而如果用于实际搜索目的，通常只会按线性顺序搜索每个级别。它往往会产生具有长而蜿蜒的走廊和非常长而扭曲的解决方案的迷宫。

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

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

递归回溯算法是一种深度优先搜索方法，用于生成完美迷宫（没有环路且任意两点之间只有一条路径的迷宫）。该方法简单、高效，并且能够生成具有长而蜿蜒的走廊的视觉吸引力十足的迷宫。

尽管它的名字是递归，但它并不一定必须使用递归来实现。它通常使用 LIFO 队列（即堆栈）以迭代方式实现。对于非常大的迷宫，使用递归更有可能导致调用堆栈溢出，具体取决于编程语言和可用内存。LIFO 队列可以更轻松地适应处理大量数据，甚至在可用内存不足的情况下将队列保存在磁盘或数据库中。

工作原理

该算法采用基于堆栈的深度优先搜索方法。以下是分步说明：

1. 选择一个起始单元格并将其标记为已访问。
2. 当存在未访问的单元格时：
   • 查看尚未访问过的邻近单元格。
   • 如果至少存在一个未访问的邻居：
     • 随机选择其中一个未访问的邻居。
     • 移除当前单元格和所选邻居之间的墙。
     • 移动到选定的邻居并将其标记为已访问。
     • 将当前单元格推入堆栈。
   • 如果不存在未访问的邻居：
     • 通过从堆栈中弹出最后一个单元格来进行回溯。
3. 继续此过程直到堆栈为空。

关于此算法的一个有趣事实是，它既可以用作迷宫生成器，也可以用作迷宫求解器。如果您在已生成的迷宫上运行它，并在到达决定的终点时停止，则堆栈将包含迷宫的解决方案。

实际上，我在这个网站上使用了该算法的两个版本：一个基于 LIFO 队列的版本，用于生成此页面上的迷宫；另一个基于递归的版本，用于解决迷宫，还有由其他算法生成的迷宫（这就是地图和解决方案的制作方式）。有两个不同的版本只是为了好玩，因为我是个觉得这很有趣的书呆子，任何一个版本都可以用于两者 ;-)