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

问题描述

请花一点时间来理解我的处境。如果不是COM prehendable，请告诉我，在注释中。

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

我有航点的ArrayList。这些航点都没有任何顺序。一个航点具有以下属性：
{int型的，浮动Z，浮动Y，浮球X，浮动旋转}

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}

这适用于一个三维的世界，但因为我的寻路应该不会在意身高（从而把世界作为一个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.

• 在这个2维世界中，X再presents X轴和Z轴重新presents y轴。
• 如果x的增加，在世界上的对象东移。如果x减小，在世界上的对象移动西
• 如果Z变大，在世界上的对象向北移动。在z减小，在世界上的对象移动南部。

因此​​，这些新航点可以简化为：航点= {浮动x，浮ÿ}

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

现在，这些航点重新present X轴（x）和Y轴（z）的一个对象的位置。此外，还有一个当前的位置： curLocation = {浮动x，浮ÿ} 和目标位置： tarLocation = {浮动x，浮ÿ} 。

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. 在其间的每个航点的距离不得大于（浮点）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最接近的路径。

我将如何实现这一目标？任何反馈是AP preciated。

How would I achieve this? Any feedback is appreciated.

推荐答案

我认为您的解决方案是开始的 Dijkstra算法先找到最短路径。你可以考虑您的航点是一个连通图，如果他们是在XY平面足够近然后应用Dijkstra算法（也有很多例子code房源的在线），其中节点连接。

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航点寻路：WPS的组合，从curLocation去targetLocation的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！