Return to Question

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 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 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 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.