artificial-intelligencepath-finding

AI Pathfinding using 2D polygons instead of waypoints - Is there a recommended algorithm?

I'm trying to use path finding on a series of convex polygons, rather than waypoints. To even further complicate this, the polygons are made by the users, and may have inconsistent vertices. For example:

https://i.sstatic.net/vgzX3.png

We know the object is X wide by Y deep, and that the polygons have vertices at certain locations. Is there a specific algorithm to find the fastest way to the goal while keeping the entire object in the polygons (If I understand correctly, A* only works on waypoints)? How do you handle the vertices not being the same object but being at the same location?

EDIT: The polygons are convex; It's 2 separate polygons with the edges on the line. Also, how do you implement * pathfinding, as a node based system wouldn't work in a 'infinite' resolution polygon?

Solution

  • In general, all shortest-path segments will have, as end-points, either polygon vertices or the start and goal points. If you build a graph that includes all those segments (from the start to each "visible" polygon vertex, from the goal to each "visible" polygon vertex, from the start to the goal, and from each polygon vertex to each other polygon vertex) and run A* on that, you have your optimal path. The cost of building the graph for A* is:

    If you are only going to apply A* once, then the price of building the fixed part of the A* graph for a single traversal may be somewhat steep. An alternative is to build the graph incrementally as you use it:

    illustrated example

    Java code implementing the above approach can be found here.