2D collision detection, 1000+ entities, very large area - quadtree?
Author
I need to implement efficient collision detection in a 2D game. Factors to consider:
1. I'd like to support a large number of dynamic entities, 1000-plus if possible (but I'll take what I can get). They all need to be tested each update. There will be very few (if any) static collidable objects.
2. Most entities can collide with most others (i.e., very few collision pairs that can be ignored).
3. The entities will often be clustered (with frequent collisions in a cluster), but the playing area is very large, so there will be great distances between clusters.
4. There won't be much variance in size of entities. There may be just a few entities larger than most, but I can implement these as a collection of smaller collision objects if necessary.
5. Most entities' actual collision primitive is a circle (and those that aren't can use a bounding circle for the initial test, of course).
6. Entities will be destroyed and new entities spawned frequently.
Given these factors, what would be my best pruning/space partitioning/whatever scheme?
I don't think a uniform grid is a good option, because of the very large area. It would take a lot of memory, with a very tiny percentage of the cells actually occupied. Or could I allocate cells as needed, keeping them (with their position) in a list? The list would need some fast hashing of some kind, to look up a cell by its x,y grid position.
I've considered recursive dimensional clustering, but I think some of the clusters would be too large for that to be efficient.
I'm thinking a quadtree might be my best option, but I have some questions about the best way to implement this. Again, due to the large area, the quadtree probably shouldn't be generated in its entirety up front. I'll have to add nodes as needed.
Should I generate the tree from scratch each update? Or keep the tree persistent, and have entities remove and add themselves to nodes as they move, adding nodes on demand and removing empty ones?
When an entity would straddle two or four child nodes, should I keep it in the parent node, or put it in both (or all four) child nodes? The problem I have with keeping it in the parent is that my main root node would have all the entities that straddle its two dividing axes, which could be a lot of entities (too many to reasonably do a n^2 test on).
Any tips or insights on this will be greatly appreciated.
For my game I use a grid. It works much better and faster than a quadtree. Basically because of the grid transversal. Quadtrees are very bad with moving objects. I use relatively large maps and I find sacrificing the RAM is worth it.
Inserting with an AABB is extremely quick with a grid. Not so quick with a quadtree. Also quadtrees tend to be mainly for static objects. Not sure what gave you the idea that a quadtree would be good for this situation...
also with a grid if your circle boundaries are smaller than a grid size then you can use a loose leaf grid by only inserting the object's center point and performing checks on 9 grids.
Inserting with an AABB is extremely quick with a grid. Not so quick with a quadtree. Also quadtrees tend to be mainly for static objects. Not sure what gave you the idea that a quadtree would be good for this situation...
also with a grid if your circle boundaries are smaller than a grid size then you can use a loose leaf grid by only inserting the object's center point and performing checks on 9 grids.
A sparse grid is a possible solution if the world is so big that a normal grid would use too much memory. Just use the coordinates as the indexes into a map containing the buckets of entities in each grid cell. Grids are great as long as entities are all about the same size. Even with different sizes, you can use multiple grids with different resolutions. A quadtree can be adapted to work just like multiresolution spatial hashing, and then people call it a loose quadtree.
Make the cells in the grid as wide as the diameter of the largest object. Now no object can occupy more than 4 cells simultaneously, and for something to collide with a given object it must be in one of the 9 cells surrounding or containing that object. There are a few ways the data structure and collision detection could work: store each object in just one cell and then check the nine adjacent cells for collision checks; store each object in nine cells and only look at one cell; store each object in four cells and look at four cells.
Make the cells in the grid as wide as the diameter of the largest object. Now no object can occupy more than 4 cells simultaneously, and for something to collide with a given object it must be in one of the 9 cells surrounding or containing that object. There are a few ways the data structure and collision detection could work: store each object in just one cell and then check the nine adjacent cells for collision checks; store each object in nine cells and only look at one cell; store each object in four cells and look at four cells.
heres what i do with a similar thing but for 3d
devide your scene up into X*Y quads each say 100x100 meters
each frame iterate over the moving objects place them in the quadtree node theyre contained in (very quick to do)
+ then each frame whenever u want to do collision detection (or neighbour advoidment etc)
just check the quad its in (+ possibly the surrounding quads also)
devide your scene up into X*Y quads each say 100x100 meters
each frame iterate over the moving objects place them in the quadtree node theyre contained in (very quick to do)
+ then each frame whenever u want to do collision detection (or neighbour advoidment etc)
just check the quad its in (+ possibly the surrounding quads also)
Another way to handle this is to keep a sorted list of object ranges [min, max) and update those each frame. The theory behind this is, that once sorted, the number of changes per frame are small compared to the number of objects in the world so the amount of work required to keep the list sorted is also small.
For collision detection, you simply "walk" across an axis gathering clusters of objects and then determine the intersection of the clusters on each axis.
Within those clusters you then perform your "classic" collision detection routines.
This solves the following issues:
- Large scale world, relatively few objects, so grid-based solutions are costly.
- As long as object movement is relatively small per frame, the number of updates required to re-sort the list for each axis is also very small.
For even larger amounts of objects, you could implement a tree-variant of this structure which (I believe) is called a "2-D Range Tree".
For collision detection, you simply "walk" across an axis gathering clusters of objects and then determine the intersection of the clusters on each axis.
Within those clusters you then perform your "classic" collision detection routines.
This solves the following issues:
- Large scale world, relatively few objects, so grid-based solutions are costly.
- As long as object movement is relatively small per frame, the number of updates required to re-sort the list for each axis is also very small.
For even larger amounts of objects, you could implement a tree-variant of this structure which (I believe) is called a "2-D Range Tree".
What about a loosely adaptable AABB binary tree:
Define your world as a rectangle (AABB)
Divide this rectangle in half perpendicular to its longest axis; believe it or not you now have two AABB rectangles [wink]
'Optimise' each rectangle, usually this means shrinking it to tightly fit all the objects it contains, but if an object was straddling between the division then the rectangle that contained >=50% of the object will have to grow slightly to contain that object whilst the other rectangle (that had <50% of the object) will leave it alone.
Continue splitting and optimising each AABB rectangle into smaller AABBs until you hit some acceptable limit where there are a manageable number of collidable objects within an AABB.
When an object moves update the bounds of the AABB and all the parent AABBs all the way up the tree.
Testing collision is done by iterating the tree top to bottom and testing whether a point is within an AABB until you reach a leaf node and then you switch to brute force between individual objects.
Eventually due to moving objects you find that two or more AABB will overlap, at this point the tree is beginning to degrade, in this case you have two options, you either have to test down each overlapping branch of the tree, or you re-build the degrading tree branches (or the whole tree from scratch) so there are no overlaps.
Re-building the tree 'could' be expensive, so perhaps keep a measure of degredation (num_overlaps perhaps), once that reaches a certain threshold then you rebuild the tree.
Edit:
Actually you have a third possibility for overlapping AABBs, the objects that live in space where the AABBs overlap are moved up the tree into the parent AABB. This is similar to traversing down each branch but could be simpler to implement. Re-building the tree is still a good idea though because the tree is still degrading.
[Edited by - dmatter on August 14, 2007 1:14:23 PM]
Define your world as a rectangle (AABB)
Divide this rectangle in half perpendicular to its longest axis; believe it or not you now have two AABB rectangles [wink]
'Optimise' each rectangle, usually this means shrinking it to tightly fit all the objects it contains, but if an object was straddling between the division then the rectangle that contained >=50% of the object will have to grow slightly to contain that object whilst the other rectangle (that had <50% of the object) will leave it alone.
Continue splitting and optimising each AABB rectangle into smaller AABBs until you hit some acceptable limit where there are a manageable number of collidable objects within an AABB.
When an object moves update the bounds of the AABB and all the parent AABBs all the way up the tree.
Testing collision is done by iterating the tree top to bottom and testing whether a point is within an AABB until you reach a leaf node and then you switch to brute force between individual objects.
Eventually due to moving objects you find that two or more AABB will overlap, at this point the tree is beginning to degrade, in this case you have two options, you either have to test down each overlapping branch of the tree, or you re-build the degrading tree branches (or the whole tree from scratch) so there are no overlaps.
Re-building the tree 'could' be expensive, so perhaps keep a measure of degredation (num_overlaps perhaps), once that reaches a certain threshold then you rebuild the tree.
Edit:
Actually you have a third possibility for overlapping AABBs, the objects that live in space where the AABBs overlap are moved up the tree into the parent AABB. This is similar to traversing down each branch but could be simpler to implement. Re-building the tree is still a good idea though because the tree is still degrading.
[Edited by - dmatter on August 14, 2007 1:14:23 PM]
I did some really novel work with 2D collidable particle systems on the order of 3000 particles using a Delaunay Triangulation. In a single thread I got about 80 updates per second on a 2GHz Intel core duo. Every particle had a circular bounding sphere, and any two particles could collide.
In the Delauney graph of the particles each particle needed only to consider its neighbors and their shared neighbors for collision, this ends up being (on average) 12-18 checks per particle per update.
Mind you, I think given your scope you could manage much faster than I did because I was simulating a fluid, and I had a steady count of about 5000 inter particle collisions per update, and another 2000 particle-boundary collisions.
OK, and here's the bad news:
I was really ONLY simulating a fluid, the render portion was extremely simple, so YMMV, you have an entire game to put on top of this?
Coding Delaunay is a bitch, even in 2D, my next goal is coding it in 3D, but Voronoi (Delaunay's dual) has not been completely solved in 3D, so it may be impossible (for me).
I had UNIFORM object size, this is CRITICAL to my neighborhoods, because I had proven that it was impossible (by definition of delaunay) to collide with a particle further in the graph than a neighbor of TWO of your own neighbors (think about that for a while, it's a little deep). OK but this means that for a system with non uniform particle size, you can't use my cute little axiom, you have to actually manually discover neighborhoods (check neighbors and their neighbors for particles within 2r of this particle) around particles.
More good news:
My preliminary work in the direction of discovered neighborhoods is actually MORE promising than my original work was, it will mean that bodies which are isolated (no other bodies within 2r of this body) will only need to check their immediate neighbors (6-8 on average), on the flip side, large bodies in tight clusters of smaller bodies will need to check many of them (because lots of their centers will be within 2r of the large body's center).
In the Delauney graph of the particles each particle needed only to consider its neighbors and their shared neighbors for collision, this ends up being (on average) 12-18 checks per particle per update.
Mind you, I think given your scope you could manage much faster than I did because I was simulating a fluid, and I had a steady count of about 5000 inter particle collisions per update, and another 2000 particle-boundary collisions.
OK, and here's the bad news:
I was really ONLY simulating a fluid, the render portion was extremely simple, so YMMV, you have an entire game to put on top of this?
Coding Delaunay is a bitch, even in 2D, my next goal is coding it in 3D, but Voronoi (Delaunay's dual) has not been completely solved in 3D, so it may be impossible (for me).
I had UNIFORM object size, this is CRITICAL to my neighborhoods, because I had proven that it was impossible (by definition of delaunay) to collide with a particle further in the graph than a neighbor of TWO of your own neighbors (think about that for a while, it's a little deep). OK but this means that for a system with non uniform particle size, you can't use my cute little axiom, you have to actually manually discover neighborhoods (check neighbors and their neighbors for particles within 2r of this particle) around particles.
More good news:
My preliminary work in the direction of discovered neighborhoods is actually MORE promising than my original work was, it will mean that bodies which are isolated (no other bodies within 2r of this body) will only need to check their immediate neighbors (6-8 on average), on the flip side, large bodies in tight clusters of smaller bodies will need to check many of them (because lots of their centers will be within 2r of the large body's center).
Quote:Original post by VorpyA sparse grid is a possible solution if the world is so big that a normal grid would use too much memory. Just use the coordinates as the indexes into a map containing the buckets of entities in each grid cell. Grids are great as long as entities are all about the same size. Even with different sizes, you can use multiple grids with different resolutions. A quadtree can be adapted to work just like multiresolution spatial hashing, and then people call it a loose quadtree.
Make the cells in the grid as wide as the diameter of the largest object. Now no object can occupy more than 4 cells simultaneously, and for something to collide with a given object it must be in one of the 9 cells surrounding or containing that object. There are a few ways the data structure and collision detection could work: store each object in just one cell and then check the nine adjacent cells for collision checks; store each object in nine cells and only look at one cell; store each object in four cells and look at four cells.
^^ What he said. In spatial hashing you basically:
- divide world by grid (best size for grid cell is a bit larger than the average mobile object).
- Maintain a hash table (a simple 1D list of buckets, each bucket is a vector containing the ID of each object that is in that cell).
- Every frame you do a "hash function" on each object which computes what bucket that object is in. Place the object ID (or a reference) in the appropriate bucket. You do not need any true hashing functions, since it is easier just to make each bucket a list with overflow (C++ vector is what I use).
- Hashing an object depends on its Bounding Volume. Axis-aligned Bounding Boxes (AABB) are fastest to hash. Spheres are fine though as well.
- During collision only collide objects in the same bucket
- Objects may hash to more than 1 bucket, that is fine. Objects on a line may do that. Large objects may as well.
Besides collision you also gain:
- Frustum culling for top down camera: hash camera, only draw objects within a certain number grid squares from camera
- Fast Proximity Queries: "who is near object X?" = nearby buckets
- Picking Optimization: hash your mouse click, only objects in that bucket are candidates for being picked
Of course - ^those^ become a bit trickier if you dont have a strictly top-down camera.
For an essentially 2D world with many mobile objects(either true 2Dgame or 3D RTS game) there isn't much better. It is O(N) to hash all objects per frame. Any tree-based will be at best O(nlogn) to rebuild the tree. Not to mention hashing is simpler to implement.
Here's a paper I did a couple years back that explains spatial hashing in pretty simple terms with some nice diagrams:
http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip
I collided 10,000 spheres with each other and the terrain, and did a simple proximity AI routine at 60+ FPS on over 3 year old hardware.
http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip
I collided 10,000 spheres with each other and the terrain, and did a simple proximity AI routine at 60+ FPS on over 3 year old hardware.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
