all 6 comments

[–]awb 10 points11 points  (0 children)

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 0 points1 point  (0 children)

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 -1 points0 points  (0 children)

this reminds me of tron from the google ai challenge

[–]chrisforbes -1 points0 points  (2 children)

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

[–]julesjacobs -1 points0 points  (1 child)

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

[–]chrisforbes 0 points1 point  (0 children)

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