Menu
I have implemented a basic grid based A* pathfindinder in Java. I would like to make a navigational mesh/polygon based pathfinder, but the problem I have is this:
If I found the orange route then I could use something like a funnel algorithm to straighten it to get the desired route (blue). However, if the program calculates the cost of each of the routes, red and orange, then it will say the red one is the cheaper one. How do I program my A* algorithm and/or create my meshes so that this doesn't happen.
823
A* pathfinding algorithm is arguably the best pathfinding algorithm when we have to find the shortest path between two nodes. A* is the golden ticket, or industry standard, that everyone uses. Dijkstra's Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren't promising.
Dijkstra's Algorithm is another algorithm used when trying to solve the problem of finding the shortest path. This algorithm specifically solves the single-source shortest path problem, where we have our start destination, and then can find the shortest path from there to every other node in the graph.
This optimization results in shortest paths being found more quickly. The A* algorithm can be used to find shortest paths between single pairs of locations, where GPS coordinates are known.
A* algorithmA* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end.
Chapter 15 in Computational Geometry: Algorithms and Applications describes and solves exactly this problem: the free space can be described by a trapezoidal map, but paths found using the map aren't necessarily the shortest. The recommended representation (also discussed in LaValle's Planning Algorithms (Section 6.2.4)) is a so-called visibility graph, which has edges that connect vertices of the obstacles.
Pseudo-code and figures are available from the book homepage and the Google preview also contains parts of the chapter.
155
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
