from Hacker News

Neat Algorithms - Flocking

by mattkirman on 2/25/11, 7:08 PM with 32 comments

  • by RiderOfGiraffes on 2/25/11, 8:18 PM

    Also submitted four days ago:

    http://news.ycombinator.com/item?id=2246089

    although it gains very few upvotes, and no comments. More evidence that getting noticed is largely chance, or gaming.

  • by swannodette on 2/25/11, 8:11 PM

    And here's a parallel version written in Clojure that scales across your cores, https://github.com/swannodette/flocking/blob/master/src/floc...

  • by Breefield on 2/25/11, 9:56 PM

    If you haven't seen the boids pseudocode page by Conrad Parker it's definitely worth checking out: http://www.vergenet.net/~conrad/boids/pseudocode.html

    Here's an implementation I wrote last month for fun: http://breefield.com/lab/flock. It doesn't have much bias in terms of direction (there's no wind, or patterns to follow), so there's generally one large swarm. Click-drag to create repellers, boids follow mouse. The white center of each boid shrinks at it's velocity increases, and the inverse happens to it's red direction line. Purple specks indicate perceived center of nearby flock. The rest is just aesthetic.

    It's always super interesting to see other implementations in action, so please share more in your comments, if you have them. I'd certainly love to see them.

  • by nihilocrat on 2/25/11, 9:57 PM

    I used flocking in a game project in college (getting ad-hoc starship fleets to get into ad-hoc formations) with another condition: When the basic requirements are met, each ship should also try to align with a master "fleet admiral" ship, and the group of boids under consideration was limited to only ships specifically defined as part of the fleet.

    It kind of worked, there were issues with stragglers and making it look organic that I couldn't fix in time. If ships got too far outside the formation sometimes they would only try aligning with the leader instead of catching up first. Also, when they did get in formation, they were eerily good at matching the leader's alignment: all ships would turn in unison and kind of ruin the organic feel of the pure flocking algorithm.

  • by krisneuharth on 2/25/11, 9:20 PM

    See also: http://en.wikipedia.org/wiki/Swarm_behaviour

    At a research company I worked at we used swarming concepts for controlling swarms of sensors, robots, and UAVs. We also used ant colony optimization techniques mixed with genetic algorithms to do predictive intelligence. Really powerful stuff.

  • by mccutchen on 2/25/11, 9:15 PM

    Here's an implementation I wrote some years ago that includes obstacle avoidance. Clicking adds obstacles, spacebar adds boids, reloading gets new colors. This ended up looking somewhat like sperm avoiding eggs...

    http://humortree.org/projects/flock03/

    (Java applet warning!)

    The source code is here:

    https://github.com/mccutchen/humortree.org/tree/master/proje...

  • by mgunes on 2/26/11, 1:05 AM

    Very well explained. There needs to be more of this (algorithms and applied math explained in a manner somewhat accessible and nourishing to non-mathematicians through code and visualization) on the web, and I'd love to be pointed to similar resources.

  • by joshes on 2/25/11, 7:31 PM

    Turning on the legend and the magnification of an individual boid (by clicking "Decorate") is very helpful. When you mouse over the magnified boid, you see the vectors immediately adjust, providing a very handy visual description of what is happening in real time.

  • by kamens on 2/25/11, 8:23 PM

    I used to use boids as an interview question for candidates who whizzed through my first few code challenges -- was interesting to discuss various collision detection options with an eye on performance.

    Such a simple algorithm w/ such a cool result.

  • by corysama on 2/25/11, 9:12 PM

  • by hebejebelus on 2/25/11, 9:53 PM

    This is fantastic! Not just the algorithm, but the explanation, the fact that there's source code readily available, and the canvas demo. Please, do more!

  • by tjarratt on 2/25/11, 9:37 PM

    I've wanted to write some exploratory algorithms for flocking for a long time now. This is just the motivation I need to start working on a silly side project.

    Thank you, everyone in the comments who submitted source code or demos. You never know when something you upload will really brighten someone's day (even if it's written in java).

  • by mirkules on 2/26/11, 4:42 PM

    Cool. There's also a book called "Swarm Intelligence" by Kennedy/Eberhart that describes swarm behaviors very well (my favorite book).

    For anyone interested, here is the Craig Reynolds page that describes the flocking behavior http://www.red3d.com/cwr/boids/

  • by pjvandehaar on 3/2/11, 1:53 AM

    It'd be great if someone added "[processor-heavy]" on to the title of posts like this.

  • by thefox on 2/25/11, 9:01 PM

    I could watch this for hours.

  • by meatsock on 2/25/11, 11:33 PM

    glad to see you've herd of this, and are flocking to it. if you're not too flighty it's worth a peep, but you may have to duck some bugs in the code. furthermore i think flocking should be part of everyone's schooling, and there's nothing fishy about that.

  • by VladRussian on 2/25/11, 8:49 PM

    discrete navier stokes?