title: Performance of an A* search implemented in Clojure
body: <p>I have implemented an <a href="http://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">A* search algorithm</a> for finding a <em>shortest</em> path between two states. 
  Algorithm uses a hash-map for storing best known distances for visited states. And one hash-map for storing child-parent relationships needed for reconstruction of the shortest path.</p>
  
  <p><a href="http://bitbucket.org/joecamel/ai-lab/src/e89eb7880ffd/heightmap/heightmap.clj#cl-51" rel="nofollow noreferrer">Here</a> is the code. Implementation of the algorithm is generic (states only need to be "hashable" and "comparable") but in this particular case states are pairs (vectors) of ints <code>[x y]</code> and they represent one cell in a given heightmap (<a href="http://bitbucket.org/joecamel/ai-lab/src/e89eb7880ffd/heightmap/heightmap.clj#cl-35" rel="nofollow noreferrer">cost</a> for jumping to <a href="http://bitbucket.org/joecamel/ai-lab/src/e89eb7880ffd/heightmap/heightmap.clj#cl-44" rel="nofollow noreferrer">neighboring cell</a> depends on the difference in heights). </p>
  
  <p>Question is whether it's possible to improve performance and how? Maybe by using some features from 1.2 or future versions, by changing logic of the algorithm implementation (e.g. using different way to store path) or changing state representation in this particular case?</p>
  
  <p><a href="http://bitbucket.org/joecamel/ai-lab/src/e89eb7880ffd/heightmap/java/src/ai/heightmap/Search.java#cl-47" rel="nofollow noreferrer">Java implementation</a> runs in an instant for <a href="http://bitbucket.org/joecamel/ai-lab/src/e89eb7880ffd/heightmap/map.in" rel="nofollow noreferrer">this map</a> and Clojure implementation takes about 40 seconds. Of course, there are some natural and obvious reasons for this: dynamic typing, persistent data structures, unnecessary (un)boxing of primitive types...</p>
  
  <p>Using transients didn't make much difference.</p>