akkartik
yesterday at 11:45 PM
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.
talkingtab
today at 12:58 AM
Wow! Thanks. The thought about "Boids is not a simple ..." is new to me and very good. The other vector in this is the evolution/genetic algorithm idea. It raises the question of what are the benefits of flocking? And could you plug those into a genetic algorithm to test survival.
It seems like perhaps the visual inputs are another interesting area. What do I (as a boid) do when I see one boid in front of me go right, one go left, for example.
But thanks!!
Yeah, the original paper gets into some of that. It was about 3D flocking! And Reynolds was very much thinking about what each bird sees, the minimum angle to turn to avoid a collision, etc. All on a then-powerful graphical workstation.