第一眼看到“用 C 语言实现一个走迷宫小游戏深度优先算法”这个题目我就觉得它特别适合拿来练手。你想想语法刚学完指针还没用熟链表还在背手里的 C 语言好像只能写个九九乘法表和猜数字。但迷宫游戏不一样它既要你动手操作一堆数组又要你理解递归、回溯、栈这些数据结构概念最后还能在终端里跑出一个看得见、玩得着的东西这种正反馈是教科书给不了的。我自己前段时间重新把这套代码从头到尾写了一遍越写越觉得“深度优先算法”这几个字被低估了。它既用来生成地图又用来自动求解一套思路打通了整个项目。这篇文章不打算堆概念我会直接带你从设计思路走一遍然后把关键代码逐段拆开讲最后列出我踩过的坑。内容适合刚学完 C 语言、想找一个综合性小项目练手的人也适合那些准备应付课程设计、但又想把算法真正弄明白的同学。1. 项目定位与整体设计思路1.1 先看清楚这个游戏到底要做什么很多同学拿到题目就急着写代码结果写着写着发现自己连“迷宫用什么数据结构存”都没想清楚。我这个项目在动手之前先拆出了四个功能模块地图生成让程序自己随机生成一张迷宫保证从起点到终点有路可走。地图渲染把二维数组变成终端里能看的画面。玩家移动接收方向输入让玩家在地图中走动撞墙不能走。自动求解按下一个键让程序用深度优先算法自己找一条路走出来。模块拆完你就明白核心难点其实就两个一是“生成”二是“求解”。渲染和移动都只是对同一个二维数组做读写。这样定位好之后整个项目的复杂度一下就降低了。1.2 为什么要用深度优先算法而不是别的算法迷宫生成算法有一大堆常见的有深度优先、广度优先、随机 Prim、Kruskal 等。为什么这个项目的标题点名要深度优先因为它生成的迷宫有一种非常典型的“气质”走廊又长又绕树枝状延伸岔路多但不容易一眼看穿。用深度优先生成的迷宫被称为“完美迷宫”翻译得直白一点就是从任意一个格子到任意另一个格子只有唯一一条路径不存在回路也不会有一大片像广场一样的开阔区域。如果换成 Prim 算法生成的迷宫会比较“均匀”每个死胡同都很短整个迷宫看起来像蜂窝煤一样密集。如果换成广度优先它又会像水波一样一圈一圈扩散迷宫整体显得太“整齐”。而深度优先那种一条路走到黑、把支路拉得很长的感觉才是最像传统意义上的迷宫。更重要的是深度优先算法的思路同时可以用在两个阶段生成迷宫时它是“探索地图、打通墙壁”求解迷宫时它是“试探路径、走不通回头”。一套核心思想解决两个问题这正是这个项目最有教学价值的地方。1.3 数据表示一张二维数组就能撑起整个迷宫可能有人会想到用图、用节点、用链表来表示迷宫但在 C 语言的项目里最朴素、最可靠的方案就是二维数组。我采用的模型是这样的整个迷宫是一张长宽都为奇数的二维数组比如 21x21。数组里只存两种值0 表示可以走的路1 表示墙壁。为什么是奇数因为这样迷宫内部才能有“奇数坐标是格子、偶数坐标是墙”的整齐划分。起点固定在数组的(1,1)位置。终点固定在数组的(H-2, W-2)位置。玩家当前位置用两个变量py、px单独记录不写进数组。这样做的好处非常明显地图生成、玩家移动、自动求解所有操作都只是对int maze[H][W]这个数组里的 0 和 1 做判断。你不用设计复杂的图结构也不用动态申请内存一个静态数组足够一个小型单文件游戏用了。2. 深度优先生成迷宫原理与优化2.1 把“回溯”想成探险家走迷宫深度优先生成迷宫的过程可以想象成一个探险家在未知区域里作业。探险家从起点出发每到一个岔路口就随机挑一条没走过的路走如果某条路走到尽头、四面都是墙他就沿着来时的路线退回上一个岔路口换一条没走过的路继续探索。直到整个迷宫的所有格子都被走过探险工作结束。在代码里这个“探险家”就是程序正在访问的格子而“来时的路线”就是存储在栈里的格子坐标当面前的格子四个方向都无法继续时就从栈顶弹出当前格子回到上一个格子。弹出的动作就是“回溯”。这一套逻辑就是深度优先算法在迷宫生成中的核心。你要想在代码里写不出来只需要掌握三个动作入栈、出栈、判断邻居格子是否已经访问过。2.2 随机化决定迷宫的“性格”深度优先算法本身是确定性的只要访问顺序固定生成出来的迷宫也就固定。放到游戏里如果每次跑起来迷宫都一样那这个游戏就没有新鲜感了。所以要在算法里加入随机化。我这里的做法是每次要选择下一步之前把四个方向打乱顺序然后按打乱后的顺序依次检查。用 C 语言实现打乱一般是一次简单的 Fisher-Yates 洗牌或者直接用rand() % 4交换几个位置。这里有一个很容易犯的错忘记调用srand(time(NULL))或者srand(1)导致每次运行生成的迷宫完全相同。正确的做法是在main函数进入后、调用生成函数之前先执行srand((unsigned)time(NULL))以系统时间作为随机种子。这样一来你每次运行程序都能得到一张全新的迷宫。如果你不洗牌只按固定的上、下、左、右顺序去访问那生成的迷宫会变成一种非常规律的“梳子”形状失去意义。随机化不是锦上添花是让迷宫真正“迷宫”起来的前提。2.3 显式栈替代递归的细节网上很多教程用递归写深度优先生成迷宫代码确实短几行就完事。但我更推荐在生成阶段使用显式栈也就是自己维护一个数组当栈用。为什么因为在生成迷宫时递归的深度可能达到格子总数级别。一张 21x21 的迷宫有 100 个左右的格子递归没问题但如果你把迷宫改成 101x101递归调用深度可能接近 5000 层。C 语言默认的函数调用栈一般只有几 MB递归太深就可能栈溢出程序会直接崩掉。而显式栈版本本质上和递归是同一个逻辑只是把函数调用栈换成了自己控制的内存数组。它可以放心地处理更大规模的迷宫也更容易让初学者看见“回溯”到底是怎么发生的。所以下面代码里我选择用显式栈来生成迷宫用递归来求解迷宫。这样两种写法你都能见到也方便对比。3. C语言实现从生成到求解的完整代码3.1 地图初始化与方向数组在迷宫生成开始之前需要把整个数组都填成墙也就是全部置 1。然后把起点(1,1)置 0表示起点是可以走的。方向数组是这个项目里比较有巧思的部分。生成迷宫时我要从一个格子跳到它相隔两格的邻居中间那个格子就是要打通的墙。所以我准备了这样两组坐标gen_dy/gen_dx用来表示“上、下、左、右”每步移动两格坐标的变化例如向上是(-2,0)。wall_dy/wall_dx用来表示“当前格子和邻居之间的那面墙的坐标偏移”例如向上是(-1,0)。这是一个很容易写混的地方。你如果不把这两组方向放在一起看很容易出现“移动了格子但是忘了打通墙”或者“把墙打通到莫名其妙的位置”这种低级错误。方向表写清楚后面生成逻辑就只剩一个循环判断。3.2 生成迷宫显式栈版的深度优先核心生成逻辑可以概括成下面这段伪代码把起点入栈。只要栈不为空就一直循环查看栈顶格子也就是当前正在探索的格子。随机打乱四个方向的顺序。依次检查每个方向如果下一个格子在地图内且还是墙说明没访问过那就把当前格子与邻居之间的墙壁置 0把邻居置 0并将邻居入栈跳出循环。如果四个方向都走不了就弹出栈顶回溯到上一个格子。关键代码看起来是这样while (top 0) { Point cur peek(); int order[4] {0, 1, 2, 3}; shuffle(order, 4); int moved 0; for (int i 0; i 4; i) { int d order[i]; int ny cur.y gen_dy[d]; int nx cur.x gen_dx[d]; if (ny 0 ny H nx 0 nx W maze[ny][nx] 1) { maze[cur.y wall_dy[d]][cur.x wall_dx[d]] 0; maze[ny][nx] 0; push((Point){ny, nx}); moved 1; break; } } if (!moved) { pop(); } }这里有一个细节值得强调为什么邻居必须是墙才说明它没有访问过因为在生成过程中所有访问过的格子都会被置为 0而没被访问过的格子还保持着初始的墙状态 1。所以maze[ny][nx] 1既是“这里是墙”的判断也是“这里还没被走过”的判断。两个信息是合并在一起的。生成结束后我还会单独把终点格子置 0确保终点不会被墙堵住maze[H - 2][W - 2] 0;注意这一步其实是锦上添花。按照深度优先的生成规则终点格子一定会在探索过程中被访问到并置 0。但单独强调一次可以让代码逻辑更清晰也避免偶发边界问题。3.3 渲染与玩家移动让迷宫真正“可玩”渲染很简单。我采用“双字符宽度”的打印方式每个格子输出两个字符。墙用#路用两个空格玩家用终点用E。这样在终端里看起来格子的长宽比例比较接近正方形。打印整个地图之前先调用system(clear)清理屏幕然后一格格输出。代码大概是这样void draw_map(int py, int px) { clear_screen(); for (int y 0; y H; y) { for (int x 0; x W; x) { if (y py x px) { printf( ); } else if (y H - 2 x W - 2) { printf(E ); } else if (maze[y][x] 0) { printf( ); } else { printf(# ); } } printf(\n); } }玩家移动的逻辑比想象中简单。我接收w/a/s/d四个字符分别对应上、下、左、右。每得到一个指令就计算出目标坐标(ny,nx)然后判断这个坐标是否在地图范围内、且maze[ny][nx] 0。如果可以通过就更新玩家坐标否则忽略。这里最容易忽略的是输入缓冲区的换行符。如果直接用getchar()你按下w再回车程序会收到w和\n两个字符。如果不在内层循环里把换行符吃掉玩家按一次w可能触发两次移动判断。所以我的处理方式是在内层循环里持续读字符读到换行符再退出。顺带提一句如果你想做成那种“不用回车、按下就动”的实时游戏体验就要使用非标准输入函数了Windows 下用_getch()Linux 下要设置终端为原始模式。为了保持代码可移植和简单我提供了回车确认版。3.4 自动求解同一个深度优先换一种用法生成迷宫时我们已经见识了深度优先的威力。求解阶段我把深度优先再用一次。这一次逻辑正好反过来生成迷宫时我按两格一格跳动中间打通墙求解时我从玩家当前位置出发每次走一格检查相邻格子是否为路值为 0并在visited数组里记录哪些格子已经走过避免重复绕圈。核心代码是递归版本int solve_dfs(int y, int x, int ey, int ex) { if (y ey x ex) { path[y][x] 1; return 1; } visited[y][x] 1; int order[4] {0, 1, 2, 3}; shuffle(order, 4); for (int i 0; i 4; i) { int d order[i]; int ny y sol_dy[d]; int nx x sol_dx[d]; if (ny 0 ny H nx 0 nx W !visited[ny][nx] maze[ny][nx] 0) { if (solve_dfs(ny, nx, ey, ex)) { path[y][x] 1; return 1; } } } return 0; }当递归到终点时函数返回 1每一层递归在回退过程中都会把当前格子标记进path数组。最终path数组里值为 1 的格子就是一条从起点到终点的路径。然后在绘图函数里增加一个判断如果path[y][x]为 1就打印*星号。这样玩家按下r键程序就会自动找出一条路径并画在迷宫上。这里有一个很多教程没讲明白的点在“完美迷宫”里为什么深度优先一定能找到路径因为任意两个格子之间只有唯一通路所以深度优先只需要不断试探一旦走到死胡同就回溯最终总能到达终点。它的效率可能不高因为可能会先走进几个死胡同再退出来但结果一定正确。如果换成一张有环路的迷宫那就要加上visited判断否则可能死循环这也是我保留visited数组的原因。3.5 完整可编译代码下面是我整理后的完整代码。我建议你直接复制到一个.c文件里编译运行。#include stdio.h #include stdlib.h #include string.h #include time.h #define W 21 #define H 21 int maze[H][W]; int visited[H][W]; int path[H][W]; typedef struct { int y, x; } Point; Point stack[H * W]; int top 0; int gen_dy[4] {-2, 2, 0, 0}; int gen_dx[4] {0, 0, -2, 2}; int wall_dy[4] {-1, 1, 0, 0}; int wall_dx[4] {0, 0, -1, 1}; int sol_dy[4] {-1, 1, 0, 0}; int sol_dx[4] {0, 0, -1, 1}; void push(Point p) { if (top H * W) stack[top] p; } Point pop(void) { return stack[--top]; } Point peek(void) { return stack[top - 1]; } void swap(int *a, int *b) { int t *a; *a *b; *b t; } void shuffle(int arr[], int n) { for (int i n - 1; i 0; i--) { int j rand() % (i 1); swap(arr[i], arr[j]); } } void generate_maze(void) { for (int y 0; y H; y) { for (int x 0; x W; x) { maze[y][x] 1; } } srand((unsigned)time(NULL)); top 0; maze[1][1] 0; push((Point){1, 1}); while (top 0) { Point cur peek(); int order[4] {0, 1, 2, 3}; shuffle(order, 4); int moved 0; for (int i 0; i 4; i) { int d order[i]; int ny cur.y gen_dy[d]; int nx cur.x gen_dx[d]; if (ny 0 ny H nx 0 nx W maze[ny][nx] 1) { maze[cur.y wall_dy[d]][cur.x wall_dx[d]] 0; maze[ny][nx] 0; push((Point){ny, nx}); moved 1; break; } } if (!moved) { pop(); } } maze[H - 2][W - 2] 0; } void clear_screen(void) { system(clear); // Windows 下把上面那行改成system(cls); } void draw_map(int py, int px) { clear_screen(); for (int y 0; y H; y) { for (int x 0; x W; x) { if (y py x px) { printf( ); } else if (y H - 2 x W - 2) { printf(E ); } else if (maze[y][x] 0) { printf( ); } else { printf(# ); } } printf(\n); } } int solve_dfs(int y, int x, int ey, int ex) { if (y ey x ex) { path[y][x] 1; return 1; } visited[y][x] 1; int order[4] {0, 1, 2, 3}; shuffle(order, 4); for (int i 0; i 4; i) { int d order[i]; int ny y sol_dy[d]; int nx x sol_dx[d]; if (ny 0 ny H nx 0 nx W !visited[ny][nx] maze[ny][nx] 0) { if (solve_dfs(ny, nx, ey, ex)) { path[y][x] 1; return 1; } } } return 0; } void draw_solution(int py, int px) { clear_screen(); for (int y 0; y H; y) { for (int x 0; x W; x) { if (y py x px) { printf( ); } else if (path[y][x]) { printf(* ); } else if (maze[y][x] 0) { printf( ); } else { printf(# ); } } printf(\n); } printf(已用深度优先算法找到一条路径按任意键返回游戏。\n); } int main(void) { generate_maze(); int px 1, py 1; int ex W - 2, ey H - 2; while (1) { draw_map(py, px); if (py ey px ex) { printf(恭喜到达终点输入 q 退出。\n); } int c getchar(); while (c ! \n c ! EOF) { int nx px, ny py; if (c w || c W) ny--; else if (c s || c S) ny; else if (c a || c A) nx--; else if (c d || c D) nx; else if (c r || c R) { memset(visited, 0, sizeof(visited)); memset(path, 0, sizeof(path)); if (solve_dfs(py, px, ey, ex)) { draw_solution(py, px); getchar(); } else { printf(没有找到路径这不应当出现。\n); } } else if (c q || c Q) { return 0; } if (nx 0 nx W ny 0 ny H maze[ny][nx] 0) { px nx; py ny; } c getchar(); } } return 0; }编译命令很简单以 GCC 为例gcc maze.c -o maze ./maze如果你在 Windows 下编译记得把clear_screen里的system(clear)改成system(cls)。如果用的是较老的编译器//行注释也可以用但保留 ANSI 风格会更稳。4. 开发中的坑与调试技巧4.1 迷宫不完整或者出现大片空白如果你运行之后发现迷宫里有大片空白区域或者有些格子孤立在墙里走不进去问题大概率出在“邻居判断”上。最常见的错误有两个第一忘记检查越界导致程序访问了maze[-1][x]或者maze[H][x]出现未定义行为第二邻居格子是否访问过的判断写反比如用maze[ny][nx] 0作为可以前进的条件结果程序永远只走已经访问过的格子走几步就停。调试这种问题最好的方法不是盲猜而是把小地图改成 5x5 或 7x7然后在生成函数里加打印每走一步输出当前栈顶坐标和访问格子数量。小地图上逻辑一目了然很快就能定位到是哪一步打错了。4.2 输入空格键和换行符带来的奇怪行为这个坑第一次遇到时我真的懵了。玩家按w后画面闪了一下却感觉走了两步或者完全没有反应。原因就是getchar()会读取回车产生的换行符。我最后采取的办法是内层循环持续读取字符直到读到\n才结束。这样就保证一次按键只处理一次移动。但这也意味着每按一次键都要多敲一次回车手感偏“回合制”。如果追求更顺滑的体验就要用_getch()或 Linux 下的原始终端模式让按键不经过回车缓冲直接进入程序。4.3 递归深度和栈溢出不是玄学我见过不少人把生成迷宫写成递归然后兴高采烈地把迷宫尺寸改成 201x201一运行直接段错误。这不是代码逻辑的问题而是函数调用栈被递归调用撑爆了。深度优先生成迷宫的递归深度和迷宫大小强相关你永远不知道某条路径会延伸多长。因此我的建议是生成部分用显式栈求解部分用递归。求解的递归深度最多不会超过格子数量21x21 的迷宫完全没问题如果你以后要挑战 501x501 的超级迷宫求解部分最好也改成显式栈或者用迭代加深。4.4 终端闪屏、中文乱码和字符比例控制台游戏的体验很大程度靠渲染调优。我之前用单字符渲染结果迷宫看起来又扁又窄后来改成每个格子输出两个字符画面比例就正常多了。闪屏问题一般出现在迷宫尺寸太大时每次system(clear)加上一千行输出会让终端闪烁。解决思路有两个一是缩小地图到 21x21、31x31 这类合理范围二是把整个画面先拼到一个字符串缓冲区里最后一次printf输出。后者思路类似双缓冲实现也不难你可以自己改着玩玩。中文乱码问题通常是 Windows 控制台代码页引起的。字符编码调试起来特别讨厌所以我全程只打印#、、E、*这类 ASCII 字符避免和中文空格或特殊符号纠缠。4.5 常见错误速查表症状可能原因解决办法迷宫生成后很多墙没打通邻居访问条件写反检查maze[ny][nx] 1和越界判断每次运行迷宫一样没有srand(time(NULL))在生成前调用一次按一次方向键触发两次移动没有处理换行符内层循环清空\n迷宫稍大就崩溃生成用了递归改为显式栈实现墙上出现玩家可以穿过的洞打通墙的坐标算错验证wall_dy/wall_dx方向表求解时程序卡死缺少visited标记递归前标记已访问Windows 下画面不刷新用了clear而不是cls替换为system(cls)5. 后续玩法与学习建议5.1 地图尺寸、棋盘比例和终点的调整改迷宫大小很简单只改W和H两个宏就行但必须保证是奇数。比如设置成 31x31迷宫规模会比默认大一圈跑起来更有身临其境的感觉。还要注意端点和起点的坐标。起点永远在(1,1)终点永远在(H-2, W-2)这两个坐标都和尺寸动态相关不要写死成19,19。一旦改了尺寸却不改终点终点就可能落在墙里。如果你想让迷宫更“壮观”可以试试打印时在字符之间不补空格改用 Unicode 的方块字符█。不过这样要考虑终端编码和字体宽度我建议先跑通 ASCII 版本再折腾美化。5.2 换用 Prim 或 BFS 感受算法的差异做完深度优先版本之后我非常建议你再写一个 Prim 算法版本对比同一张尺寸下两种迷宫的模样。这个对比能让你真正理解“数据结构决定算法行为”这句话。Prim 算法维护一个候选边集合每一步从集合里挑一条边打通看起来不会产生很长很深的走廊分支更均匀。广度优先生成迷宫则是从一个起点按层扩散迷宫会呈现类似年轮的结构。这三种算法生成出来的迷宫你在终端里一眼就能分辨出来。这种对比实验的价值在于算法不是背出来的而是调试出来的。你看得越多动手改得越多才会对递归、队列、栈这些概念有肌肉记忆。5.3 给初学者的三条实践建议第一不要直接复制我的完整代码。你至少应该自己把生成函数重写一遍哪怕对着参考代码敲一遍也行。手敲和复制粘贴的理解深度完全不同。第二从小尺寸开始调试。先用 7x7 的迷宫跑通生成逻辑再慢慢改大。小磁场上你能完整看到每个墙是怎么打通的出错也容易定位。第三给代码加注释没有坏处。过两周你再回头看这份代码会感谢当时写注释的自己。尤其是方向数组和栈的回溯逻辑就算再过半年也是重点。我个人在实际操作中的一个体会是深搜求解时把路径用星号标出来其实比玩家自己走更让人兴奋。看着程序从的位置一路试探、碰壁、回头、再前进最后画出一条完整的*路径你会觉得递归这个东西不再抽象了。如果还有余力你可以在自动求解后面再加一步“路径动画”让求解器每次找到下一步时休眠几十毫秒把递归回溯的过程一帧一帧画出来。那才是把这个项目做得最酷的收尾方式。