I am trying to implement A* on a triangle navmesh. I've been using this thesis for the A* details: https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf​ (page 67, PDF page 80). Most of the calculations are based on the edge between two triangles (parent and successor). The heuristic is quite simple and I'm confident that this is correct. However, I think that the suggested implementation of g(x) isn't quite working for me. For now, I assume that all edges within the navmesh are traversable (meaning that the resulting shortest path should always be a straight line). One thing that I'm suspicious of is my implementation of how to handle the start point within the start triangle and the goal point within the goal triangle.

Here are some images that show what I'm seeing: https://imgur.com/a/DCfwoOE.​ As you can see, one of the images is showing that the path from start (green dot) to goal (red dot) is correct. However, when I slightly move the goal point, as shown in another image, the path is incorrect. Finally, in the gif, you can see how the result of the algorithm is sometimes right and sometimes wrong. I don't think the gif gives much insight, it just shows the weird behavior.

I'm not sure exactly what you are asking here. The distance itself is easily calculated by adding together all the line segments.

As far as it generating an “incorrect” path, note that A* is not guaranteed to generate optimal solutions. Carefully implemented with optimizations like priority queues and correctly-implemented cost estimate heuristics it usually finds a minimal-cost path, but not always the optimal one, and not always one that is visually appealing, although you can add some extra costs to help it be more appealing like a cost for turns.

Implementing it on a triangular mesh like you show can be quite tricky to get right, as small triangles and degenerate triangles can cause difficulty, deciding where along the edge to cross can also be difficult. Even so, the algorithm should work correctly on the mesh.

Since you don't link to any code, know that there are a bunch of freely available implementations out there, including an implementation in the Boost library, plus pathfinding implementations in all the major game engines. Many lesser libraries also provide implementations. You can certainly write it yourself, but many portable implementations are easily found.

@frob Thanks for the reply. I'll try to rephrase what I'm asking after I respond to what you said.

I'm pretty familiar with A*, and I am pretty sure that as long as g(x) is correct and h(x) is admissible and consistent, then A* should be providing optimal paths. Further, I think if the heuristic were to always return 0, then A* should still return the optimal path, the only problem is that it will not necessarily explore nodes in an intelligent order; it will behave just like Dijkstra's. I'm sure that if my distance/cost function (g(x)) is correct, then it should return an optimal path.

I understand your point about certain kinds of triangles, but I am currently facing a much less subtle problem. I'll keep that point in mind as I move forward.

I could share my code, if you think it would be helpful. I figured it would be easier to discuss the details of the thesis that I've linked to first. I'm not in a situation to use external code. Here is a link to my relevant code: https://pastebin.com/LNqftD6E​

Now, what am I trying to ask? First, does the linked thesis' method for computing g(x) seem reasonable? I'm pretty sure that I've implemented it as explained. Except, maybe I've got something wrong around the start and end points? That is my second question; the thesis' description explains calculating g(x) from one triangle to another, but I'm not sure what I should be doing for the calculation from the start point and around the goal point. I'm also looking for other ways to implement the distance/cost function for a triangle navmesh.

It looks like your heuristic goes along triangle endpoints, and is only taking the distance between two endpoints. It looks like it does not consider a path that touches only a vertex. It also looks like it doesn't account for a score if it enters and exits on the same vertex. If the two sides are the same or adjacent the distance is invalid, if they're not it takes the shortest edge. Your distance doesn't take into account moving from the starting point to one of the corners, nor the possibility of moving through the middle of an edge; everything is done at triangle endpoints.

More simply, I think the core issues are a combination of these:

• It isn't possible to share a vertex, it MUST move along an edge. This means multiple triangles touching a single vertex are disqualified, only routes touching two verts are allowed.
• It isn't possible to move in the middle of an edge, only from vertex to vertex.

I'm not certain, but it looks like your “incorrect” results follow the shortest path when using that as a heuristic. the function calculateHValue only considers the distance from the corners of the triangles containing the point, basically this:

Assuming the red box is a barrier it looks like segment 3 is a problem, even though the points are on the boundary of the object the triangle is inside it and shouldn't have been considered. Otherwise, those do look like the shortest distances between the two marked triangle corners.

When you move around below, notice that your code does not allow for a shared vertex. It only considers a point to be valid if it traverses and edge. Since these shared points are disqualified, it probably gives this path:

The same here, staying on a vertex is invalid:

And as your video progresses, more motion similarly follows what I think is a shortest path between edges:

Assuming you want to cut through the middle of the triangles you are going to need a more complex function that permits both staying on a single vertex and also cutting through the edges, rather than only going from vertex to vertex.

