What broad-phase collision algorithms are suited to a static tiled world with dynamic objects of different sizes?

Question

Sorry for this routine question, but I can't think of what broad-phase collision algorithms really work in the following, reasonably standard, setup:

• 2D tile based world, consisting of objects that do not move but might be altered/changed in some ways (not too often).
• Significant amount of dynamic objects, interacting with eachother and with the static tiles. These objects can be of variable size, possibly much larger than the tile size.

I started thinking about using just a grid to store the static tiles, but that has its issues. One example would be a level which is a long corridor following the edges of a square; I'm anxious about creating a whole nxn grid when there is a huge amount of irrelevant space in the middle. Also I'm not sure a grid is going to be helpful when figuring out what needs to be considered for collision, or needs to be drawn on screen; a quadtree seems more appropriate.

So far, I'm thinking of:

• using a quadtree to store the static tiles (to account for the possibility of large empty spaces in the middle of the grid for instance); hopefully that won't be prohibitively expensive when I need to modify some tiles (this shouldn't happen excessively often);
• using some other data structure (I'm undecided which is most suited) to store the dynamic objects, which might have very different sizes;
• once that's done, from the tile map I determine which tile edges are empty, solid or need further investigation for collisions; then I would use axis aligned bounding boxes for the dynamic objects to see if there is a possible collision with the static world, and some other algorithm (depending on the data structure for the dynamic objects) to model collisions between dynamic objects.

Maybe something slightly different would be more suited for the tiles, I'm thinking some sort of grid but with "off limits" regions that can be dismissed. I'm also somewhat anxious about fast-moving dynamic objects; so maybe those could belong to yet another data structure. I wouldn't expect them to be of large size (so they should fit inside tiles nicely), but I'd like to keep my options open in case I make some design changes.

(One thing I am completely neglecting is what generally happens with off-screen dynamic objects; I'm ignoring that problem for now and assuming everything is to be simulated together, but that might be a blunder.)

Answer 1

I'm very leery of tossing out a grid simply because of potential wasted space. Go for a grid for your tiles until you actually have a problem because of it. If and only if you get into that situation, consider simply adding one higher level above the grid of tiles—i.e., a grid of 8x8 or 16x16 tiles, perhaps. If needed, larger chunks that are completely empty could be neglected. But unless you have a very large amount of per-tile data that can't be skipped for empty tiles, just bite the bullet and store the whole grid.

If you don't want to store small dynamic objects in the grid structure, consider spatial hashing (i.e. treating the coordinates of your grid position as the key for a hash table). And if you have very large objects that span so many tiles that you don't want to use the same structure for them, you probably have so few of them that a spatial data structure might not be worth it.