A* PathFinder algorithm

A*

Given a graph G(V,A), a Vs start vertex and a Vg goal vertex, the A* algorithm returns a smallest path from Vs to Vg.

Logic

First, we need two groups to differentiate the vertex at V, the evaluated and toEvaluate groups. We need to define fromStartDistance, possibleDistance and cameFrom for each vertex.

1. fromStartDistance: is the actual distance from Vs to this vertex.
2. possibleDistance: is the fromStartDistance + the distance in straight line to Vg.
3. cameFrom: is the predecessor of this vertex in the path.

While toEvaluate group is not empty,

take the vertex Vx that have the smallest possibleDistance

if (Vx is goal) found a path! Take path from cameFrom vector

remove Vx from toEvaluate

insert Vx in evaluated

and evaluate Vx.

Evaluating

Get all this vertex neighbors

Define tentativeFromStartDistance = fromStartDistance[current] + distance[current,neighbor]

Define tentativePossibleDistance = tentativeFromStartDistance + possibleDistance[neighbor]

if (neighbor is in Evaluated and tentativePossibleDistance >= possibleDistance[neighbor]) go to next neighbor

if (neighbor is not toEvaluated or tentativePossibleDistance < possibleDistance[neighbor])

cameFrom[neighbor] = current

possibleDistance[neighbor] = tentativePossibleDistance

fromStartDistance[neighbor] = tentativeFromStartDistance

if(neighbor is not in toEvaluate) insert neighbor in toEvaluate