*The green rectangle represents our search area.*

*The quadtree returns these two objects as they intersect the search area.*

Quadtree.cpp

```
std::vector<std::shared_ptr<C_BoxCollider>> Quadtree::Search(const sf::FloatRect& area)
{
std::vector<std::shared_ptr<C_BoxCollider>> possibleOverlaps; // 1
Search(area, possibleOverlaps); // 2
std::vector<std::shared_ptr<C_BoxCollider>> returnList;
for (auto collider : possibleOverlaps)
{
if (area.intersects(collider->GetCollidable())) // 3
{
returnList.emplace_back(collider); // 4
}
}
return returnList;
}
```

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.

Quadtree.cpp

```
void Quadtree::Search(const sf::FloatRect& area,
std::vector<std::shared_ptr<C_BoxCollider>>& overlappingObjects)
{
overlappingObjects.insert(overlappingObjects.end(), objects.begin(), objects.end()); // 1
if(children[0] != nullptr)
{
int index = GetChildIndexForObject(area); // 2
if(index == thisTree) // 3
{
for(int i = 0; i < 4; i++)
{
if(children[i]->GetBounds().intersects(area))
{
children[i]->Search(area, overlappingObjects);
}
}
}
else // 4
{
children[index]->Search(area, overlappingObjects);
}
}
}
```

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.

Quadtree.cpp

```
const sf::FloatRect& Quadtree::GetBounds() const
{
return bounds;
}
```

Quadtree.cpp

```
int Quadtree::GetChildIndexForObject(const sf::FloatRect& objectBounds)
{
int index = -1;
double verticalDividingLine = bounds.left + bounds.width * 0.5f;
double horizontalDividingLine = bounds.top + bounds.height * 0.5f;
bool north = objectBounds.top < horizontalDividingLine
&& (objectBounds.height + objectBounds.top < horizontalDividingLine);
bool south = objectBounds.top > horizontalDividingLine;
bool west = objectBounds.left < verticalDividingLine
&& (objectBounds.left + objectBounds.width < verticalDividingLine);
bool east = objectBounds.left > verticalDividingLine;
if(east)
{
if(north)
{
index = childNE;
}
else if(south)
{
index = childSE;
}
}
else if(west)
{
if(north)
{
index = childNW;
}
else if(south)
{
index = childSW;
}
}
return index;
}
```

Quadtree.cpp

```
void Quadtree::Split()
{
const int childWidth = bounds.width / 2;
const int childHeight = bounds.height / 2;
children[childNE] = std::make_shared<Quadtree>(maxObjects, maxLevels, level + 1,
sf::FloatRect(bounds.left + childWidth, bounds.top, childWidth, childHeight),
this);
children[childNW] = std::make_shared<Quadtree>(maxObjects, maxLevels, level + 1,
sf::FloatRect(bounds.left, bounds.top, childWidth, childHeight),
this);
children[childSW] = std::make_shared<Quadtree>(maxObjects, maxLevels, level + 1,
sf::FloatRect(bounds.left, bounds.top + childHeight, childWidth, childHeight),
this);
children[childSE] = std::make_shared<Quadtree>(maxObjects, maxLevels, level + 1,
sf::FloatRect(bounds.left + childWidth, bounds.top + childHeight, childWidth, childHeight),
this);
}
```

*One parent node split into four child nodes.*