I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when considered from the user's perspective. I have narrowed this down to the cost calculations for long edges when the agent is trying to hug one edge of the polygon. To be clear the graph connects polygon edges, not polygon centroids. I have an idea for a solution, but first please consider the following diagram with both path through midpoints, and optimal path. It is only a subset of the search space, but one that is currently not traversed because the total cost is too high when compared to another part of the mesh.
To get from the start point to the end points, the cost calculations use the midpoints of each edge. However, the best path is actually a lot cheaper, but the algorithm does not return this set of edges because the valuation is too high. Always using mid points causes these bad routes to be ignored in cases of long edges, so I have modified my algorithm to generate three nodes per edge - the two end points and the mid point. This solves the problem - agents now take this path - but at the cost of a much larger search space.
As a solution I have been thinking instead of doing a closest-point-to-edge test when doing the scoring, essentially making a dynamic, adaptive point on the edge for scoring. For each edge I would do a closest point on the edge segment to the segment from the grandparent cell's midpoint - the parent of the parent - to the current edge's midpoint, and then score from that, instead of using the parent's midpoint. You can see these steps and the composite path in the following diagram, where G is the grandparent midpoint, X is the current edge midpoint and A is the adaptive midpoint. I have included a diagram showing the composite cost of the edges, which looks odd but is shorter than the original mid-point only (I think).
I have yet to implement this in my system. My question is does changing the cost calculations to use the 'adaptive' points seem reasonable or am I going to blow up my cost valuations? What if I use the minimum cost of this value and the midpoint value? Does anyone have any other good ideas here? Currently the cost of doing 3 times the nodes is too much as is three times the memory for the nodes.