用C语言手搓一个迷宫游戏：从邻接矩阵到DFS/BFS路径搜索的完整实现
想象一下，你正站在一个迷宫的入口处，四周是高耸的墙壁，眼前是错综复杂的通道。你会选择哪种策略来找到出口？是像探险家一样沿着一条路一直走到底（DFS），还是像扫雷一样层层推进（BFS）？今天，我们就用C语言来实现这个有趣的迷宫游戏，同时探索这两种经典算法的奥秘。
1. 迷宫的数据结构设计
迷宫本质上就是一个图结构，每个交叉点或死胡同都可以看作图中的一个节点，而通道则是连接这些节点的边。在C语言中，我们通常用邻接矩阵或邻接表来表示图。
1.1 邻接矩阵表示法
邻接矩阵是一个二维数组，其中matrix[i][j]的值表示节点i和节点j之间是否有通路。对于迷宫来说，我们可以这样定义：
#define MAX_SIZE 100 // 迷宫最大尺寸 typedef struct { int size; // 迷宫实际尺寸 int matrix[MAX_SIZE][MAX_SIZE]; // 邻接矩阵 char nodes[MAX_SIZE]; // 节点附加信息（如坐标） } Maze;这种表示法的优点是查找两个节点是否相邻非常快（O(1)时间复杂度），但缺点是空间复杂度高（O(n²)），特别是对于稀疏的迷宫（通道较少的情况）。
1.2 邻接表表示法
邻接表使用链表来存储每个节点的相邻节点，更适合稀疏图：
typedef struct AdjListNode { int dest; struct AdjListNode* next; } AdjListNode; typedef struct { AdjListNode* head; } AdjList; typedef struct { int size; AdjList* array; char nodes[MAX_SIZE]; } Maze;邻接表的空间复杂度是O(V+E)，其中V是顶点数，E是边数，对于大多数迷宫来说更为高效。
提示：在实际项目中，如果迷宫规模较大且通道较少，邻接表是更好的选择；如果是小型迷宫或完全连通的迷宫，邻接矩阵可能更简单直观。
2. 迷宫生成算法
2.1 随机Prim算法
Prim算法不仅可以用于生成最小生成树，还能用来创建有趣的迷宫。它的核心思想是随机选择"墙"来打破，逐步扩展迷宫区域。
void generateMaze(Maze* maze) { // 初始化所有墙都存在 for(int i=0; i<maze->size; i++) { for(int j=0; j<maze->size; j++) { maze->matrix[i][j] = 0; // 0表示无通路 } } // 随机选择一个起始单元格 int start = rand() % maze->size; int visited[maze->size]; memset(visited, 0, sizeof(visited)); visited[start] = 1; // 使用优先队列存储边界墙 // 实际实现中可以用数组模拟 // ... while(/* 还有未访问的单元格 */) { // 随机选择一个已访问单元格的未访问邻居 // 打破它们之间的墙 // 标记邻居为已访问 // 将邻居的未访问邻居加入边界 } }2.2 递归分割法
这种方法将迷宫区域递归地分割为更小的区域，然后在分割线上开洞：
- 将整个迷宫作为一个区域
- 选择一个分割线（水平或垂直）
- 在分割线上随机开几个洞
- 对每个子区域递归应用相同的方法
这种方法生成的迷宫通常有更长的走廊和更少的死胡同。
3. 迷宫可视化
在控制台中显示迷宫是一门艺术。我们可以用简单的ASCII字符来表示墙壁和通道：
void printMaze(Maze* maze) { for(int i=0; i<maze->size; i++) { for(int j=0; j<maze->size; j++) { if(maze->matrix[i][j]) { printf(" "); // 通路 } else { printf("██"); // 墙 } } printf("\n"); } }更高级的可视化可以包括：
- 使用不同颜色区分已访问和未访问区域
- 显示当前搜索路径
- 动画效果展示搜索过程
4. 深度优先搜索(DFS)实现
DFS就像一个人在迷宫中探索，总是选择一条路走到尽头，然后回溯尝试其他路径。
4.1 递归实现
int dfs(Maze* maze, int current, int end, int* visited, int* path) { static int found = 0; if(current == end) { path[current] = 1; return 1; // 找到终点 } visited[current] = 1; for(int neighbor=0; neighbor<maze->size; neighbor++) { if(maze->matrix[current][neighbor] && !visited[neighbor]) { if(dfs(maze, neighbor, end, visited, path)) { path[current] = 1; // 标记路径 return 1; } } } return 0; }4.2 非递归实现（使用栈）
int dfs_iterative(Maze* maze, int start, int end, int* path) { int stack[MAX_SIZE]; int top = -1; int visited[MAX_SIZE] = {0}; int parent[MAX_SIZE]; stack[++top] = start; visited[start] = 1; parent[start] = -1; while(top >= 0) { int current = stack[top--]; if(current == end) { // 回溯构建路径 int node = end; while(node != -1) { path[node] = 1; node = parent[node]; } return 1; } for(int neighbor=0; neighbor<maze->size; neighbor++) { if(maze->matrix[current][neighbor] && !visited[neighbor]) { visited[neighbor] = 1; parent[neighbor] = current; stack[++top] = neighbor; } } } return 0; }DFS的特点：
- 内存消耗相对较小（栈深度）
- 可能会找到非常绕的路径
- 实现简单直观
5. 广度优先搜索(BFS)实现
BFS像水波纹一样从起点向外扩散，总是先探索距离起点更近的节点，因此能找到最短路径。
5.1 BFS实现代码
int bfs(Maze* maze, int start, int end, int* path) { int queue[MAX_SIZE]; int front = 0, rear = 0; int visited[MAX_SIZE] = {0}; int parent[MAX_SIZE]; queue[rear++] = start; visited[start] = 1; parent[start] = -1; while(front < rear) { int current = queue[front++]; if(current == end) { // 回溯构建路径 int node = end; while(node != -1) { path[node] = 1; node = parent[node]; } return 1; } for(int neighbor=0; neighbor<maze->size; neighbor++) { if(maze->matrix[current][neighbor] && !visited[neighbor]) { visited[neighbor] = 1; parent[neighbor] = current; queue[rear++] = neighbor; } } } return 0; }5.2 BFS与DFS的比较
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈 |
| 空间复杂度 | O(V) | O(d) (d为最大深度) |
| 找到的路径 | 最短路径 | 不一定最短 |
| 适用场景 | 寻找最短路径 | 拓扑排序、连通分量 |
| 实现难度 | 中等 | 简单 |
注意：在迷宫中，如果只需要判断是否有路径而不关心路径长度，DFS通常更快；如果需要最短路径，则必须使用BFS。
6. 性能优化与扩展功能
6.1 双向BFS
对于大型迷宫，可以同时从起点和终点开始BFS，当两个搜索相遇时即找到路径。这种方法可以显著减少搜索空间。
int bidirectional_bfs(Maze* maze, int start, int end, int* path) { int queue1[MAX_SIZE], queue2[MAX_SIZE]; int front1=0, rear1=0, front2=0, rear2=0; int visited1[MAX_SIZE] = {0}, visited2[MAX_SIZE] = {0}; int parent1[MAX_SIZE], parent2[MAX_SIZE]; queue1[rear1++] = start; visited1[start] = 1; parent1[start] = -1; queue2[rear2++] = end; visited2[end] = 1; parent2[end] = -1; while(front1<rear1 && front2<rear2) { // 扩展前向搜索 int current1 = queue1[front1++]; if(visited2[current1]) { // 找到交汇点，构建路径 build_path(parent1, parent2, current1, path); return 1; } // ... 扩展邻居 // 扩展反向搜索 int current2 = queue2[front2++]; if(visited1[current2]) { // 找到交汇点，构建路径 build_path(parent1, parent2, current2, path); return 1; } // ... 扩展邻居 } return 0; }6.2 A*算法
结合了BFS和启发式搜索，使用优先队列，总是优先扩展最有希望的节点：
typedef struct { int node; int cost; // f(n) = g(n) + h(n) } AStarNode; int heuristic(int a, int b) { // 简单的曼哈顿距离启发式 int x1 = a % MAZE_WIDTH, y1 = a / MAZE_WIDTH; int x2 = b % MAZE_WIDTH, y2 = b / MAZE_WIDTH; return abs(x1-x2) + abs(y1-y2); } void a_star(Maze* maze, int start, int end, int* path) { // 使用优先队列实现 // 每个节点记录g值（实际成本）和f值（g+h） // ... }6.3 迷宫游戏扩展功能
- 多关卡设计：不同大小和复杂度的迷宫
- 动态障碍物：会移动的墙或敌人
- 收集物品：需要在路径上收集钥匙等物品
- 可视化工具：实时显示搜索过程和算法比较
- 性能统计：比较不同算法的时间和空间复杂度
7. 实际项目中的应用技巧
在实现迷宫游戏时，有几个容易踩坑的地方需要注意：
- 边界条件处理：确保搜索不会越界，特别是在迷宫边缘
- 内存管理：特别是使用邻接表时，记得释放分配的内存
- 随机数生成：迷宫生成需要良好的随机性，避免可预测的模式
- 路径回溯：记录父节点时确保正确性，否则路径构建会出错
- 可视化优化：控制台刷新频率不宜过高，否则会导致闪烁
一个实用的调试技巧是在搜索过程中打印当前状态：
void print_search_state(Maze* maze, int* visited, int* path) { for(int i=0; i<maze->size; i++) { for(int j=0; j<maze->size; j++) { int node = i*maze->size + j; if(path[node]) printf("PP"); else if(visited[node]) printf(".."); else if(maze->matrix[i][j]) printf(" "); else printf("██"); } printf("\n"); } printf("\n"); }在迷宫算法的实际应用中，我发现最有趣的部分是观察不同算法探索迷宫的方式。DFS像是一个固执的探险家，执着地深入每个角落；而BFS则像是一支训练有素的搜救队，系统性地覆盖每个区域。当实现双向BFS时，看到从两端出发的搜索最终相遇，那种感觉就像见证了两个探险队在迷宫中心胜利会师。
