# Triangulation A* (TA*) pathfinding algorithm

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81.

He describes how to adapt the regular A* algorithm for triangulation, to search for other possibly more optimal paths, even after the final node is reached/expanded. Regular A* stops when the final node is expanded, but this is not always the best path when used in a triangulated graph. This is exactly the problem I'm having.

The problem is illustrated on page 78, Figure 5.4: I understand how to calculate the g and h values presented in the paper (page 80).

And I think the search stop condition is:

if (currentNode.fCost > shortestDistanceFound)
{
// stop
break;
}


where currentNode is the search node popped from the open list (priority queue), which has the lowest f-score. shortestDistanceFound is the actual distance of the shortest path found so far.

But how do I exclude the previously found paths from future searches? Because if I do the search again, it will obviously find the same path. Do I reset the closed list? I need to modify something, but I don't know what it is I need to change. The paper lacks pseudocode, so that would be helpful.

I haven't implemented this, but as I read it, I think you'd do something like this:

shortestDistance = infinity
do A* with modified g cost
if node.fCost > shortestDistance (section 5.5)
don't open node
if node.isGoal()
run funnel algorithm (string pulling)
update shortestDistance


The difference is that even if you find a path to the goal, it's not necessarily the shortest path. But you'll keep improving the upper bounds on the shortest path, meaning that you won't have to open all nodes. Eventually your open set should be empty, and the best path you've found so far should be the shortest.

The modified g cost that he describes seems like a big underestimate, so I'm skeptical about how well it works in practice.

• Hmm, I could be wrong, but I am interpreting that as the stopping condition rather than the condition for adding to the open list. The following sounds like the condition for adding to the open list: "As a side note, a child of a search state will not be generated for a particular adjacent triangle if a state corresponding to that triangle is already an ancestor of that state. This exclusion can be done because it will never eliminate an optimal path, only one that could become shorter by removing part of it, as stated in Theorem 4.3.4." – Morrowless Feb 4 '11 at 10:47