Flocking | Hacker News Reader

Flocking

blog.drewcutchins.com

121 pointsoctosphere23 comments

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.

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

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?

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.

Interesting. So maybe it is an evolutionarily stable strategy, if you assume it's too hard for the fish to keep track globally of where they are in the shoal (and are therefore limited to strategies where they only react to what's immediately around them). It would be fun to simulate this and see if there are any other strategies that offer an advantage.

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.

To be clear, though, there's no evolutionary function that optimizes for the overall benefit of unrelated individuals. So-called group selection has never been shown to exist in nature.

Cheating is moderated by the success rate of cheaters and non-cheaters individually. If cheating strategies come easy but counter-cheating strategies difficult, then the species success in the larger ecosystem will indeed be limited in as much as organized, goal-oriented behavior is beneficial. There's no group-wide selective pressure to favor the non-cheaters over cheaters as there's no group-wide inheritance mechanism that can accomplish that.

It's why schools of fish aren't as efficient as one might naively think they could be at evading, e.g., a giant whale. The cheaters can and do drag down the whole group because the equilibrium rate of cheaters in the school isn't responsive to the success rate of schools as a whole.

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..

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.

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.

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.

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

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).

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

Another nice interactive explaining the same ideas:

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

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.

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

What language is this? I was surprised to see that

averagePosition /= count;

apparently means

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

I think?

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

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

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};
  }

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."

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

Reply on news.ycombinator.com