Editing A* search algorithm (section)

===Pseudocode===
The following [[pseudocode]] describes the algorithm:

<syntaxhighlight lang="pascal" start="1">
function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the currently known cost of the cheapest path from start to n.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how cheap a path could be from start to finish if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure
</syntaxhighlight>

'''Remark:''' In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is [[admissible heuristic|admissible]] but not  [[Consistent heuristic|consistent]].   If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test ‘<code>tentative_gScore < gScore[neighbor]</code>’ will always fail if the node is reached again. The pseudocode implemented here is sometimes called the ''graph-search'' version of A*.<ref>{{Cite book|title=Artificial intelligence: A modern approach |last1=Russell |first1=Stuart J.|author-link1=Stuart J. Russell|date=2009|last2=Norvig|first2=Peter|author-link2=Peter Norvig|publisher=Pearson|isbn=978-0136042594|edition= 3rd|location=Boston|page=95}}</ref> This is in contrast with the version without the ‘<code>tentative_gScore < gScore[neighbor]</code>’ test to add nodes back to openSet, which is sometimes called the ''tree-search'' version of A* and require a consistent heuristic to guarantee optimality.

[[Image:Astar progress animation.gif|thumb|Illustration of A* search for finding path from a start node to a goal node in a [[robotics|robot]] [[motion planning]] problem. The empty circles represent the nodes in the ''open set'', i.e., those that remain to be explored, and the filled ones are in the closed set. Color on each closed node indicates the distance from the goal: the greener, the closer. One can first see the A* moving in a straight line in the direction of the goal, then when hitting the obstacle, it explores alternative routes through the nodes from the open set. {{see also|Dijkstra's algorithm}}]]