4 ms·

Neat Algorithms - Flocking

160 points by bochi 14y ago

jeffehobbs 14y ago
oh, FLOCKing. Yes. That is neat too.
- clockstrikesten 14y ago
  Delete your comment immediately.
seivan 14y ago
Thank you so much! Great article, found some stuff I could definitely use for games I'm working on.
hythloday 14y ago
The original paper[0], published in '86, in addition to being a huge step forward over contemporary graphics techniques, is extremely comprehensible and an excellent read. It also goes into some detail about collision avoidance, which is hard to see in the browser demo (boids will avoid the mouse but not in a very large area), and goal seeking, which isn't in it. It ends with a fairly eyebrow-raising testament to the increase in computer power over the last two and a half decades: "This report would be incomplete without a rough estimate of the actual performance of the system. With a flock of 80 boids, using the naive O(N^2) algorithm (and so 6400 individual boid-to-boid comparisons), on a single Lisp Machine without any special hardware accelerators, the simulation ran for about 95 seconds per frame. A ten-second (300 frame) motion test took about eight hours of real time to produce." [0] http://www.red3d.com/cwr/papers/1987/boids.html http://www.red3d.com/cwr/papers/1987/boids.html
- delinka 14y ago
  I have a vague recollection of reading about this in a magazine when I was in 7th or 8th grade. I also recall being very disappointed in the results of my coding based on the article. I had recalled through the years my attempts at drawing some flocking pixels, but had forgotten the source of my 'inspiration' and never really regained my curiosity. I think I had decided that I just didn't understand the material. Now I think that the article wasn't a technical paper and I didn't know any better at the time. Your link to the original paper (!) is most certainly welcome. I've finally decided to get back to some graphics programming and this would be a fun exercise.
- EtienneK 14y ago
  If anyone's interested, I have started implementing Reynold's demos on an HTML 5 canvas: http://www.etiennek.com/demos/html5steering/ http://www.etiennek.com/demos/html5steering/
repocussion 14y ago
My friend actually recently released an Android game based on exactly this: https://play.google.com/store/apps/details?id=co.uk.iceroad.complexcity.floqua https://play.google.com/store/apps/details?id=co.uk.iceroad....
mlu 14y ago
I once programmed a swarm simulation as a project for a course I attended. You can set various parameters of the swarm and introduce a predator which can try to eat inidividuals of the swarm. You then can set a bunch of escape strategies. This was pretty much fun when I wrote it. Just uploaded it to my bitbucket repository in case anyone is interested. https://bitbucket.org/mlux/swarm-simulation https://bitbucket.org/mlux/swarm-simulation
- Radim 14y ago
  My app with a very similar goal (predators & prey), but C++ with OpenGL :) https://github.com/piskvorky/PredatorPrey https://github.com/piskvorky/PredatorPrey I remember decoupling the simulation speed from graphics rendering speed (aka frame rate) and AI thinking speed was a lot of fun!
runemadsen 14y ago
You should definitely check out Daniel Shiffmans "Nature of Code" book that is coming out soon. It's full of stuff like this.
- Volscio 14y ago
  Furthermore: http://www.shiffman.net/teaching/nature/ http://www.shiffman.net/teaching/nature/ (hey Rune!)
- hbrundage 14y ago
  Original author here: I backed the book and have been eagerly following along. Really cool stuff.
bawllz 14y ago
Woah! Super cool idea. So many ways you can take this to a new level. Also, if anyone is looking to contribute to some open source, this would be a great opportunity as there is lots of epic optimization problems in this algorithm to work on. For example, whats the fastest data structure/algorithm to make searching for neighbours?
- postfuturist 14y ago
  I'd guess some type of BSP tree. I agree, it looks fun to work on, see how massive of a simulation you could run in real time.
wsbail29 14y ago
Here's a CoffeeScript port of this algorithm I did awhile ago. https://gist.github.com/3733089 https://gist.github.com/3733089 and a demo: http://wsb.im/flocking/index.html http://wsb.im/flocking/index.html Definitely fun stuff to play around with.
- chime 14y ago
  Yours is a lot more fun to play with. Good job!
