迷宫生成算法

迷宫生成算法是创建迷宫的自动方法。

迷宫可以从预先确定的细胞排列（最常见的是矩形网格，但也可能有其他排列）开始生成，细胞之间有壁垒。这种预定的安排可以被看作是一个连接图，边代表可能的墙址，节点代表单元。然后，迷宫生成算法的目的可以被认为是制作一个子图，在其中找到两个特定节点之间的路线是具有挑战性的。如果子图没有连接，那么图中就有一些区域被浪费了，因为它们对搜索空间没有贡献。如果图形包含循环，那么在所选节点之间可能有多条路径。正因为如此，迷宫生成通常被视为生成一个随机生成树。循环可能会迷惑天真的迷宫求解者，可以通过在算法过程中向结果添加随机边来引入。动画显示了不在矩形网格上的图形的迷宫生成步骤。首先，计算机创建一个随机的平面图形G，以蓝色显示，其对偶F以黄色显示。其次，计算机使用一种选定的算法（如深度优先搜索）遍历F，将路径染成红色。在遍历过程中，每当一条红边与一条蓝边交叉时，蓝边就会被删除。最后，当F的所有顶点都被访问过后，F被擦除，G的两条边，一条是入口，一条是出口，被删除。

这种算法也被称为递归回溯算法，是深度优先搜索算法的随机化版本。经常用堆栈来实现，这种方法是使用计算机生成迷宫的最简单方法之一。考虑到迷宫的空间是一个由单元格组成的大网格（像一个大棋盘），每个单元格开始有四面墙。计算机从一个随机单元开始，然后随机选择一个尚未被访问过的相邻单元。计算机移除两个单元之间的墙，并将新的单元标记为已访问，并将其添加到堆栈中以方便回溯。计算机继续这个过程，没有未访问过的邻居的单元被认为是一个死胡同。

当处于死胡同时，它通过路径回溯，直到到达一个有未访问邻居的单元，通过访问这个新的、未访问的单元继续生成路径（创建一个新的结点）。这个过程一直持续到每一个单元都被访问过，导致计算机一路回溯到起始单元。我们可以确定每个单元都被访问过。如上所述，该算法涉及深度递归，在某些计算机架构上可能导致堆栈溢出问题。通过将回溯信息存储在迷宫本身，该算法可以被重新安排为一个循环。这也提供了一个快速显示解决方案的方法，从任何给定的点开始，回溯到起点。用深度优先搜索产生的迷宫有一个低的分支系数，包含许多长的走廊，因为该算法在回溯之前尽可能地沿着每个分支探索。

迷宫生成的深度优先搜索算法经常使用回溯来实现。这可以用下面的递归程序来描述。

将当前单元标记为已访问的单元当当前单元有任何未访问的邻接单元时选择一个未访问的邻接单元移除当前单元和所选单元之间的墙对所选单元递归调用该程序，对该区域的任何初始单元调用一次。

xxx种方法的缺点是递归深度大–在最坏的情况下，该例程可能需要对被处理区域的每个单元进行递归，这在许多环境中可能超过xxx的递归栈深度。作为一个解决方案，同样的回溯方法可以用一个显式堆栈来实现，通常允许堆栈增长得更大而无害。选择初始单元，将其标记为已访问，并将其推至堆栈当堆栈不是空的时候从堆栈中弹出一个单元，使其成为当前单元如果当前单元有任何未访问的邻居将当前单元推至堆栈从未访问的邻居中选择一个删除当前单元和所选单元之间的墙将所选单元标记为已访问，并将其推至堆栈随机化Kruskal算法该算法是Kruskal算法的随机化版本。创建一个所有墙的列表，并为每个单元格创建一个集合，每个集合只包含一个单元格。对于每个墙，以某种随机的顺序：如果被这个墙分割的单元格属于不同的集合：移除当前的墙。连接以前分割的单元格的集合。