1. 引言
本文介绍如何通过算法生成迷宫。
我们关注的是完美迷宫（Perfect Maze），即迷宫中任意两个点之间有且仅有一条通路，不存在孤立区域。这种迷宫结构在游戏、路径规划、算法教学中都有广泛应用。
2. 迷宫类型概述
迷宫种类繁多，常见的有矩形迷宫、环形迷宫等。迷宫可以有一个或多个起点/终点，也可以有多条通路，甚至包含无法到达的区域。
✅ 完美迷宫的定义：迷宫中任意两点之间有且仅有一条路径，所有区域都可到达。这种迷宫没有循环，也没有孤立区域，结构简洁清晰。
我们接下来将重点介绍两种生成完美迷宫的方法：基于最小生成树（MST）的方法和基于随机深度优先搜索（DFS）的方法。
3. 基于 MST 的迷宫生成
生成完美迷宫的经典方法之一是利用最小生成树（Minimum Spanning Tree, MST）的思想。
📌 核心思路：
- 把迷宫中的每个格子看作图中的一个节点。
- 所有相邻格子之间的连接（上下左右）作为图的边。
- 给每条边分配一个随机权重。
- 使用 Kruskal 或 Prim 算法计算 MST。
- MST 中的边表示“打通”的墙，其余边表示“保留”的墙。
生成流程
- 初始化一个网格，每个格子四面都有墙。
- 构建图模型，连接所有相邻格子。
- 为每条边分配随机权重。
- 计算 MST。
- 删除 MST 中对应边的墙，最终形成完美迷宫。
示例图解
图1：初始网格
图2：生成 MST 后的图结构
图3：最终生成的迷宫
特点
- 保证迷宫完美性。
- 可使用最短路径算法（如 Dijkstra）寻找起点到终点的路径。
- 若将 MST 视为墙，可生成一条贯穿整个迷宫的唯一路径。
4. 基于随机 DFS 的迷宫生成
4.1 描述
另一种生成完美迷宫的方法是利用随机化深度优先搜索（Randomized DFS）。
📌 核心思想：
- 从某个起点开始，标记为已访问。
- 随机选择一个未访问的邻居，打通当前格子与邻居之间的墙。
- 递归或迭代地继续探索。
- 当当前格子无未访问邻居时，回溯至上一个有未访问邻居的格子。
- 所有格子都被访问后算法结束。
算法伪代码
algorithm CreateMaze():
// OUTPUT
// A maze generated using randomized DFS
startVertex <- Vertex(0, 0)
randomizedDFS(startVertex)
algorithm RandomizedDFS(vertex):
// INPUT
// vertex = current vertex in the maze
// OUTPUT
// Modifies the maze structure
mark vertex as visited
nextVertex <- next random unvisited neighbour
while nextVertex != null:
connectCells(vertex, nextVertex)
randomizedDFS(nextVertex)
nextVertex <- next random unvisited neighbour
⚠️ 注意：递归实现可能导致栈溢出，建议使用栈结构实现为迭代版本。
4.2 示例图解
动画中红色表示当前正在处理的格子。可以看到，随着迷宫不断扩展，跳跃的幅度也会变大。
图：随机 DFS 生成迷宫过程
特点
- 简单高效，适合快速实现。
- 迷宫结构偏向于“长路径 + 少分支”，回溯时容易形成死胡同。
- 生成的迷宫是完美迷宫，无孤立区域。
5. 总结
我们介绍了两种生成完美迷宫的方法：
| 方法 | 优点 | 缺点 |
|---|---|---|
| MST 基础方法 | 结构均匀，路径分布合理 | 实现复杂，计算开销较大 |
| 随机 DFS 方法 | 实现简单，效率高 | 结构偏向长路径，分支少 |
✅ 小贴士：
- 若你希望迷宫看起来更“自然”或“人工设计感强”，MST 方法是不错的选择。
- 如果你追求实现简单、快速生成，随机 DFS 更适合。
- 不论哪种方法，底层都是图结构，可以借助图论进行分析和优化。
迷宫生成不仅有趣，也是理解图论和算法的好方式。希望你通过本文掌握了实用的迷宫生成技巧，并能将其应用到自己的项目中！