0

I have a boids flocking simulation setup. It originally worked by having every boid loop through every boid so that they all constantly know where each other are at in order to tell if they are close or far away, but then I switched to a quadtree design so that boids only have to loop through boids that are actually nearby. However, it has made virtually no improvement to the simulation's FPS. It's as if I'm still looping through every single boid.

Is there some mistake in my implementation? Repo is here, relevant code is mostly in main.js, quadtree.js, and boid.js. LIve site is here

Michael Moreno
  • 947
  • 1
  • 7
  • 24
  • 1
    So... if the little buggers are moving, you have to re-create the quad-tree for each frame? – enhzflep May 01 '21 at 22:23
  • Correct, I recreate the quadtree every frame. – Michael Moreno May 01 '21 at 22:32
  • @Ouroborus do you know any methods that would work well with moving objects like boids? – Michael Moreno May 01 '21 at 22:42
  • @Ouroborus - For the sake of correctness, I think you meant to say that using distance squared rather than distance removes a SQRT operation, right? – enhzflep May 02 '21 at 02:33
  • 1
    @Ouroborus You mention the quadtree being constructed every frame which negates its usefulness; I don't think this is true. For a single frame, if you put everything in to a quadtree, each boid will have to do less neighbor-checking for that frame, thanks to the spatial partitioning of the quadtree. The question is whether the savings on neighbor-checking outweighs the construction of a quadtree. If you profile his code you'll realize your wager is wrong. The vast majority of the time is spent querying the quadtree and quadtree construction is comparatively insignificant. – ldlework May 02 '21 at 04:54
  • @Ouroborus You're not correct, and I've explained why in an answer. – ldlework May 02 '21 at 13:09
  • 1
    FYI, I wrote an answer about using spatial data structures with boids or other multi-agent simulations over here: https://stackoverflow.com/a/68122142/1991373 – Craig Reynolds Jun 26 '21 at 17:33

1 Answers1

4

The reason why you are not seeing obvious performance gains from the Quadtree is because of the nature of your simulation. Currently, the default separation causes a large number of boids to "converge" to the same position.

Lots of objects in the same position is going to negate possible speedups due to spatial partitioning. If all the objects are in the same or near position, boids in the area a forced to check against all other boids in the area.

You can demonstrate to yourself that your Quadtree is working by watching or profiling your application with its default settings. Now turn separation up to maximum. You will see visually, or through profiling, that as the boids spread out more evenly, the FPS increases significantly. This is because the Quadtree can now prevent computations thanks to its spatial partitioning.

With default low separation: With low separation

With maximum separation: With maximum separation

You can see how performance is increased in the second image. Also note, that the conjecture by another commentor that it is the construction of the Quadtree (insert) that is taking up all the time is wrong.

While in some applications you may be able to update a Quadtree as things move around, since in this simulation every constituent moves every frame, reconstructing the Quadtree from scratch is less work, then taking every object out and reinserting it into its new position.

The advice to skip square-rooting and just use the distance-squared is good though as this will get you a bit more performance.

ldlework
  • 187
  • 1
  • 8