Prim's Algorithm in ClojureScript

Published Apr 5, 2014 in Front End

If you want to jump to the animation in its natural habitat, see it here. If you want to jump to the code: see the ClojureScript or JavaScript on GitHub.

After being interested in maze generation and after checking out the Wikipedia page, I thought it’d be cool to implement one in JavaScript. After that, it looked like a good opportunity to try porting some JavaScript to ClojureScript.

For the sake of brevity I’m leaving some of the more boilerplate functions out of this post. For the full code in each language, see the GitHub links above.

Von Neumann neighborhood

var vonNeumannNeighborhood = function(cell) {
  return [[-1, 0], [1, 0], [0, -1], [0, 1]].map(function(dir) {
    var y = cell[0] + dir[0];
    var x = cell[1] + dir[1];
    return [y, x];
  });
};

(defn von-neumann-neighborhood [coord]
  [(map
    (fn [dir]
      [(+ (first coord) (first dir)) (+ (last coord) (last dir))])
    [[-1 0] [1 0] [0 -1] [0 1]]))])

Opposite Cell

In Prim’s algorithm, on each turn we need to pick the opposite wall. The translation is pretty straightforward.

var oppositeCoord = function(from, to) {
  var yDiff = to[0] - from[0];
  var xDiff = to[1] - from[1];
  return [to[0] + yDiff, to[1] + xDiff];
};

(defn opposite-coord [from to]
  (let [yDiff (- (first to) (first from))
        xDiff (- (last to) (last from))]
    [(+ (first to) yDiff) (+ (last to) xDiff)]))

At coordinate

Frequently we need to see what’s at a certain coordinate in our graph data structure. Clojure’s get-in makes working with nested data structures ridiculously easy, since our coordinates (e.g. (y, x)) map directly to the nested data elements.

var at = function(coord) {
  return coord && graph[coord[0]] && graph[coord[0]][coord[1]];
};

(defn at [coord]
  (get-in @graph coord))

Place at coordinate

The opposite of our getter, at, above, place is our setter.

var place = function(coord, item) {
  graph[coord[0]][coord[1]] = item;
};

(defn place [coord item]
  (swap! graph assoc-in coord item))

requestAnimationFrame polyfill

Here we’re using an outer IIFE to cycle through and find the first built-in requestAnimationFrame that exists. If it falls through, we simply supply a regular setTimeout.

window.requestAnimFrame = (function(){
  return window.requestAnimationFrame       ||
         window.webkitRequestAnimationFrame ||
         window.mozRequestAnimationFrame    ||
         function(callback) {
           window.setTimeout(callback, 17);
         };
})();

(def request-animation-frame
  (or (.-requestAnimationFrame js/window)
      (.-webkitRequestAnimationFrame js/window)
      (.-mozRequestAnimationFrame js/window)
      (.-msRequestAnimationFrame js/window)
      (fn [callback] (js/setTimeout callback 17))))

jeffcarp

Software

Life