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])
|
||||
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.
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
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.
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.
Breaking the operations in to related sections makes it easier to follow.
Naming functions with verbs and naming functions that return booleans with
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.
The big loop that does all the work would be clearer if you could quickly see
what situation would trigger the loop ending.
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.
|
|||
|
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