无限平面上的无图运动规划

Question

一个对象位于 A，想要移动到 B。 我想计算一个移动向量，不会在数组C 中的待避点的距离D内移动。

因此，如果移动向量（B-A）被归一化并乘以物体的速度会使其接近 C 中任何一个点 D 的范围，那么该向量将旋转，以便它不会这样做。

这是在二维中的。另外，如果这个操作有一个名称，请在评论中指出或自己编辑这个问题，因为我不知道该怎么称呼它。

此外，我的第一反应是将活动区域分成节点，并运行 A*，但我想尝试这个问题的数学方法，对于群集的一些实验给我留下了可以做到的印象。 更新（来自评论）：这张图片非常接近我想要的解决方案：

假设我们从左边的点开始，我们向右转向目标（另一个点），我们在右边检测到一堵墙，所以我们停止转向并向前移动。墙消失了，所以我们允许重新开始朝着目标旋转，以此类推。我知道这可能导致对象根本无法到达那里，但我想定义一种行为，而不是必须要有一个解决方案，如果你知道我的意思的话。 更新2：将活动区域转换为一组节点可能会证明效率低下。 A*和其他启发式图遍历算法非常适合低维问题。但是我想要移动的区域在大小上是无限的，并且只有少数障碍物分散其中。节点本身或者更准确地说是潜在位置是无限小的。当然，这可以通过某种四叉树进行优化，但我有一种感觉，简单的移动向量在某种程度上旋转和插值也可以解决这个问题。

- Mizipzor

---

你是想找到满足这个条件的最小路径，还是任何解决方案？ - chillysapien

任何解决方案。或者更准确地说，我根本不在寻找路径。物体不应该“规划”它的路径，而是只能看一步之遥。它不是一个规划路径的机器人，在这里更像是群集或细胞自动机。至少这是我想要的效果。 - Mizipzor

Answer 1

我听到这被称为运动规划和路径规划（如上所述）。

有很多算法，但从您的描述来看，可见图可能是一个不错的起点。您有一个由点A、B和每个点周围的多边形C组成的图形（您也可以通过计算每个点的切线来用圆形实现，我相信）。您将边缘计算为点之间的潜在路径。这里有一个幻灯片演示，可以更好地解释它。

然后，在可见性图的基础上，应用像A*（一种启发式搜索）这样的搜索算法，以找到最优路径。

然而，您应该考虑您要寻找什么。上述方法将通过紧贴所有角落找到最短路径，但其他算法可能更适合您的最优化想法。

- Todd Gardner

---

你发布的“运动规划”维基文章中的“有效路径示例”图像非常接近我想要的解决方案。假设我们从左边的点开始，向右转向目标（另一个点），我们检测到右侧有一堵墙，所以我们停止转向并向前移动。墙消失了，所以我们再次开始朝着目标转向，如此往复。我知道这可能导致物体根本无法到达那里，但我想定义一种行为，而不是解决方案，如果你知道我的意思。 - Mizipzor

Answer 2

在您的回答中所链接的页面（点击此处）上，也有关于驾驶行为的讨论。

特别是，请查看他的包含和路径跟随页面，以获取良好的示例。 自主角色的驾驶行为。

- Andy Mikula

Answer 3

你可以考虑使用势场算法。这种方法可以避免“贴着障碍物边缘”的问题。

但需要注意的是，与A*算法一样，这需要对状态空间进行量化，因此根据所需的精度，可能会非常计算密集。

- j_random_hacker

---

昂贵的计算是我想避免使用A*的主要原因。同时请注意，我的世界正在快速变化，使得对其进行量化几乎不可能。虽然这篇文章很有价值，但我认为很难将其应用到我的问题上。 - Mizipzor

Answer 4

我在这个页面上找到了一个相当冗长的群集算法描述。

对于所有障碍物使用分离规则，仅朝向目标位置进行对齐（因为我们没有群体伙伴），并且（出于同样的原因）忽略凝聚力规则。

我想知道是否会产生预期效果。

- Mizipzor