QuadTree for 2D collision detection

Question

I'm currently working on a 2D shoot them up type of game, and I'm using a quad tree for my collision detections. I wrote a working quad tree that correctly pushes my actors into the nodes/leaves they belong to in the tree. However, I've got a few problems.

Firstly, how do I actually use my quadtree to select against which other objects an object should test collisions ? I'm unsure about how this is done.

Which brings up a second question. Say I have an object in node that is not a neighbour of another node, but that the object is large enough that it spans a few node, how can I check for an actual collision, since I'm guessing the tree might consider it's not close enough to collide with objects in a "far away" node? Should objects that don't completely fit in a node be kept in the parent node?

In my game, most of the objects are of different sizes and moving around.

I've read a good number of blogs/articles about quadtrees but most just explain how to build a tree which is not really what I'm looking for.

Any help/info is welcome.

Answer 1

You can establish a convention that every element is contained in the smallest quadtree node which contains it fully.

Then when you check the collisions for node A, you proceed like this:

1. current node = root node
2. check collisions of A with each element directly in current node
3. if A can be contained entirely in any of sub-nodes of the current node, set the current node to that sub-node and go to 2 again
4. finally, check collisions of A with all the elements in children nodes of the current node, recursively.

Note that the smaller the objects, the deeper they will be located in the quad tree, hence they will be compared less often.