A*

priorityqueue	Open
list	Closed
AStarSearch
s.g = 0	// s is the start node
s.h = GoalDistEstimate( s )
s.f = s.g + s.h
s.parent = null
push s on Open
while Open is not empty
pop node n from Open // n has the lowest f
if n is a goal node
construct path
return success
for each successor n' of n
newg = n.g + cost(n,n')
if n' is in Open or Closed,
and n'.g <= newg
skip
n'.parent = n
n'.g = newg
n'.h = GoalDistEstimate( n' )
n'.f = n'.g + n'.h
if n' is in Closed
remove it from Closed
if n' is not yet in Open
push n' on Open
push n onto Closed
return failure // if no path found