基于DFS和BFS的迷宫生成与寻路：C语言数据结构课设实战

简介面向NOJ大作业的OpenGL实践项目核心功能是用代码绘制一只可爱小熊并通过旋转、平移等变换使其在电脑屏幕上跳舞。项目体量虽小但涵盖OpenGL绘图管线、模型组织、动画帧更新等基础知识点适合计算机图形学初学者与正在完成同类课程设计的同学们参考也适合对OpenGL动画控制感兴趣的开发者快速获取灵感。压缩包总计6个文件包括cpp源代码、exe可执行程序、Code::Blocks工程文件cbp、layout布局文件以及编译生成的o依赖文件既有可直接运行的成品也能打开工程查看源码和依赖关系方便二次修改。资源包仅21KB非常轻量。目前已有1928人学习下载热度表现不错。借助这套资源读者可以快速理解小熊建模、肢体旋转与动画计时等实现方法并将其中思路迁移到其他图形学作业中也可以直接运行exe观察效果再从cpp源码入手逐步调试提升对OpenGL的实操能力。1. 从“刷题”到“做项目”NOJ大作业为什么值得你认真写完如果你对NOJ的印象还停留在“在线刷题、攒AC数、考试前突击”这个层面那这篇博文可能会改变你的想法。NOJ大作业和平时那些判题题单完全是两种物种——题目只是给你一个函数或一段逻辑提交之后机器判个分就结束了大作业则要求你从头设计、动手实现、最终交付一个“能玩/能用/能演示”的完整程序。当时我拿到题目清单的时候一眼扫过去全是“图像增强、迷宫寻路、文本检索”这类听起来很唬人的方向而我的选择是不挑现成题目自己给自己定了一个基于深度优先搜索的迷宫生成与自动寻路程序并给整个工程起了个内部代号叫“快乐的小熊”。这个名字看起来随意其实藏着我的规划既然课程核心是数据结构与算法那这个项目就必须把栈、队列、图、搜索算法这些知识点全部装进去。迷宫生成器天然适合用递归回溯本质是栈实现自动寻路天然适合用BFS本质是队列再加上地图的二维数组建模、路径的可视化渲染整个项目几乎就是一本数据结构教材的浓缩版。做完之后你会发现NOJ大作业的意义不是让你交一份能跑的代码而是逼着你把课上那些孤立的概念串成一个整体——这玩意儿写进简历比十个“熟练使用C语言”管用得多。这篇文章我会把这套项目的完整思路、核心算法原理、踩过的坑、调试经验全部拆开讲清楚。不管你是南理工本校学生正在为这门课的期末作业头秃还是其他学校正被类似课设折磨只要你准备在C/C课设里做一个有分量的项目这篇内容都能直接作为你的开工参考。2. 核心算法选型迷宫生成与寻路为什么是DFS和BFS2.1 迷宫生成算法对比为什么不用Kruskal或随机Prim迷宫生成算法不止一种常见的有递归回溯Randomized DFS、随机Prim、Kruskal并查集生成等。很多人第一反应是“能生成就行”但课设大作业和玩具程序的区别就在于——你要能解释清楚为什么这么选。我逐个分析过递归回溯DFS生成的迷宫有非常明显的“长走廊”特征路径比较弯曲分支相对较少。内存占用极低实现代码最短是课程范围内最容易讲清楚原理的算法。算法复杂度O(V)对迷宫这种网格图来说非常高效。随机Prim生成结果偏向于“树状分叉多、走廊短”的风格整体更均匀。但它需要维护一个候选墙列表每次随机取一个代码量和调试成本都比DFS高不少。Kruskal本质是并查集应用把每个格子当作一个集合不断随机打通两个不同集合之间的墙。这个算法的特点是区域感强、迷宫纹理好看但要在课设里给评委讲清楚并查集和生成迷宫之间的关系等于给自己增加了一倍的答辩压力。对比下来我的选择是递归回溯。理由非常直接课设的核心目标是展示栈的运用、DFS思想、递归转非递归的能力而不是展示“我会写并查集”。用一个简单到极致的算法把程序结构做清晰、把交互做完善、把边界问题处理干净比堆一个华丽但解释不清的算法更有说服力。当然如果你已经熟练掌握了并查集和最小生成树做Kruskal版本的迷宫生成会让答辩老师眼前一亮这个后面我会在扩展方向里说。2.2 递归回溯生成迷宫核心原理和最小可用实现递归回溯的原理用一句话说就是从一个格子出发随机选择一个当前格子的相邻未访问格子拆掉中间的墙走到那个格子然后重复这个过程如果无路可走就回溯到上一个格子继续尝试。这个东西用图的角度理解特别直观迷宫本身是一个图每个格子是一个节点相邻格子之间原本有墙边断裂DFS就是沿着一条路走到黑走不通就退回来换一条路直到所有节点都被访问过一遍。最终生成的路径覆盖了所有格子并且是一棵生成树。代码实现上我用的是C语言纯递归版本核心逻辑浓缩下来只有几十行#define ROWS 21 // 奇数行列保证迷宫外围是墙 #define COLS 21 int maze[ROWS][COLS]; // 1表示墙0表示通路 int dirs[4][2] {{0, -2}, {0, 2}, {-2, 0}, {2, 0}}; void dfs_gen(int x, int y) { maze[x][y] 0; // 随机打乱方向顺序 for (int i 3; i 0; i--) { int j rand() % (i 1); int tmp dirs[i][0]; dirs[i][0] dirs[j][0]; dirs[j][0] tmp; tmp dirs[i][1]; dirs[i][1] dirs[j][1]; dirs[j][1] tmp; } for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; if (nx 0 nx ROWS - 1 ny 0 ny COLS - 1 maze[nx][ny]) { maze[x dirs[i][0] / 2][y dirs[i][1] / 2] 0; // 拆墙 dfs_gen(nx, ny); } } }这里有几个我踩过坑的细节必须说明第一为什么行列必须是奇数。如果迷宫尺寸是偶数生成时会出现边界格子无法正确配对墙的问题。比如在一个8×8的地图上从(0,0)出发跨两格走到(2,0)中间拆掉的墙是(1,0)但(1,0)又和相邻格子的距离不匹配整个迷宫会乱掉。把尺寸设为21×21、31×31这类奇数起始格坐标是(1,1)每次步进2拆墙位置始终落在中间格子上边界永远是一整圈完整的墙逻辑就自洽了。第二递归深度的风险。一眼看过去递归深度和格子数量成正比——对21×21的迷宫是大约100层递归没问题但如果哪天你把迷宫尺寸加到101×101递归深度就是2500层乘以分支深度C语言默认栈空间在Windows上是1MBLinux上是8MB极可能栈溢出。课程设计交上去的代码如果因为地图太大瞬间崩溃那基本等于当场社死。我的方案是在剖题阶段就限定迷宫规模在15×15到41×41之间并在生成前用ROWS * COLS / 4估算递归深度超过800就直接拒绝生成要求用户调整尺寸。这个“防御性设计”在答辩时反而是加分项。2.3 自动寻路BFS为什么是迷宫的最优解迷宫生成完之后我把入口设在地图左上角(1,1)出口设在右下角(ROWS-2, COLS-2)。然后写一个自动演示模式程序调用BFS算法从入口向出口搜索并把搜索过的路径用不同颜色标识出来最后展示一条最短路线。选BFS不选DFS做寻路核心原因就一条BFS天然保证第一次到达终点时的路径是步数最短的。迷宫这种无权图场景BFS按层扩展每一层都比上一层多走一步终点一旦被访问到那条路径必然是最短路径。DFS则完全看运气它可能在一条死胡同上走到黑跑出来的路径绕了好几圈。BFS需要维护一个先进先出的队列这正好呼应了课程里“广度优先遍历需要借助队列”的知识点。我把队列实现写成了一个独立的模块没有用链表而是用了环形队列数组简单直观typedef struct { int x, y; } Point; Point queue[ROWS * COLS]; int head 0, tail 0; // 记录每个格子的父节点用于回溯最短路径 Point pre[ROWS][COLS]; int visited[ROWS][COLS]; void bfs_find_path(int sx, int sy, int ex, int ey) { head tail 0; queue[tail] (Point){sx, sy}; visited[sx][sy] 1; while (head tail) { Point cur queue[head]; if (cur.x ex cur.y ey) break; for (int i 0; i 4; i) { int nx cur.x dirs[i][0] / 2; int ny cur.y dirs[i][1] / 2; if (nx 0 nx ROWS ny 0 ny COLS !visited[nx][ny] maze[nx][ny] 0) { visited[nx][ny] 1; pre[nx][ny] cur; queue[tail] (Point){nx, ny}; } } } }这里的pre数组是整个程序最妙的部分每个格子存着“我是从哪个格子走过来的”等到BFS结束从终点沿着pre一路回溯回起点倒序打印就是最短路径。这个“记录父节点”的技巧在几乎所有最短路径场景都适用课设做完了以后你以后做寻路类的项目还会反复用到它。3. 工程结构搭建一个拿得出手的大作业模块该怎么划分很多同学写课设喜欢把几百行代码一锅炖在main.c里函数之间互相调用全局变量满天飞。代码少的时候看着没什么等你要加功能、修bug的时候就是灾难。我做这个项目的时候刻意练习了模块化拆分整个工程分成了四个核心文件模块职责关键接口main.c程序入口、菜单循环、模式分发main(), run_menu()map.c / map.h迷宫地图的初始化、生成、存储、打印init_map(), dfs_generate(), render_map()algorithm.c / algorithm.h寻路算法与路径回溯bfs_find_path(), trace_path()input.c / input.h键盘交互、玩家手动走迷宫get_key(), move_player()模块划分的原则我总结成一句话谁的数据谁管理谁的功能谁实现。地图模块只管迷宫的所有数据算法模块只接收地图数组然后返回路径结果输入模块只处理按键和玩家坐标main.c只负责调用和组装。这样我在写算法的时候根本不用关心地图到底是怎么打印的在写界面的时候也不用操心算法内部怎么跑每部分都能单独测试。模块化还有一个实际的好处最终交付的时候你可以在README里画一张模块调用关系图答辩老师一看就知道你具备工程意识。很多同学代码能力不差但一开口就是“我这个程序就是一堆函数”而你说“我分了四个模块互相独立通过接口通信”这差距一下就拉开了。地图的数据结构我选的是二维整型数组没有用链表结构或者十字链表。原因很直接这个场景是密集网格访问二维数组支持O(1)随机访问而且内存是连续的cache命中率高。如果地图规模扩大二维数组的内存占用是O(ROWS × COLS)对课设规模完全够用。虽然链表结构在动态扩展上更灵活但它带来的指针操作复杂度完全没有必要。地图打印这块我没有用第三方图形库而是用了控制台输出。墙用实心方块字符比如█通路用空格玩家位置用P出口用E寻路访问过的格子用*标记最短路径用#标记。这样只在文本层面做处理整个程序零依赖拷到任何机器上装上gcc就能编译运行。4. 从“能跑”到“能看”控制台交互设计里那些必须较真的细节4.1 地图渲染别小看那棵ASCII艺术树迷宫渲染看起来是最简单的部分其实暗藏一个巨坑——控制台光标控制和刷新频率。如果直接while循环printf整个地图每次刷新都会在终端里留下大量滚动历史屏幕会闪得跟幻灯片一样。正确的做法是在Linux终端里清屏用ANSI转义序列\033[H将光标移到左上角刷新时只重绘地图区域而不是追加输出。void render_map() { printf(\033[H); // 光标归位 for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { if (i player_x j player_y) printf(P); else if (i exit_x j exit_y) printf(E); else if (maze[i][j] 1) printf(█); else if (path_flag[i][j] 1) printf(#); else if (visited_flag[i][j] 1) printf(*); else printf( ); } printf(\n); } fflush(stdout); }这一步做完整个程序的体感立刻从“学生作业”变成了“有点东西的小工具”。4.2 键盘交互把scanf丢掉换成getch手动模式里玩家需要用方向键控制小熊在地图里走这里如果你还用scanf(%c, cmd)回车键会卡死你的输入缓冲每次都得多按一下回车体验极其难受。这里必须用非缓冲输入也就是getch()风格的单字符即时读取。Windows下直接用_getch()在conio.h里Linux下需要手动把终端设置为raw模式。Linux的代码就这么几行#include termios.h #include unistd.h void enable_raw_mode() { struct termios raw; tcgetattr(STDIN_FILENO, raw); raw.c_lflag ~(ICANON | ECHO); tcsetattr(STDIN_FILENO, TCSANOW, raw); } void disable_raw_mode() { struct termios raw; tcgetattr(STDIN_FILENO, raw); raw.c_lflag | (ICANON | ECHO); tcsetattr(STDIN_FILENO, TCSANOW, raw); }注意方向键的读取按下方向键时终端会一次性发送三个字节的转义序列ESC [ A/B/C/D分别是上、下、右、左。所以不能只读一个char得判断第一个字节是\033ESC之后再读后面两个字节int get_key() { int c getchar(); if (c 0x1b) { getchar(); // 吃掉[ switch (getchar()) { case A: return KEY_UP; case B: return KEY_DOWN; case C: return KEY_RIGHT; case D: return KEY_LEFT; } } return c; }这个坑如果不踩一次你永远不知道为什么方向键在程序里完全没反应查了半天以为是自己逻辑错误其实只是字节流没读干净。我在第一次实现的时候就是只用了一个getchar()去读方向键结果上下左右全变成ESC开头加乱码当时排查了近一个小时才反应过来——这种细节说出来轻巧不自己撞一次真的不会往那上面想。4.3 自动演示模式给寻路套一个延时自动演示模式的逻辑很简单调用BFS把访问过的格子每隔80毫秒逐步标记出来观众能看到搜索像水波一样一圈一圈往外扩最后一条高亮路径从入口连到出口。延时实现方式就一行usleep(80000)Linux或者Sleep(80)Windows。但这里有个挑战是如果完全阻塞式延时用户在演示过程中无法按任何键退出万一迷宫大了路径很长演示可能得等半天。我的处理是每渲染一帧检查一次键盘是否有输入用select或者_kbhit检测检测到q键就提前退出演示返回主菜单。这种小细节就像一个“退出按钮”好的交互设计就是要让用户随时有掌控感。5. 复盘与避坑我迭代这个项目时踩过的四个问题5.1 随机数种子不设每次生成一模一样的迷宫这个问题我在写测试用例的时候最先撞到连续跑三次程序生成的迷宫一模一样。原因是我根本没调用srand(time(NULL))而rand()默认种子是1随机序列自然是固定的。加上这一行问题立刻消失。但更隐蔽的问题是如果用srand(time(NULL))同一秒内多次启动程序种子相同、迷宫也相同。所以在我的程序里特意把生成迷宫和开始游戏分成两个步骤每次进入游戏前重新generate一次并且让用户可选“输入随机种子”或者“用当前时间秒数做种子”。输入固定种子的好处是你发现某个迷宫走不通虽然理论不会或者你特别想复盘某个迷宫的走法可以输入同样的种子再次生成保证可复现性。别小看这个“可复现”特性它在调试的时候救了我无数回。5.2 迷宫生成进入死循环陷入了“看似访问过但实际是无路可走”的状态第一次测试生成效果时程序跑起来后卡住了屏幕上只有左上角一小片区域是通路其他全是墙进程也不结束。我打断点进去看发现递归正在一个死角里反复尝试四个方向但四个方向的格子要么越界、要么已经被访问过。理论上这种情况应该触发递归返回可我检查条件的时候发现——我的越界检测用的是if (maze[nx][ny] 0)就跳过但是初始化数组的时候maze里除了最外面一圈墙是1内部未初始化的元素默认是0这意味着程序以为那些格子已经被访问通路是0过永远不会走进去于是所有能走的方向全是“已访问”状态递归不断回退到头而真正的空白区域又永远不会被探索。修复其实就一行确定好墙和通路的定义后maze初始化为1全是墙起点先挖成0再递归。但排查的过程让我记住了一个教训C语言里任何数组统计都要先判断初始值静态变量不初始化是0局部数组不初始化是乱七八糟的栈上残留值哪种都不是你想当然的那一种。5.3 地图渲染“吃掉”了方块字符编码导致的对齐问题Linux终端默认UTF-8编码█和#显示正常但如果把代码拷到Windows控制台或者老版本xterm█这个UTF-8字符可能显示成乱码地图错位到没法看。为了兼容性我在代码里加了一个常量表用字符索引来替换特殊字符并实现了一个detect_encoding()函数根据平台切换字符集。Windows下的SetConsoleOutputCP(CP_UTF8)这行命令就是处理这个问题的#ifdef _WIN32 SetConsoleOutputCP(CP_UTF8); #endif我最初在macOS和Linux双环境下测试都能正常显示交作业前拿到Windows上一跑满屏乱码差点心态爆炸。之后所有控制台渲染类的项目我都会先确认平台和终端编码再决定用哪个版本的字符集绝不默认“我这边看着没问题”。5.4 BFS队列溢出环形队列的容量陷阱如果BFS直接用定长数组做队列最坏情况下队列元素数量是地图格子总数。我的队列大小是ROWS * COLS看似够用但如果把入队条件写松了比如没有判重就入队队列会迅速被重复节点撑爆。我调试时把队列长度上限打印出来发现搜索到中后期队列元素数量超过了数组容量直接内存越界程序崩溃。两种解决方案一是效率高但代码略复杂的“环形队列”——队列头尾指针走一圈取模二是简单粗暴的“每次入队前先查重”。我两个方法都试了最后保留的是环形队列查重双保险环形队列把容量问题从根上解决了查重减少了无效入队顺带把BFS的扩展次数从O(V²)降到接近O(V)。你如果也想用BFS我的建议是最初先用普通数组把功能跑通、再用环形队列优化容量不要一步到位否则出了问题你也不知道是容量崩了还是算法写错了。6. 交作业之后还能怎么玩三个会让老师加分的扩展方向课程设计做到这基础版已经可以交了但如果时间还有富余我强烈推荐你选一个方向加进去带来的答辩效果完全不同。第一个方向是加入存档与回放系统。玩家手动走的每一步都记录在链表中退出时把行走序列序列化写入文件下次启动程序加载存档可以在自动演示模式下按时间轴重放整个过程。这个功能看起来复杂其实核心就是文件读写链表遍历属于数据结构课程的完美延伸。第二个方向是地图难度分级与算法对抗。入口输入1/2/3对应不同尺寸的迷宫比如15、25、35或者新增一个“随机Prim生成器”和DFS生成器放在一起。答辩时现场生成两幅迷宫进行对比然后解释两种算法生成的迷宫在“分支数”“最长路径”“死胡同数量”上的统计学差异——这个数据分析和对比实验直接让你的课设从“我会写代码”上升到“我会做研究”层级。第三个方向我特别想推荐把寻路算法换成A*。在迷宫这种网格地图上A加入曼哈顿距离|x1-x2| |y1-y2|作为启发式函数会让搜索面积明显小于BFS。你可以在程序里加一个计数器分别显示BFS访问了多少个格子、A访问了多少个格子这个数字对比放在终极演示里极其直观。我实测在41×41的地图上BFS大约要访问400多个格子A只用访问两百左右就能到达终点。当然A不是课程大纲要求的算法但如果你在答辩时说一句“BFS能保证最短路径但搜索空间大我额外实现了A*进行优化用曼哈顿距离剪枝搜索空间”老师很难不给高分。最后说一点我的真实体会NOJ大作业这个项目我前后写了大概两周真正写代码的时间不到三天剩下时间全花在调随机数、处理编码问题、优化交互体验这些“非核心”但“极度致命”的事情上。如果让我重新做一次我会更早把模块划分好更早把跨平台问题纳入考虑更早去写测试用例而不是每次手动输入几个方向键就宣布“测完了”。程序的价值不仅在于它能跑更在于你知道它为什么能跑、在什么情况下会崩、如何改进才能更稳。这些东西刷一百道OJ判断题都教不会你而一次认真的大作业可以。“快乐的小熊”这个代号提醒我的是写完它的时候我是真的快乐。本文还有配套的精品资源点击获取