在圆形障碍中寻找出路

森林导航

*路径查找器算法是用于快速生成最佳路径的强大工具。 从网格导航地图时，通常会显示A *，但它不仅可用于网格！ 它可以与任何图形一起使用。 您可以使用A *在圆形障碍物世界中找到自己的路。


在原始文章中，所有图像都是交互式的。

一种算法如何解决这两个问题？ 让我们首先简要介绍A *的工作原理。

算法A *

算法A *找到从起点到终点的最佳路径 ，避免了沿途的障碍。 他意识到了这一点，逐渐扩展了许多局部路径 。 每个局部路径都是从起点到道路上某个中间点的一系列步骤。 在处理A *的过程中，部分路径越来越接近终点。 该算法在找到完整路径时会停止工作，这比其余选项要好，并且可以证明这一点。

在算法的每个步骤中，A *都会评估部分路径的集合并生成新路径，从而将最有希望的路径扩展到集合之外。 为此，A *将部分路径存储在优先级队列中，并按近似长度 （实际测得的路径长度加上到目标的近似剩余距离）排序。 这种近似应该被低估 ; 也就是说，近似值可以小于真实距离，但不大于真实距离。 在大多数路径查找任务中，一个低估的好方法是从局部路径的终点到终点的直线上的几何距离。 从部分路径的末端到目标的真实最佳路径可以长于此直线距离，但不能短。

当A *开始时，优先级队列仅包含一个部分路径：起点。 该算法反复从优先级队列中删除最有希望的路径，即具有最小近似长度的路径。 如果此路径在端点处结束，则该算法已完成任务-优先级队列可确保没有其他路径会更好。 否则，从他从队列中删除的部分路径的末尾开始，A *会生成更多的新路径，并在所有可能的方向上采取单位步长。 他将这些新路径放回优先级队列，然后再次开始该过程。

数

*与图形配合使用：一组由边连接的节点 。 在基于网格的世界中，每个节点表示一个单独的网格单元，并且每个边都是与北部，南部，东部或西部的相邻单元的连接。

在能够从圆形障碍物为森林运行A *之前，我们需要将其转换为图形。 穿过森林的所有路径均由交替的线段和弧段组成。 它们是路径图的边缘。 这些边的端点成为节点。

通过图的路径是由边连接的一系列节点：


段和圆弧都是图形的边缘。 我们将这些段称为过渡边缘 ，因为路径会使用这些段在障碍物之间移动。 我们称圆弧为包络边 ，因为沿途的任务是绕过障碍物的侧面。

接下来，我们将探索一种简单的方法来将具有障碍物的森林转换为图形：我们将生成所有可能的过渡边缘和边缘包络。

过渡边缘生成

一对圆之间的过渡边缘是几乎不接触两个圆的线段。 这样的线段称为到两个点的切线 ，每对圆有四个这样的线切线。 与圆之间相交的两个点的切线称为内部切线，两个点之间的切线称为外部切线 。

内切线为两点

过去，寻找内切线对于计算连接两个不同尺寸的皮带轮的皮带的长度很重要，因此将内切线创建到两个点的任务称为皮带问题 。 要找到两个点的内切线，您需要计算角度 $$$\ theta$ 在下图中。


事实证明，对于有中心的圆 $$和 $$$B$ 和半径 $$$r_A$ 和 $$$r_B$ 中心距离一定 $$$d$ ：

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

定义 $$$\ theta$ 我们可以轻松找到要点 $$$C$ ， $$$D$ ， $$$E$ 和 $$$F$ 。

外切线至两点

在构造外切线时（这是皮带轮的任务 ），使用了类似的技术。


对于外部切线，我们可以找到 $$$\ theta$ 如下：

$$

$$\ theta = \ arccos {{\ lvert r_A-r_B \ rvert} \ over d}$$

哪个圆圈更大（A或B）都没有关系，但是从图片中您可以看到， $$$\ theta$ 放在最靠近B的A侧，但最远离A的B侧。

