Flocking

https://www.blog.drewcutchins.com/blog/2018-8-16-flocking

by octosphere • 8 years ago

121 23 8 years ago

blog.drewcutchins.com

zinodaur• 8 years ago

Emergent behavior in animal groups is very cool. I once saw another interesting algorithm in the wild: schools of anchovies sharing the most dangerous roles in the schools.

The front and back of the school is the most dangerous spot - since it is the most exposed to predators. However, anchovies share this responsibility of being in the most dangerous spot by following two simple rules.

Rule 1. When you get to the front of the school, slow down to a speed slower than the school.

Rule 2. When you get to the back of the school, match the speed of the school.

Following these two rules means that the anchovies will constantly rotate between all the varying degrees of safety of the school, a problem that would be difficult to orchestrate from an outside perspective, but one that is easy for the anchovies to figure out for themselves.

avar• 8 years ago

The same algorithm is found among human racing cyclists to rotate position at the front of the pack.

bayes2• 8 years ago

Why would they do this though? Why wouldn't a gene for 'cheating' (e.g. not slowing down when you reach the front) to avoid danger be favoured by natural selection? Animals with complex social structures (like us) avoid this by evolving to identify and punish cheaters, but there must be some other mechanism in these fish?

iainmerrick• 8 years ago

If you don’t slow down when you get to the front, you’ll end up separated from the school and more vulnerable to attack. Likewise if you don’t match the school’s speed when you’re at the back.

Staying in the middle would be advantageous, but when the whole school is cycling slowly, that’s tricky to do. The cheating behavior would need to be a little more complex so that’s an obstacle to its evolution.

Additionally, the more cheaters there are, the slower the school will move overall, which harms everybody (including the cheaters) so that limits the spread of cheating somewhat.

Overall, I’d guess that cheating could evolve, but only in a careful balance with the normal behavior. If the cheating starts to get significantly more complex, policing methods would co-evolve with it.

jcims• 8 years ago

Because then you evolve societies that spend so much time fighting each other for marginal increases in individual safety that the benefit of working together is lost.

ur-whale• 8 years ago

This is particularly fun to implement on a modern GPU to simulate very large boids populations.

It's also the perfect toy problem to learn the strengths, limitations and complexities of high performance GPU programming..

nestorD• 8 years ago

A very good toy problem in general : it is visual, simple to get something up and working while leaving ample space for optimisation and added complexity.

fromthestart2• 8 years ago

The nested loop in the UpdateFlock function could be optimized. The nested j loop should start at j=i+1, not j=0. Currently the author is making each comparison twice.

plopz• 8 years ago

If you did that the later boids in the list wouldn't know about any of their own neighbors.

fromthestart2• 8 years ago

In the current implementation, yes. But the code should be structured to append neighbors to both boids[i] and boids[j] simultaneously.

This is especially critical in physics simulations like these, where niave particle interaction algorithms can be an expensive O(n^2).

lonesword• 8 years ago

Reminds me of Daniel Shiffman's "Nature of Code". I started programming when I was 15 in Processing. Ah the good old days.

mysterydip• 8 years ago

Flocking is one of my favorite algorithms. I used it as the AI in a game once where fish play capture the flag. I gave each player a "personality" by weighting separation/cohesion/alignment slightly different.

I also added in cohesion towards enemies (for attacking) or the flag (for capturing), and separation of obstacles. If one had the flag, they changed to separation of enemies and cohesion towards their own flag. With a few simple additions, watching the results was very satisfying.

nstart• 8 years ago

For anyone who prefers to absorb similar information more visually, I dug through my YouTube memories to find this talk. https://www.youtube.com/watch?v=Q52oYMO962w

Most material on flocking is roughly the same but I particularly enjoyed this talk. Not sure whether it was the presentation method or the simplicity of NetLogo that allowed me to keep the context of code and concept in my head, but either way this one really clicked for me.

default-kramer• 8 years ago

What language is this? I was surprised to see that

averagePosition /= count;

apparently means

averagePosition.x /= count; averagePosition.y /= count;

I think?

Retr0spectrum• 8 years ago

This language feature (at a fundamental level) is called "operator overloading", which is present in a lot of languages (more often in OO languages).

https://en.wikipedia.org/wiki/Operator_overloading

fenwick67• 8 years ago

Javascript doesn't support operator overloading, I think the code in the examples is just pseudocode.

SloopJon• 8 years ago

This looks like buggy JavaScript. The cohesion() function in the script element at the end of the post is a little different than the calculateCohesion() function described in the post:

  var averagePosition;
  if (count > 0) {
      averagePosition = {
          x: positionSum.x / count,
          y: positionSum.y / count
      };
  } else {
      return {x: 0, y:0};
  }

oblib• 8 years ago

The author, Drew Cutchins, says "If you inspect the source code of the page you can see the code I used to implement the simulations."

jeffbaumes• 8 years ago

Another nice interactive explaining the same ideas:

https://beta.observablehq.com/@herbps10/boids

jowiar• 8 years ago

For those who like flocking, Robert Hodgin's Eyeo talk is my favorite set of flocking demos: https://vimeo.com/103537259

lsh• 8 years ago

Michael Chricton published a book called Prey which focuses on emergent behaviour (and nanotechnology) with several mathematical equations I never understood.

Flocking

Related Stories