2D collision detection, 1000+ entities, very large area - quadtree?

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.

Moved to Game Programming at the OP's request.

Cheers!

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.

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)

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".

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]

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).

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.

Quote:

Original post by FippyDarkpaw 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.

How is hashing implemented?
I have a feeling it could sneakily be a O(nLogn) algorithm, with n == num_buckets..?

Either way its worth pointing out that with the spatial hashing method you described you have to re-hash every object every frame, O(N) or not this will cost something.
With the tree method I described re-building the tree is a deferred task that doesnt take place every frame and you could conceptually think of the leaf nodes in the tree as 'buckets'.

Testing a collision actually only requires brute force between other objects in that leaf node and any others in any nodes above it (assuming you go with the idea that objects living in overlapping space move up the tree into the best-fit AABB).

http://www.flipcode.com/articles/article_raytrace04.shtml

Here's an article I used for grid transversal of points. Very good for projectiles.

You can find which cell an aabb is in by looking at the center of it as a vector, dividing by the cell size, and flooring the result (or something similiar, depending on how you're using it). That gives us the integer coordinates of the cell. Now just hash those coordinates, which is an O(d) operation where d is the number of dimensions, which will be a constant. The number of buckets doesn't matter. The algorithm is O(n+h) where n is the number of objects and h is the number of objects that are in buckets close enough for a possible collision. Broad phase collision detection is necessarily output sensitive. If every object collided with every other object, any algorithm would require O(n^2) time to report all the possible collisions.

The overhead of hashing and looking through buckets can be significant, so a dense representation (storing buckets in a matrix) is desirable unless the world is really too big. A 1024 by 1024 grid would only require 4 megabytes (8 on 64 bit machines) to store a grid of pointers and then a small overhead per object to chain together the lists. If you have less than 65537 objects then you can store the objects in a pool of memory and access them by an index of 16 bits or less, reducing the needed memory to only 2 megabytes (plus per object cost).

An object's entry in the table only needs to be updated if it moves enough to change the cells it occupies. In most cases only a division, floor, and conditional statement will be needed.

A dynamic tree or a sorted list of ranges might work just as well or better. It might depend on properties like the number of objects, the size of the scene, variance in the size of the objects, the speed objects move at, etc., so it's hard to say.

Thanks for all the responses, guys. I appreciate it.

After reading through it all, I'm leaning toward a simple uniform grid. I was biased against it initially, because I've used a 3D grid in the past on a particle-based fluid simulation, and had performance issues with it due to cache thrashing. Even had disk thrashing on larger grids which, needless to say, made it far from real-time.

Since the world in my game will be very large, I just assumed I would have similar problems. But after considering the actual numbers, I don't think it'll be a problem after all, since memory usage in a 2D grid doesn't blow up anywhere nearly as bad as a 3D grid. My world will likely be around 4000 x 4000 units, with entities having a typical size of around 4 x 4. If I made my cell size 10, that's a grid of 400 x 400 cells, or 160,000. Even an 8000 x 8000 world would only have 640,000 cells. After I get it working, though, I may still play with some kind of sparse grid to reduce cache thrashing.

Symphonic, your Delauney triangulation approach sounds interesting. I've used Voronoi maps before, and I'm familiar with Delauney, but I've never considered it in the context of collision detection.

El Greco, I've considered a couple different min/max sorted list approaches. As mentioned in my original post, I considered recursive dimensional clustering (mostly because it's a really cool algorithm that I've always wanted an excuse to implement). I also looked into sweep and prune, but destroying and inserting new entities (which I'll do a lot of) would perform very badly.

I've actually concocted a different min/max sorted list algorithm of my own, which I might experiment with. It assumes implied, uniform-width vertical strips. A list of all entities is sorted by a primary key of which strip they fall in (i.e., entity's min x quantized to strip width), and a secondary key of their min y (not quantized). Then, within each strip, each entity would be tested against the entities coming after it in the list, until it reaches one whose min y is greater than this entity's max y. The complicating factor would be entities that overlap into the next strip. I would need to have a sort of "proxy entity" in the neighboring strip, with a phony x-strip position (so it gets sorted into the neighboring strip, not it's own), but that refers back to the "real" entity for the actual collision distance test.

Anyway, I think I'll go with a simple uniform grid for now, since it's the quickest to implement. I can then see how that performs, and use it to prototype the actual gameplay which will give me a better idea of actual world size, entity clustering, etc.