视线

总而言之，两个圆之间的两个点的内部和外部切线形成了圆之间过渡的边缘。 但是，如果一个或多个过渡边闭合第三个圆，该怎么办？


如果过渡边缘与另一个圆重叠，那么我们需要丢弃该边缘。 为了识别这种情况，我们对点和线之间的距离进行了简单的计算。 如果从过渡边缘到障碍物中心的距离小于障碍物的半径，则障碍物与过渡边缘重叠，因此我们必须将其丢弃。

计算到一个点的距离 $$$C$ 到直线段 $$$\上线{AB}$ 我们将使用以下方法 ：

首先，我们计算 $$$u$ -沿线段的距离的一部分 $$$\上线{AB}$ 垂直线与点相交的位置 $$$C$ ：

$$

$$u = {（C-A）\ cdot（B-A）\ over（B-A）\ cdot（B-A）}$$

然后我们计算位置 $$$E$ 在 $$$\上线{AB}$ ：

$$

$$E = A + \ mathrm {clamp}（u，0，1）*（B-A）$$

距离 $$$d$ 来自 $$$C$ 削减 $$$\上线{AB}$ 是距离 $$$C$ 之前 $$$E$ ：

$$

$$d = \ | E-C \ |$$

由于 $$$d <r$ ，圆圈与的视线重叠 $$在 $$$B$ ，并且边缘必须丢弃。 如果 $$$d \ ge$ 然后视线 $$在 $$$B$ 存在，应保留肋骨。

边缘包络生成

图的节点将过渡边和包络边连接起来。 在前面的部分中，我们生成了过渡边缘。 为了生成边缘的包络，我们从过渡边缘的终点开始，绕圆旋转，并在另一个过渡边缘的终点结束。


为了找到圆的边的包络集，我们首先找到与圆相切的过渡的所有边。 然后在圆上过渡边的所有端点之间创建边的包络。

全部放在一起

生成过渡边，边和节点的包络，然后丢弃所有重叠的过渡边后，我们可以创建图并开始使用A *算法搜索路径。

增强功能

我们检查的图形生成过程足以很好地说明算法，但可以在许多方面进行改进。 这样的改进将使算法可以花费更少的CPU和内存资源，并处理更多的情况。 让我们看一些情况。

彼此关注的障碍

您可能已经注意到，在上面显示的示例中，圆形障碍物没有重叠甚至没有接触。 假设圆可以互相接触，这会使寻找路径的任务复杂化

两点切线

回想一下，可以使用此公式对内部切线找到两点的切线：

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

和外切线公式：

$$

$$\ theta = \ arccos {{\ lvert r_A-r_B \ rvert} \ over d}$$

当两个圆彼此接触或相交时，它们之间就没有内部切线。 在那种情况下 $$${r_A + r_B} \超过d$ 不止一个。 由于反余弦的值超出定义范围 $$$[-1，1]$ 未定义，重要的是在找到反余弦之前检查圆的交点。

同样，如果一个圆完全位于另一个圆中，则它们之间将没有外部切线。 在那种情况下 $$${r_A-r_B} \超过d$ 超出范围 $$$[-1，1]$ ，即没有反余弦。

过渡边缘可见线

如果我们允许接触或越过障碍物的可能性，那么在计算过渡边缘视线时就会出现新的情况。

回顾计算 $$$u$ -垂直于该点的边缘沿过渡边缘的距离的一部分。 如果不允许触摸圆圈，则该值 $$$u$ 超出范围 $$$[0,1]$ ，即圆不能接触边缘，因为为此，它必须接触边缘的端点之一。 这是不可能的，因为边缘的端点已经与其他圆相切。

但是，如果我们允许重叠的圆圈，则这些值 $$$u$ 超出范围 $$$[0,1]$ 可以沿着边缘重叠视线。 这对应于圆位于过渡边的端点之外，但重叠或接触端点的情况。 为了以数学方式跟踪此类情况，我们将限制 $$$u$ 间隔 $$$[0,1]$ ：

