Calculating distance based on radius can be expensive, due to the need for a sqrt() call, but you can replace that check with squaring the other side of the equation (i.e. compare x^2 + y^2 vs radius^2), which is not only faster, but often easily cacheable since you end up using this value multiple times.
Quadtrees (with tweaks) also work if you want to do gravitational calculations (planetary orbits, star systems). You can approximate masses far away being in single location in their quadtree address.
It should be possible for each boid to report if they have left a quad tree square. That could make a real time quad tree which has a lower performance overhead possible. It would be harder to implement though.
Probably one method could also be to generate circles that grow slowly, and only take into consideration the first "x" number of boids around you (or stop when circle reaches vision limit)
Yup, that was my first approach.. It still o(n^2) though as you need to check whos in the circle.. Combining it with the quadtree gives it a nice performance boost
Today I just came up with an algorithm for a dynamic quadtree and implemented it. Instead of rebuilding the quadtree each 100ms, it passes the moving boids around the nodes of the tree, and deletes useless children. I have two interchangeable implementations of a quadtree in the same project, dynamic and static. The static quadtree is 129 lines of code and the dynamic one is 187. I haven't tested the performance boost yet. I think it is much better, as it runs slightly faster (no hard data yet), and you do not loose any precision due to the limited rebuilding frequency.
This system lets you have more detail in areas where more is going on. If you used a fixed grid there would be more sections where needless computations are being made.
In the animation at 3:17, it looks like it's still storing points in the root node, instead of distributing them among the 4 new children nodes? not sure which way is correct
I’m not sure how easy it would be to do this in Java, but wouldn’t it work well to store pointers to the trees and which spatial location they are managing, so that when you need a new tree you can recycle an old, currently unused one instead of creating a new one?
bit late to this but on the object avoidance (not the predator), couldnt you have a portion of that view range (distance forward) (so in terms, if 'object' is closer then ___ and further then ___ from "boid/me",) to have the boid move slower before completely turning away or going around the object, to give more realism to the object avoidance, and avoid the disjointed "forcefield" effet you currently have (not that forcefields arnt cool) so you end up with the boid growing slower when they get closer to an object they dont wanna crash into, and if they get too close then they avoid.
yup, good idea.. I ended up just reducing the weight assigned to the avoidance factor for non boid objects.. If I drop it low enough they swoop around it instead of bouncing off it.
Another thing you could do especially for really large flocks would be to give up on exact calculations, and only check a random sample of boids for neighbors.
What if instead of searching boids every frame from grid, the boids remembered their neighbors and only look at them until they are too far? And always try to have at least like 6-12 remembered neighbors, so that they collide less likely
@@sebastianjost If the distance is small enough, count of remembered high enough, then unlikely - all the possible spaces nearby would be occupied, and for new ones to come near, some would have to go. Those on the edges of boids will guard the insides.
@@overloader7900 What about those boids who *are* on the edges? In a tight cluster, sure, the interior ones are surrounded, but the exterior ones by definition are not, but still have their full allotment of "nearest neighbors". If two such clusters drift close together, neither will be capable of detecting the other if they stop checking after checking only their "known neighbors". Also, what about a simulation with a far greater number of immobile objects -- e.g., birds flying through a forest; immobile objects by their nature are not going to be persistent "nearest neighbors" of any of the boids. How does a tight cluster of boids detect them? I'm genuinely curious how your scheme would handle these. Thanks.
Some of my vid's are just smaller components of larger projects.. So they won't all have a direct AI element; but thats the general thrust of this channel..
Calculating distance based on radius can be expensive, due to the need for a sqrt() call, but you can replace that check with squaring the other side of the equation (i.e. compare x^2 + y^2 vs radius^2), which is not only faster, but often easily cacheable since you end up using this value multiple times.
Brilliant solution
this is only true for much older computers, but in normal ones the square root instruction takes only a few cpu cycles
Isn’t there silicon dedicated on the cpu these days to fast sqrt operations?
@@fwame6187 not convinced sqrt isnt slower than multiplying
@@chrstfer2452 depends on whether you are using a compute shader to do an obsene number of them for ray calc or shader physics
Quadtrees (with tweaks) also work if you want to do gravitational calculations (planetary orbits, star systems). You can approximate masses far away being in single location in their quadtree address.
good to know.. I'm going to mock up a sim of the solar system and see if an AI can plot a course to mars..
Excellent !!! The coding train advice is spot on as well.
Glad it was helpful!
I love the quality of these videos - very simple yet entertaining!
Glad you like them!
The quadtree grid looks really neat in real time.
its one of the reasons I made it.. It does look really good.. and its fast
I don't think I knew about quadtrees, turns out they are really, really NEAT!
Yup, they're probably my favorite for Boids.. and with lots of other applications..
It should be possible for each boid to report if they have left a quad tree square. That could make a real time quad tree which has a lower performance overhead possible. It would be harder to implement though.
Probably one method could also be to generate circles that grow slowly, and only take into consideration the first "x" number of boids around you (or stop when circle reaches vision limit)
Yup, that was my first approach.. It still o(n^2) though as you need to check whos in the circle.. Combining it with the quadtree gives it a nice performance boost
I've noticed you referring to what seems to be JavaScript as Java for some reason in several videos, are you aware of this mistake?
Today I just came up with an algorithm for a dynamic quadtree and implemented it. Instead of rebuilding the quadtree each 100ms, it passes the moving boids around the nodes of the tree, and deletes useless children.
I have two interchangeable implementations of a quadtree in the same project, dynamic and static. The static quadtree is 129 lines of code and the dynamic one is 187. I haven't tested the performance boost yet.
I think it is much better, as it runs slightly faster (no hard data yet), and you do not loose any precision due to the limited rebuilding frequency.
very nice, its on my list of things to do.. It was just easier to blank it and rebuild..
Add more and more boids. It's unaboidable.
Again, some lovely helpful thought shared here, thanks!
Glad it was helpful!
What is the advantage over using a fixed grid? Would that not reduce the amount of calculation that is needed?
This system lets you have more detail in areas where more is going on. If you used a fixed grid there would be more sections where needless computations are being made.
Love your vids lad!
Thanks for the feedback !
Great video again!
Thanks again!
In the animation at 3:17, it looks like it's still storing points in the root node, instead of distributing them among the 4 new children nodes? not sure which way is correct
Pretty sure that's an error in the video as storing in the root doesn't do anything good.
Yay, I'm famous now! 2:23
Wow, just wow
Quadtree boids
Take me home
To the place
Where I can code
I’m not sure how easy it would be to do this in Java, but wouldn’t it work well to store pointers to the trees and which spatial location they are managing, so that when you need a new tree you can recycle an old, currently unused one instead of creating a new one?
Your videos are very interesting
Glad you like them!
@@neatai6702 I also used rtNEAT for my master thesis, it's nice to see a channel called NEAT :)
Spatial hash or layered spatial hash is gonna be a lot faster for this since it doesn't have expensive inserts.
bit late to this but on the object avoidance (not the predator), couldnt you have a portion of that view range (distance forward) (so in terms, if 'object' is closer then ___ and further then ___ from "boid/me",) to have the boid move slower before completely turning away or going around the object, to give more realism to the object avoidance, and avoid the disjointed "forcefield" effet you currently have (not that forcefields arnt cool)
so you end up with the boid growing slower when they get closer to an object they dont wanna crash into, and if they get too close then they avoid.
yup, good idea.. I ended up just reducing the weight assigned to the avoidance factor for non boid objects.. If I drop it low enough they swoop around it instead of bouncing off it.
No joke today i started implementing NEAT and was wondering about this exact problem of O(n²) and looked into quadtrees
Great.... Spatial hashing is even quicker O(n).. I'm doing a video on that at the moment..
Nice
Javascript and Java are not the same, by a long margin.
👍
Another thing you could do especially for really large flocks would be to give up on exact calculations, and only check a random sample of boids for neighbors.
That could even be faster than the quadtree method in some cases, given a large enough flock.
at 1:51 you confused java and javascript, which is unacceptable
What if instead of searching boids every frame from grid, the boids remembered their neighbors and only look at them until they are too far? And always try to have at least like 6-12 remembered neighbors, so that they collide less likely
How would you handle new voids coming close with that method?
You can't remember them if they were never close to each other before.
@@sebastianjost Only search for new neighbor boids if the old ones went too far?
@@overloader7900 but new voids can come close without others getting further away.
Think of two groups meeting.
@@sebastianjost If the distance is small enough, count of remembered high enough, then unlikely - all the possible spaces nearby would be occupied, and for new ones to come near, some would have to go. Those on the edges of boids will guard the insides.
@@overloader7900 What about those boids who *are* on the edges? In a tight cluster, sure, the interior ones are surrounded, but the exterior ones by definition are not, but still have their full allotment of "nearest neighbors". If two such clusters drift close together, neither will be capable of detecting the other if they stop checking after checking only their "known neighbors". Also, what about a simulation with a far greater number of immobile objects -- e.g., birds flying through a forest; immobile objects by their nature are not going to be persistent "nearest neighbors" of any of the boids. How does a tight cluster of boids detect them? I'm genuinely curious how your scheme would handle these. Thanks.
Provide source code please
And where's the AI here?
Some of my vid's are just smaller components of larger projects.. So they won't all have a direct AI element; but thats the general thrust of this channel..
Am I early?