2 views

Is the A* pathfinding 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)

{

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

{

// 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 neighbors 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;

}

by (108k points)

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 are not good enough, A* does practically the same as Dijkstra.

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

The thing that most people miss is that the heuristic algorithm must underestimate the cost of traversal to the final solution which is known as admissible. As long as the heuristic is admissible, it will find the shortest path.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence(AI) Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.