Hi,
I'm looking for space partitioning structure which will be good for moving points and will enable fast fixed radius near neighbors search.
Space partitioning for flocking
Well, you could use binary space partitions or quadtree's, which are probably easier for 2d things, or even octrees which are easier to use with 3d things.
Or, you can just use a grid, when each cell in the grid has a pointer to the objects in it, the objects only have to check for collisions with objects that are in the same cell.
Or, you can just use a grid, when each cell in the grid has a pointer to the objects in it, the objects only have to check for collisions with objects that are in the same cell.
A simple grid is what I would try first, they're the easiest thing to implement and often very effective (especially for uniform size/fixed radius).
See Ericson's Real-Time Collision Detection for a terrific chapter on various ways to implement and use grids.
See Ericson's Real-Time Collision Detection for a terrific chapter on various ways to implement and use grids.
I second the grid, since presumably your objects are all the same size and you can tune the size of the grid cells.
Author
But with grid I would need to search 9 cells right? And what if I would need different radius in future? Anyway I'll test the grid thing. I should also mention that this its in 2d and I'm just using points if that helps in some case.
9 is pretty arbitrary. Whatever size grid works well. The key is that the grid is only for reducing the candidates for comparison, not doing the actual comparison. Say you have a flock of 64 objects. If you use a grid of size 8 by 8, on average there will be 1 object per cell (obviously for flocking some cells would have more). Based on this average you would need to do distance checks for the objects in a cell with the contents of that cell and the directly neighbouring cells too. So around 8 distance comparisons per cell. Which may seem like a lot, but still miles better than comparing every object to every other object.
Excuse my late-night mathematics skills if there are errors. ;)
Excuse my late-night mathematics skills if there are errors. ;)
Alternatively, skip the partitioning and instead only do a fixed number of distance checks at all. There's research that real flockers (i.e. birds, fish) do that same thing too. Not sursprising if you think about it, a fish brain isn't so terribly huge.
Looking at half a dozen randomly selected (not necessarily nearest) neighbours pretty accurately simulates real flocking.
Looking at half a dozen randomly selected (not necessarily nearest) neighbours pretty accurately simulates real flocking.
I don't think that 3*3 = 9 is an arbitrary number any more than 3*3*3 = 27 is... As long as the sphere's radius is less than or equal to the cell size.
But with grid I would need to search 9 cells right? And what if I would need different radius in future? Anyway I'll test the grid thing. I should also mention that this its in 2d and I'm just using points if that helps in some case.
No, you only need to check for collision in the 4 neighbouring cells with a higher number. That is the neighbour to the right and the three neighbours below (assuming cell 0 is top left corner and last cell is bottom right corner).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