$$

$$E = A +钳位（u，0，1）*（B-A）$$

信封视线

当障碍物可以相互接触或相交时，边缘的包络可以与过渡边缘相同的方式被障碍物阻挡。 从下图考虑信封边缘。 如果肋骨的包皮碰到另一个障碍物，则肋骨被阻塞，必须丢弃。


为了确定边缘的包络是否被另一个障碍物遮挡，我们使用以下方法确定两个圆相交的点。 如果圆以点为中心 $$和 $$$B$ 和半径 $$$r_A$ 和 $$$r_B$ 在哪里 $$$d$ -之间的距离 $$和 $$$B$ ，对于初学者来说，我们需要检查几种情况。 如果圆圈彼此不接触（即 $$$d> r_A + r_B$ ），
在另一个里面 $$$d <| r_A-r_B |$ ）或匹配（ $$$d = 0$ 和 $$$r_A = r_B$ ），则圈子不会影响彼此的信封。

如果不满足这些条件之一，则圆在两个点相交。 如果圆彼此接触，则这两个点重合。 考虑连接相交点的根轴 ； 它垂直于连接线 $$和 $$$B$ 在某个时候 $$$C$ 。 我们可以计算距离 $$$一$ 来自 $$之前 $$$C$ 如下：

$$

$$a = {r_A ^ 2-r_B ^ 2 + d ^ 2 \ over 2d}$$

寻找 $$$一$ 我们可以找到角度 $$$\ theta$ ：

$$

$$\ theta = \ arccos {a \ over r_A}$$

如果 $$$\ theta$ 为零，则圆圈触及 $$$C$ 。 否则，有两个交点分别对应正负 $$$\ theta$ 。


接下来，我们确定是否有任何交点在边缘包络的起点和终点之间。 如果是这样，则障碍会阻塞包络线边缘，我们必须丢弃该边缘。 请注意，我们不需要考虑包络线边缘完全位于障碍物内部的情况，因为过渡边缘的视线截止点已经脱离了该边缘。

在更改了到两个点的切线的计算以及过渡边和边的包络的视线之后，一切正常。

可变的演员半径和Minkowski扩展

在圆形障碍物世界中计算圆形物体的导航时，可以考虑简化问题解决方案的观察结果。 首先，可以通过注意到半径为r的圆通过森林的运动与点通过相同森林的运动类似，只是有一个变化就可以简化工作：每个障碍物的半径都增加r 。 这是应用Minkowski和的极其简单的情况。 如果角色的半径大于零，那么在开始之前，我们只需增加障碍物的大小即可。

延边生成

一般而言， $$$n$ 障碍物包含 $$$O（n ^ 2）$ 过渡边缘，但是由于每个边缘都需要通过 $$$n$ 障碍物，则总图生成时间为 $$$O（n ^ 3）$ 。 此外，成对的过渡边缘会导致产生包络边缘，并且必须用视线中的每个障碍物检查它们中的每一个。 但是，由于A *算法的高效率，它通常仅查看此大图的一部分以创建最佳路径。

我们可以通过在执行A *算法的过程中动态生成图表的一小部分来节省时间，而不必事先完成所有工作。 如果A *快速找到路径，那么我们将仅生成图的一小部分。 为此，我们将边缘生成移至neighbors()函数。

有几种情况。 在算法开始时，我们需要起点的邻居。 这些是从起点到每个障碍物左右边缘的过渡边缘。

下一种情况是当A *达到临界点时 $$$p$ 在障碍的边缘 $$$C$ 沿过渡边缘： neighbors()应返回从引出的边缘的包络 $$$p$ 。 为此，我们通过计算到两个点之间的切线的切线，确定哪些过渡边超出了障碍物。 $$$C$ 和所有其他障碍，丢弃所有不在视线范围内的障碍。 然后我们找到连接边的所有包络 $$$p$ 通过这些过渡边缘，将那些被其他障碍物阻挡的边缘掉落。 我们返回边缘的所有这些包络，保存过渡边缘以在随后的对neighbors()调用中返回。

