Weighting navigation mesh nodes for A*

Question

I'm trying to implement path finding for my game using a navigation mesh and A* search. While I believe I got this working correctly I'm having trouble getting desired results because I don't know how to decide the cost between each node.

While the algorithm correctly chooses the path with the least amount of nodes. Sometimes the result can be quite nonsensical.

Here the entity would take take a detour(yellow) around the obstacle instead of using the more optimal path (green)

Right now each triangle/node has the same cost and I'm not sure how best to compute it since it depends on how the entity is going to travel through the triangles. I've been thinking about splitting the triangles further to make sure they have about the same size but this might not help in this case. For me it's not important that the Path is 100% the shortest possible, but I want to avoid such weird detours. How could I approach this issue?

Edit for clarification: I'm asking about how to compute the cost between nodes/triangles to help me compute the shortest path instead of just to least amount of nodes to travel.

Answer 1

Here I am assuming that you already know what is going on with A* and heuristics, because it seems the problem is elsewhere.

I'm having trouble implementing the heuristic that computes the cost between nodes since the way the entity will move depends on the final path.

Yes, The funnel algorithm is carried out after the path is selected. We can only find the shortest path before path straightening.

The path on the right in the figure is indeed shorter than the path on the left:

The accuracy of the final path depends on how uniform the mesh is, the more evenly all paths are straightened, the more correct the result. For example the path on the right can be selected largely because of a particularly thin triangle in a suitable place:

If you change the split shape of this triangle so that it is not so thin, things will be much better:

There happens to be an algorithm that is often used for navmesh generation called Delaunay triangulation. It can improve the shape of triangles inside the mesh and avoid some edge cases.

And some modern pathfinding suites use convex polygons instead of triangles as pathfinding nodes, which reduces the number of nodes and also reduces the impact of malformed triangles. The Hertel-Mehlhorn Algorithm is the standard approach for doing this.

In summary, you can:

1. Improve the shape of the mesh during the navmesh generation phase(by re-triangulation), making it more uniform, which will reduce the difference in shortest paths before and after straightening.
2. Artificially adding some vertices can also help.
3. You can also use polygonal meshes instead of triangular meshes.
4. Then use a heuristic function to find only the shortest path before straightening.
5. Finally straighten the path.

Edit:

Why do I use midpoints of sides instead of triangle centers as pathfinding nodes in the example graph?

This is actually to reduce the error before and after the path is straightened. When a path passes through two adjacent triangles, after being straightened, it must pass through the common side of the two triangles. Its intersection with the common edge may be anywhere along the edge. To minimize the error before and after straightening the path, or try to make the error of different paths more stable, we can minimize the error of this intersection point.

This is an example. If the midpoints of adjacent sides are used as nodes, then the maximum error is |AB|/2. If the center of the triangle is used as the node, then the maximum error is >|AB|. Using midpoints of triangle sides as nodes gives more stable results.

Answer 2

According to the comments, your A* implementation does treat all edges equally and doesn't consider that different edges have a different traversal cost. When you do that, then the algorithm is always going to prefer routes with few long edges over routes with many short edges.

To fix that issue, the cost of each edge needs to be equivalent to how long it takes to traverse that edge. If we can assume that entities in your game are able to travel with a fixed velocity in any direction, then the time it takes to travel from node1 to node2 would be equivalent to their distance as calculated using the Pythagorean theorem \$a^2 + b^2 = c^2\$ or \$c = \sqrt{a^2 + b^2}\$. Or expressed in C-style programming language syntax:

float dist_x = node1.x - node2.x;
float dist_y = node1.y - node2.y;
float edge_cost = Math.sqrt(dist_x * dist_x + dist_y * dist_y);

To improve accuracy, you should do the "string pulling" step you usually have when using a navigation mesh after each path navigation step and revise the total cost of the path accordingly.