Quad Tree Example Video

This is an example of my XNA game’s quad tree collision detection implementation. Each time an enemy moves to another section of the screen, it is placed into a different node in the quad tree, I then draw a box over the part of the screen corresponding to the node of the tree.

In my implementation of the quad tree, I start with an empty tree and create the nodes in the tree as I go. I do not remove nodes when they are empty, so as to minimize garbage collection. I’ll need those nodes later on when new enemies enter that section of the screen.

A little background…

I’m not simply trying to draw a quad tree so it looks like a tree.
The quad tree is the underlying data structure.

Quad trees are used to divide 2d maps and regions into grids so that each square in the grid represents a node on the tree. You can then search the tree fairly quickly. In this case i’m using it to divide my game screen into quads, then those quads into quads, and so on until the quads are just the right size to fit my smallest enemy.
What you see in the video is that when an enemy moves across the screen, it is being placed and then moved around in the quad tree. To show this on the screen I am drawing a square around the section of screen that is represented by that node on the tree the enemy just entered.
Another important thing to mention is that if an enemy overlaps 2 or more quads, it is placed into the parent node on the tree that represents those quads.
When I update the bullets in my gameloop, I find the leaf node the bullet is in, then do collision detection on only the enemies in that leaf node. If i did not hit anything I check the parent node. The, I work my way up the tree till I reach the root.
The entire point of all of this is so you are not checking each bullet against each enemy every time. You are only checking 1 bullet with the enemies that are next to it on the screen.