6 ms·

Show HN: Boids Simulation

63 points by anoopelias 12y ago

deleted 12y ago
[deleted]
cporios 12y ago
Nice! I've done something similar in the past: http://static.mysti.co.in/boids/ http://static.mysti.co.in/boids/ Source: https://github.com/tech-no-crat/boids https://github.com/tech-no-crat/boids
- nacs 12y ago
  If you use 'requestAnimationFrame()' instead of a 'setInterval()' for triggering your update method, your animation will perform a lot smoother: https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame https://developer.mozilla.org/en-US/docs/Web/API/window/requ...
  - anoop-elias 12y ago
    Have a look at this one, highly recommended, https://github.com/hughsk/ticker https://github.com/hughsk/ticker
timdaub 12y ago
If you're into this kind of artificial life simulation, I can recommend you watching this talk: http://developertalks.tumblr.com/post/109998034809/simon-swain-deep-space-a-simulation-drama http://developertalks.tumblr.com/post/109998034809/simon-swa...
- anoop-elias 12y ago
  Excellent link. Thank you. I haven't looked deep in to these kind of simulations in general. Inspiration came from the Princeton Algortihms course in coursera.org. There is this sample problem, http://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/boids.html http://www.cs.princeton.edu/courses/archive/spr10/cos226/ass...
stared 12y ago
For ones want to dive deeper into collective motion and self-propelled particles: http://arxiv.org/abs/1010.5017 http://arxiv.org/abs/1010.5017
bhouston 12y ago
Somewhat related: ThreeJS GPU boids simulation http://threejs.org/examples/#webgl_gpgpu_birds http://threejs.org/examples/#webgl_gpgpu_birds
- fudged71 12y ago
  Okay now attach this code to drones
postnihilism 12y ago
I was inspired by this to create my own a few months ago. It uses a quadtree to optimize nearest neighbor lookup to ideally reduce complexity from n^2 to nlogn on each tick. http://jrhdoty.github.io/SwarmJS/ http://jrhdoty.github.io/SwarmJS/
- anoop-elias 12y ago
  Yes, looks beautiful. Quite similar, I guess. I had run in to some performance issues, the initial few ticks are quiet slow even now, esp. on a phone. This one uses a kdtree instead. I'll have to try quadtree and benchmark. Thanks.
  - repsilat 12y ago
    The best data structure to use depends a lot on what you're actually doing with your neighbours. If what you actually want to do is to have each boid be affected by each boid in a fixed-size neighbourhood, the best acceleration structure is actually just fixed-size bins.
    - anoopelias 12y ago
      Where can I read more about fixed-size bins?
      - repsilat 12y ago
        I mean if your world is 1024 by 768, and a boid is affected by all other boids within 64 pixels of it, you should just break the world up into 16 by 12 bins, each representing a 64 by 64 pixel block. Each of these blocks is just a growable array. All of a boid's "close enough" neighbours will be found in the 8-neighbourhood of its block.
        anoopelias 12y ago
        Yep got it. Thanks. Feels a good idea. Have to try it to know for sure.
fersaysrelax 12y ago
If you enjoy this kind of simulations, this is a good intro book. http://natureofcode.com/ http://natureofcode.com/
akilism 12y ago
Khan Academy has a good Natural Simulations in JS tract. https://www.khanacademy.org/computing/computer-programming/programming-natural-simulations https://www.khanacademy.org/computing/computer-programming/p... It uses processing.js when I worked through it I just ended up implementing everything with canvas and making my own versions of the processing specific classes and functions needed.
maaaats 12y ago
I think almost every AI-guy have tried making a boids simulation. They are such a good way to show emergent behavior from very simple rules. I'm a TA for an AI-course at my uni, and this semester my students had to program a boids simulation for the first project. In addition to what's shown here, the boids also had to avoid obstacles and flee from predators. I think the students liked it, it's very rewarding to code and actually see the result. The students also had to implement sliders, for how much cohesion, separation and alignment is weighted. It's pretty fun to change them and watch the behavior of the boids change.
- avyfain 12y ago
  Is the course content available online?
