CoffeeScript implementation of A* algorithm

Question

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

Answer 1

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
  addNode = (node, src) ->
    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
    addNode start, null

    # 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
        addNode 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)