在 GitHub 查看 绕一组圆形障碍物的路径寻找 2017年3月 在森林中导航 A* 路径寻找算法是一种快速生成最优路径的强大方法。通常，人们演示 A* 在基于网格的地图中的导航，但 A* 不仅仅是一个网格算法！它可以在任何图上运行。我们可以使用 A* 在这个圆形障碍物的世界中找到一条路径。这同样的算法是如何解决这两个问题的？让我们从 A* 的工作原理开始回顾。 A* 算法 A* 算法从起点找到到达终点的最优路径，避免沿途的障碍。它通过逐渐扩展一组部分路径来实现这一点。每个部分路径是从起点到目标途中某个中间点的一系列步骤。随着 A* 的进展，部分路径越来越接近目标点。当它找到一条可以证明比任何剩余可能性更好的完整路径时，算法终止。在算法的每一步中，A* 评估部分路径集，并通过扩展集合中最有前途的路径生成一些新路径。为此，A* 将部分路径保存在优先队列中，按估计长度排序——截至目前路径的实际测量长度，加上对到达目标的剩余距离的猜测。这个猜测必须是低估；也就是说，猜测可以小于实际距离，但不能大于。在大多数路径寻找问题中，一个好的低估是从部分路径的终点到目标的几何直线距离。从部分路径的终点到目标的实际最佳路径可能比这条直线距离更长，但不可能更短。当 A* 开始时，优先队列中只包含一个部分路径：起点。算法通过不断从优先队列中移除最有前途的路径，即估计长度最小的路径来工作。如果这条路径以目标点结束，算法就完成了——优先队列确保没有其他路径可能更好。否则，从它从队列中移除的部分路径的末尾开始，A* 通过在所有可能的方向上单步生成一些新路径。它将这些新路径放回优先队列，并再次开始该过程。 图 A* 在图上运行：一组由边连接的节点。在基于网格的世界中，每个节点表示一个单独的网格位置，而每条边表示与邻近位置的连接，分别位于北、南、东或西。在 A* 能够在圆形障碍的森林中运行之前，我们需要将其转换为图。森林中的所有路径由交替的线段和弧段组成。这些是路径图中的边。这些边的端点变成节点。通过图的路径是一系列通过边连接的节点：线段和弧都作为图中的边。我们称线段为冲浪边，因为路径使用它们在障碍物之间冲浪。我们将弧称为拥抱边，因为它们在路径中的作用是紧贴障碍物的边缘。接下来我们将探讨将障碍森林转换为图的一种简单方法：生成所有可能的冲浪边和拥抱边。这称为切线可见性图。 生成冲浪边 两个圆之间的冲浪边是刚好吻合两个圆的线段；这些线段被称为双切线，每一对圆有四条双切线。交叉在两个圆之间的双切线是内双切线，而沿外部的双切线是外双切线。 内双切线 历史上，内双切线对计算跨越两个不同大小滑轮的带的长度非常重要，因此构造内双切线的问题被称为带问题。要找到内双切线，计算下图中的角度  heta。相交的圆没有双切线 显然，给定以点 A 和 B 为中心、半径为 r_A 和 r_B 的圆，且其中心之间距离为 d： \[ heta = \arccos\frac{r_A+r_B}{d}\] 一旦知道了  heta，找到点 C、D、E 和 F 就很简单。 外双切线 构造外双切线——滑轮问题——使用类似的技巧。较小的圆完全包含在较大的圆中 对于外双切线，我们可以通过以下方式找到  heta： \[ heta = \arccos\frac{|r_A - r_B|}{d}\] 无论圆 A 或 B 哪个更大都没有关系，但如图所示， heta 出现在 A 朝向 B 的一侧，而在 B 离开 A 的一侧。 视线 结合起来，两个圆之间的内双切线和外双切线构成了圆之间的冲浪边。但如果一个第三个圆阻挡了一条或多条冲浪边呢？ 圆阻挡视线 A 和 B 互相可见 如果一条冲浪边被另一个障碍物阻挡，