java - 二维航路点寻路 : combinations of WPs to go from curLocation to targetLocation

Question

请花点时间了解我的情况。如果有不明白的地方，请在评论中告诉我。

我有一个航点数组列表。这些航路点没有任何顺序。航点具有以下属性:
{int type, float z, float y, float x, float rotation}

这适用于 3 维世界，但由于我的寻路不应该关心高度(因此将世界视为 2 维世界)，y 值将被忽略。旋转对于这个问题并不重要。

• 在这个二维世界中，x 代表 x 轴，z 代表 y 轴。
• 如果 x 增加，则世界中的物体向东移动。如果 x 减小，则世界中的物体向西移动。
• 如果 z 增加，则世界中的对象向北移动。如果 z 减小，则世界中的物体向南移动。

因此，这些"new"航路点可以简化为:waypoint = {float x, float y} .

现在，这些航路点表示对象的 X 轴 (x) 和 Y 轴 (z) 位置。此外，还有一个当前位置:curLocation = {float x, float y}和目标位置:tarLocation = {float x, float y} .

这就是我想要得到的:
将从curLocation出发的所有航路点组合(又名:路径或路线)至 tarLocation 在以下严格条件下:

1. 每个航路点之间的距离不得大于(float) maxInbetweenDistance .这包括与 curLocation 的初始距离到第一个航路点和最后一个航路点到tarLocation的距离.如果不可能有这样的航路点组合，则应返回 null。
2. 当在 maxInbetweenDistance 内发现多个航路点时从通向目标航路点的航路点，应选择最近的航路点(如果稍微远一点的替代航路点会导致一条距离更长的新路径也返回，则更好)。
3. 返回的航点组合(路径)的顺序应该是从最短路线(最短距离)到最长路线(最远距离)

最后，请考虑以下几点:

1. 这是我唯一需要明智地进行 AI/寻路的事情，这就是为什么我不希望使用成熟的寻路或 AI 框架的原因。我相信一个函数应该能够处理上述问题。
2. 如果返回所有可能的航路点组合会导致过多的开销，那么如果可以指定最大数量的组合(但仍按从最近到最远的顺序)也没有问题。例如。 5 条最近的路径。

我将如何实现这一目标？感谢任何反馈。

Answer 1

我认为您的解决方案是从 Dijkstra's Algorithm 开始首先找到最短路径。您可以将您的航路点视为一个连通图，其中如果节点在 xy 平面中足够近则它们是连通的，然后应用 Dijkstra(网上有许多示例代码 list )。

现在您有了从头到尾穿过图形的最短路径，它将由图形的 N 条边组成。

接下来您需要创建 N 个新图，每个图都与第一个图一样，但最短路线的一部分未连接。在这些修改后的图表上找到从头到尾的最短路线。现在您有 N+1 条路线，您可以按长度排序。

重复此操作，直到找到满足您需要的足够路径，或者没有未排序的路径。

我还没有找到这种技术的名称，但它被描述为对 Dijkstra here 的修改。 .