algorithm - 这种寻路算法的名称是什么？

Question

这些图片显示了一个节点图，这些节点排列成具有直行和直列的像素网格。每个节点(边缘上的节点除外)都有 8 条边，这些边都指向它周围最近的 8 个节点。右图显示了一个 A* 搜索，使用简单的移动距离 + 目标启发式欧氏距离。

现在，我说右图给出的路径不够好。相反，我想要一条路径，如果您使用最短的字符串连接起始节点和目标节点，您将获得该路径。调用它的算法是什么？

Answer 1

可以使用 Theta* 执行基于可遍历空间的二维网格离散化的欧氏最短路径查找算法。

另一种(更常用的)方法是基于标准的 4 向或 8 向寻路(左图)，然后进行“字符串拉动”优化。最常见的算法称为 "Funnel algorithm" .

请注意，这两种方法都不能保证产生全局最短路径。此外，这些假设您已准备好将世界表示为网格；如果您改为将其表示为一组凸多边形，则其他算法更合适。