deleted 12y ago
[deleted]
14113 12y ago
Ah, Boids! One of my favorite examples of systems that can be "embarassingly parallel". I managed to write (with very little optimisation - not even using quadtrees to optimise neighbour lookup) a GPU accelerated version about a year ago that managed to stay above 30fps even up to about 5000 individual agents. It also hammered home the problem of device/host memory reigions which you've got to deal with when doing GPU programming. I found that other, simpler, systems didn't manage to get as much speedup as Boids did, as transferring data, not computation, was where they bottlenecked. With Boids, by contrast, I could keep everything (computation, and rendering) on the GPU, and never even have to touch the CPU, aside from calling various CUDA and OpenCL functions.
- M8 12y ago
  Can you really call them agents if they are calculated on GPU? I always assumed that using GPU would reduce them to particles (colour + position). They were probably stored in a huge array as values rather than a linked list of objects?
  - 14113 12y ago
    They were stored as values in a huge array. I fail, however, to see how that causes them to be distinguished from "agents"? Surely they still fulfil the properties required to be "agents" in an abstract sense? They gather information about their environment (the positions of other agents), deliberate (work out where to move to next), and then act (change their position). That process is entirely abstracted from the storage method of the agent data itself!
    - M8 12y ago
      What would happen if you need to add more properties/state to agents?
      - 14113 12y ago
        You'd have to change the program? Each agent was stored as a C structure - so adding further information to that would be trivial.
luddypants 12y ago
I don't think the fps calculation is quite accurate, I was getting close to 60 fps and seeing lots of jerks.
- anoopelias 12y ago
  I will have a look. The value initializes as 60, so it will show as 60 until it gets updated for the first time. Would that be what you are talking about? The initial few seconds performance is not at optimum so that is a problem. Are you on a laptop or a mobile/tablet device?
efkv 12y ago
Like everyone else it seems, I also wrote a 3D flocking simulation a while back: http://edkelleyv.com/Flocking/ http://edkelleyv.com/Flocking/ Source: https://github.com/ekelleyv/Flocking https://github.com/ekelleyv/Flocking

63 points by anoopelias 12y ago

deleted 12y ago

[deleted]

Nice! I've done something similar in the past: http://static.mysti.co.in/boids/ http://static.mysti.co.in/boids/ Source: https://github.com/tech-no-crat/boids https://github.com/tech-no-crat/boids

nacs 12y ago
If you use 'requestAnimationFrame()' instead of a 'setInterval()' for triggering your update method, your animation will perform a lot smoother: https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame https://developer.mozilla.org/en-US/docs/Web/API/window/requ...
- anoop-elias 12y ago
  Have a look at this one, highly recommended, https://github.com/hughsk/ticker https://github.com/hughsk/ticker

timdaub 12y ago

If you're into this kind of artificial life simulation, I can recommend you watching this talk: http://developertalks.tumblr.com/post/109998034809/simon-swain-deep-space-a-simulation-drama http://developertalks.tumblr.com/post/109998034809/simon-swa...

anoop-elias 12y ago
Excellent link. Thank you. I haven't looked deep in to these kind of simulations in general. Inspiration came from the Princeton Algortihms course in coursera.org. There is this sample problem, http://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/boids.html http://www.cs.princeton.edu/courses/archive/spr10/cos226/ass...

stared 12y ago

For ones want to dive deeper into collective motion and self-propelled particles: http://arxiv.org/abs/1010.5017 http://arxiv.org/abs/1010.5017

bhouston 12y ago

Somewhat related: ThreeJS GPU boids simulation http://threejs.org/examples/#webgl_gpgpu_birds http://threejs.org/examples/#webgl_gpgpu_birds

fudged71 12y ago
Okay now attach this code to drones

postnihilism 12y ago

I was inspired by this to create my own a few months ago. It uses a quadtree to optimize nearest neighbor lookup to ideally reduce complexity from n^2 to nlogn on each tick. http://jrhdoty.github.io/SwarmJS/ http://jrhdoty.github.io/SwarmJS/

