Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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: enter image description here

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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." –  hyn Feb 4 '11 at 10:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.