在游戏开发、路径规划训练和算法教学中，迷宫生成是一类经典问题。不同算法不仅影响迷宫的视觉结构，更直接决定了生成效率与解法难度。本文从工程实现角度，对四种经典迷宫生成算法进行深度解析，给出可直接落地的参数建议与性能对比。
递归回溯算法：深度优先的直观实现
递归回溯（Recursive Backtracking）又称深度优先搜索（DFS）算法，是最直观的迷宫生成方法。其核心思想是从起始单元格出发，随机选择未访问的相邻单元格并打通墙壁，持续前进直至无法继续时回溯寻找新的分支。
在工程实现中，该算法需要维护一个访问标记数组和可选邻接列表。推荐使用栈结构显式实现而非递归调用，以避免大规模网格下的栈溢出问题。伪代码实现如下：初始化访问数组为全 false，将起始点入栈；当栈非空时弹出栈顶，查找其未访问邻接点；若存在则随机选择一个邻接点、打通当前点与邻接点之间的墙壁、标记邻接点为已访问并入栈；若不存在则继续弹栈。关键参数包括随机数生成器的种子（建议使用系统时间或 UUID 确保每次运行不同）以及邻接点选择顺序（洗牌算法可确保真正随机）。
该算法的时间复杂度为 O (N)，空间复杂度为 O (N)，其中 N 为单元格总数。实际测试中，100×100 网格生成时间通常在 50 毫秒以内。生成的迷宫特征为长走廊较多、分支点密集，对玩家而言难度较高但探索趣味性强。
Prim 算法：平衡走廊的最小生成树
Prim 算法源自最小生成树思想，其核心是从单个起始单元格开始，逐步将 “前沿” 单元格纳入迷宫。每次随机选择一条连接已访问区域与未访问区域的墙壁，打通后将该未访问单元格加入已访问区域。
工程实现需要维护一个前沿列表（Frontier List）。初始时将起始单元格的所有邻接边加入前沿；每次迭代从前沿中随机选择一条边，若边的另一端未被访问，则打通墙壁并将新单元格的未访问邻接边加入前沿。为提升性能，前沿列表可使用哈希集合实现 O (1) 查找，或使用优先队列按特定权重选择。推荐参数：前沿列表最大规模约为单元格总数的 O (log N)，对于常规游戏地图可直接使用动态数组。
时间复杂度为 O (N log N) 或 O (N)（取决于数据结构选择），空间复杂度为 O (N)。Prim 算法生成的迷宫走廊长度分布较为均匀，分支密度适中，适合需要 “可解但不太难” 场景的游戏。实测 50×50 网格生成时间通常在 20 至 40 毫秒区间。
Kruskal 算法：全局随机性的边驱动
Kruskal 算法将迷宫生成转化为最小生成树问题，但采用随机顺序处理所有可能的墙壁边。其核心数据结构为并查集（Disjoint-Set Union，DSU），用于判断两个单元格是否已连通。
工程实现步骤如下：首先枚举所有可能的墙壁边并随机打乱顺序；遍历每条边，使用并查集判断边的两端是否属于同一集合；若不属于则打通墙壁并合并两个集合。并查集实现需包含路径压缩和按秩合并两个优化，这使得 find 和 union 操作均摊复杂度接近 O (α(N))，其中 α 为阿克曼函数的反函数。
该算法时间复杂度为 O (E α(E))，空间复杂度为 O (N + E)，E 为边数（约为 2N）。由于边处理顺序完全随机，Kruskal 算法产生的迷宫局部 randomness 强，整体结构均匀。缺点是初期需要存储所有边，对于超大地图可能面临内存压力。工程建议：对于 100×100 以下网格可直接使用数组存储边，更大规模建议采用分块处理或流式边生成。
Eller 算法：逐行处理的内存友好型
Eller 算法是最适合大规模网格的迷宫生成方法，其独特之处在于仅需逐行处理即可生成完美迷宫（任意两点间唯一路径）。算法维护当前行的集合归属信息，每行处理时随机决定水平连接（同一行内相邻单元格是否打通）和垂直连接（当前行与下一行的连接）。
工程实现核心在于集合管理：每行开始时每个单元格属于独立集合；水平连接时若两个单元格属于不同集合则合并，并随机决定是否打通墙壁；垂直连接时每个集合必须至少与下一行建立一个连接以保证连通性，但只能有一个以避免环。关键参数是垂直连接的概率，建议设置为 0.3 至 0.5 之间以平衡走廊长度与分支密度。
该算法时间复杂度为 O (N)，空间复杂度仅为 O (W)，其中 W 为网格宽度（仅需保存当前行和下一行信息）。这一特性使 Eller 算法成为处理无限或超大规模迷宫的理想选择，如 RogueLike 游戏的地牢生成。1000×1000 网格生成时间可控制在 500 毫秒以内。
性能对比与选型建议
四种算法在生成特性与性能表现上存在显著差异。递归回溯适合需要高难度、长探索路径的场景；Prim 算法生成结构均衡，适合一般游戏关卡；Kruskal 算法随机性强，适合需要每次体验差异大的情况；Eller 算法则是大规模生成的首选。
工程实践中，可参考以下选型原则：网格小于 20×20 时四种算法性能差异可忽略，可任选；20×20 至 100×100 推荐 Prim 或 Kruskal，生成质量与性能平衡较好；100×100 以上强烈建议 Eller 算法，空间效率优势明显；若需要特定走廊长度分布，可在回溯算法中加入方向偏好参数调整。
以上四种算法的实现代码均可在网上找到成熟参考，具体选用时应结合项目需求与技术约束综合考量。
资料来源
本文算法原理参考维基百科迷宫生成算法词条及 Jamis Buck 的经典博客系列。