Last week we started work on the data structure that will store all of the objects that we want to be colliding. The quadtree will store our collidables spatially to help us minimise the number of collision calls we need to make. If you would like a refresher on the theory behind quadtrees then see my previous tutorial here. This week we will finish the quadtree by implementing: search functionality, the ability to split a parent node to create children nodes, and a few other helper functions.
The function performs the following steps:
- Creates a vector to hold all objects that may be overlapping with our search area.
- Calls the private search function, passing it the vector as a reference (we’ll write this next). This function fills the vector with all of the objects in the nodes that intersect with our search area.
- As our area may not necessarily intersect with all of the objects in the returned nodes, we then need to iterate over all of these possible overlaps and performs a rectangle intersection check. We do this check because it is quick, if we require more detailed collision checks we would perform them in our collision system.
- If the object is intersecting with our search area we add it to the vector of objects that are returned from this function.
We’ll go through this method step by step as well:
- It starts by adding all the objects in this node to the vector. As you’ll remember from the beginning of this tutorial this will contain either all the objects that do not fit neatly into a child node (if there are child nodes) or it will contain all the objects that fit within this node if there are no child nodes.
- Retrieves the child index for the search area. This function will either return a -1 to signify that the search area does not fit into a child node completely (or there are no child nodes) or it will return an index to the child node that contains the area.
- If it returns an index to this tree and we have children nodes then we need to call the search functions for any child node that intersects with our area to make sure that we have added all objects that could possibly be intersecting our area.
- If it returns an index to a child node then we need to call that child nodes search function.