QuadTree:
Tutorial 2: Using the Quad Tree

Tutorial 1 <-- Tutorial 2

Introduction

Now that we have the Tree created, we can begin adding objects and checking their neighbors.

Source code for tutorials can be downloaded from here.

Inserting Objects • Accessing Objects • Updating Objects

Inserting objects

It is recommended that you have all your objects in an easily accessible Array for inserting and checking. You insert your objects one at a time and in this example we do so with a for loop:

		this.mQuadTree = new Quadtree([-100, 100, -100, 100], 10, 10);
		this.mObjectArray; //Already filled with objects
		
		for(var i = 0; i < this.mObjectArray.length; i++){
			this.mQuadTree.insert(this.mObjectArray[i]);
		}

It's as simple as that, with the pre-defined information, all of the objects are in a specific location of the tree.

Accessing objects for hit collision

Now that the tree is filled, we can find objects for collision, we will be using our Array again to run through and grab nearby objects:

		for(var i = 0; i < this.mObjectArray.length; i++){
			var objects = Array.from(this.mQuadTree.getObjectsNear(this.mObjectArray[i]));
			for(var j = 0; i < objects.length; j++){
				if(objects[j] !== this.mObjectArray[i] && this.mObjectArray[i].pixelTouches(objects[j])){
					// Do Collision reaction
				}
			}
		}

Updating Objects

For moving objects, we need to update them within the tree so that they're always in the quadrant they're actually in. To do that we must remove then re-insert them into the tree. Depending on your scenario it may be more efficient to clear the tree entirely and re-insert everything, but otherwise you'd remove and insert anytime an object had a movement or size update.

		this.mQuadTree.clear()
		for(var i = 0; i < this.mObjectArray.length; i++){
			this.mQuadTree.insert(this.mObjectArray[i]);
		}
		
		// object #42 changed locations
		this.mQuadTree.remove(this.mObjectArray[41]);
		this.mQuadTree.insert(this.mObjectArray[42]);

Either way works, but since the implementation of QuadTree exists to save on time and energy, it's important to consider which way will be more efficient for your system. Additionally the easiest way to make sure things update would be to remove and insert the line after a position change or a size change.

Conclusion

That's all there is to know about the main functionality of the Quad Tree and hopefully this tutorial helped.