A* in Clojure

unsorted — cgrand, 4 September 2010 @ 4 h 22 min

Thanks to Mark Engelberg there’s now a nice priority map in contrib. With such a facility, it becomes really easy to write a nice implementation of the A* algorithm.

(ns net.cgrand.clj-me.a-star
  (:use [clojure.contrib.priority-map :only [priority-map]]))

(defn A*
 "Finds a path between start and goal inside the graph described by edges
  (a map of edge to distance); estimate is an heuristic for the actual
  distance. Accepts a named option: :monotonic (default to true).
  Returns the path if found or nil."
 [edges estimate start goal & {mono :monotonic :or {mono true}}]
  (let [f (memoize #(estimate % goal)) ; unsure the memoization is worthy
        neighbours (reduce (fn [m [a b]] (assoc m a (conj (m a #{}) b)))
                      {} (keys edges))]
    (loop [q (priority-map start (f start))
           preds {}
           shortest {start 0}
           done #{}]
      (when-let [[x hx] (peek q)]
        (if (= goal x)
          (reverse (take-while identity (iterate preds goal)))
          (let [dx (- hx (f x))
                bn (for [n (remove done (neighbours x))
                         :let [hn (+ dx (edges [x n]) (f n))
                               sn (shortest n Double/POSITIVE_INFINITY)]
                         :when (< hn sn)]
                     [n hn])]
            (recur (into (pop q) bn)
              (into preds (for [[n] bn] [n x]))
              (into shortest bn)
              (if mono (conj done x) done))))))))

Example:

(defn euclidian-distance [a b] ; multidimensional
  (Math/sqrt (reduce + (map #(let [c (- %1 %2)] (* c c)) a b))))

;; generate a grid graph whose outlying edges are one-way
(defn grid [x y w h]
  (into {}
    (for [i (range w) j (range h)
          :let [x0 (+ x i) y0 (+ y j) x1 (inc x0) y1 (inc y0)]]
      {[[x0 y0] [x1 y0]] 1
       [[x1 y0] [x1 y1]] 1
       [[x1 y1] [x0 y1]] 1
       [[x0 y1] [x0 y0]] 1})))

(def g (apply dissoc (grid 0 0 4 4) (keys (grid 1 1 2 2))))

(comment 
user=> (A* g euclidian-distance [0 3] [4 2])
([0 3] [1 3] [2 3] [3 3] [3 2] [4 2])
)

Shameless plug: if you are in Europe and want to learn Clojure, don’t forget to register for the Frankfurt course, October 26-28.

13 Comments »

  1. Hey, I have generic AI search (including A*) in clojure (http://github.com/aria42/mochi/blob/master/src/mochi/search.clj)
    and it was using java.util.PriorityQueue, clojure.contrib.priority-map would be much better.

    Comment by Aria Haghighi — 4 September 2010 @ 5 h 42 min
  2. This appears to be not A* but a simplified algorithm which assumes that your heuristic is monotonic.

    Comment by foo — 5 September 2010 @ 23 h 17 min
  3. @foo I may have commited an oversight in implementing A* so I’d really like to hear more from you. However note that the closed set is augmented (monotonic A*) only when the option :monotonic is set to true.

    Comment by cgrand — 6 September 2010 @ 10 h 04 min
  4. it’s still moonspeak.

    Comment by ghlugh — 7 September 2010 @ 7 h 36 min
  5. [...] may also be interesting to compare this a* search function to that of cgrande’s. a* algorithm, dijkstra's algorithm, [...]

  6. Thanks for the nice example. I couple of minor comments:
    The Math/sqrt is kinda slow and seems unnecessary in Eucl-dist; and if all the costs were integers, one could avoid Math/sqrt and replace the Double constant in A* with a Long (cheaper comparisons?).
    The memoize is indeed worthy (question you posed above) as lookups of the same node may be done multiple times (node x may be rejected once but selected at a later time). I wonder though whether memoize is a better choice than sticking values into a regular hash-map.(?)

    Comment by Vish — 30 January 2012 @ 22 h 57 min
  7. Hi,
    Thanks for your post, insightful as usual ☺.

    Just passing by, I wondered if you had considered using cheplist [*].

    Best Regards,

    B.

    [*]http://nakkaya.com/2011/10/10/cheaplist-in-clojure/

    Comment by bernard — 7 March 2013 @ 18 h 09 min
  8. @Bernard, no I haven’t, merci pour le pointeur.

    Comment by cgrand — 8 March 2013 @ 14 h 15 min
  9. This is brilliant and beautiful!

    My favorite part is the code to trace back through the preds to recover the path: (reverse (take-while identity (iterate preds goal))) … what could be more succinct?

    Comment by clojure newb — 22 December 2014 @ 8 h 52 min
  10. These usually consist of a sizeable array of emotional,
    social and attitudinal variables. The concept
    of Total Asset Management come into play as building owners start to focus on not only the development cost of a building but also the cost to
    maintain the building throughout the building life cycle.
    IT consulting Canberra companies stand beside IT infrastructure and
    business organizations to help them in finding the
    best candidate for their jobs.

    Comment by Facilities Recruitment — 10 February 2015 @ 18 h 12 min
  11. The root cause of the problem was that the union negotiators could not strike up a collective bargaining
    agreement that could protect the baseball players from the shrewd
    manipulations of the team owners. At the rear of the cave may
    be a Toktz-Ket-Dill (level 100), who’s armor you initially ought to break edge tool before you’ll deal
    harm. Counter MVP – Kill the #1 player on the enemy team ten times in a
    single match.

    Comment by csgo skins Jackpot — 28 November 2015 @ 4 h 13 min
  12. Rattling fantastic information can be found on weblog. I believe in nothing, everything is sacred. I believe in everything, nothing is sacred. by Tom Robbins.

    Comment by suba suba — 11 June 2020 @ 12 h 32 min
  13. Appreciate your effort to bring light to this subject.

    Comment by Khalid Negm — 24 June 2024 @ 13 h 01 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2024 Clojure and me | powered by WordPress with Barecity