2D 航路点寻路:从 curLocation 到 targetLocation 的 WP 组合 [英] 2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation

问题描述

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

Please take a moment to understand my situation. If it is not comprehendable, please tell me in a comment.

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

I have an ArrayList of Waypoints. These waypoints are not in any order. A waypoint has the following properties:
{int type, float z, float y, float x, float rotation}

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

This applies to a 3 dimensional world, but since my pathfinding should not care about height (and thus treat the world as a 2 dimensional one), the y value is ignored. Rotation is not of importance for this question.

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

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

Thus, these "new" waypoints can be simplified to: waypoint = {float x, float y}.

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

Now, these waypoints represent the X-axis (x) and Y-axis (z) locations of an object. Moreover, there is a current location: curLocation = {float x, float y} and a target location: tarLocation = {float x, float y}.

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

This is what I want to get:
All combinations of waypoints (aka: paths or routes) that will lead from curLocation to tarLocation under the following strict conditions:

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

1. The distance inbetween each waypoint may not be bigger than (float) maxInbetweenDistance. This includes the initial distance from curLocation to the first waypoint and the distance from the last waypoint to tarLocation. If no such combination of waypoints is possible, null should be returned.
2. When multiple waypoints are found within maxInbetweenDistance from a waypoint that lead towards the target waypoint, the closest waypoint should be chosen (even better would be if an alternative waypoint that is slightly further away would result in a new path with a longer distance that is also returned).
3. The order of returned waypoint combinations (paths) should be from shortest route (minimum distance) to longest route (maximum distance)

最后，请考虑以下几点:

Finally, please consider these points:

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

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

How would I achieve this? Any feedback is appreciated.

推荐答案

我认为你的解决方案是从 Dijkstra 算法首先找到最短路径.您可以将您的航路点视为一个连通图，其中如果节点在 xy 平面中足够接近，则这些节点是相互连接的，然后应用 Dijkstra(网上有许多示例代码清单).

I think your solution is to start with Dijkstra's Algorithm to find the shortest path first. You can consider your waypoints to be a connected graph where nodes are connected if they are close enough in the xy plane then apply Dijkstra (there are many example code listings online).

现在您拥有了从开始到结束通过图表的最短路径，该路径将由图表的 N 条边组成.

Now you have the shortest path through your graph from start to finish, which will be composed of N edges of the graph.

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

You would next need to create N new graphs, each just like the first, but with one segment of your shortest route un-connected. Find the shortest routes from start to finish on these modified graphs. Now you have N+1 routes which you can sort by length.

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

Repeat this until you have found enough paths for your needs, or there are no unranked paths left.

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

I haven't found a name for this technique, but it is described as a modification to Dijkstra here.

这篇关于2D 航路点寻路:从 curLocation 到 targetLocation 的 WP 组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！