Hacker News new | past | comments | ask | show | jobs | submit login
Neat Algorithms - Flocking (harry.me)
220 points by mattkirman on Feb 25, 2011 | hide | past | web | favorite | 32 comments



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.


>More evidence that getting noticed is largely chance,

Or chaotic flocking behavior. :)


"... Also submitted four days ago: ...although it gains very few upvotes, and no comments ..."

If this wasn't re-posted I wouldn't be able to read it as I missed the first submission. Maybe a suggestion would be having an additional link of 'resumitted' ie: http://news.ycombinator.com/resub Then you can catchup on interesting articles previously submitted.

As for gaming - submissions has always been flakey. A simple check in the submission code could against previous submissions. Rejecting slight differences in a url.


Is this a reference to the quality of HN discussion going on lately? I'd lurked long before I ever signed up, and I just always assumed that getting noticed was largely chance. For whatever reason, it feels like you're saying this wasn't always the case.


There used to be vastly fewer submissions per day, so if you read /newest once a day you'd see a greater fraction of the submissions. Now that /newest only holds about the last hour, submissions scroll off before very many people even see them.


What's funny is that I bookmarked it then, checked it out today, tweeted it a few hours ago, and I know Matt. I could be wrong but I think this might have gone full circle! :)

But yeah, as ever, not enough people monitor /new (or there's not enough incentive to do so).


Sorry guys, but that's probably what's happened. I did do a quick site: Google search for the page title but it didn't bring back any results. Apologies for the double post.


I think the point here is.. it was a good link first time around and it kinda failed in the system so this resubmission turned out for the best! ;-)


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


You sure are pretty prolific in the Clojure community. I look at my Clojure code and then I look at yours and I wish mine was as elegant as yours.


To be honest I continued to work on my Clojure flocking code long after it was working.

I actually took this code as challenge to learn how to put together idiomatic, fast Clojure code that read better than the original Java on which it is based.

Of course, nearly a year later since I wrote this version, I can see ways to make it even faster (nearly on par with Java and faster when parallel), cleaner and more elegant.


Do have any tips for someone looking to do better?


Partly it's API familiarity - clojure and clojure.contrib have a LOT of functions to offer, and a lot of the time may have higher order functions to do what you might be doing the hard way :)


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.


This is super cool! I really like the visuals in your implementation, way better looking than my blocky vectors. You also get pretty great performance by using raw canvas api calls which by the looks of your code wasn't too unwieldy. You also didn't implement any wrap around which stirs things up when the flock hits the edges, which goes a long way to demonstrate the actual behaviour as they reflect off the side. Nicely done!


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.


Sounds like something you could have fixed with another, slightly randomized factor: "attention-span". Long boughts of straight flying would result in an increasingly large but seemingly random delay.

Cool sounding use case though!


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.


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


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.


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.


You can also cut a boid out of the flock by moving the mouse cursor to one side or the other, sort of interesting to see what happens to a lone boid...


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.



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!


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


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/


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


I could watch this for hours.


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.


discrete navier stokes?


It definitely has a very similar feel, watching the movement over time.




Registration is open for Startup School 2019. Classes start July 22nd.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: