I think the flocking behavior of birds is one of the most entrancing natural phenomena, it's great to see it play out in such an intuitive way here. Is a quadtree generalizable to three dimensions? This looks like so much fun, thank you for sharing, I'm looking forward to playing with this over the holiday.

Note that even without an acceleration structure ("direct summation" in N-body research terminology), a CUDA program or GLSL shader program can exceed 60 fps with 10,000 to 20,000 particles. And a parallel, C/C++/fortran vectorized CPU code can do the same with over 5 thousand.

Related, 3 weeks ago: Functional Quadtrees (49 comments)

https://news.ycombinator.com/item?id=46147341

The boids in this demo form smaller flocks (both tighter, and fewer individuals) than other implementations I've seen. I had a look at the code and I'm not sure it's "right"? (I know the whole thing is subjective, I mean it doesn't follow the original)

In no particular order:

- the original boids code didn't cap the magnitude of acceleration after adding all the contributions; it added the contributions _by priority_, starting with separation, and if the max acceleration was exceeded it didn't add the others

- the max acceleration was decided by adding the _magnitudes_ not vectors of components, so the cohesion vector and the separation vector wouldn't cancel out - separation would win. I think this is why both this and the p5js one form very tight clumps which later "explode". That's this bit of the code (from https://www.red3d.com/cwr/code/boids.lisp):

    ;;
    ;; Available-acceleration should probably be 1.0, but I've set it a little higher to
    ;; avoid have to readjust the weighting factors for all of the acceleration requests.
    ;;
    (vlet* ((composite-acceleration (prioritized-acceleration-allocation 1.3 ;; 1.0
          avoid-obstacles
          avoid-flockmates
          velocity-matching
          centering-urge
          migratory-urge
          course-leveling
          course-damping))

- this implementation, unlike the p5js version it's based on, caps the acceleration _twice_ - before adding the contributions and after https://github.com/LauJensen/practical-quadtree/blob/7f5bdea... (this is the 'after' bit)

- the original had different radii for different components (the separation threshold was 4, the cohesion, alignment thresholds were 5)

- both the clojure and p5js versions use the same strength for cohesion, separation, and alignment. In the original, separation is much stronger (1, vs 0.3 for cohesion and 0.23 for alignment). Again this might explain the tight clumps.

I've not yet mucked with the rules to see if the behaviour recovers, but the p5js version makes it easy to hack on https://editor.p5js.org/pattvira/sketches/v_tmN-BC5 - as a first change, in draw() in sketch.js change the print statement to this:

    print(frameRate(), boids.length);
    if (frameRate()>50) {
      boids.push(new Boid(random(width), random(height)));    
    } else if (frameRate() < 40) {
      boids.pop()
    }

... and the two loops below it to use 'boids.length' not 'num'. Then the thing will dynamically adjust the number of boids to give you an acceptable framerate.

Aside: both the p5 and clojure versions do preserve the typo of 'seperation' from the Craig Reynold's code tho ;) ... I have to wonder if that's like 'referer' and now we have to spell it that way in a boids context.

This title is like an optical illusion, but for swearing.

Thank you - I was just about to point out some of that.

The reason that the flocks are tight is because the separation "force" is normally computed as a repulsion between a target boid and all other nearby boids individually, not vs. the center of mass of all nearby boids.