Polygon based pathfinding

Question

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.

Answer 1

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.