# CoffeeScript implementation of A* algorithm

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

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

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])

-
Out of curiosity, in what context are you implementing an A* algorithme in coffeescript? Note that "for fun" or "to learn" are 2 good answers. – jackdbernier Feb 6 '14 at 2:19
Neither. I needed it for a client side puzzle game I wrote in HTML5 + AngularJs. – pathikrit Feb 6 '14 at 2:27
I see... I was thinking that javascript is not a the best fit for this kind of task but in the browser you have pretty much 2 options. Javascript or calling an api. Note that actionscript is not mentioned ;) – jackdbernier Feb 6 '14 at 2:47
I have to say that 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]) is quite long and does a lot of things for a single line. I feel like you are performing A* in one line. – jackdbernier Feb 6 '14 at 2:49

I am not an expert on the A* algorithm. I'm suggesting changes based on the Rules of Clarity, Simplicity, and Economy and the code you provided, not on an extensive knowlege of graph traversal methods.

Extensive documentation inline is tricky to read. Consider using a standardized docstring format like those in docco or codo for detailed inline docs.

###
returns the goal node or null if path not found. Reconstruct path by
following the goalNode.src until null

@param [Object] start The node to start searching from
@param [Object] options The options object

@option [Function] neighbors Takes node, returns array of neighbors
@option [Function] heuristic Takes node, returns A* heuristic
@option [Function] isGoal Takes node, returns true if node is goal
@option [Function] distance Takes two nodes returns distance between them

@returns {Object} Returns the goal node with a tracable path to the start
###


It's not clear which options you expect you be left as their default values most frequently. If most options will be left as defaults most of the time, and the function will "just work" without configuration, use an options object and set sensible defaults.

aStar = (start, opts = {}) ->
opts.neighbors or= (node) -> []
opts.heuristic or= (node) -> 0
opts.isGoal    or= (node) -> opts.heuristic(node) is 0
opts.distance  or= (a, b) -> 1


If you want to find paths from many start points, you might setup your function once and allow several calls, each providing a start point.

AStar = (opts = {}) ->
opts.distance  or= (a, b) -> 1
# ... and other defaults

(start) ->
# logic for calculating path from "start"

# use it like this
astar = AStar
isGoal: -> yes
neighbors: -> [1, 2, 3]

# goal is the destination node (as it was in the original logic)
goal = astar {x: 1, y: 2}


Inside the logic function, remember that "Clarity is better than cleverness". Slightly longer, but much more descriptive names go a long way to making the operations easier to understand.

(start) ->
closed = {} # nodes already evaluated
nodes  = {} # key: node to be evaluated, value: f-score (F = G + H)
gscore = [] # the exact cost to reach this node from start


Breaking the operations in to related sections makes it easier to follow.

  # constructing path
node.src = src
gscore[node] = if src? then gscore[src] + opts.distance src, node else 0
nodes[node] = gscore[node] + opts.heuristic(node)


Naming functions with verbs and naming functions that return booleans with is and has usually increases clarity. Verbs do things, so do functions. You want the behavior of your code to be unsurprising to the person reading it.

  # selecting best path
isBetter = (a, b) ->
a is null or b < nodes[a]

selectBest = (best = null) ->
best = node for node, fscore of nodes when isBetter(best, fscore)
closed[best] = yes if best?
delete nodes[best]
best


Break complex boolean questions into parts so the reader (which is also you, later) can follow (with a minimal cognitive load) what you intend to be determining with your comparisons.

  # answers about current node
isOpen = (node) ->
not closed[node]

isShorter = (a, b) ->
nodes[a] is null or gscore[b] + opts.distance(a, b) <= gscore[a]

isAvailable = (neighbor, node) ->
isOpen(neighbor) and isShorter(neighbor, node)


The big loop that does all the work would be clearer if you could quickly see what situation would trigger the loop ending. while true is less communicative than doneSearching.

  findGoal = (start) ->
# insert start point

# store the node in use
node = null

doneSearching = ->
node = selectBest()
return yes if node is null or opts.isGoal node
no

# find the shortest path in the current open set
# stop looking when out of options or at the goal
until doneSearching()
for neighbor in getNeighbors node when isAvailable neighbor, node
node


Everything up to here defines the operations that will be used. This is the single point that triggers action in this function. Reducing the number of moving parts makes tracing the logic path easier.

  findGoal(start)

-