2017年圆形障碍物路径规划新算法

背景

2017 年，一篇题为《Circular Obstacle Pathfinding》的文章在 Hacker News 上引发讨论。作者旨在展示 A* 寻路算法不仅适用于传统的网格地图，还能在任意图（graph）上运行，并以此解决一个更具挑战性的问题：在由圆形障碍物构成的“森林”中规划出一条最优路径。传统上，人们常将 A* 与网格绑定（如游戏中的方格地图），但文章通过将圆形世界转化为图（tangent visibility graph），证明了 A* 的通用性。这一思路对机器人导航、游戏 AI 及任何涉及非网格环境的路径规划均有启发意义。

核心内容

A* 算法基础

A* 是一种最优路径查找算法，通过逐步扩展部分路径来工作。算法维护一个优先队列，队列中的部分路径按估计总长度排序（实际已走长度 + 到终点的启发式估计距离）。启发式必须为低估（underestimate），通常使用直线距离（几何最短距离）。每次迭代，算法取出估计长度最小的部分路径；若其终点就是目标点，则算法终止并返回该路径；否则，从该路径终点出发，向所有可能方向“迈出一步”，生成新的部分路径并放入队列。该过程保证最终找到的路径是最优的。

从网格到圆形障碍物世界

A* 运行在由节点（node）和边（edge）构成的图上。在网格中，节点是每个格子，边是相邻格子的连接。但在圆形障碍物森林中，路径由两种基本单元组成：直线段和圆弧段。这些单元就是图上的边，它们的端点则成为节点。文章将直线段称为 surfing edges（滑行边），因为路径利用它们“滑行”越过障碍物之间的空隙；圆弧段称为 hugging edges（贴边弧），因为它们的作用是紧贴障碍物边缘绕行。通过生成所有可能的 surfing edges 和 hugging edges，就能将圆形世界转化为一个图，这个图被称为 tangent visibility graph（切线可见图）。

生成 surfing edges（滑行边）

对于任意一对圆形障碍物（即两个圆），它们之间可能的滑行边是那些恰好与两个圆相切的直线段。这些线段被称为 bitangents（公切线）。每一对圆存在四条公切线：两条 internal bitangents（内公切线），它们穿过两个圆之间；两条 external bitangents（外公切线），它们沿两圆的外侧经过。

• 内公切线计算：根据圆心的距离 (d) 和半径 (r_A, r_B)，先计算角 (\theta = \arccos\frac{r_A + r_B}{d})，然后以圆心连线为基准，旋转出切点位置。
• 外公切线计算：使用公式 (\theta = \arccos\frac{|r_A - r_B|}{d})，方向按照图示确定：对于较大的圆，切点朝向另一圆；对于较小的圆，切点则远离另一圆。

处理阻塞与视线检查

并不是所有公切线都能作为有效的滑行边，因为可能被其他圆形障碍物阻挡。为了检测一个 surfing edge 是否被阻挡，需要对每个障碍物（圆心 C，半径 r）计算该线段 AB 到圆心 C 的最小距离 d。如果 d < r，则线段被该圆阻挡，应将其剔除；否则保留。距离计算方法如下：

1. 计算参数 (u = \frac{(C - A) \cdot (B - A)}{(B - A) \cdot (B - A)})。
2. 在线段 AB 上找到垂足点 (E = A + \mathrm{clamp}(u, 0, 1) \times (B - A))。
3. 距离 (d = |E - C|)。

生成 hugging edges（贴边弧）

对于每个圆形障碍物，首先找到所有与该圆相切的 surfing edges 的端点（即切点）。然后，在这些切点之间沿着圆周创建 hugging edges。这样，图上的节点就是 surfing edges 的端点，而 hugging edges 连接了同一圆上不同的切点。

完整图与 A* 寻路

将所有未被阻挡的 surfing edges 和所有 hugging edges 收集起来，加上起点和终点（可视为虚拟圆半径为 0 的点），就构成了完整的图。使用标准 A* 算法在此图上运行，即可找到从起点到终点的最优路径（由交替的直线段和圆弧段组成）。

重叠与接触情况的处理

文章指出，当圆形障碍物允许互相接触或重叠时，寻路问题会变得略微复杂：

• 对于接触或重叠的两个圆，内公切线不存在，因为公式中的 (\frac{r_A + r_B}{d} > 1)，arccos 无定义。必须先检查是否重叠再计算。
• 如果一个圆完全包含另一个圆，则外公切线不存在，因为 (\frac{|r_A - r_B|}{d}) 超出 [-1,1] 范围。
• 在视线检查中，若垂足参数 u 超出 [0,1]（即垂足不在线段上），则可能意味着障碍物位于线段延长线上，需要特殊处理（原文在此处因截断未完整结束，但已明确指出需要根据新情况调整算法）。

文章最后提到，上述图生成方法是教学性的，实际应用中可以通过多种优化来降低 CPU 和内存消耗，并支持更多边界情况。

关键要点

• A* 算法不局限于网格，只要能将问题空间转化为图（节点 + 边），就能适用。
• 在圆形障碍物环境中，最优路径由直线段（surfing edges）和圆弧段（hugging edges）交替组成，分别对应切线滑行和贴边绕行。
• 图的构建基于切线可见图（tangent visibility graph），核心是生成所有可能的公切线（internal/external bitangents），并剔除被其他障碍物阻挡的边。
• 内公切线计算公式 (\theta = \arccos((r_A + r_B)/d))；外公切线公式 (\theta = \arccos(|r_A - r_B|/d))。
• 视线阻塞检测使用点到线段的距离公式：计算垂足参数 u，截断至 [0,1]，再计算距离 d，若 d < 障碍物半径则阻挡。
• 当圆形障碍物重叠或包含时，对应的公切线可能不存在，需在计算前检查合法性。
• 该方法是教学级别的，实际实现可通过空间索引、剪枝等技术大幅提升性能。

意义与影响

这篇文章以简洁而直观的方式，将经典的 A* 算法从网格推广到连续几何环境，为开发者提供了一个清晰的实现思路。其核心思想——将几何世界转化为图——是许多现代路径规划系统的基础（如机器人运动规划中的 PRM、RRT* 等概率路线图方法，尽管后者使用了随机采样而非全连接）。文中对公切线、视线检测和障碍物处理的讲解，为后续研究（如圆形障碍物的最优路径、多障碍物场景的优化）铺平了道路。

此外，该文强调了“算法通用性”这一重要概念：A* 不只是网格算法，只要能抽象出图，它就能工作。这一观点有助于打破初学者的认知局限，鼓励他们在游戏 AI、无人机航线规划、CAD 布局等更广泛的领域中应用 A*。尽管文中使用了全连接图（生成所有可能边），对于大量障碍物场景计算量较大，但该方法为后续优化（如稀疏图、分层图）提供了理论基础。整体而言，这篇 2017 年的文章是路径规划教学中的一篇优秀参考，至今仍值得开发者研读。