最后一种情况是A *沿着障碍物绕过信封边缘 $$$C$ 他需要离开 $$$C$ 沿着过渡的边缘。 由于上一步已计算并保存了所有过渡边缘，因此您只需查找并返回正确的一组边缘即可。

我们切掉肋骨的尖头信封

信封边缘连接接触一个圆的过渡边缘，但事实证明，其中许多信封边缘都不适合以最佳方式使用。 我们可以通过消除它们来加快算法的速度。

穿过障碍林的最佳路径始终由交替的过渡边缘和边缘包络组成。 假设我们输入一个节点 $$并决定如何摆脱困境：


通过登录 $$表示我们正在顺时针移动（ $$$\ circlearrowright$ ） 我们必须通过节点退出，这样我们才能继续顺时针移动（ $$$\ circlearrowright$ ），也就是说，我们只能通过节点退出 $$$B$ 或 $$$D$ 。 如果您通过退出 $$$C$ 然后是拐点 （ $$$\ curlwedge$ ）永远不会是最佳的方式。 我们需要过滤掉这些尖锐的边缘。

首先，请注意，A *始终会处理每个非定向边。 $$$P \ longleftrightarrow Q$ 像两个定向的边缘 $$$P \ longrightarrow Q$ 和 $$$Q \ longrightarrow P$ 。 我们可以通过标记边缘和节点的方向来利用这一点。

1. 结 $$$P$ 成为具有方向的节点-顺时针（ $$$P \ circlearrowright$ ）或逆时针（ $$$P \ circlearrowleft$ ）箭头。
2. 未定向的过渡边 $$$P \ longleftrightarrow Q$ 成为定向的边缘 $$$P，p \ longrightarrow Q，\帽子{q}$ 和 $$$Q，q \ longrightarrow P，\ hat {p}$ 在哪里 $$$p$ 和 $$$q$ 是方向，并且 $$$\帽子{x}$ 表示相反的方向 $$$x$ 。
3. 无方向的肋骨信封 $$$P \ longleftrightarrow Q$ 成为定向的边缘 $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ 和 $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ 。 这是发生过滤的地方：我们不启用 $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ 和 $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ ，因为方向改变会导致扭结（ $$$\ curlwedge$ ）

在我们的电路中，节点 $$将变成两个节点， $$$A \ circlearrowright$ 和 $$$A \ circlearrowleft$ 它具有传入的过渡边缘 $$$\ longrightarrow A \ circlearrowright$ 和输出过渡边缘 $$$A \ circlearrowleft \ longrightarrow$ 。 如果我们通过 $$$A \ circlearrowright$ 然后应该通过节点退出 $$$\ circlearrowright$ 这将是过渡边缘 $$$B \ circlearrowright \ longrightarrow$ （通过信封边缘 $$$A \ circlearrowright \ longarrowarrow B \ circlearrowright$ ）或过渡边 $$$D \ circlearrowright \ longrightarrow$ （通过信封边缘 $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ） 我们无法摆脱困境 $$$C \ circlearrowleft \ longrightarrow$ ，因为旋转方向将以这种方式改变，因此我们过滤了边缘的包络 $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ 。

通过从图中滤除边缘的这些尖锐的包络，我们提高了算法的效率。

切除相交的边缘

可以截断部分路径，该路径的最后一个过渡边缘与倒数第二个过渡边缘交叉。

多边形障碍

请参阅由Thomas Young撰写的《 游戏编程宝石2 》第3.10章，优化视点寻路。 本章讨论剪贴节点，但不讨论圆形，而是讨论多边形。

参考文献

• 皮带的任务
• 皮带轮任务
• 点与线之间的距离
• 两个圆的交点