Pathfinding polygon

Question

I have implemented a basic grid-based A * pathfindinder in Java. I would like to create a navigation mesh / polygon based pathfinder, but I have a problem:

If I found an orange route, 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 that red is cheaper. How to program my A * algorithm and / or create my grids to prevent this from happening.

Answer 1

Chapter 15 in Computational Geometry: Algorithms and Applications describes and solves precisely this problem: the free space can be described by a trapezoidal map, but the paths found using the map are not necessarily the shortest. The recommended view (also discussed in LaValle Planning Algorithms (Section 6.2.4) ) is the so-called visibility graph, which has edges connecting the vertices of the obstacles.

Pseudocode and numbers are available on the book’s homepage, and Google Preview also contains parts of the chapter.

Answer 2

you should check out this link: http://alienryderflex.com/shortest_path/ he explains how to calculate the shortest path within the polygon, a very clear explanation and code implementation.

Answer 3

Sorry, I can’t help with your question directly, but we have ported the multi-user pathfinder for haxe and it can compile in java (only with swing, but can try slick2d soon) and can be integrated into the Java project taking into account some studies. It is called hxDaedalus and is located on github and can be an interesting reference point.