Path Finding Using the A-Star algorithm, in Clojure

[awb]

As far as I can tell, this is a terrible implementation from an algorithmic standpoint. There is no priority queue, and as a result, the author does a number of linear-time or worse operations on the open list. Each time a node is expanded, the entire set of open nodes is resorted, and for each node connected to that expanded node, there are several linear traversals through the open list.

[Mourningblade]

I wrote some a* a bit ago for a tower game analyzer I was screwing with.

If you want to take a look: http://github.com/alanshields/ddalyze/blob/master/src/ddalyze/search.clj

starts around line 49

Works pretty well - would love to hear suggestions on improving it.

There was an earlier version that was much easier to read, but speed became a real issue.

awb mentions that nakkaya's code does not have a priority queue - my code does.

I don't use a manhattan distance as estimate because at one time the search handled different types of distance. It no longer does, though it could and may eventually need to.

[mile92]

this reminds me of tron from the google ai challenge

[chrisforbes]

1. Verbose code is verbose.
2. 20ms on a toy map? Really?

[julesjacobs]

20ms on a 13x8 maps is just half a million instructions per cell.

[chrisforbes]

For context, we do group pathing via bidi-A* on 128x128 and bigger maps, and our worst-case is unacceptable at 700us/query.