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.

Ute

If the game you are making is really like the video you linked, it's you should not be using a spatial index at all, An unsorted list of entities will still probably be faster up to a few hundred moving objects. – Judge

Depends on the collision I think... probably so for circle-based collision, probably not for pixel-based. Also, for low number of objects looking up neighbors in a 1D-sorted list of entites is usually fastest, IIRC. But implementing a working quadtree is worth it for the sheer experience. (And also, the bullet hell-trend shoot'em ups can have hundreds of moving objects easily :)) – Caponize

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.

Caponize

BTW- this convention where not only leaves can contain elements is probably not the only one which exists- just the first that comes to my mind. You might have stumbled upon other variants which take different assumptions and hence need a different approach. – Caponize

So I basicaly need to repeat those 4 steps for each object in the game to test it for any potential collisions ? – Ute

Yes, in the general case. But you can have several trees at once - for example bullets don't collide with bullets, so you even can have separate trees for bullets and separate for, say, enemies, and check every bullet with the enemy tree, etc. Check your logic and think how many trees you actually need in this variant :) – Caponize