A_Star(Graph, StartNode, EndNode):
//all Graph nodes except StartNode are
//initialized with fScore and gScore of infinity
StartNode.fScore = 0
StartNode.gScore = 0
//pq - priority queue based on Node's f score
priorityQueue = {}
priorityQueue.push(StartNode)
while priorityQueue.size() > 0 do:
currentNode = priorityQueue.top()
priorityQueue.pop()
if currentNode == EndNode do:
path = {}
path.push(currentNode)
nextNode = currentNode->parent
while nextNode do:
path.push(nextNode)
nextNode = nextNode->parent
return path
for each neighbour of currentNode do:
gScore = currentNode.gScore + stepCost
if gScore < current gScore of neighbour do:
newNode = neighbour
newNode.gScore = gScore
newNode.fScore = h(neighbour) + gScore
newNode.parent = currentNode
priorityQueue.push(newNode)
The A* algorithm paths through an input graph from a starting node to an end node. At each step, it evaluates a function \(f(n) = h(n) + g(n)\)
Here, \(h(n)\) is a distance estimate from current node to the end node, often computed as Euclidean distance.
\(g(n)\) represents the cost to reach a given node from the start node.
The nodes with the lowest f-score will be explored first. The algorithm stops when the end node is reached or when the priority queue is empty.
Users can adjust parametrized cost functions to change the pathfinding output based on factors like terrain slopes or turning angles.
