In a recent blogpost I demonstrated how to build purely functional quadtrees in submilliseconds and this week I'll take it up a notch and show how to add multiple focal points and add some boid flocking logic.

A demo

Below you should see 200 boids acting as individuals when apart and as flocks when closer together.

How to flock

To build this simulation, assuming you've read how to build a functional quadtree, we need only 3 things

• A way to represent a Boid
• Some fast way to get it's closest neighbors
• Figure out how these neighbors interact

So let's start with a generous representation of a Boid. I say generous because I'm purposely including more data than needed. The cost is a bit more memory but it makes it easier to be purely functional down the road:

(def boid-defaults
  {:max-speed     2.0
   :max-force     0.4
   :perception   30})

(defn initialize-boids
  [ width height ]
  (->> (for [idx (range num-boids)]
         (merge boid-defaults
                {:id idx
                 :position     [(rand-int width) (rand-int height)]
                 :max-w        width
                 :max-h        height
                 :velocity     [(- (u/rand-float 3) 1.5)
                                (- (u/rand-float 3) 1.5)]
                 :acceleration [0 0]}))
       (reset! boids)))

If you're new to clojure, be aware that 'for' is a way of walking a list and returning a list. In this case we walk over (range num-boids), ie the number of 0..num-boids and for each of those we select a random starting point and a random velocity vector (direction) - And then we pipe that list into reset! which stores it in an atom.

Now that we have our flock (list of boids) we simply need to walk the list, updating the position of each boid relative to its velocity vector - But before that, we need to make sure that the velocity vector is pointing in a direction which is similar to how a flock of birds would move.

The simplest way to model this, to my knowledge at least, is this:

• Find the boids that are close enough to affect the one you're updating
• Make a new acceleration vector, which aligns the current boid to the average direction of his friends
• Create some cohesion in the flock, by slightly pointing this vector towards the center of the group
• Enable separation, by adding a force away from the center, if the boids get too close (inversely proportional to distance)

Once you have computed this flock-acceleration vector, add it to the current velocity and off it goes. In Clojure it looks like so:

