I'm learning Clojure and I'm interested in areas that could be more idiomatic. The main function is below. If you're interested in the whole lib, check out this.
The function operates on a grid
, which contains a finite number of cells
. A cell is a single point in a grid. neighbours-of
will get information about moving one step away from a given cell. The info is in the form of a set of neighbouring cells, and a map giving the cost of moving to a given neighbour.
The loop vars are open-nodes
, which is a sorted list of cell/cost pairs, visited-cells
, which is a set of cells we don't want to look at again, and parents
, which is a map giving the parent of a given cell.
parents
is used in create-route
to produce a path as a list of cells.
It doesn't currently handle the no-route case, nor is it very optimal. I'm not worried about the first, but if you have hints on the latter then that would be great (that order-by is probably a hotspot for large grids). Mostly I'm interested in what is and is not idiomatic.
(defn navigate-to [grid start dest]
"provides route from start to dest, not including start"
(validate-cell grid start)
(validate-cell grid dest)
(loop [[{current-cell :cell current-cost :cost} & open-nodes] (list (traversal 0 start))
visited-cells #{}
parents {}]
(if (= dest current-cell)
(create-route parents current-cell)
(let [;; traversals is list of {:cell :cost}
{all-neighbours :neighbours traversals :traversals} (neighbours-of
grid
current-cell)
unvisited-neighbours (set/difference all-neighbours visited-cells)
;; add current route cost to traversals:
neighbour-total-distances (into {}
(for [[neighbour cost] traversals]
[neighbour (+ current-cost cost)]))
;; keep bigger distances
;; ...first merge in seen neighbours, keeping higher values
better-neighbours (->> open-nodes
(filter
(fn [{open-cell :cell current-cost :cost :as open-node}]
(and (contains? unvisited-neighbours open-cell)
(> current-cost
(neighbour-total-distances open-cell)))))
(map #(% :cell))
set)
updated-open (map (fn [{open-cell :cell current-cost :cost :as open-node}]
(if (contains? better-neighbours open-cell)
(traversal (neighbour-total-distances open-cell) open-cell)
open-node))
open-nodes)
updated-parents (reduce #(assoc %1 %2 current-cell) {} better-neighbours)
;; ...then create new neighbours
all-open-cells (set (map #(% :cell) open-nodes))
new-neighbours (set/difference unvisited-neighbours all-open-cells)
new-open-nodes (map #(traversal (neighbour-total-distances %) %) new-neighbours)
new-parents (reduce #(assoc %1 %2 current-cell) {} new-neighbours)]
(recur (sort-by :cost (concat updated-open new-open-nodes))
(conj visited-cells current-cell)
(merge parents updated-parents new-parents))))))
start = goal
). \$\endgroup\$ – coderodde Jan 4 '16 at 11:08