pacaro 14y ago
This is covered very well (a long with many other neat algorithms) in The Computational Beauty of Nature[1], one of those books I keep coming back to [1] http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://mitpress.mit.edu/books/FLAOH/cbnhtml/
- elemeno 14y ago
  A fantastic and seemingly little known book. Not necessarily for anyone who's not comfortable with the math, but a very rewarding a mind opening read.
- raverbashing 14y ago
  This is a really great book! And a real mind opener. Even if you know about some areas already.
- haraball 14y ago
  The book Clever Algorithms (free to download) is also covering some swarm algorithms: http://www.cleveralgorithms.com/nature-inspired/swarm.html http://www.cleveralgorithms.com/nature-inspired/swarm.html
tsahyt 14y ago
The visual demonstration is rather hypnotizing to watch. This algorithm is an example how seemingly intelligent behaviour roots in just a handful of simple rules. In this way it kind of reminds me of Conway's Game of Life: A few simple rules stimulating stunningly complex behaviour.
Havoc 14y ago
Bat swarms and game AI aside, what are the real world applications of something like this? It strikes me as significantly less useful than say a neural net.
- msellout 14y ago
  Au contraire, these [swarms can be very useful](http://en.wikipedia.org/wiki/Swarm_intelligence http://en.wikipedia.org/wiki/Swarm_intelligence). No one machine learning algorithm is best for all tasks. With current state-of-the-art technology, a human must choose the most appropriate algorithm by using what you could consider a priori knowledge about the task.
Bjartr 14y ago
I made a boids implementation in WebGL a while back http://www.cs.rit.edu/~bpd9116/WebGLU/examples/boids/boids.html http://www.cs.rit.edu/~bpd9116/WebGLU/examples/boids/boids.h...
haihaibye 14y ago
http://proceduralgraphics.blogspot.com.au/2010/06/flock-in-cloudy-blue-sky.html?m=1 http://proceduralgraphics.blogspot.com.au/2010/06/flock-in-c... In straight js and canvas, with bird silhouettes and Perlin sky

160 points by bochi 14y ago

jeffehobbs 14y ago

oh, FLOCKing. Yes. That is neat too.

clockstrikesten 14y ago
Delete your comment immediately.

seivan 14y ago

Thank you so much! Great article, found some stuff I could definitely use for games I'm working on.

hythloday 14y ago

The original paper[0], published in '86, in addition to being a huge step forward over contemporary graphics techniques, is extremely comprehensible and an excellent read. It also goes into some detail about collision avoidance, which is hard to see in the browser demo (boids will avoid the mouse but not in a very large area), and goal seeking, which isn't in it. It ends with a fairly eyebrow-raising testament to the increase in computer power over the last two and a half decades: "This report would be incomplete without a rough estimate of the actual performance of the system. With a flock of 80 boids, using the naive O(N^2) algorithm (and so 6400 individual boid-to-boid comparisons), on a single Lisp Machine without any special hardware accelerators, the simulation ran for about 95 seconds per frame. A ten-second (300 frame) motion test took about eight hours of real time to produce." [0] http://www.red3d.com/cwr/papers/1987/boids.html http://www.red3d.com/cwr/papers/1987/boids.html

delinka 14y ago
I have a vague recollection of reading about this in a magazine when I was in 7th or 8th grade. I also recall being very disappointed in the results of my coding based on the article. I had recalled through the years my attempts at drawing some flocking pixels, but had forgotten the source of my 'inspiration' and never really regained my curiosity. I think I had decided that I just didn't understand the material. Now I think that the article wasn't a technical paper and I didn't know any better at the time. Your link to the original paper (!) is most certainly welcome. I've finally decided to get back to some graphics programming and this would be a fun exercise.
EtienneK 14y ago
If anyone's interested, I have started implementing Reynold's demos on an HTML 5 canvas: http://www.etiennek.com/demos/html5steering/ http://www.etiennek.com/demos/html5steering/

repocussion 14y ago

My friend actually recently released an Android game based on exactly this: https://play.google.com/store/apps/details?id=co.uk.iceroad.complexcity.floqua https://play.google.com/store/apps/details?id=co.uk.iceroad....

mlu 14y ago

I once programmed a swarm simulation as a project for a course I attended. You can set various parameters of the swarm and introduce a predator which can try to eat inidividuals of the swarm. You then can set a bunch of escape strategies. This was pretty much fun when I wrote it. Just uploaded it to my bitbucket repository in case anyone is interested. https://bitbucket.org/mlux/swarm-simulation https://bitbucket.org/mlux/swarm-simulation

Radim 14y ago
My app with a very similar goal (predators & prey), but C++ with OpenGL :) https://github.com/piskvorky/PredatorPrey https://github.com/piskvorky/PredatorPrey I remember decoupling the simulation speed from graphics rendering speed (aka frame rate) and AI thinking speed was a lot of fun!

