A* pathfinding guaranteed to find shortest path?

Is the A* path finding algorithm guaranteed to find the shortest path 100% or the time, if implemented correctly?

int Graph::FindPath(Node *start, Node *finish, list< vec2f > &path)
{
    list<NodeRecord*> open;
    list<NodeRecord*> closed;
    list<NodeRecord*>::iterator openIt;
    list<NodeRecord*>::iterator closedIt;

    // add the starting node to the open list
    open.push_back( new NodeRecord(start, NULL, 0.0f, 0.0f + start->pos.DistanceSq(finish->pos) ) );
  // NodeRecord(Node *node, Node *from, float cost, float totalCost)

    while(!open.empty())
    {
        // find the node record with the lowest cost
        NodeRecord *currentRecord = open.front();
        openIt = ++open.begin();

        while(openIt != open.end())
        {
            if((*openIt)->total < currentRecord->total)
                currentRecord = (*openIt);

            openIt++;
        }

        // get a pointer to the current node
        Node *currentNode = currentRecord->node;

        // if the current node is the finish point
        if(currentNode == finish)
        {
            // add the finish node
            path.push_front(currentNode->pos);

            // add all the from nodes
            Node *from = currentRecord->from;

            while(!closed.empty())
            {
                // if this node record is where the path came from,
                if(closed.back()->node == from) //&& closed.back()->from != NULL
                {
                  开发者_如何学JAVA  // add it to the path
                    path.push_front( from->pos );

                    // get the next 'from' node
                    from = closed.back()->from;
                }

                // delete the node record
                delete closed.back();
                closed.pop_back();
            }

            while(! open.empty() )
            {
                delete open.back();
                open.pop_back();
            }

            // a path was found
            return 0;
        }

        // cycle through all neighbours of the current node

        bool isClosed, isOpen;

        for(int i = 0; i < (int)currentNode->neighbours.size(); i++)
        {
            // check if neigbour is on the closed list
            isClosed = false;
            closedIt = closed.begin();
            while(closedIt != closed.end())
            {
                if(currentNode->neighbours[i] == (*closedIt)->node)
                {
                    isClosed = true;
                    break;
                }

                closedIt++;
            }

            // skip if already on the closed list
            if(isClosed == true)
                continue;

            float cost = currentRecord->cost + currentNode->distance[i];
            float totalCost = cost + currentNode->neighbours[i]->pos.DistanceSq(finish->pos);

            // check if this neighbour is already on the open list
            isOpen = false;
            openIt = open.begin();
            while(openIt != open.end())
            {
                if(currentNode->neighbours[i] == (*openIt)->node)
                {
                    // node was found on the open list
                    if(totalCost < (*openIt)->total)
                    {
                        // node on open list was updated
                        (*openIt)->cost = cost;
                        (*openIt)->total = totalCost;
                        (*openIt)->from = currentNode;
                    }

                    isOpen = true;
                    break;
                }

                openIt++;

            }

            // skip if already on the open list
            if(isOpen == true)
                continue;

            // add to the open list
            open.push_back( new NodeRecord(currentNode->neighbours[i], currentNode, cost, totalCost) );
        }

        // move the current node to the closed list after it has been evaluated
        closed.push_back( currentRecord );
        open.remove( currentRecord );
    }

    // free any nodes left on the closed list
    while(! closed.empty() )
    {
        delete closed.back();
        closed.pop_back();
    }

    // no path was found
    return -1;
}

---

Yes (but I haven't looked deeply at your implementation).

The thing that most people miss is that the heuristic algorithm MUST underestimate the cost of traversal to the final solution (this is called "admissible"). It is also good (but not absolutely required) for the heuristic to monotonically approach the solution (this is called "consistent")

---

Anyway, at my glance at your code, you probably should use std::set for your closed list and std::deque for your open one so that your searches and insertion in these two lists aren't O(n). You also shouldn't make new NodeRecords, since it gives you a level of indirection with no benefit (and your algorithm will leak memory if an exception is thrown).

---

According to Wikipedia, A* uses heuristics for faster finding shortest path, but actually it is a modification of Dijkstra's shortest path algorithm, and if the heuristics is not good enough, A* does practically the same as Dijkstra.

So yes, it is guaranteed that A* finds the shortest path.

---

Interestingly, while admissible heuristics provide the optimal solution 100% of the time, they can be slow in certain situations. If there are several paths which are roughly the same total distance, an inadmissible heuristic will provide faster "decision-making" between the relatively equivalent paths. Note that you must use a closed list (which you did) for this to work.

In fact, Pearl in his book "Heuristics" proves that if your heuristic overestimates by a small amount, the solution provided will only be longer than the optimal by that same amount (at most)!

For certain fast/real-time applications, this can be a real help to boost speed, at a small cost to the solution quality.