anoop-elias 12y ago
Yes, looks beautiful. Quite similar, I guess. I had run in to some performance issues, the initial few ticks are quiet slow even now, esp. on a phone. This one uses a kdtree instead. I'll have to try quadtree and benchmark. Thanks.
- repsilat 12y ago
  The best data structure to use depends a lot on what you're actually doing with your neighbours. If what you actually want to do is to have each boid be affected by each boid in a fixed-size neighbourhood, the best acceleration structure is actually just fixed-size bins.
  - anoopelias 12y ago
    Where can I read more about fixed-size bins?
    - repsilat 12y ago
      I mean if your world is 1024 by 768, and a boid is affected by all other boids within 64 pixels of it, you should just break the world up into 16 by 12 bins, each representing a 64 by 64 pixel block. Each of these blocks is just a growable array. All of a boid's "close enough" neighbours will be found in the 8-neighbourhood of its block.
      - anoopelias 12y ago
        Yep got it. Thanks. Feels a good idea. Have to try it to know for sure.

fersaysrelax 12y ago

If you enjoy this kind of simulations, this is a good intro book. http://natureofcode.com/ http://natureofcode.com/

akilism 12y ago

Khan Academy has a good Natural Simulations in JS tract. https://www.khanacademy.org/computing/computer-programming/programming-natural-simulations https://www.khanacademy.org/computing/computer-programming/p... It uses processing.js when I worked through it I just ended up implementing everything with canvas and making my own versions of the processing specific classes and functions needed.

maaaats 12y ago

I think almost every AI-guy have tried making a boids simulation. They are such a good way to show emergent behavior from very simple rules. I'm a TA for an AI-course at my uni, and this semester my students had to program a boids simulation for the first project. In addition to what's shown here, the boids also had to avoid obstacles and flee from predators. I think the students liked it, it's very rewarding to code and actually see the result. The students also had to implement sliders, for how much cohesion, separation and alignment is weighted. It's pretty fun to change them and watch the behavior of the boids change.

avyfain 12y ago
Is the course content available online?

deleted 12y ago

[deleted]

14113 12y ago

Ah, Boids! One of my favorite examples of systems that can be "embarassingly parallel". I managed to write (with very little optimisation - not even using quadtrees to optimise neighbour lookup) a GPU accelerated version about a year ago that managed to stay above 30fps even up to about 5000 individual agents. It also hammered home the problem of device/host memory reigions which you've got to deal with when doing GPU programming. I found that other, simpler, systems didn't manage to get as much speedup as Boids did, as transferring data, not computation, was where they bottlenecked. With Boids, by contrast, I could keep everything (computation, and rendering) on the GPU, and never even have to touch the CPU, aside from calling various CUDA and OpenCL functions.

M8 12y ago
Can you really call them agents if they are calculated on GPU? I always assumed that using GPU would reduce them to particles (colour + position). They were probably stored in a huge array as values rather than a linked list of objects?
- 14113 12y ago
  They were stored as values in a huge array. I fail, however, to see how that causes them to be distinguished from "agents"? Surely they still fulfil the properties required to be "agents" in an abstract sense? They gather information about their environment (the positions of other agents), deliberate (work out where to move to next), and then act (change their position). That process is entirely abstracted from the storage method of the agent data itself!
  - M8 12y ago
    What would happen if you need to add more properties/state to agents?
    - 14113 12y ago
      You'd have to change the program? Each agent was stored as a C structure - so adding further information to that would be trivial.

luddypants 12y ago

I don't think the fps calculation is quite accurate, I was getting close to 60 fps and seeing lots of jerks.

anoopelias 12y ago
I will have a look. The value initializes as 60, so it will show as 60 until it gets updated for the first time. Would that be what you are talking about? The initial few seconds performance is not at optimum so that is a problem. Are you on a laptop or a mobile/tablet device?

efkv 12y ago

Like everyone else it seems, I also wrote a 3D flocking simulation a while back: http://edkelleyv.com/Flocking/ http://edkelleyv.com/Flocking/ Source: https://github.com/ekelleyv/Flocking https://github.com/ekelleyv/Flocking