runemadsen 14y ago

You should definitely check out Daniel Shiffmans "Nature of Code" book that is coming out soon. It's full of stuff like this.

Volscio 14y ago
Furthermore: http://www.shiffman.net/teaching/nature/ http://www.shiffman.net/teaching/nature/ (hey Rune!)
hbrundage 14y ago
Original author here: I backed the book and have been eagerly following along. Really cool stuff.

bawllz 14y ago

Woah! Super cool idea. So many ways you can take this to a new level. Also, if anyone is looking to contribute to some open source, this would be a great opportunity as there is lots of epic optimization problems in this algorithm to work on. For example, whats the fastest data structure/algorithm to make searching for neighbours?

postfuturist 14y ago
I'd guess some type of BSP tree. I agree, it looks fun to work on, see how massive of a simulation you could run in real time.

wsbail29 14y ago

Here's a CoffeeScript port of this algorithm I did awhile ago. https://gist.github.com/3733089 https://gist.github.com/3733089 and a demo: http://wsb.im/flocking/index.html http://wsb.im/flocking/index.html Definitely fun stuff to play around with.

chime 14y ago
Yours is a lot more fun to play with. Good job!

pacaro 14y ago

This is covered very well (a long with many other neat algorithms) in The Computational Beauty of Nature[1], one of those books I keep coming back to [1] http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://mitpress.mit.edu/books/FLAOH/cbnhtml/

elemeno 14y ago
A fantastic and seemingly little known book. Not necessarily for anyone who's not comfortable with the math, but a very rewarding a mind opening read.
raverbashing 14y ago
This is a really great book! And a real mind opener. Even if you know about some areas already.
haraball 14y ago
The book Clever Algorithms (free to download) is also covering some swarm algorithms: http://www.cleveralgorithms.com/nature-inspired/swarm.html http://www.cleveralgorithms.com/nature-inspired/swarm.html

tsahyt 14y ago

The visual demonstration is rather hypnotizing to watch. This algorithm is an example how seemingly intelligent behaviour roots in just a handful of simple rules. In this way it kind of reminds me of Conway's Game of Life: A few simple rules stimulating stunningly complex behaviour.

Havoc 14y ago

Bat swarms and game AI aside, what are the real world applications of something like this? It strikes me as significantly less useful than say a neural net.

msellout 14y ago
Au contraire, these [swarms can be very useful](http://en.wikipedia.org/wiki/Swarm_intelligence http://en.wikipedia.org/wiki/Swarm_intelligence). No one machine learning algorithm is best for all tasks. With current state-of-the-art technology, a human must choose the most appropriate algorithm by using what you could consider a priori knowledge about the task.

Bjartr 14y ago

I made a boids implementation in WebGL a while back http://www.cs.rit.edu/~bpd9116/WebGLU/examples/boids/boids.html http://www.cs.rit.edu/~bpd9116/WebGLU/examples/boids/boids.h...

haihaibye 14y ago

http://proceduralgraphics.blogspot.com.au/2010/06/flock-in-cloudy-blue-sky.html?m=1 http://proceduralgraphics.blogspot.com.au/2010/06/flock-in-c... In straight js and canvas, with bird silhouettes and Perlin sky