Quad Tree:
Tutorial 1: Setting Up the Quad Tree

Tutorial 1 --> Tutorial 2

Introduction

The Quad Tree system is designed to be used in lue of basic collision checking, rather than checking every object with every object that could possibly collide in the entire world space. You can just check objects nearby for collisions.

Source code for tutorials can be downloaded from here.

Development Environment

It is assumed that you have your development environment set up already to work with the GTCS Game Engine, if that's not the case, please follow the tutorial here.

Entry Point

JavaScript Includes

Be sure to have the QuadTree files included in your index.html which should look something like this:


        <!-- Utilities -->
            <script type="text/javascript" src="src/Engine/Utils/Transform.js"></script>
            <script type="text/javascript" src="src/Engine/Utils/BoundingBox.js"></script>
            <script type="text/javascript" src="src/Engine/Utils/Interpolate.js"></script>
            <script type="text/javascript" src="src/Engine/Utils/InterpolateVec2.js"></script>
            <script type="text/javascript" src="src/Engine/Utils/ShakePosition.js"></script>
            <script type="text/javascript" src="src/Engine/Utils/CollisionInfo.js"></script>
		
		<script type="text/javascript" src="src/Engine/Utils/Quadtree/Quadtree.js"></script>
		<script type="text/javascript" src="src/Engine/Utils/Quadtree/QNode.js"></script>

Setting it up in your level

In order for the Quad Tree to give you accurate information, the tree needs to have all objects you plan on having collision responses for. In our case we created a ObjectManager.js file that deals with all objects created so we only have one file needing to update the Quad Tree on objects. The Quad Tree can work with multiple files sending in objects, it just becomes more to worry about. Regardless you need to create the Quad Tree before it can be used:

			this.mQuadTree = new Quadtree([-100, 100, -100, 100], 10, 10);

For this specific QuadTree we've declared that the max boundaries of the World Space is (-100,-100) and (100,100) in a MinX MaxX MinY MaxY format, make sure to correctly define the boundaries of your world space otherwise the Quad Tree will not function properly. We've also decided that 10 is the max number of objects allowed to be in each quadrant of the world space, that means when the number is exceeded, the tree splits that quadrant up into smaller quadrants until the limit is satisfied. Lastly we declared that the max depth of the tree is 10 meaning that no quadrant can be divided up more than 10 times, if this happens the tree will ignore the max objects limit to follow the max depth limit.

Conclusion

Now that you've declared and defined your Quad Tree, it is ready to accept objects. In tutorial 2, we will look at inserting objects and accessing them.