"as the number of calculations needed each frame increases exponentially with the number of boids" O(n^2) is a polynomial runtime (quadratic), *not* exponential. Exponential is O(2^n), which is drastically worse than the worst case boids algorithm.
I came here hoping to learn a new way to accelerate my just-for-fun physics code, and left realizing that I had accidentally reinvented spatial hashing on my own.:P
I wish every single CS video on YT would have referenced as many good papers as you have done here, Sr. Well done; this is just what I was looking for!
In this particular case, because you know the maximum number of entries in the hash table and the maximum number of buckets in the hash table, you could structure the the table's buckets as an array of linked list heads. The nodes would be allocated directly within the boids as a 'next' pointer. With that, you should be able to run the spatial partitioning and boid simulation on multiple cores or even on your gpu if you have one. Because every bucket would always be allocated (though some would be empty), finding the neighboring cells would be as simple as adding or subtracting width to go up/down, and 1 to go left/right. With a method similar to what I described, I was able to simulate and render with lighting and shadows 100000 3D boids blended with sphere collision and 2D pathfinding while maintaining +80fps on my NVIDIA GeForce RTX 2060.
@@neatai6702 What I've described is really just a strange combination of a few types of collections so I don't think any links I provide will really get the core of the idea. I can create something similar for you to reference if you're interested.
I don't like how hashing approaches are called O(N). It's not true; the logarithm is still there, it's just hidden behind large enough constant somewhere. It's kind of like if we say that our O(N log N) sort is effectively O(N) because log(N) will never exceed 64.
Big-O notation is all about the dominant term. Take your second example, and replace "log N" with the worst case, "64". What's the Big-O notation for "O(N * 64)" ? It is exactly O(N), because N * 64 scales in exactly the same way as just N. For your first example, you reveal the key yourself, with the phrase "large enough constant"; when the constant is large enough (or the "log N" term small enough -- it's all about relative sizes), then the "log N" term is lost in the magnitude of the "N" term. Big-O notation is all about the dominant term.
Maybe it's my imagination, but it seems like there might be emergent grid artifacting in the final implementation. I'd be curious to see a side-by-side comparison against the painstakingly slow O(n^2) implementation. In theory, they should yield identical results aside from the performance penalty, but it would demonstrate proof of the spatial hash approach being correct, and/or highlight any subtle quirks/imperfections (if any) of the optimized method.
NEAT! Have you compared the performance to the QuadTree approach? I read somewhere that QuadTree is faster for clustered objects and spatial hashing is better for uniformly distributed objects.
Hi, I've read that as well but for Boids the hash method is about 2 times faster. I meant to include a comparison section but just ran out of time.. That said, theres just something very elegant about a Quadtree..
@@neatai6702 Something that just occurred to me is that a hybrid data structure may be the best of both worlds: What I mean by that is some kind of data structure similar to a quadtree, except each node divides recursively into an N by N grid of smaller, spatially hashed squares, rather than a 2 by 2 grid. It would be likely be faster to construct than a quadtree, owing to the fact that it goes fewer layers deep. It would handle densely-packed areas more effectively while being somewhat better at weeding out sparse areas. Of course this is just speculation so I could easily be wrong here.
@@Radian628 The thing is I don't think the algorithm really does a nearest neighbor search but instead makes sure it is at least X distance from all other boids. Therefore the spatial hashing is likely better for his algorithm since he just does a loop on all items within X range. A quadtree would likely be more comparable if his algorithm didn't use a significant portion of the boids in each grid square, but given his search radius is generally larger than a single grid square it is likely spatial hashing at the top level is best with little benefit to an additional quadtree approach. Essentially for the boxcast / circlecast check with size near the grid size, spatial hashing is pretty effecient.
I implemented this yesterday, well similar to it. I used the pivot table idea to avoid a list in each cell. You can multithread the building of the structure using _interlockedincrement and _interlockeddecrement. I was able to populate the structure with 1,000,000 objects in about 14ms on my PC, which isn't too shabby.
Would be nice now to show the process of tweaking this method so that it performs as well as the quad tree, because it felt less fluid than the quad tree approach. It might just be a frame rate issue if the distance travelled by a boid between two frames is a not a function of the time between those two frames
Is the "Neat AI" that makes these videos a human, or an intelligent talking computer program? The video naming convention makes me unsure of the answer.
I was also thinking about using hex cells instead of a grid of square cells. Then the comparison would be with only 6 neighbours, not 8. I haven't worked out what the hash function would be for that yet.
I have a version that does just that.. Not only does the boid know its own cell ref. but also the cell ref. of its eight neighbors, so it'll use the boids in those as well.. It really depends on the size of the cells as to how necessary this is, but it works well..
@Neat AI Thanks for another interesting and educational video. But I can't "help" but think that these boids look a bit "erratic" in their movements. Is this because they only "check and adapt" to boids in their own "grid-cell" ? Which (as far as I understand) means that whenever a "apparent flock" is "bisected" by a (invisible) "cell border" that "apparent flock" no longer "behaves" like a "coherent flock", but rather it has become "split" into smaller flocks. Where the some "apparently adjacent" boids that "appear to be in the same flock" don't move as a flock, due to them being in different "grid-cells". So they instead "flock" (move together) with other more distant boids simply because these, although more distant are within the same "grid-cell"... Or am I misunderstanding something ? Best regards.
I see no point in the "hash table" being 1D. It's a 2D grid and you need to know what the neighbor cells of the grid are, so that 2D structure is relevant. So just use a 2D array with indices row = floor(x/width), col = floor(y/width). Seems like using a 1D "hash table" is needlessly obscuring the obvious, perhaps to make the paper sound more impressive than it is. Also, with constant grid cell size, it is not adaptive like the quad tree, and you can run into the N^2 performance issues if too many boids clump up in a single grid cell. Depending on the rules of boid movement, this may never happen, but is very simulation dependent.
Because when you extend to higher dimensions and create bigger grids, you end up with a big structure mostly full of nothing. The hash table gets created every frame and only contains the nodes that have something in them. This also speeds up neighbour lookups when the neighbour is empty. The hashset (or dictionary or whatever) will very quickly tell you if a cell exists and if it doesn't then you know it's empty.
And as for your second issue, if the boids are clumped together then the n^2 tests are essential for the behaviour. What the grid helps eliminate are the unnecessary tests for distant boids.
@@merseyviking Watch the video again, pay attention to both the code and the diagrams. All width^2 cells exist, including the empty ones. The example is a 4x4 grid resulting in a a 1D array of 16 "buckets", most of which are empty (presumably containing null points for empty lists, though the specific representation does not matter). The index (hash) for this array is just [x/w]*w + [y/w], where [] means "floor", which, under the hood, is exactly how memory address offsets for elements of a 2D array are calculated if we also multiply by the #bytes per cell. In normal implementations of hash tables, all the of the "buckets" exist, empty or not. And a hash function usually has a pseudo-random relationship to whatever key data it is calculated from, not such a structured relationship. Calling this a hash table is superfluous.
@@merseyviking re: 2nd issue. The point of avoiding tests for distant bots is precisely to avoid the order N^2 run time. After all the point of the N^2 tests is to calculate distance to know which boids are closest. If they clump up in a single cell, you lose the advantage of this technique and the simulation bogs down. Adaptive methods such as quad tree or variable metric grid avoid this problem by focusing more and smaller cells to divide up the densest clumps and fewer larger cells for the emptiest regions. This is done at the cost of greater overhead for managing the variable cell structure, but with large number of boids (and depending on their rules of motion) avoiding the N^2 processing that may happen with clumps is worth it. For the example shown here, the rules governing the boid movement prevents them from clumping too much, so it does fine. But if you change the boid rules so they like to fly much closer together, then it would bog down. You have to tune the boid rules, number of boids, and grid spacing to get this running efficiently.
On the issue of clumping.. I've coded it so when a boid is checking the table to see who its neighbors are, its capped at 5 neighbours.. so even if there are 100 boids in the same cell.. it doesn't slow it down..
It could look interesting if you gave the boyds something they were attracted to - like birds landing on a tree. They could stick around there until a predator came to rouse them.
"as the number of calculations needed each frame increases exponentially with the number of boids"
O(n^2) is a polynomial runtime (quadratic), *not* exponential. Exponential is O(2^n), which is drastically worse than the worst case boids algorithm.
was just waiting for someone to call me out on that.. Thanks for the clarification..!
I came here hoping to learn a new way to accelerate my just-for-fun physics code, and left realizing that I had accidentally reinvented spatial hashing on my own.:P
Lol
same.. its just the obvious thing to do when you want to speed things up..
Yeah I've always just called it "I make a grid that remembers where all the particles are".
I wish every single CS video on YT would have referenced as many good papers as you have done here, Sr. Well done; this is just what I was looking for!
Minute 4 of this video was an amazingly clear explanation for hashing of 2D spatial positions.
Thanks LF !
In this particular case, because you know the maximum number of entries in the hash table and the maximum number of buckets in the hash table, you could structure the the table's buckets as an array of linked list heads. The nodes would be allocated directly within the boids as a 'next' pointer. With that, you should be able to run the spatial partitioning and boid simulation on multiple cores or even on your gpu if you have one. Because every bucket would always be allocated (though some would be empty), finding the neighboring cells would be as simple as adding or subtracting width to go up/down, and 1 to go left/right. With a method similar to what I described, I was able to simulate and render with lighting and shadows 100000 3D boids blended with sphere collision and 2D pathfinding while maintaining +80fps on my NVIDIA GeForce RTX 2060.
I'll have to give that a go.. Any references or websites you based this on ?
@@neatai6702 What I've described is really just a strange combination of a few types of collections so I don't think any links I provide will really get the core of the idea. I can create something similar for you to reference if you're interested.
I like the simplicity of the spatial hashing.
I don't like how hashing approaches are called O(N). It's not true; the logarithm is still there, it's just hidden behind large enough constant somewhere. It's kind of like if we say that our O(N log N) sort is effectively O(N) because log(N) will never exceed 64.
Big-O notation is all about the dominant term. Take your second example, and replace "log N" with the worst case, "64". What's the Big-O notation for "O(N * 64)" ? It is exactly O(N), because N * 64 scales in exactly the same way as just N. For your first example, you reveal the key yourself, with the phrase "large enough constant"; when the constant is large enough (or the "log N" term small enough -- it's all about relative sizes), then the "log N" term is lost in the magnitude of the "N" term. Big-O notation is all about the dominant term.
Nice and clear tutorial. I used this method for open world multiplayer server.
I think I just found my new favorite CZcams channel
Woah this is such an underrated channel.
may i ask what do you program these beautiful representations in?
Lots of programs.. I'm always messing about with java, processing, c#
@@neatai6702 very nice
This doesn't seem to flow as nicely as the quadtree.
Maybe it's my imagination, but it seems like there might be emergent grid artifacting in the final implementation.
I'd be curious to see a side-by-side comparison against the painstakingly slow O(n^2) implementation. In theory, they should yield identical results aside from the performance penalty, but it would demonstrate proof of the spatial hash approach being correct, and/or highlight any subtle quirks/imperfections (if any) of the optimized method.
NEAT! Have you compared the performance to the QuadTree approach? I read somewhere that QuadTree is faster for clustered objects and spatial hashing is better for uniformly distributed objects.
Hi, I've read that as well but for Boids the hash method is about 2 times faster. I meant to include a comparison section but just ran out of time.. That said, theres just something very elegant about a Quadtree..
@@neatai6702 Something that just occurred to me is that a hybrid data structure may be the best of both worlds: What I mean by that is some kind of data structure similar to a quadtree, except each node divides recursively into an N by N grid of smaller, spatially hashed squares, rather than a 2 by 2 grid. It would be likely be faster to construct than a quadtree, owing to the fact that it goes fewer layers deep. It would handle densely-packed areas more effectively while being somewhat better at weeding out sparse areas. Of course this is just speculation so I could easily be wrong here.
@@Radian628 The thing is I don't think the algorithm really does a nearest neighbor search but instead makes sure it is at least X distance from all other boids. Therefore the spatial hashing is likely better for his algorithm since he just does a loop on all items within X range. A quadtree would likely be more comparable if his algorithm didn't use a significant portion of the boids in each grid square, but given his search radius is generally larger than a single grid square it is likely spatial hashing at the top level is best with little benefit to an additional quadtree approach. Essentially for the boxcast / circlecast check with size near the grid size, spatial hashing is pretty effecient.
Can you please link the papers in the description?
I implemented this yesterday, well similar to it. I used the pivot table idea to avoid a list in each cell. You can multithread the building of the structure using _interlockedincrement and _interlockeddecrement. I was able to populate the structure with 1,000,000 objects in about 14ms on my PC, which isn't too shabby.
So close yet so far. You need a smaller grid the boids are in a checkerboard pattern. Looks bad compared to the quad tree
Would be nice now to show the process of tweaking this method so that it performs as well as the quad tree, because it felt less fluid than the quad tree approach.
It might just be a frame rate issue if the distance travelled by a boid between two frames is a not a function of the time between those two frames
yup.. I've always preferred the quadtree.. and its performance is generally on par with the hashing approach
Is the "Neat AI" that makes these videos a human, or an intelligent talking computer program? The video naming convention makes me unsure of the answer.
I would like to see someone add little blasters to them and make them Dogfight.
I was also thinking about using hex cells instead of a grid of square cells. Then the comparison would be with only 6 neighbours, not 8. I haven't worked out what the hash function would be for that yet.
Any chance you can link the papers?
I'm in the weeds of this right now and it would definitely help
Am I missing something or you didn't explain how to go from O((n/16)^2) to O(n)??
I'd be really interested to see the effects of a turn rate limitation for the boids, either predator, prey, or both
good idea... I'll add it to the list of improvements
What happens when boids are right next to another cell? Are they checking the cells all around the current cell they exist in?
I have a version that does just that.. Not only does the boid know its own cell ref. but also the cell ref. of its eight neighbors, so it'll use the boids in those as well..
It really depends on the size of the cells as to how necessary this is, but it works well..
Is there a repo of this code available?
@Neat AI
Thanks for another interesting and educational video. But I can't "help" but think that these boids look a bit "erratic" in their movements. Is this because they only "check and adapt" to boids in their own "grid-cell" ?
Which (as far as I understand) means that whenever a "apparent flock" is "bisected" by a (invisible) "cell border" that "apparent flock" no longer "behaves" like a "coherent flock", but rather it has become "split" into smaller flocks. Where the some "apparently adjacent" boids that "appear to be in the same flock" don't move as a flock, due to them being in different "grid-cells". So they instead "flock" (move together) with other more distant boids simply because these, although more distant are within the same "grid-cell"...
Or am I misunderstanding something ?
Best regards.
I see no point in the "hash table" being 1D. It's a 2D grid and you need to know what the neighbor cells of the grid are, so that 2D structure is relevant. So just use a 2D array with indices row = floor(x/width), col = floor(y/width). Seems like using a 1D "hash table" is needlessly obscuring the obvious, perhaps to make the paper sound more impressive than it is.
Also, with constant grid cell size, it is not adaptive like the quad tree, and you can run into the N^2 performance issues if too many boids clump up in a single grid cell. Depending on the rules of boid movement, this may never happen, but is very simulation dependent.
Because when you extend to higher dimensions and create bigger grids, you end up with a big structure mostly full of nothing. The hash table gets created every frame and only contains the nodes that have something in them. This also speeds up neighbour lookups when the neighbour is empty. The hashset (or dictionary or whatever) will very quickly tell you if a cell exists and if it doesn't then you know it's empty.
And as for your second issue, if the boids are clumped together then the n^2 tests are essential for the behaviour. What the grid helps eliminate are the unnecessary tests for distant boids.
@@merseyviking Watch the video again, pay attention to both the code and the diagrams. All width^2 cells exist, including the empty ones. The example is a 4x4 grid resulting in a a 1D array of 16 "buckets", most of which are empty (presumably containing null points for empty lists, though the specific representation does not matter). The index (hash) for this array is just [x/w]*w + [y/w], where [] means "floor", which, under the hood, is exactly how memory address offsets for elements of a 2D array are calculated if we also multiply by the #bytes per cell.
In normal implementations of hash tables, all the of the "buckets" exist, empty or not. And a hash function usually has a pseudo-random relationship to whatever key data it is calculated from, not such a structured relationship. Calling this a hash table is superfluous.
@@merseyviking re: 2nd issue. The point of avoiding tests for distant bots is precisely to avoid the order N^2 run time. After all the point of the N^2 tests is to calculate distance to know which boids are closest. If they clump up in a single cell, you lose the advantage of this technique and the simulation bogs down.
Adaptive methods such as quad tree or variable metric grid avoid this problem by focusing more and smaller cells to divide up the densest clumps and fewer larger cells for the emptiest regions. This is done at the cost of greater overhead for managing the variable cell structure, but with large number of boids (and depending on their rules of motion) avoiding the N^2 processing that may happen with clumps is worth it.
For the example shown here, the rules governing the boid movement prevents them from clumping too much, so it does fine. But if you change the boid rules so they like to fly much closer together, then it would bog down. You have to tune the boid rules, number of boids, and grid spacing to get this running efficiently.
On the issue of clumping.. I've coded it so when a boid is checking the table to see who its neighbors are, its capped at 5 neighbours.. so even if there are 100 boids in the same cell.. it doesn't slow it down..
It could look interesting if you gave the boyds something they were attracted to - like birds landing on a tree. They could stick around there until a predator came to rouse them.
I've seen that done as well. they can land on the ground until disturbed...
Like 400 and comment 42.