0
\$\begingroup\$

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. green=optimal/expected path, yellow=actual

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ In order to find the problem with your implementation, we would need to actually see it. Specifically we would need to see how you calculate edge costs. \$\endgroup\$
    – Philipp
    Feb 8 at 10:01
  • \$\begingroup\$ @Philipp I don't. My question is about how to compute the cost. \$\endgroup\$ Feb 8 at 14:44
  • 1
    \$\begingroup\$ Then that would be your problem. The cost of an edge needs to be the time it takes to traverse it. When you ignore that and assume that the cost of every edge is the same, then the algorithm is going to prefer routes with few long edges over routes with many short edges. If you showed us the code of your A* implementation, then we might be able to show you where and how to implement edge costs. \$\endgroup\$
    – Philipp
    Feb 8 at 14:46
  • \$\begingroup\$ @Philipp I know. This is exactly what I described. I asking about how to compute the cost. \$\endgroup\$ Feb 8 at 14:49
  • 1
    \$\begingroup\$ OK, then I am going to post an answer that will tell you that. But please don't reject it because you don't know what to do with that information in your A* implementation. \$\endgroup\$
    – Philipp
    Feb 8 at 14:52

2 Answers 2

2
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think a key component of this answer is that the nodes in your version are the midpoints of the sides of the triangles, not the triangles themselves. So each triangle gives three navigation edges, each weighted by the Euclidean distance from the midpoint of one side to the midpoint of another. The start/end point get their own navigation edges to the sides of the triangle they're in. It sounds like OP is using a model where each triangle is a node, rather than its sides. Clarifying this difference may help them. \$\endgroup\$
    – DMGregory
    Feb 9 at 13:56
  • \$\begingroup\$ Thanks for the suggestion, I don't know if this is customary on SE, but I took some extra information from comments on other answers, the OP said to have tried a (weighted by Euclidean distance) with triangle centers as nodes A*, so I'm assuming they already knows how to use weighted A* correctly. Maybe I'm guessing too much? \$\endgroup\$
    – Mangata
    Feb 9 at 15:33
  • 1
    \$\begingroup\$ What I mean is that I don't see the idea "use midpoints of sides as your A* pathfinding nodes" explicitly stated in any of the answers or comments here, and that could be a useful tip to make explicit - whether for OP's benefit, or to help future searchers who happen upon this thread. \$\endgroup\$
    – DMGregory
    Feb 9 at 15:39
  • \$\begingroup\$ @Mangata Thanks for your thorough answer. I was actually thinking about trying out Hertel-Mehlhorn but wanted to get the triangulated mesh working before trying out convex partitioning. I actually have gotten pretty good results now just using the distance between points closest to the desired target. I will try and see if using midpoints of sides can be used to improve this even further. Tanks \$\endgroup\$ Feb 9 at 16:50
  • \$\begingroup\$ Quick question though. To know the midpoints of sides don't I need to know the previous triangle as well as the one after the next one? I've only seen implementations that use the current and next one to determine the travel cost. \$\endgroup\$ Feb 9 at 17:14
2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ What exactly is node1 node2 in your example? The center of each node? If so I already tried that which is of course far from optimal. My assumption was that the string pulling algorithm is to be done after the path is calculated. Otherwise I would need to know beforehand where I need to move. Is this incorrect? \$\endgroup\$ Feb 8 at 16:43
  • \$\begingroup\$ @user1566228 That's the reason why I asked you to post your sourcecode. They would be the actual nodes of your path, however you decide what is and isn't a possible node of your path. \$\endgroup\$
    – Philipp
    Feb 8 at 16:45
  • \$\begingroup\$ I'm not sure what part of my source code you'd want to see. It's just your standard A* algorithm. A node is a arbitrary triangle defined by 3 points and up to 3 neighbors. 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 \$\endgroup\$ Feb 8 at 17:03
  • \$\begingroup\$ @user1566228 That's why you need to do string pulling (optimizing the path to go tightly around corners) into your pathfinding algorithm not just at the end but also while tracing a path. Without string pulling, you won't know the actual cost of path edges. \$\endgroup\$
    – Philipp
    Feb 9 at 13:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .