迷宫生成器 - 算法随机迷宫Canvas绘制

迷宫生成算法是一类用于自动创建迷宫结构的计算机算法的统称。这些算法通过在二维网格中有策略地打通墙壁来构造迷宫，目标是生成一个起点和终点之间存在至少一条通路的连通结构。常见的迷宫生成算法包括递归回溯算法、Prim 算法、Kruskal 算法和递归分割法等。每种算法都基于不同的数学原理和搜索策略，因此生成的迷宫在结构风格上存在显著差异。理解这些算法的原理有助于我们选择最适合特定需求的生成方式。

递归回溯算法的工作流程可以概括为以下步骤：首先在网格中随机选择一个起始单元格并将其标记为已访问状态。然后检查当前单元格的四个方向（上、下、左、右）是否存在未访问的相邻单元格。如果存在，则随机选择其中一个，打通两者之间的墙壁，并将该相邻单元格设置为新的当前单元格，然后递归地执行相同的操作。当某个单元格的所有四个方向的相邻单元格都已被访问完毕时，算法执行回溯操作，返回到调用它的上一个单元格，继续检查该单元格的其他未探索方向。这个递归和回溯的过程持续进行，直到所有单元格都被访问，最终形成一个完美的迷宫结构。其本质是深度优先搜索在网格图上的应用。

两者都是基于图论中最小生成树（MST）概念的迷宫生成算法，但实现原理和生成风格存在明显不同。Prim 算法维护一个「前沿列表」，每次从与已访问区域直接相邻的未访问单元格中随机选择一个进行连接，生成的迷宫具有分支密集、死胡同分布均匀的特点。Kruskal 算法则采取完全不同的策略：首先将网格中所有墙壁收集到一个列表中并随机打乱顺序，然后逐一检查每面墙壁两侧的单元格是否属于不同的连通分量。如果是，则打通该墙壁并使用并查集（Union-Find）数据结构合并两个连通分量。Kruskal 算法生成的迷宫随机性更强、结构更加均匀，没有明显的「生长中心」。在实际应用中，两种算法各有优劣，选择取决于用户希望获得的迷宫风格。

BFS（广度优先搜索）求解迷宫的过程可以描述为：从起点开始，将其标记为已访问状态并加入搜索队列。然后循环取出队列前端的单元格，检查其四个方向的相邻单元格。如果某个相邻单元格未被访问且两者之间没有墙壁阻隔，则将其标记为已访问、记录其父节点信息（用于最终路径重建），并加入队列尾部。这个过程持续进行，直到目标终点被从队列中取出。此时，通过从终点沿父节点链回溯到起点，即可得到一条完整的路径。由于 BFS 逐层扩展的特性，它保证找到的路径是从起点到终点经过单元格数最少的最短路径。BFS 的时间复杂度为 O(V+E)，其中 V 是单元格总数，E 是墙壁打通后的边数。

「完美迷宫」（Perfect Maze）是指迷宫中任意两个单元格之间都恰好只有一条通路的迷宫结构。这意味着迷宫中不存在回路（环形结构）、不存在被墙壁完全包围的孤立区域，所有单元格都相互连通。从图论的角度来理解，完美迷宫等价于将网格图的所有节点连接起来的一棵生成树，即边数等于节点数减一的连通无环图。本工具默认使用递归回溯和 Prim 算法生成的迷宫都是完美迷宫。与完美迷宫相对的概念是「有环迷宫」或「非完美迷宫」，它允许存在多条通路和封闭区域，结构更加复杂但也更难分析和求解。

这是因为算法在关键决策步骤中引入了随机性。在递归回溯算法中，每一步选择下一个访问方向时都是从可用方向中随机挑选的；在 Prim 算法中，每一步从前沿列表中选取单元格时也是随机的。这些随机选择通过计算机的伪随机数生成器实现，由于随机种子的不同，即使使用完全相同的算法代码和迷宫尺寸参数，每次生成的迷宫结构也会截然不同。这种随机性设计是刻意为之的，它确保了迷宫的多样性和可重复玩性，让用户每次使用工具都能获得全新的体验。

迷宫尺寸的选择应该根据实际使用目的来决定，而非一味追求大尺寸。对于算法教学和原理演示，中等尺寸（20×20 至 40×40）的迷宫已经足够清晰地展示算法的工作过程，同时生成和求解的速度也很快。对于打印制作实体迷宫游戏，30×30 左右的尺寸在标准 A4 纸上的视觉效果最佳，既有足够的复杂度又不至于过于密集。对于想要挑战极限的用户，可以尝试 80×80 甚至 100×100 的超大尺寸，但需要注意大尺寸迷宫在屏幕上需要滚动查看，生成动画可能会有轻微延迟，打印时也需要更大幅面的纸张和更高的分辨率设置。

这取决于您选择的求解算法类型。BFS（广度优先搜索）算法保证找到的路径是从起点到终点的最短路径，因为 BFS 是按照距离起点的远近逐层向外扩展的，第一次到达终点时经过的路径一定是最短的。而 DFS（深度优先搜索）算法找到的路径通常不是最短的，因为它会沿一条路径尽可能深入地探索，可能会绕很多弯路才到达终点。如果您需要确保找到最短路径，请在求解时选择 BFS 算法。值得一提的是，即使是最短路径，也可能存在多条等长的最短路径，BFS 会找到其中一条。