Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
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]) 
share|improve this question
    
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 at 2:19
    
Neither. I needed it for a client side puzzle game I wrote in HTML5 + AngularJs. –  wrick Feb 6 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 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 at 2:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.