-
-
Save dfcarpenter/8a51c06bf58170b1fa781cf7f7df1a7f to your computer and use it in GitHub Desktop.
Clojure implementation of the A* path finding algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; This is the Wikipedia entry example encoded graph. | |
(def graph {:orig [{:a 1.5 :d 2} 0] | |
:a [{:orig 1.5 :b 2} 4] | |
:b [{:a 2 :c 3} 2] | |
:c [{:b 3 :dest 4} 4] | |
:dest [{:c 4 :e 2} 0] | |
:e [{:dest 2 :d 3} 2] | |
:d [{:orig 2 :e 3} 4.5]}) | |
(defn a* [graph orig dest] | |
(letfn [(discover [node path visited] | |
(let [walkable (first (graph node)) | |
seen (map last (keys visited))] | |
(reduce dissoc walkable (conj seen (last path))))) | |
(walk [visited] | |
(let [[[score node :as current] [path total-distance]] (first visited)] | |
(if (= dest node) | |
(conj path dest) | |
(recur | |
(reduce-kv | |
(fn [m neighbour partial-distance] | |
(let [d (+ total-distance partial-distance) | |
score (+ d (last (graph neighbour)))] | |
(assoc m [score neighbour] [(conj path node) d]))) | |
(dissoc visited current) | |
(discover node path visited))))))] | |
(walk (sorted-map-by compare [0 orig] [[] 0])))) | |
(a* graph :orig :dest) | |
;; [:orig :d :e :dest] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment