Polygon based pathfinding

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.

---

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.

---

Sorry I can't help with your question directly, but we ported a polygon based pathfinder to haxe and it can compile to java ( only tried with swing so far but might try slick2d soon ) and could be integrated into a Java project given some research. It's called hxDaedalus and is on github and might be an interesting point of reference.