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

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.