4 ms·

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

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.
        repsilat 12y ago
        One important thing to note while implementing it is that you have to be a little smart about how you move boids from one bin to another. You don't want to get quadratic behaviour because you're removing individual boids from the middle of lists again and again, you don't want to accidentally move a boid twice in an iteration and so on. The best way to do this is to make a list of "boids to add" and "boids to delete" for each bin, which you build as you call "move", and which you apply after you've done your movement calculations on all of your boids.
        anoopelias 12y ago
        There are a few ways to be clever on going about it. One as you mentioned is to do a two phase scan one to move and one to correct the bins. Also instead of a square shaped range you can get a hexagonal range by dividing corner boxes diagonally to two and then checking which half of square the boid is. :)

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.
      - repsilat 12y ago
        One important thing to note while implementing it is that you have to be a little smart about how you move boids from one bin to another. You don't want to get quadratic behaviour because you're removing individual boids from the middle of lists again and again, you don't want to accidentally move a boid twice in an iteration and so on. The best way to do this is to make a list of "boids to add" and "boids to delete" for each bin, which you build as you call "move", and which you apply after you've done your movement calculations on all of your boids.
        anoopelias 12y ago
        There are a few ways to be clever on going about it. One as you mentioned is to do a two phase scan one to move and one to correct the bins. Also instead of a square shaped range you can get a hexagonal range by dividing corner boxes diagonally to two and then checking which half of square the boid is. :)