请花点时间了解我的情况。如果不明白，请在评论中告诉我。
我有一个航点数组列表。这些路径点没有任何顺序。航点具有以下属性:
{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 在以下严格条件下:
- 每个航路点之间的距离不得大于
(float) maxInbetweenDistance。这包括距curLocation的初始距离到第一个航点以及从最后一个航点到tarLocation的距离。如果不可能存在这样的路径点组合，则应返回 null。 - 当在
maxInbetweenDistance内找到多个航路点时从通向目标航路点的航路点，应选择最近的航路点(如果稍微远一点的替代航路点会导致返回距离较长的新路径，那就更好了)。 - 返回的航路点组合(路径)的顺序应为从最短路线(最小距离)到最长路线(最大距离)
最后，请考虑以下几点:
- 这是我唯一需要做的人工智能/寻路明智的事情，这就是为什么我不希望使用完整的寻路或人工智能框架。我相信一个函数应该能够处理上述问题。
- 如果返回路径点的所有可能组合会导致过多的开销，那么如果可以指定最大数量的组合(但仍按从最近到最远的顺序排序)也可以。例如。 5 个最近的路径。
我该如何实现这一目标？如有任何反馈，我们将不胜感激。
最佳答案
我认为你的解决方案是从 Dijkstra's Algorithm 开始首先找到最短路径。您可以将您的航路点视为一个连通图，其中如果节点在 xy 平面上足够近，则它们是相连的，然后应用 Dijkstra(网上有许多示例代码 list )。
现在您已经有了图形从开始到结束的最短路径，它将由图形的 N 条边组成。
接下来您需要创建N 个新图表，每个图表都与第一个图表类似，但最短路线的一段未连接。在这些修改后的图表上找到从起点到终点的最短路线。现在您有 N+1 条路线，您可以按长度排序。
重复此操作，直到找到足够的路径来满足您的需求，或者没有剩余未排名的路径。
我还没有找到这项技术的名称，但它被描述为对 Dijkstra here 的修改.
关于java - 2D 路径点寻路 : combinations of WPs to go from curLocation to targetLocation，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5194482/