A Quadtree is a tree data structure, which is useful for giving more focus/detail to certain regions of your data, while saving resources elsewhere. I could only find a couple tutorials/guides and both were imperative, so I figured it'd be fun to do a functional version in Clojure which runs in the browser.

A demo

In this blogpost I'll show you how to build both a functional Quadtree and the visualization you see below. Imagine the canvas to be a top-view of map and your mouse-position to be the spot you're occupying on the map. Near you, you want crisp details, small cells of high resolution. The further away we get from you/the camera (your mouse-position), the less we care about details.

Be aware that on mobile, you have to click at the spot you want to simulate the cameras position. I recommend you view this on a desktop system with a mouse, where the simulation reacts to the mouse position in real time.

The recursive approach

It's hard to find any tutorials on how to build a general purpose Quadtree, but the 2 I did find both took the imperative approach, ie. editing directly on each node. Nothing wrong with that approach, it can be blazingly fast but it does leave you with the housekeeping, ie. downscaling nodes that are no longer close to the camera. I'd much prefer a declarative definition that rebuilds the entire tree in sub-milliseconds, so let's make that happen.

In this implementation, I want to show a very general functional approach and goes like this:

1. Read a camera (player,mouse,focus-point,whatever) position
2. Test if the current node is optimally sized
3. If not, split into 4 children, goto 2

Optimally sized in this case is just "Am I too far away from the edge of the node" ? If the distance is greater than some threshold, let's say the width of the node, then we split.

Our data model

Depending on your use-case, you can fit as much information as you want into this model. If you're doing some kind of 3D rendering, you might want to keep tabs on neighbor-relations, LOD steps and such, but for the basic tree structure, you just need this:

(defn qtree
  " Instantiates a tree node "
  [[x1 y1 x2 y2]]
  {:root?   false
   :bounds  [x1 y1 x2 y2]
   :center  (mapv #(js/Math.floor %)
                  [(half x2 x1)
                   (half y2 y1)])
   :width   (- x2 x1)})

In fact we strictly speaking, don't need the center/width stored, but it does make life a bit easier.

Given a root node and a camera-position we can determine if we want to split or not, simply by testing the distance from the camera to the center:

(defn distance
  [[x1 y1] [x2 y2]]
  (js/Math.sqrt
   (+ (js/Math.pow (- x2 x1) 2)
      (js/Math.pow (- y2 y1) 2))))

(defn too-close?
  " Determines if the camera is closer than halfway to
    the edge of a node "
  [ node camera ]
  (< (distance camera (:center node))
     (:width node)))

(defn split?
  [ node camera ]
  (and (too-close? node camera)
       (> (:width node) _Q_MINIMUM_SIZE)))

That final check on the width of the node, essentially allow us to recurse until we can't split anymore. In Clojure we have 2 very powerful idioms for walking a tree structure: Postwalk and Prewalk.

Postwalk is a depth-first, post-order walk of the tree which applies some arbitrary function to each element.

(w/postwalk (fn [e]
                (prn "Looking at: " e)
                e)
            {:rootval 1
            :node1 {:data "foo"
            :vec  [1 2 3]}})
"Looking at: " :rootval
"Looking at: " 1
"Looking at: " [:rootval 1]
"Looking at: " :node1
"Looking at: " :data
"Looking at: " "foo"
"Looking at: " [:data "foo"]
"Looking at: " :vec
"Looking at: " 1
"Looking at: " 2
"Looking at: " 3
"Looking at: " [1 2 3]
"Looking at: " [:vec [1 2 3]]
"Looking at: " {:data "foo", :vec [1 2 3]}
"Looking at: " [:node1 {:data "foo", :vec [1 2 3]}]
"Looking at: " {:rootval 1, :node1 {:data "foo", :vec [1 2 3]}}
{:rootval 1, :node1 {:data "foo", :vec [1 2 3]}}

I hope this is an intuitive way to see the path postwalk takes. The function only prints what it sees and then returns it as is, thus the end result is exactly the map we started out with. Notice how we first see the root key, then its value, then both together as a MapEntry, then it goes deeper into the tree.

Now compare that with prewalk:

(w/prewalk (fn [e]
               (prn "Looking at: " e)
               e)
           {:rootval 1
           :node1 {:data "foo"
           :vec  [1 2 3]}})
