A* 不只会走方格：绕开一片圆形障碍，最短路可以这样算
作者：林岚
林岚
算法可视化作者 Red Blob Games 更新了 Circular Obstacle Pathfinding：它不把世界切成方格，而是把圆形障碍之间的公切线与沿圆周的弧线组成一张图，再交给 A* 找到最短路径。
一句话结论： A* 从来不是“格子算法”，它只需要一张图；真正困难的是根据问题几何结构，构造一张既不漏掉最优路线、又不会大到算不动的图。
在常见教程里，地图被切成方格，每个格子连接上下左右邻居，于是很多人把 A* 和网格绑定起来。其实 A* 只做一件事：从候选路径里优先扩展“已经走的距离 + 对剩余距离的保守估计”最小者。只要节点和边定义正确，边可以是直线、弧线，甚至是完全抽象的状态转换。
圆形障碍的最短路径有一个漂亮性质：离开起点后，路线要么沿直线擦过圆，要么贴着圆周走一段。两圆之间刚好相切的直线叫公切线，作者称为 surfing edge；沿圆周连接两个切点的弧线叫 hugging edge。把起点、终点和所有有效切点当节点，这些线段与弧当边，就得到切线可见图。
听起来只要把所有边都生成即可，但麻烦马上出现。两圆相交时某些公切线不存在；一条切线可能穿过第三个圆；沿某个圆的弧线又可能被别的圆遮挡。朴素生成会产生大量无效边和没有必要的拐点。文章逐步加入遮挡检测、方向标注和延迟生成，只在 A* 真正需要扩展某节点时计算部分边。
这套方法适合什么？当障碍近似圆、需要光滑且几何上接近最短的路径时，它比粗网格自然，例如二维游戏里的单位避障、机器人周围的安全半径、布线和动画镜头。若环境是复杂多边形、障碍动态变化或角色有转弯半径与速度约束，就需要可见图、导航网格、采样规划或时空搜索等其他工具。
林岚认为，这篇教程最好的地方是把“运行算法”和“建模问题”分开。很多性能争论最后都不是 A* 快不快，而是图建得太大、启发函数太弱，或者边根本没有表达真实约束。选对表示，往往比换一套搜索算法更重要。
关键事实
- 路径由圆之间的公切线段与沿圆周的弧线组成。
- 图节点是切点、起点和终点，A* 仍使用直线距离作为可采纳启发。
- 需要过滤穿过其他障碍的线段与被遮挡的圆弧。
- 延迟生成边可减少不必要的预计算。
OC 判断
A* 的通用性来自图，而不是网格。工程上最重要的问题是“哪些状态值得成为节点、哪些移动值得成为边”。
为什么重要
- 对开发者：可把同一搜索框架迁移到几何、调度和状态规划问题。
- 对企业：针对地图结构建图，可同时改善路径质量和计算成本。
- 对用户：更平滑的路径不是简单“提高分辨率”，而是换了世界表示方式。
评论
围绕这篇文章补充信息、提出问题或分享观察。