(defn move-boid
  [ tree {:keys [id
                 position
                 velocity
                 perception
                 max-speed
                 max-force]
          :as boid} ]
  (let [friends        (->> (qt/search tree perception position)
                            (filterv #(not= id (:id %))))
        acceleration   (->> (v/add
                             (alignment boid friends)
                             (cohesion boid friends)
                             (seperation boid friends))
                            (v/limit-mag max-force))
        velocity       (->> (v/add velocity acceleration)
                            (v/limit-mag max-speed))]
    (edge-wrap
     (assoc boid
            :position     (v/add position velocity)
            :velocity     velocity
            :acceleration [0 0]))))

The math in each of these is actually fairly straightforward, so I'll just dive into one of them: Cohesion. Have a look at the code first and I'll pick it apart below:

(defn cohesion
  " Steer towards center of friends "
  [ {:keys [position max-speed max-force velocity]} friends ]
  (if (seq friends)
    (->> (map :position friends)
         (reduce #(v/add %1 %2) [0 0])
         (v/div (count friends))
         (v/sub position)
         (v/magnitude max-speed)
         (v/sub velocity)
         (v/limit-mag max-force))
    [0 0]))

As you saw in move-boid, all of these steering function receive a list of nearby-boids, ie friends. They are not really friends in the sense that they share private details and give each other advise on worldly matters, only in the sense that they are now so close that they are within each others radius of perception.

From these friends, I map :position, giving me a list of their positions. From an origin of 0, 0, I simply add all of these together and in the very next line divide by their number, effectively giving me an average of positions, ie. the center.

I then subtract the center from my own position, giving me a vector pointing from me towards the center. Ideally, this is actually enough to create cohesion in a flock, but since I'm computing a force which will act on my current velocity, I need to make sure that it never exceeds some acceptable threshold, ie. separation must not push the boid off the map completely. For this reason I set the magnitude to the maximum speed, then from subtract that sanitized vector from my current velocity (directional vector) and again make sure that the result does not exceed the maximum-force (clamping).

Alignment is nearly identically implemented, except that it looks at the friends velocity (I want to go the same way as you) and separation is like the opposite of cohesion, but with an extra push for small distances. Check them out on Github

So that only leaves one thing, finding the nearby-boids.

Flocking Quadtrees

I assume that by now, you know everything there is to know about Quadtrees and how to build them functionally. But in case you want a bit more information on how to add multiple focal points and search through them quickly, I'll share a few insights.

The only 2 changes in the tree itself, is a new variable called MINIMUM-LEAF-WIDTH which blocks infinite recursion while subdividing, and some method of moving all the objects in a cell, into it's new children:

(defn inside?
  [ bounds [x y] ]
  (when-let [[x1 y1 x2 y2] (seq bounds)]
    (and (<= x1 x x2)
         (<= y1 y y2))))

(defn subdivide
  " Attaches 4 :children to the node "
  [ {:keys [bounds objects] :as node} ]
  (let [[x1 y1 x2 y2] bounds
        top-left      [x1           y1           (half x2 x1) (half y2 y1)]
        top-right     [(half x2 x1) y1           x2           (half y2 y1)]
        bottom-left   [x1           (half y2 y1) (half x2 x1) y2]
        bottom-right  [(half x2 x1) (half y2 y1) x2           y2]]
    (->> [top-left top-right bottom-left bottom-right]
         (mapv #(->> (filterv (fn [p] (inside? % (:position p))) objects)
                     (assoc (qtree %) :objects)))
         (assoc node :objects [] :children))))

I think for these kinds of manipulations, Clojure really shines in it's simplicity. The only change in this version of the subdivide function, is the inner call to filterv, which quickly and easily filters the objects into the child-nodes. This can be made much, much faster of course, but it turns out that for a goal of 60 fps, this does just fine.

For the search itself, we're getting a bit dirty:

(defn search
  [node r center]
  (let [r2 (* r r)]
    (letfn [(drill [n acc]
              (if (not (circle-intersects-rect? center r (:bounds n)))
                acc
                (if-let [chs (:children n)]
                  (reduce (fn [a c] (drill c a)) acc chs)
                  (reduce (fn [a p]
                            (if (<= (dist2 center (:position p)) r2)
                              (conj a p)
                              a))
                          acc
                          (:objects n)))))]
      (drill node []))))

Perhaps not the most beautiful code, but pretty fast. I recursively look for overlaps between the radius of my search-circle and the tree nodes. To shave off a few mikroseconds, I don't do any sqrt computations, but just compare the squared radius to the squad distance. I have a feeling this is old wisdom, but some habits die hard.

The algorithm is, thanks to the structure of quadtrees, very simple. We look at a node and check if it overlaps with our search, if not we're done, return whatever we've found. If so, repeat the step for each child, and you're done. This is very quick, but it's not actually the quickest. The reason I've chosen it here, is 1) I was already blogging about Quadtress and 2) It's the most fun to visualize.

Conclusions

As always, feel free to checkout the code, start a repl, experiments, it's on Github.

A comment on purity: I don't strive for 100% purity, but this is close. The exception being that the boids are in an atom which is updated each step. Since we're compiling to Javascript for your interactive reading-pleasure, we're single-threaded. If we compiled to Clojure, I could show you a neat trick where we use iterate to compute every single motion of every boid and simply show the nth step. Maybe I'll demonstrate this with webworkers in a future post. It's a fun exercise but not much is gained.

A comment on performance: I always start by making my code as functional, pure and concise as possible. In this case that means using prewalk as I did in the first post. I think it's a very elegant solution, but unfortunately it does visit every single element at least thrice, meaning it was a 200x speedup to write insert more manually. All in all, I was pleasantly surprised at how few compromises I had to make to get 60 fps.

And finally I want to thank Patt Vira for the inspiration for throwing Boids into the Quadmix. She demonstrates an interesting imperative approach in P5/JS in this video.