2

请花一点时间了解我的情况。如果不能理解，请在评论中告诉我。

我有一个航点的 ArrayList。这些航点没有任何顺序。航点具有以下属性：
{int type, float z, float y, float x, float rotation}

这适用于 3 维世界，但由于我的寻路不应该关心高度（因此将世界视为 2 维世界），因此忽略 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}。

这就是我想要得到的：在以下严格条件下将导致从到的
所有航路点组合（又名：路径或路线） ：curLocationtarLocation

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

最后，请考虑以下几点：

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

我将如何实现这一目标？任何反馈表示赞赏。

4

3 回答 3

2

如果您的航点具有连通性，您应该看看 Dijkstra 的最短路径算法。谷歌的前几个热门甚至列出了 Java 中的实现。（我不知道从帖子中是否知道连通性，但它确实包含“图形算法”标签，所以我假设是这样）。顾名思义，此方法为您提供了两个节点之间的最短路径。

您的约束具有挑战性，因为在这些约束下需要所有可能的路径组合。再次 - 假设存在连接 - 您的节点邻接矩阵可以强制执行您的 maxInbetweenDistance 规则。同样，您可以使用此矩阵来获得“次佳”解决方案。一旦知道最佳路径，您可以将该路径（或其元素）标记为不可用，然后重新运行 Dijkstra 算法。通过重复这个过程，你可以获得一组越来越次优的路径。

作为惯例：在大多数计算几何问题中，Z 是高度，水平面由 XY 轴形成。

于 2011-03-04T20:02:01.440 回答
2

我认为您的解决方案是从Dijkstra 算法开始，首先找到最短路径。您可以将您的航路点视为一个连接图，如果节点在 xy 平面上足够接近，则连接节点，然后应用 Dijkstra（网上有许多示例代码清单）。

现在你有了从开始到结束的最短路径，它将由图形的N条边组成。

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

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

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

于 2011-03-04T20:57:08.527 回答
1

那么最容易实现的可能是创建一个路径的ArrayList，它又是一个包含所有可能路径的航点的ArrayList，然后使用递归函数返回每个路径是否有效，给定起点和终点值和最大距离，如果路径无效，则将其从列表中删除。下一步将遍历剩下的每条路径，并将它们从最短的总距离排序到最短。这将是获得您想要的东西的蛮力方法，因此可能是效率最低的方法。当我今晚回家时，如果有人还没有用更有效的方法在 java 中执行此操作，我将重新发布。

编辑：如果蛮力方法太多，则必须对航路点列表进行排序，最好的方法可能是最初根据与起点的距离对它们进行排序。

于 2011-03-04T19:33:36.167 回答