用C语言手搓一个迷宫游戏：从邻接矩阵到DFS/BFS路径搜索的完整实现

用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(VE)其中V是顶点数E是边数对于大多数迷宫来说更为高效。提示在实际项目中如果迷宫规模较大且通道较少邻接表是更好的选择如果是小型迷宫或完全连通的迷宫邻接矩阵可能更简单直观。2. 迷宫生成算法2.1 随机Prim算法Prim算法不仅可以用于生成最小生成树还能用来创建有趣的迷宫。它的核心思想是随机选择墙来打破逐步扩展迷宫区域。void generateMaze(Maze* maze) { // 初始化所有墙都存在 for(int i0; imaze-size; i) { for(int j0; jmaze-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 i0; imaze-size; i) { for(int j0; jmaze-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 neighbor0; neighbormaze-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 neighbor0; neighbormaze-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 neighbor0; neighbormaze-size; neighbor) { if(maze-matrix[current][neighbor] !visited[neighbor]) { visited[neighbor] 1; parent[neighbor] current; queue[rear] neighbor; } } } return 0; }5.2 BFS与DFS的比较特性BFSDFS数据结构队列栈空间复杂度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 front10, rear10, front20, rear20; 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(front1rear1 front2rear2) { // 扩展前向搜索 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值gh // ... }6.3 迷宫游戏扩展功能多关卡设计不同大小和复杂度的迷宫动态障碍物会移动的墙或敌人收集物品需要在路径上收集钥匙等物品可视化工具实时显示搜索过程和算法比较性能统计比较不同算法的时间和空间复杂度7. 实际项目中的应用技巧在实现迷宫游戏时有几个容易踩坑的地方需要注意边界条件处理确保搜索不会越界特别是在迷宫边缘内存管理特别是使用邻接表时记得释放分配的内存随机数生成迷宫生成需要良好的随机性避免可预测的模式路径回溯记录父节点时确保正确性否则路径构建会出错可视化优化控制台刷新频率不宜过高否则会导致闪烁一个实用的调试技巧是在搜索过程中打印当前状态void print_search_state(Maze* maze, int* visited, int* path) { for(int i0; imaze-size; i) { for(int j0; jmaze-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时看到从两端出发的搜索最终相遇那种感觉就像见证了两个探险队在迷宫中心胜利会师。