Detecting Collisions Between Dynamic Objects in a 2D Environment

Question

Let's say we have a lot of dynamic objects in a two-dimensional world, e.g. characters, projectiles, power-ups, the usual stuff you'd find in a game. All of them are moving. We want to detect collisions between them. What is a good way to do it?

I have looked at quad-trees, but it seems like to detect collisions between dynamically moving objects, I'd have to re-create quad-tree every frame (because objects change their positions with every frame). This looks like a costly operation.

Are there any other approaches to this problem besides quad-trees? Is there a way to improve the quad-tree approach? Maybe re-creating the tree on every frame is not so costly after all?

Answer 1

Normally, you update the quadtree (rather than throwing away the old one and building a new one), and this is not as expensive as you think: normally objects move only a small distance in each frame, so that the majority remain in the same node of the quadtree and there are few changes. Even in the worst case, where every item moves across a major boundary and has to be removed and reinserted, the cost is only O(n log n). But more or less any loop over all your items will cost about this much, so one more loop isn't such a big deal.