Ad

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.

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}

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.

  • In this 2 dimensional world, the x represents the x axis and the z represents the y axis.
  • If x increases, the object in the world moves east. If x decreases, the object in the world moves west.
  • If z increases, the object in the world moves north. If z decreases, the object in the world moves south.

Thus, these "new" waypoints can be simplified to: waypoint = {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}.

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

  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. This is the only thing I need to do AI/pathfinding wise, which is why I do not wish to use a full blown pathfinding or AI framework. I believe one function should be able to handle the above.
  2. If returning all possible combinations of waypoints causes too much overhead, it'd also be fine if one can specify a maximum amount of combinations (but still ordered from closest to furthest). Eg. the 5 closest paths.

How would I achieve this? Any feedback is appreciated.

Ad

Answer

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).

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

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.

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

Ad
source: stackoverflow.com
Ad