Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active December 16, 2019 04:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericnormand/c029a7ef7324a4d36923a7becf8fef11 to your computer and use it in GitHub Desktop.
Save ericnormand/c029a7ef7324a4d36923a7becf8fef11 to your computer and use it in GitHub Desktop.

A-Star Algorithm

A neat algorithm for finding a short path through a graph is A-Star. It's used in a lot of games for the characters to find paths through a map.

One thing that's fun about this algorithm is that it's traditionally formulated in terms of mutable data structures. What would this look like as a functional implementation?

Your task is to implement A-Star in Clojure. You can use mutable state if you want! The Wikipedia page has a good description of the algorithm.

(defn repath [came-from current]
(loop [current current
path (list current)]
(if (contains? came-from current)
(recur (get came-from current) (conj path (get came-from current)))
path)))
;; neigh is Node -> #{Node}
(defn a* [neigh start goal h]
(loop [current start
open #{}
came-from {}
gscore {start 0}
fscore {start (h start goal)}
neighbors (neigh start)]
(cond
(= current goal)
(repath came-from current)
(not (empty? neighbors))
(let [n (first neighbors)
tg (+ (get gscore current)
1)]
(if (< tg (get gscore n Long/MAX_VALUE))
(recur current
(conj open n)
(assoc came-from n current)
(assoc gscore n tg)
(assoc fscore n (+ tg (h n goal)))
(rest neighbors))
(recur current
open
came-from
gscore
fscore
(rest neighbors))))
(not (empty? open))
(let [current (apply min-key #(get fscore % Long/MAX_VALUE) open)]
(recur current
(disj open current)
came-from
gscore
fscore
(neigh current)))
:else
:fail!)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment