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