A tail recursive implementation of A* search in Clojure (adopted from The Joy of Clojure)

astar.clj

(defn neighbours
  ([size node] (neighbours [[-1 0] [0 -1] [1 0] [0 1]] size node))
  ([deltas size node]
   (vec (filter (fn [n]
                  (every? #(< -1 % size) n))
                (map #(vec (map + node %)) deltas)))))

;; h(x)
(defn heuristic-estimate [step-cost size y x]
  (- (+ size size) y x 2))

;; g(x)
(defn path-cost [cell-cost cheapest-nbr]
  (+ cell-cost (:cost cheapest-nbr 0)))

;; cost function f(x) = g(x) + h(x)
(defn total-cost [path-cost step-cost size y x]
  (+ path-cost (heuristic-estimate step-cost size y x)))


(defn min-by [f coll]
  (when (seq coll)
    (reduce #(if (< (f %1) (f %2)) %1 %2) coll)))
  

(defn astar-search [node step-cost world]
  (let [size (count world)]
    (loop [routes (vec (replicate size (vec (replicate size nil))))
           queue  (sorted-set [0 node])]
      (if (empty? queue)
        (peek (peek routes))  ;; return [4 4]
        (let [[_ curr-node :as qitem] (first queue)
              rest-queue              (disj queue qitem)
              neighbours              (neighbours size curr-node)
              cheapest-nbr            (minby :cost (keep #(get-in routes %) neighbours))
              new-path-cost           (path-cost (get-in world curr-node) cheapest-nbr)
              old-path-cost           (:cost (get-in routes curr-node))]
          (if (and old-path-cost (>= new-path-cost old-path-cost))
            (recur routes rest-queue)
            (recur (assoc-in routes curr-node
                             {:cost new-path-cost
                              :nodes (conj (:nodes cheapest-nbr []) curr-node)})
                   (apply conj
                          rest-queue
                          (map (fn [node]
                               (let [[y x] node]
                                 [(total-cost new-path-cost step-cost size y x) node]))
                             neighbours)))))))))


(def world [[ 1   1   1   1    1]
            [999 999 999 999   1]
            [ 1   1   1   1    1]
            [ 1  999 999 999 999]
            [ 1   1   1   1    1]])


(astar-search [4 0] 900 world) 
;; {:cost 17, :nodes [[0 0] [0 1] [0 2] [0 3] [0 4] [1 4] [2 4] [2 3] [2 2] [2 1] [2 0] [3 0] [4 0] [4 1] [4 2] [4 3] [4 4]]}