Your sorted list algorithm actually sounds pretty good to me. I think it can be viewed partially as a spatial partitioning scheme. Actually it seems to be just like using a uniform grid, except that the grid cells are very coarse and within the cells a different culling algorithm is used.

Going through the sorted list within the cell would be less efficient in some degenerate cases, but with fairly rectangular, uniform size objects that are about the size of each cell's width it should work very well. Assuming the AABBs of the objects are roughly squares the same width as the cells, the odds of two AABBs colliding when they are in the same cell and their y axes overlap are extremely good. Since the objects aren't wider than the cells, you only need to check for collisions in one adjacent cell. I can sort of imagine a way of going through the objects diagonally, advancing down all the cells in parallel to more quickly find a good starting spot for checking an object against objects in the next column. While advancing down column 1, advance down column 2 until the next object in column 2's min y coordinate is greater than the next object in column 1's max y coordinate. Now the object in column 1 can be checked, and when looking at objects in column 2 we can start from the next object to be checked in that column. For square shaped objects this should work well.

This method uses far less memory since only a one dimensional grid is needed. There is the increased overhead from having to sort objects in each cell, but sorting an almost sorted sequence is very quick. And it might even be better than the grid method at culling non-collisions (for fat, roughly uniformly sized objects).

Just want to clarify something; people keep saying sorting a mostly sorted list is quick; This depends on your sorting algorithm.

Quicksort and Mergesort are both order nlogn regardless of the input set.

Insertion sort is linear (order n) in the number of inversions in the average case of sorting there are order n^2 inversions, but if there are few inversions (ie the list is mostly sorted) then it will be faster than the above algorithms.

Heapsort is an interesting example, it may actually benefit from partially sorted lists, but I can't confirm this off-hand, I may come back to this later.

A note about nlogn complexity:

suppose you're using an order nlogn algorithm the times it takes to do stuff will look roughly like this:

n = 10, t = 10
n = 100, t = 200
n = 1000, t = 3000
n = 10000, t = 40000
n = 100000, t = 500000

This really is very scalable, if your problem size is roughly confined to [n/2,2n] (where n is the average problem size) the scaling will be indistinguishable from linear.

Quote:

Original post by Symphonic Quicksort and Mergesort are both order nlogn regardless of the input set.

Not quite, Quicksort has a worst case of O(n^2)

A good sorting algorithm that does benefit from a nearly sorted list is a natural-mergesort, if i remember correectly it runs at O(nlogn) for 'random' datasets and almost O(n) for nearly sorted data.
In comparison a radix sort is also O(n) (for any dataset) but its overhead is greater than a natual-mergesort.

Wikipedia has a good sort comparison page.

[Edited by - dmatter on August 15, 2007 12:10:37 PM]

Quote:

Original post by dmatter Quote: Original post by FippyDarkpaw 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. How is hashing implemented? I have a feeling it could sneakily be a O(nLogn) algorithm, with n == num_buckets..?

Its O(n), n is # of moving objects. Each frame, hash each mobile object. The hash function is extremely simple it just converts object position into a grid cell.

Quote:

Original post by MartoonIf I made my cell size 10, that's a grid of 400 x 400 cells, or 160,000. Even an 8000 x 8000 world would only have 640,000 cells. After I get it working, though, I may still play with some kind of sparse grid to reduce cache thrashing.

I'd try a few values. As you change cell size there is a sweet spot somewhere between fewer collision checks and number of empty buckets. I'd make cell size adjustable during execution, which is no problem since every frame all objects are rehashed anyway.

Quote:

Original post by dmatter Quote: Original post by Symphonic Quicksort and Mergesort are both order nlogn regardless of the input set. Not quite, Quicksort has a worst case of O(n^2)

What you say is typically true (i.e. for most implementations), but is not true in theory. Let me recycle an old post of mine that I end up posting every few years:

If the data is partitioned into two equal-size parts at each step,then quicksort is worst-case O(n log n). Such a split can be doneby using any linear-time median selection algorithm as thepartitioning algorithm, for example the Blum, Floyd, Pratt,Rivest, and Tarjan one as described in:Blum M., Floyd, Pratt, Rivest and Tarjan. Time Bounds for Selection.J Comput Sys Sci 7(4), 1973, 448-461An improvement, using fewer comparisons is given in:Dor, Dorit. Uri Zwick. Selecting the median. Proceedings of the6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 28--37,1995.

But yes, for any garden-variety partitioning method (such as median-of-three) quicksort is O(n^2) worst-case (but you're unlikely to encounter the worst case in real life).