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