"Looking at: " {:rootval 1, :node1 {:data "foo", :vec [1 2 3]}}
"Looking at: " [:rootval 1]
"Looking at: " :rootval
"Looking at: " 1
"Looking at: " [:node1 {:data "foo", :vec [1 2 3]}]
"Looking at: " :node1
"Looking at: " {:data "foo", :vec [1 2 3]}
"Looking at: " [:data "foo"]
"Looking at: " :data
"Looking at: " "foo"
"Looking at: " [:vec [1 2 3]]
"Looking at: " :vec
"Looking at: " [1 2 3]
"Looking at: " 1
"Looking at: " 2
"Looking at: " 3
{:rootval 1, :node1 {:data "foo", :vec [1 2 3]}}

Prewalk examines the same elements and in the same way, but the path is what we call a pre-order traversal, which means you see contents of nodes before the elements - And by implication, you can swap those nodes and then visit the elements. All in all, prewalk makes for a very simple recursive pattern:

(w/prewalk
 (fn [n]
     (if (and (map? n) (split? n [x y]))
         (subdivide n)
       n))
 qtree)

Yes, it's really that simple. Given a root-node and a camera-position (x,y), this will recursively resolve all children to the maximum resolution.

The Visualization

If you want to read ahead, I've shared a repo here: Github

The code should run straight out of the box and open a webinterface on port 8020. Shadow-cljs makes light work of compiling anything from a single file to a huge frontend application, into a single JS file.

Running in a browser we get a nice 2D API from the standard canvas element. Basically, to draw our Quadtree we need only 3 things:

• A Quadtree
• A function which draws a node
• A function which draws all children

As you've probably guessed, the Quadtree itself is just a simple map with some keys. But because this is a realtime visualization, I want to create a connection between whichever tree I generated and what's drawn on screen. Fortunately both Clojure and Clojurescript support both atoms and watches:

(def quadInst (atom nil))

(add-watch quadInst :updateQuads
           (fn [_ _ old-tree new-tree]
             (draw-all new-tree)))

By convention in Clojure, we name arguments underscore (_) if we do not care about them. In this case, I only need the new-tree for the visualization. If you're not a native Clojurian you might find this pattern appealing as it gives you access to both the pre-updated version and the updated tree, meaning you can run diffs, add new children to a scene while removing others.

I mention it here for demonstration purposes only, in the latest commit you'll see I actually remove all atoms and demonstrate a 100% pure functional solution without atoms. However for the purpose of explaining Quadtree this is a simple subscription-pattern which most developers will recognize. It ensures that whenever the atom Quadtree is updated, so is the screen.

(defn draw-all
  [ tree ]
  (draw (:root? tree)
        tree
        (get-tree-color tree))
  (when-let [children (:children tree)]
    (doseq [c children]
      (draw-all c))))

However there's a fun detail here. To make it seem fairly consistent I couldn't just use random colors, that would make the entire screen flicker whenever you moved the mouse. Basically, if I have a rectangle centered at 50,50 - I always want it to have the same color. A really neat and simple trick is the 32bit hash, which is succinctly implemented in javascript like so:

function fastHash(str) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash << 5) - hash + str.charCodeAt(i); // Hash computation
        hash |= 0; // Convert to 32bit integer
    }
    return hash >>> 0; // Ensure the result is unsigned
}

Basically my idea is to hash the center, ie "[50,50]" and convert that to a hex color. In Clojurescript, you could do it like so:

(defn hash-str
  " Standard 32bit hash: [..].map((% << 5) - h + ch(idx) "
  [ s ]
  (reduce #(-> (bit-shift-left %1 5)
               (- %1)
               (+ (.charCodeAt %2 0))
               (bit-or 0))
          0 s))

(defn get-tree-color
  [ {c :center} ]
  (let [hash (bit-and (hash-str (str c)) 0xffffff)
        hex  (.toString hash 16)]
    (str "#" (apply str (repeat (- 6 (count hex)) "0")) hex)))

That's basically all you need.

Conclusion

Quadtrees are great when you have more work to do, than resources available. Imagine using a VR headset. Whichever point you're focused at, needs to be crisp in detail, you want the highest resolution possible on your hardware. Everything outside of your focus area should be dialed down in resolution because your eyes won't be able to pick it up anyway, so that compute power can be used elsewhere. There are many other applications.

Clojurescript is great, because it allows us to express ourselves succinctly and functionally. The core of this implementation is only about 25 lines long. That's much easier to reason about and debug, than some other implementations I've seen, which span several hundred lines.

Shadow-cljs is great for more reasons than I can cover in this post, but I will highlight the ability to quickly ship highly optimized bit of JS using only 10 lines of configuration - And they even throw in a free webserver for easy testing and repl driven development, what's not to like?

Full source code: Github