简介一份基于 Qt 框架的随机迷宫生成与最短路径查找实战项目面向需要结合图形界面理解数据结构与算法的开发者重点演示了并查集、深度优先搜索与 A* 算法的综合运用。压缩包共 66 个文件以 cpp/h 源码、VS 工程文件、dll 运行库及编译生成的 exe 为主同时包含界面资源与图标整体约 28MB下载后可直接运行查看效果。该资源已有 353 人学习浏览适合作为 Qt 入门实践或课程设计的参考。项目不仅提供完整代码还覆盖迷宫随机生成、路径可视化绘制、交互式起点重算等关键模块便于读者对照学习算法落地和 GUI 事件处理能有效提升从零搭建小型图形应用的能力。1. 项目定位一个迷宫程序为什么值得写用 Qt 写随机迷宫及路径获取这个需求我在项目里见过不止一次有人是为了做算法课设有人是想把迷宫放到产品里当个小游戏也有人只是单纯想在界面上画出点“能跑起来的东西”练手。不管动机是什么这个题目本身的覆盖面相当全面随机算法、二维数据结构、QGraphicsView 绘制、路径搜索、定时器动画、甚至发布打包时的坑全都串在一起了。所以这篇文章是按“一个完整可运行的 Qt 桌面程序”来拆解的最终效果是窗口里生成一张随机迷宫点击“开始寻路”之后迷宫中能看到探索过程动画最后高亮显示从起点到终点的最短路径。程序支持调节迷宫行列数也可以一键重新生成。整体技术路线是 C Qt Widgets 模块绘制部分用 QGraphicsView / QGraphicsScene不引入额外的图形库保证大家照着代码就能跑。这个程序适合三类人刚学完 C 想上手 Qt 的初学者想找一个完整项目练数据结构与算法的在校学生以及在工作中需要快速实现可视化网格类工具的开发人员。读完之后你不仅能拿到迷宫生成和路径查找的完整代码还能避开我在开发过程中踩过的几个坑比如动画卡界面、窗口缩放后迷宫显示不完整、发布 exe 后提示找不到 platform plugin 这类问题。2. 算法选型随机迷宫生成的几种思路2.1 递归回溯主流的迷宫生成算法随机迷宫生成算法里最容易理解和实现的就是递归回溯Recursive Backtracking也常被叫作深度优先迷宫生成法。它的核心思想非常直白从一个格子出发随机选一个方向往前走走到没有未访问邻居的格子就往回退回退到最近一个有未访问邻居的格子再继续走。听上去像是绕圈但实际生成出来的迷宫非常“像迷宫”通道细长、岔路多、死胡同多。原因是深度优先策略决定了它会在当前路径上一直走到尽头才会回头所以容易出现一条很长的走廊然后突然分叉的情况天然满足大家对“迷宫”的直觉印象。实现上需要用到一个二维数组记录每个格子是否访问过再额外记录每面墙是否存在。递归退化的风险在迷宫特别大的时候会出现比如行列都在 200 以上递归深度可能直接导致栈溢出这时候可以把递归改成显式栈迭代逻辑不变只是把系统栈换成了堆里的 std::stack。2.2 随机 Prim分支更均衡的变体如果你想生成分支更分散、路线更曲折的迷宫可以用随机 Prim 算法。它和递归回溯的最大区别在于候选方向的选择是全局随机的而不是顺着当前路径往下钻。Prim 算法的流程是先把起点标记为“已加入迷宫”把它四周的墙加入候选列表从候选列表随机取一面墙如果墙的另一侧格子还没有加入迷宫就把这面墙拆掉把那个格子加入迷宫再把该格子四周未处理的墙加入候选列表重复这个过程直到候选列表为空。这样生成的迷宫没有明显的主干道整体分叉非常均匀看起来更“野生”。代价是代码量比递归回溯多一点点需要额外维护一个边缘墙容器并且在迷宫比较大的时候随机取元素的效率要注意一下一般可以用 QList 加随机下标随机删除或者用 std::vector 配合随机交换再 pop_back。2.3 算法对比与选型建议算法迷宫特征实现难度大迷宫表现递归回溯长通道多、主路明显、死胡同长简单递归过深需改迭代栈随机 Prim分支均衡、弯曲多、路径短且碎中等稳定但候选容器开销略大实际项目里我推荐先用递归回溯因为代码少、容易调试。如果你只需要 50x50 以内的迷宫性能差异几乎感知不到选哪个全看想要什么视觉效果。我这个项目默认用递归回溯同时把算法封装在独立类里想换 Prim 直接替换生成函数就行。3. 核心代码实现从数据结构到界面绘制3.1 数据结构设计用二维数组表示迷宫迷宫本质是一个单元格网格每个格子有四面墙上、右、下、左。我在项目里用结构体保存墙面状态再用二维 QVector 组织整个网格。struct Cell { bool walls[4]; // 0: 上, 1: 右, 2: 下, 3: 左 bool visited; Cell() { walls[0] walls[1] walls[2] walls[3] true; visited false; } };建迷宫时只需要操作每个格子的 walls 数组。拆墙的时候要注意方向配对如果拆掉当前格子的右墙那么右边邻居的左墙也要拆掉否则画出来的图会有缺口。用方向数组统一处理会方便很多// 方向定义上(-1,0) 右(0,1) 下(1,0) 左(0,-1) const int dr[4] {-1, 0, 1, 0}; const int dc[4] {0, 1, 0, -1};拆墙时的邻居索引计算当前格子 row r, col c要拆除方向 dir 的墙则邻居在 (r dr[dir], c dc[dir])邻居那边需要拆除的墙方向是 (dir 2) % 4。这个公式我每次写都会在心里验证一遍防止方向搞反导致迷宫画出来歪歪扭扭的。3.2 迷宫生成的完整实现下面这段代码是递归回溯生成迷宫的完整核心逻辑我把它放在 MazeGenerator 类里class MazeGenerator { public: void generate(int rows, int cols) { grid.clear(); grid.resize(rows, QVectorCell(cols)); genRecursive(0, 0); // 从左上角开始 } private: QVectorQVectorCell grid; void genRecursive(int r, int c) { grid[r][c].visited true; QVectorint dirs {0, 1, 2, 3}; std::shuffle(dirs.begin(), dirs.end(), rng); // 随机打乱方向 for (int dir : dirs) { int nr r dr[dir]; int nc c dc[dir]; if (nr 0 || nr grid.size() || nc 0 || nc grid[0].size()) continue; if (grid[nr][nc].visited) continue; // 拆墙 grid[r][c].walls[dir] false; grid[nr][nc].walls[(dir 2) % 4] false; genRecursive(nr, nc); } } };这里有两个容易出错的地方。第一std::shuffle 需要传入一个随机数引擎建议用 std::default_random_engine 加随机种子否则每次生成结果都一样。第二visited 标记必须在进入下一次递归之前设置我见过有人把 visited 放在 for 循环外面而忘记给起始格打标导致第一格被重复访问。如果你要做大迷宫把递归函数改写成非递归版本也很简单用一个栈保存当前格子的坐标pop 出来之后处理方向push 进下一个格子逻辑完全一样。3.3 QGraphicsView 绘制迷宫绘制用 QGraphicsView 加 QGraphicsScene每个格子画四面墙墙存在就用 QGraphicsLineItem 画一条线段。这样比用 QWidget 的 paintEvent 手动画更省心因为 QGraphicsView 自带坐标变换后续做缩放很轻松。void Widget::rebuildScene() { scene-clear(); int block 20; // 每个格子的像素大小 for (int r 0; r rows; r) { for (int c 0; c cols; c) { int x c * block; int y r * block; const Cell cell generator.getGrid()[r][c]; QPen pen(Qt::black, 2); if (cell.walls[0]) scene-addLine(x, y, x block, y, pen); if (cell.walls[1]) scene-addLine(x block, y, x block, y block, pen); if (cell.walls[2]) scene-addLine(x block, y block, x, y block, pen); if (cell.walls[3]) scene-addLine(x, y block, x, y, pen); } } view-fitInView(scene-sceneRect(), Qt::KeepAspectRatio); }这里有个细节要提醒先生成迷宫再一次性把所有墙添加到 scene不要边生成边绘制否则窗口刷新次数太多大迷宫会肉眼可见地卡。fitInView 可以自适应缩放把整个迷宫塞进视口但如果你在窗口改变大小后不重新调用它迷宫就会只显示一部分或者缩得太小我就是在这里踩过一次坑。4. 路径获取BFS 求最短路径4.1 为什么选 BFS 而不是 DFS路径获取需求在大多数场景下是“求最短路径”因为用户看到一条绕远的路会觉得程序不够聪明。深度优先搜索虽然能找出一条路径但它不保证最短。BFS广度优先搜索按层扩展第一次到达终点时走的步数一定是最少所以直接选 BFS。在块大小为 10、迷宫行列在 100x100 以内时BFS 的性能完全够用遍历一遍所有格子也就一万个节点耗时在毫秒级别。更大的迷宫可以考虑 A*但需要设计启发函数代码复杂度更高性价比反而不高。4.2 BFS 寻路实现BFS 算法本质是用一个队列维护待访问格子从起点出发依次访问邻居直到队列空或者到达终点。为了最后能回溯完整路径需要记录每个格子的“父节点”我用一维整型数表示格子坐标父节点数组初始化为 -1。QVectorQPoint solveMaze(const QVectorQVectorCell grid, QPoint start, QPoint end) { int rows grid.size(); int cols grid[0].size(); QVectorint parent(rows * cols, -1); QQueueQPoint q; q.enqueue(start); parent[start.x() * cols start.y()] start.x() * cols start.y(); while (!q.isEmpty()) { QPoint cur q.dequeue(); if (cur end) break; for (int dir 0; dir 4; dir) { if (grid[cur.x()][cur.y()].walls[dir]) continue; // 有墙不能走 int nr cur.x() dr[dir]; int nc cur.y() dc[dir]; if (nr 0 || nr rows || nc 0 || nc cols) continue; int idx nr * cols nc; if (parent[idx] ! -1) continue; // 已访问过 parent[idx] cur.x() * cols cur.y(); q.enqueue(QPoint(nr, nc)); } } // 回溯路径 QVectorQPoint path; if (parent[end.x() * cols end.y()] -1) return path; // 无路径 int curIdx end.x() * cols end.y(); while (curIdx ! start.x() * cols start.y()) { int r curIdx / cols; int c curIdx % cols; path.append(QPoint(r, c)); curIdx parent[r * cols c]; } path.append(start); std::reverse(path.begin(), path.end()); return path; }这里判断“是否可以走”的关键是检查当前格子的墙是否存在而不是简单检查邻居数组。把墙拆了、数据同步对了BFS 才能正确穿过通道。如果路径为空界面上最好弹个提示而不是什么都不显示否则用户会以为程序出 bug 了。4.3 路径可视化与动画不卡界面的做法把路径直接画出来很简单在迷宫格子上用醒目的颜色填充矩形就行。但更有意思的是展示 BFS 的“探索过程”从起点开始一圈一圈往外扩散最后缩成一条红色最短路径。这个动画效果我在实机运行后觉得非常直观适合演示算法流程。实现动画最忌讳的就是在 BFS 主循环里加 QThread::sleep 或者循环绘制等待。那会让主界面进入假死状态窗口拖不动、按钮点不了。正确做法是先把 BFS 的每次“出队访问顺序”保存在一个容器里然后用 QTimer 定时刷新界面每次从容器里取一批格子添加到 scene 中上色。QTimer *timer new QTimer(this); connect(timer, QTimer::timeout, [this]() { // 每次从探索顺序中弹出若干格子标记为浅蓝色 for (int i 0; i 20 !visitedOrder.isEmpty(); i) { QPoint p visitedOrder.takeFirst(); addColoredRect(p, QColor(100, 180, 255)); } if (visitedOrder.isEmpty()) { timer-stop(); drawFinalPath(); } }); timer-start(30);这个套路和 Qt 里“大量耗时计算不能阻塞 GUI 线程”的原则是一致的。类似的思路也能用在网络请求上不要在按钮槽里直接发阻塞请求而是用 QNetworkAccessManager 的异步回调或 QThreadPool 跑任务。跑完再通过信号把结果拿回主线程原理跟这个定时器动态刷新完全一样。5. 实际调试记录与常见问题开发这个项目的过程中有几个问题反复出现我把它们整理成速查表后面再做这类 Qt 项目时可以少走弯路。问题表现原因解决办法界面启动后提示 “Qt platform plugin could not be initialized”可执行文件缺少 platforms 目录用windeployqt重新生成部署文件迷宫画出来缺口对不上拆墙时只拆了当前格的墙没拆邻居的墙按公式同时处理 (dir 2) % 4 方向的墙窗口放大缩小后迷宫显示不完整没有重新调用 fitInView重写 resizeEvent每次调整视口动画过程中界面点击无响应在循环里用了阻塞等待改用 QTimer 分批刷新不要 sleep设置不同行列数后按钮点击崩溃旧 scene 上残留 line item或者数组越界先 scene-clear()再重新建图检查起点终点是否越界发布 exe 到别的电脑后运行报错缺少 Qt 运行库打包时带上整个 exe 同级的 Qt 动态库和 plugins 目录补充一个我自己的习惯寻找并解决“platform plugin”报错的最佳实践是在 Qt Creator 里把构建后的 exe 所在目录整个拷贝到一个新文件夹然后打开 Qt 自带的命令行工具比如“Qt 5.15.2 (MSVC 2019 64-bit)”执行windeployqt 你的程序名.exe它会自动把依赖的库和插件复制过去。之后再检查移植性就基本没问题了。另外在 Windows 上MSVC 版的 Qt 和 MinGW 版的 Qt 在发布时容易混淆windeployqt 必须选择与编译套件对应的版本否则即使部署成功运行时也会出现找不到 Qt5Core.dll 之类的报错。我自己就曾经用 MinGW 的 windeployqt 去部署 MSVC 编译的 exe栽过跟头。6. 还能怎么扩展让这个迷宫项目“长”出花来6.1 升级 A* 与不同行走成本BFS 保证最短路径但如果你希望路径能区分“平路”和“窄路”或者允许斜着走那就得换 A*。两者核心差异是 A* 引入了启发函数比如曼哈顿距离或欧氏距离每次从优先队列里取出估计代价最小的格子扩展。改造成本不大把 QQueue 换成 std::priority_queue再给每个格子增加 g 值和 f 值即可。允许斜穿时还要额外检查两面墙是否同时打开避免从直角墙角直接切过去。6.2 迷宫导出与一键生成题目答案把当前迷宫导出成图片用 QImage 绘制所有墙线然后保存 PNG几行代码就能搞定。这个功能很实用比如你想打印一张纸质迷宫给孩子玩或者把迷宫嵌到报告里做示例图。再进一步可以做一个“生成题目”模式随机指定起点和终点界面只给用户展示迷宫用户点“查看答案”时才高亮路径这就是一个完整的迷宫练习工具。6.3 发布打包与跨平台思路项目最终要交付给别人的话Qt 打包是个绕不开的环节。Windows 上用 windeployqt 部署 Qt 依赖Mac 上可以用 macdeployqtLinux 上推荐用 linuxdeployqt 或 AppImage 方案。如果你的开发环境是 MSVC记得安装对应版本的 VC Redistributable否则目标机器可能会缺少运行库。还有一个适合团队协作的细节把界面、生成器、求解器分别拆成独立类生成器和求解器不依赖任何 Qt 图形类只接收二维数组。这样就算以后要移植到命令行工具或者网页后端核心算法也能直接复用不用动大手术。这也是这类小项目保持长期生命力的关键。我自己把每一步都拆开之后后续加功能轻松了很多也不再担心改 UI 会把算法改坏。本文还有配套的精品资源点击获取