@frob Sorry, let me clarify some of the visualization stuff. Currently, red and green edges are treated the same, meaning that all edges and vertices are walkable. That also means that the shortest path should always be a straight line. The green dot is the start, the red dot is the path. The shaded green triangles are the triangles through which the shortest path should go. Again, currently, this should always be the triangles underneath the straight line between the green and red dot. At a later point, once I have this corridor, I can run a funnel algorithm to find the actual shortest path within it.

Now, regarding the heuristic. As long as A* underestimates the heuristic, the algorithm should still result in an optimal path, it will just need to expand more nodes. I've tried returning 0 as the heuristic (calculateHValue) and I still do not calculate the correct path. This leads me to believe that my g(x) calculation is incorrect.

To clarify on the current heuristic. It is the distance from the goal to the closest point on the edge of the triangle through which we entered. If this isn't the last triangle in the list, this could be a straight line through the middle of some edge in one of the triangles on the way to the goal.

Hmm, I'm not quite sure I follow why you think that I am not allowing multiple uses of the same vertex. The g(x) calculation uses the two vertices of edge that was used to enter the triangle. Since that vertex can be shared between edges of successive triangles, the vertex can be reused.

Based on the logic I understand from the thesis, the 3rd case which is using the difference of heuristics for the calculation of g(x), I think it is possible to traverse the middles of triangle edges.

SandSnip3r said:
meaning that all edges and vertices are walkable. That also means that the shortest path should always be a straight line.

I'm confused from your images, which illustrate the found path with shading the triangles. This implies you use the triangles as graph nodes, not the triangle vertices as you said. So maybe your visualization is not ideal and you can change it for better feedback on the algorithm. (Your results look all correct to me).

Drawn a picture showing both options:

Red is vertices and edges, green is triangle centers and dual edges. But no matter what you use, it won't be a straight line ofc.

SandSnip3r said:
The green dot is the start, the red dot is the path. The shaded green triangles are the triangles through which the shortest path should go. Again, currently, this should always be the triangles underneath the straight line between the green and red dot.

Here's related confusion, coming from your animated gif:
Are the shaded triangles the path, or are they a reference visualization got from intersecting triangles with a straight line?
If it's the latter, the path (along vertices and edges) is not shown at all?

I can't comment on how various heuristics affect the results (using only Dijkstra myself), but i doubt an ‘always perfect’ solution is possible.
So it's not clear what your exact concerns are, what's your expectations, and how much of your goals are more a matter of other improvements like the funnel.

BTW, there is some new work on geodesic paths which seems much simpler then the previous methods. Maybe those ideas are useful for games too: https://nmwsharp.com/research/flip-geodesics/

JoeJ said:

I'm confused from your images, which illustrate the found path with shading the triangles. This implies you use the triangles as graph nodes, not the triangle vertices as you said. So maybe your visualization is not ideal and you can change it for better feedback on the algorithm. (Your results look all correct to me).

Ok, I see what you mean and where our miscommunication is. At the moment, I do not visualize an optimal path at all. Based on what I've been reading, the proper way to find the shortest path is to first find the corridor of polygons through which the optimal path will pass and then later running a funnel algorithm to create the actual shortest path within that corridor. That means that my shaded triangles is just trying to indicate the optimal corridor; it does not have any correlation with whether I am using triangles or vertices as graph nodes. I now understand why it looks correct to you and I understand @frob's blue paths a bit better. I'll explain more about this in a moment.

JoeJ said:

Red is vertices and edges, green is triangle centers and dual edges. But no matter what you use, it won't be a straight line ofc.

Based on my reading, I'm pretty sure that the green method is not guaranteed to find the shortest path. I understand that neither of these will result in a straight path.

JoeJ said:

Here's related confusion, coming from your animated gif:
Are the shaded triangles the path, or are they a reference visualization got from intersecting triangles with a straight line?
If it's the latter, the path (along vertices and edges) is not shown at all?

As mentioned above, shaded triangles are neither of these things. The shaded triangles should represent the corridor through which the shortest path will exist (and be found after a funnel algorithm). The fact that the shortest path should be a straight line is just an easy way to compare the actual shaded triangles to what they should be.

JoeJ said:

…but i doubt an ‘always perfect’ solution is possible…

So it's not clear what your exact concerns are, what's your expectations, and how much of your goals are more a matter of other improvements like the funnel.

First, I do expect that an optimal path should be able to be found. My goal is to find this optimal corridor and then use a funnel algorithm afterwards. My main problem is that I know that I'm finding the wrong corridor and I think that the given algorithm in the linked thesis should be finding the optimal corridor.

Now, to address using vertices vs triangles as nodes. I'll assume that you've looked at this single mentioned page of the linked thesis (which explains how to calculate g(x)), but I will try to rephrase the details. For A* to find the optimal path, I need to be able to measure the distance traveled so far. My nodes are a structure which is the triangle combined with the edge through which this triangle was entered. The thesis is choosing a maximum of three possible values to determine g(x). Note that the thesis is also considering that the character has some radius, so it not be able to pass directly up against a vertex of a constrained edge, but I am assuming character radius 0 at this point.

