路径规划：一个基于 Qt 的 A* 算法演示器

写在前面

这是我在《算法设计与优化》课设里做的一个小软件，题目方向是无人机路径搜索与优化。更准确一点说，它并不只是“实现一个 A* 算法”，而是想把常见路径规划算法做成一个可交互、可视化、方便演示的小工具。

这篇文章其实在 2023 年底就写过一版了，不过当时演示内容一直没补完整。前段时间刚好抽空把一些演示 GIF 和细节重新整理了一下，所以索性重发一次，也顺手把内容按现在的新博客框架重新收拾一下。

从完成度上看，这个项目当然算不上多成熟。它更像是一个带界面的算法实验场：可以自己画地图、设置起点终点和障碍物，切换不同算法，看它们怎么搜索、怎么扩展节点、最后怎么得到路径。对课设展示来说，这种“看得见过程”的形式，比单纯打印几行结果要直观得多。

项目环境与界面

项目基于 Qt 框架，使用 C++ 开发，开发环境如下：

主界面长这样：

界面本身没有什么特别高深的设计，主要目标还是围绕“演示”服务：地图区域尽量清晰，工具栏操作尽量直接，底部状态栏可以辅助调试，算法执行结果则尽量用颜色、路径和节点状态展示出来。说白了，它不是一个追求工业级美观的产品，而是一个偏实用的教学和展示工具。

这个项目能做什么

如果只看名字，“A* 算法演示器”听起来好像功能不多，但实际做着做着，还是往里面塞了不少东西。

先说地图交互这部分。项目支持自定义地图宽高，单元格大小也可以调整；起点、终点、障碍物都能手动设置；绘制好的地图支持保存成本地 .Amap 文件，方便下次直接载入，不用每次都现场手画。为了让演示过程更灵活，我还加了随机地图、导入背景图、清除背景图这些功能，虽然有些地方做得还比较粗糙，但至少把“可操作性”这一块补上了。

算法部分则不止 A* 一种。我把自己当时课设里涉及到的一些经典搜索算法都做进去了，包括：

其中我自己投入最多的，还是优化版 A* 这一块。为了让它更有“可调参数”的感觉，我加入了几种不同的启发式距离定义，包括切比雪夫距离、曼哈顿距离和欧几里得距离；同时还加入了动态权重、拐角代价和安全距离模式等参数，方便观察不同策略对最终路径结果的影响。

严格来说，这些优化还谈不上多么系统，更多还是面向课设场景下的一种工程化尝试：既想让它比“最原始版本”更灵活一点，又希望界面上能比较直观地把差异体现出来。

如何获取与使用

源码我放在 GitHub 上了，直接下载或者克隆都可以。

Astar

项目 GitHub 仓库，包含源码与工程文件。

如果你习惯直接拉仓库，也可以用下面这条命令：

git clone git@github.com:JJLibra/Astar.git

考虑到 GitHub 访问有时候比较慢，我当时也顺手留了一个网盘备份，不过网盘里通常只放最新版代码：

百度网盘下载

备用下载地址，提取码：16ca

下载源码之后，比较推荐直接用 Qt Creator 打开项目里的 Astar.pro 工程文件。这样最省事，也方便你顺手改代码做二次开发。

如果只是想在 Windows 下打包成可执行文件，我当时用的是 Enigma Virtual Box。这块不是本文重点，就不展开讲了，有需要的话可以自己搜相关教程。

一些实际演示

先是最基础的地图设置。这个项目支持自由设置地图大小，然后在网格里标记起点、终点和障碍物。整个交互其实不复杂，但对演示来说已经够用了：

下面这个是优化版 A* 的演示，同时还把贝塞尔曲线作为最终轨迹做了绘制。也就是说，程序给出的原始路径并不是最后的展示结果，我又额外做了一层平滑处理，让它看起来更像“无人机轨迹”而不是简单折线：

随机地图和一键重置也加进去了。这里的随机地图逻辑其实比较朴素，就是基于伪随机数去生成障碍，严格来说还不够聪明，不能保证每次都生成存在可行解的地图。这个地方如果以后要继续做，我觉得最值得优先重构的就是它：

为了适配课设答辩这种场景，我还做了地图保存功能。毕竟现场再一点点手画地图既费时间，也容易翻车，提前把测试地图存好显然更稳：

载入地图同样是支持的。下面这个演示里还顺便展示了深度优先搜索。这里有个小插曲：录视频的时候我忘了演示“深搜最短”这个按钮，实际它是能工作的，只是操作时要稍微按顺序来，不然有些状态切换容易把自己绕晕：

背景图导入这个功能，本来是我给“地图栅格化”留的一个过渡方案。原本我确实想继续往“真实地图栅格化”方向做，但当时课设时间已经有点紧了，最后就退一步，先支持导入本地图片作为背景，再手动在上面描地图。虽然只是个折中方案，但至少把这个思路跑通了：

除此之外，还有一些不太显眼、但我自己当时做得挺上头的小细节，比如关于页、性能分析可视化、状态栏提示、操作反馈，以及一些不太成熟但多少有点意思的界面动画：

做这个项目时的一些取舍

现在回头看，这个项目其实挺典型：想做的东西很多，真正能在课设周期里做完的东西却很有限。

比如我原本很想把“真实地图栅格化”“更稳定的随机地图生成”“增量式搜索算法的完整交互”这些部分做扎实，但最后都只能在时间、复杂度和展示效果之间做妥协。于是项目里就出现了很多这种状态：功能已经有雏形，能演示，也能跑，但还远没到我自己心里那个“做舒服了”的程度。

所以如果你下载代码以后，看到里面有些写法不太规范、某些逻辑有点糙、局部实现带着明显的课设味道，也不用太意外。这个项目本来就是一边学、一边试、一边补出来的。小细节不少，bug 其实也不少，改到后面代码确实有点朝着“能跑就先别动”那个方向滑过去了。

最后

由于这个项目本身是学校课设，所以里面有些图标素材会带一点校内元素。如果你只是想参考算法实现、界面思路或者工程组织方式，直接看源码就够了；如果你想要一个更早期、相对更原始的版本，我也可以单独提供。

总之，这个项目的定位一直都很明确：它不是一个成熟产品，而是一个把路径搜索算法“做给人看”的小工具。对我来说，它最大的意义不只是把 A* 写出来，而是把算法、界面、交互和演示这一整套流程都亲手串了一遍。

如果你正好对这个项目感兴趣，或者准备拿它做一点自己的二次开发，欢迎去仓库里看看。
当然，别忘了顺手点个免费的 Star，这个对学生项目来说还是很有鼓励意义的。