a_star = # returns the goal node (or null if path not found). To reconstruct path follow the node.__src till null
(
start, # starting node
neighbors, # a function that takes in a node and returns list of neighbours
h, # admissable A* heuristic distance from goal i.e. heurisitic(x) <= distance(x,y) + heuristic(y) for all x,y
dist = (a,b) -> 1, # takes two nodes and returns distance between them (optional - default is 1)
isGoal = (x) -> h(x) is 0 # returns true iff node is goal (optional - assumes heurisitc(goal) = 0)
) ->
closed = {} # set of nodes already evaluated
q = {} # set of tentative nodes to be evaluated, the value is the 'f_score' (F = G + H)
g = [] # 'g-score' - the exact cost to reach this node from start
add = (node, parent) ->
node.__src = parent
g[node] = if parent? then g[parent] + dist parent, node else 0
q[node] = g[node] + h(node)
remove_best = ->
best = null
best = node for node,f of q when best is null or f < q[best]
if best? then closed[best] = true; delete q[best]
return best
add start, null
while true
c = remove_best()
if c is null or isGoal c then return c
add n, c for n in neighbours c when not closed[n] and (q[n] is null or g[c] + dist(c, n) <= g[n])