1. The first value is a straight line from the starting point to the closest point on the edge through which we entered this triangle.
2. The second value is the (parent node's g(x)) + (the distance to move though the parent triangle from its entry edge to the successor's entry edge). Since the character radius is 0 and these two edges will share a vertex, this distance is going to be 0. @frob, this means that your statement “It isn't possible to share a vertex, it MUST move along an edge” is not true.
3. The third value is the (parent node's g(x)) + (the difference between the current node's heuristic and the parent node's heuristic). I'm honestly having a bit of trouble understanding what this specifically represents and what the implications are. I'm suspicious of this part of my implementation of the algorithm.

Now, with these as the factors when trying to calculate the distance traveled, if value #1 is selected as the g(x) value, then it is clear that this “path” is expected to cross through some point of an edge that is not a vertex. I think this is similar for value #3, but again, I'm no so confident.

With all that being said, although my formal graph nodes are a combination of triangles, vertices, and edges, these aren't explicitly being used as nodes in the graph. They're used in combination to calculate the distance from start to the node based on the 3 values above.

JoeJ said:

BTW, there is some new work on geodesic paths which seems much simpler then the previous methods. Maybe those ideas are useful for games too: https://nmwsharp.com/research/flip-geodesics/​

Thanks for sharing this! This maybe seems like a type of string pulling/funnel algorithm? I didn't look in extreme detail yet, but I will.

SandSnip3r said:
Based on my reading, I'm pretty sure that the green method is not guaranteed to find the shortest path. I understand that neither of these will result in a straight path.

Um, no. There are surely differences depending on application, but in general both methods are exactly the same. I even use the same Dijkstra implementation for both cases, which gives me the same minimized cost paths. This paths can be the shortest if i set weights accordingly, but ofc. only in the given graph which has no sense about area in either case.
This just said to point out you should not rule out the ‘green method’, but i don't know which one games usually use for nav meshes (having only experience with geometry processing).

It's a bit misleading that i have drawn the green path segments to the midpoints of the edges they have crossed, but that's just for illustration - the algorithm and properties of results are equal. Here is a picture which shows a mesh and its dual. Vertices and faces change roles, edges remain but ‘rotate’. But any graph algorithm can process both variants.

SandSnip3r said:
The shaded triangles should represent the corridor through which the shortest path will exist (and be found after a funnel algorithm). The fact that the shortest path should be a straight line is just an easy way to compare the actual shaded triangles to what they should be.

I think there is a wrong assumption of yours, explaining it all…

You seemingly assume there is a guarantee that A* gives a result where the path touches the same triangles we would get from a intersection test. And this we could call an optimal path.
But that's not what path finding algorithms are doing. They ignore geometry and only minimize the edge cost we refer with edges.

You surely know this old problem, where both paths have equal cost and are thus optimal to an algorithm like Dijkstra, if we do not allow it to make diagonal moves in a grid:

Now, i assume A* gives the green line always because of its additional euclidean distance heuristic, but i'm sure we can easily construct a 2D mesh where it would fail to find all those optimally intersected triangles.

SandSnip3r said:
First, I do expect that an optimal path should be able to be found. My goal is to find this optimal corridor and then use a funnel algorithm afterwards. My main problem is that I know that I'm finding the wrong corridor and I think that the given algorithm in the linked thesis should be finding the optimal corridor.

Your plan should work, but if it's about corridors mainly, maybe using the polygons as graph nodes would be better. Because this way it's guaranteed those corridors are connected:

The green approach could not find this illegal path, because the dashed edge does not exist. (not really an argument, but maybe it's more intuitive this way.)

SandSnip3r said:
I'll assume that you've looked at this single mentioned page of the linked thesis

No - i know nothing about A* and would need to start with basics first. So i can not really help.

My nodes are a structure which is the triangle combined with the edge through which this triangle was entered.

But then you are already using triangles as nodes, not vertices. : )

Terminolgy is hard. E.g., in graph algorithms it's common to call nodes ‘vertices’ in any case, even if they come from triangles of a mesh.

My guess is the paper tries to get the best out of tweaking heuristics by looking at real geometry, which the graph itself does not know about. How much this is ‘optimal’ depends surely on definition of that term. For example, on a 3D mesh i can not use A* at all because euclidean distance can not describe the multiple local minima real geodesic distance has. To have fast path finding for complex game worlds, surely there's a of of trickery and extra data involved. One could for example parametrize the nav mesh to multiple separated domains to make A* work. That's a similar problem like making automatic UV charts for a mesh.