algorithm - A* 用于寻找最短路径并避免将线作为障碍物

Question

我必须得到 2D 中两点之间的（最短）/（最佳）距离。我必须避免可能连接在一起的线条形状。关于如何表示我可以旅行的节点有什么建议吗？我曾想过制作一个网格，但这听起来不太准确或优雅。如果一条线的任何点在正方形内（节点是正方形的中心），我会认为一个节点是不可行走的。

一个例子是从 A 点到 B 点。

网格是解决此问题的推荐方法吗？提前非常感谢！

Answer 1

我认为这本质上是 Larsmans 的回答更加算法化：

图的节点是障碍物的顶点。每个内部顶点实际上代表两个节点：凹边和凸边。

1. 使用欧几里得启发式距离将起始节点推入优先级队列。
2. 从优先级队列中弹出顶部节点。
3. 做一个从节点到目标的线相交测试（可能使用光线追踪数据结构技术来加速）。如果失败了，
4. 考虑从当前节点到每个其他顶点的射线。如果当前节点与所考虑的顶点之间没有交集，并且从当前节点的角度来看该顶点是凸的，则将该顶点添加到优先级队列中，使用当前节点中的累积距离加上与当前节点的距离进行排序节点到顶点加上启发式距离。
5. 返回到 2。

如果障碍物中存在诸如“T”形接头之类的东西，则您必须进行额外的预处理工作，而且我发现它在许多情况下都会中断，我不会感到惊讶。您可以通过仅考虑位于当前节点和目标之间的连接组件的顶点来使事情变得更快。

因此，在您的示例中，在第一次尝试A,B之后，您将推送A,8、A,5、A,1、A,11和A,2。考虑的第一个节点是A,8、A,1和A,5，但它们无法退出，并且它们可以到达的节点已经以较短的累积距离推入队列。 A,2和A,11将被考虑，事情将从那里开始。

Answer 2

我认为您可以通过在定义为的图上进行 A* 搜索来解决此问题：

• 顶点：障碍物边缘的起点、终点和所有端点。
• 边（后继函数）：对应线不穿过任何障碍物边的任意一对。一个简单的实现只会检查潜在边缘和所有障碍物边缘之间的交叉点。更快的实现可能会使用某种二维光线追踪算法。

即，没有必要将平面离散化为网格，但没有它，后继函数变得难以定义。

Answer 3

一个网格，A* 穿过它是要走的路。我所知道的所有游戏都使用 A* 或对它的全球路线的改编，并通过转向行为来补充它以实现局部准确性。也许您不知道使用转向行为将解决您对准确性的所有担忧（搜索引擎）。

编辑：我只记得一个使用流场的策略游戏。但它不是主流。

顺便说一句：要了解转向行为对您的对象的作用，请查看许多有关它的 youtube 视频。他们中的一些人在更一般的意义上使用术语寻路：包括全局算法 (A*) 以及涉及转向行为的碰撞避免、路径平滑和对象惯性。