A* Search Algorithm Visualization

A* Search Algorithm Visualization.clj

(def grid-size 30)

;; A collection of walls 
(def walls (atom #{}))

;; The route to the finish
(def route (atom #{}))

(defstruct point :x :y)

(defn make-cost-and-goal-fn 
  "Make a goal function so the point reaches the goal"
  [x y]
  [(fn [g]
     (let [dx (- x (:x g)) dy (- y (:y g))]
       (Math/sqrt (+ (* dx dx) (* dy dy)))))
   (fn [g]
     (and (= (:x g) x)
	  (= (:y g) y)))])

(defn make-point [x y] (struct point x y))

(defn make-successors-fn
  "Make a successors function with chance of a surrounding wall"
  [wall-locations]
  (fn [p]
    (let [neighbours #{[1 0] [-1 0] [0 1] [0 -1]}]
      (set
       (remove 
	(fn [pt]
	  (or (< (:x pt) 0)
	      (< (:y pt) 0)
	      (>= (:x pt) grid-size)
	      (>= (:y pt) grid-size)
	      (wall-locations [(:x pt) (:y pt)])))
	(map 
	 (fn [[x y]] (make-point (+ x (:x p)) (+ y (:y p))))
	 neighbours))))))

(defn get-points-on
  "Get the points on the path"
  [solution]
  (let [s (:state solution)
	p (:previous solution)]
    (when-not (nil? p)
      (lazy-seq 
      (cons
       [(:x s) (:y s)]
       (get-points-on p))))))

(defn set-route-from
  "Set the route"
  [solution]
  (swap! route (constantly (set (get-points-on solution)))))

(def canvas 
     (proxy [JPanel] [] 
       (paintComponent 
	[g]
     (proxy-super paintComponent g)
     (let [sq-size (/ (min (.getHeight this) (.getWidth this)) grid-size)]
       (doseq [x (range 0 grid-size)]
	 (doseq [y (range 0 grid-size)]
	   (cond 
	     (= [0 0] [x y]) (.setColor g Color/GREEN)
	     (= [(dec grid-size) (dec grid-size)] [x y]) (.setColor g Color/RED)
	     (@walls [x y]) (.setColor g Color/BLACK)
	     (@route [x y]) (.setColor g Color/PINK)
	     :else (.setColor g Color/BLUE))
	   (doto g
	     (.fillRect (* x sq-size) (* y sq-size) (dec sq-size) (dec sq-size)))))))))

(defn visualize
  []
  "A quick and dirty visualization of A* search on a 100 x 100 grid"
  (let [frame (JFrame. "A* Search Algorithm Visualization")
	[costf goal?] (make-cost-and-goal-fn 50 50)]
    (doto canvas
      (.addMouseListener 
       (proxy [MouseAdapter] []
	 (mouseClicked 
	  [e]
	  (if (= (MouseEvent/BUTTON1) (.getButton e))
	    (let [sq-size (/ (min (.getHeight canvas) (.getWidth canvas)) grid-size)
		  x (int (/ (.getX e) sq-size))
		  y (int (/ (.getY e) sq-size))]
	      (swap! walls (fn [walls] 
			     (if (walls [x y])
			       (disj walls [x y])
			       (conj walls [x y]))))
	      (.repaint canvas))
	    (let [[cost-fn goal?] (make-cost-and-goal-fn (dec grid-size) (dec grid-size))
		  solution (a*-search 
			    (list (make-path (make-point 0 0) nil 0 0))
			    goal?
			    (make-successors-fn @walls)
			    (constantly 1) ;; cost per unit is 1
			    cost-fn)]
	      (set-route-from solution)
	      (.repaint canvas)))))))
    (doto frame
      (.add canvas)
      (.setSize 600 600)
      (.setResizable true)
      (.setVisible true))))