Show HN: Genetic Boids Web Simulation

I don't know if this will address your question, but I had a long-standing question about boids that might overlap, which I coincidentally only resolved to my satisfaction a month ago. Here's the Lua code I ended up with:

    function update_positions(boids, dt)
      local max_speed = 0.5  -- per frame
      local max_accel = 20  -- per second
      local max_turn_angle = math.pi/6  -- per second
      for _,boid in ipairs(boids) do
        boid.pos = vadd(boid.pos, boid.velocity)
      end
      for i,boid in ipairs(boids) do
        local accel = {x=0, y=0}
        accel = vadd(accel, vscale(avoid_others(boid, boids), 20*dt))
        accel = vadd(accel, vscale(seek_others(boid, boids), 10*dt))
        accel = vadd(accel, vscale(align_with_others(boid, boids), 10*dt))
        accel = vadd(accel, vscale(remain_within_viewport(boid), 40*dt))
        local curr_heading = vnorm(boid.velocity)  -- could be nil
        accel = vclamp2(accel, max_accel*dt, curr_heading, max_turn_angle*dt)
        boid.velocity = vadd(boid.velocity, accel)
        boid.velocity = vclamp(boid.velocity, max_speed)
      end
    end

Here, avoid_others, seek_others and align_with_others are the 3 rules you can find on Wikipedia (https://en.wikipedia.org/wiki/Boids): separation, cohesion, alignment. Each of the functions returns a unit vector, which I then weight using vscale.

The key is the last 4 lines. My intuition here is that the way muscle mechanics work, there are limits on both how fast you can accelerate and also how much you can turn per unit time. That's what vclamp2 is doing. It separately clamps both magnitude and angle of acceleration.

My rough sense after this experience was:

* Boids is not a simple program the way the Game of Life or Mandelbrot set is. The original paper had tons of nuance that we gloss over in the internet era.

* Every implementation I've found is either extremely sensitive to weights or does weird stuff in the steering. Stuff like subtracting velocity from acceleration when the units are different, and so on. There may be a numeric basis for them, but it's never been explained to my satisfaction. Whereas my vclamp2 idea roughly hangs together for me. And the evidence it's on the right track is that a wide variety of weights (the 10s, 20s and 40s above) result in behavior that looks right to me.

Just a clarifying note, Craig Reynolds is the original researcher for Boids, and he did have a Java applet implementation in the above page. But the original Boids simulation was from 1986, almost a decade prior to Java applets.

The original paper, published in 1987, is "Flocks, herds and schools: A distributed behavioral model"[1]. The implementation was done in Lisp on a Symbolics 3600 Lisp Machine.

Edit: One quite interesting paragraph from the paper regarding performance:

The boid software has not been optimized for speed. But this report would be incomplete without a rough estimate of the actual performance of the system. With a flock of 80 boids, using the naive O(N²) algorithm (and so 6400 individual boid-to-boid comparisons), on a single Lisp Machine without any special hardware accelerators, the simulation ran for about 95 seconds per frame. A ten-second (300 frame) motion test took about eight hours of real time to produce.

Once again, amazing how far hardware has advanced.

1. https://dl.acm.org/doi/10.1145/37402.37406

oh, so i wasn't really aware that there was a original boid sim (I will check it today). mostly I saw it on some other demos and I wanted to add this behaviour of signaling boids which are far away + color code based on genome + do a simple cross-mutate. and yes you are right about fitness func.

Beyond this i was trying to add a map which effects their movement. (if you wanna check how it looks - https://x.com/attentionmech/status/1925690991555531143)

thanks!

hey thanks! color is coming from genome (check brightColorFromGenome)! nice suggestions, will definitely try to incorporate some of them.

dies in the sense machine gets hung or all boids vanish?

EDIT: also pushed some fixes in params (allow offsprings at larger distance, etc), but basically if the boids don't end up closer, they won't reproduce and the population dies so play with that and lmk

oh nice, webGPU thing should learn sometime!

so, i just used them like conceptually..

each boid has a string, when boids come close , they produce a offspring with mixed string + mutation age lets boids die too

nothing fancy, just for sake of sim

anything AI can do GAs can do worse

I don't know myself, but it seems to give boids their own unique state and add another layer of influence to their acceleration.

https://github.com/attentionmech/genetic-boids/blob/485fe482...

I'm reading the code but I don't know what it actually DOES in practice; my guess is that Boids with opposite genomes (binary strings with default length 6) are slightly attracted to eachother.

I learned about Boids when I was 16 thanks to Sebastian Lague's amazing video on it: https://youtu.be/bqtqltqcQhw

Highly recommend, especially his older videos on simulations.