2D航路点寻路：WP的组合从curLocation到targetLocation
请花点时间了解我的情况。 如果不可理解，请在评论中告诉我。
我有一个Waypoints的ArrayList。 这些航点不是任何顺序。 航点具有以下属性：
{int type, float z, float y, float x, float rotation}
这适用于三维世界，但由于我的寻路不应该关心高度（因此将世界视为二维世界），因此忽略y值。 轮换对于这个问题并不重要。
- 在该二维世界中，x表示x轴，z表示y轴。
- 如果x增加，则世界中的物体向东移动。 如果x减小，则世界中的物体向西移动。
- 如果z增加，则世界中的物体向北移动。 如果z减小，则世界中的物体向南移动。
因此，这些“新”航路点可以简化为： 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内找到多个航路点时，应选择最近的航点（如果距离稍远一点的替代航路maxInbetweenDistance导致距离maxInbetweenDistance的新航路点也更好回）。 - 返回航路点组合（路径）的顺序应该是从最短路径（最小距离）到最长路线（最大距离）
最后，请考虑以下几点：
- 这是我唯一需要进行AI /寻路操作的方法，这就是为什么我不希望使用完整的路径寻找或AI框架。 我相信一个function应该能够处理上述问题。
- 如果返回所有可能的航点组合会导致过多的开销，那么如果可以指定最大组合数量（但仍然从最接近最远的顺序排序）也可以。 例如。 5条最近的路径。
我怎么做到这一点？ 任何反馈都表示赞赏。
我认为你的解决方案是从Dijkstra的算法开始，首先找到最短的路径。 您可以将您的航点视为连接图，如果它们在xy平面中足够接近，则连接节点然后应用Dijkstra（在线有许多示例代码清单）。
现在，您从头到尾拥有通过图表的最短路径，该路径将由图形的N个边缘组成。
接下来你需要创建N个新图形，每个图形与第一个图形一样，但是最短路径的一段不连接。 在这些修改过的图表上找到从头到尾的最短路径。 现在您有N + 1条路线，您可以按长度排序。
重复此操作，直到找到满足您需求的足够路径，或者没有任何未排除的路径。
我没有找到这种技术的名称，但它被描述为Dijkstra的修改。
如果您的航点具有连通性，您应该看看Dijkstra的最短路径算法。 第一对谷歌点击甚至列出了Java的实现。 （我不知道post中是否知道连接性，但它确实包含“graph-algorithm”标签，所以我假设如此）。 顾名思义，这种方法为您提供了两个节点之间的最短路径。
您的约束条件具有挑战性，因为在这些约束条件下需要所有可能的路径组合。 再次 – 假设连接存在 – 您的节点邻接矩阵可以强制执行maxInbetweenDistance规则。 同样，您可以使用此矩阵来获得“次佳”解决方案。 一旦知道了最佳路径，就可以将该路径（或其中的元素）标记为不可用，然后重新运行Dijkstra的算法。 通过重复此过程，您可以获得一组越来越次优的路径。
作为惯例：在大多数计算几何问题中，Z是高度，水平面由XY轴形成。
那么最容易实现的可能就是创建一个路径的ArrayList，它又是一个包含所有可能路径的航点的ArrayList，然后使用递归函数返回每个路径是否有效给定起点和结束点值和最大距离，如果路径无效，请从列表中删除它。 下一步将通过剩下的每条路径并将它们从最短的总距离排序到最短的路径。 这将是获得你想要的蛮力方法，所以效率最低。 当我今晚回到家时，如果某人已经没有更有效的方法在java中这样做，我会重新发布。
编辑：如果蛮力方法太多，航路点列表将必须按一些方式进行排序，最好的方法可能是根据距离起点的距离对它们进行排序。