QuadTree for collision detection

Question

I was recently working on a game using the SFML library, Later on, I experienced performance issues due to collision detection. I have been told to use a QuadTree structure to optimize the collision detection. I have implemented the basic of the QuadTree functionality and it seems work fine in my game. The full project is available here. I would like to know how I can improve it.

QuadTree.hpp

#pragma once


#include "SceneNode.hpp"

#include <array>


class QuadTree final : private sf::NonCopyable
{
    static const auto DefaultNodes  = 4u;
    using Ptr                       = std::unique_ptr<QuadTree>;
    using ChildrenContainer         = std::array<Ptr, DefaultNodes>;
    using ObjectsContainer          = std::vector<SceneNode*>;


public:
    explicit                QuadTree(std::size_t Level, const sf::FloatRect& Bounds);
                            ~QuadTree();

    void                    clear();
    void                    insert(SceneNode& object);
    void                    getCloseObjects(const sf::FloatRect& Bounds, ObjectsContainer& returnObjects);


private:
    void                    split();
    int                     getIndex(const sf::FloatRect& Rect);


private:
    ObjectsContainer        mObjects;
    ChildrenContainer       mChildren;

    sf::FloatRect           mBounds;
    std::size_t             mlevel;
};

QuadTree.cpp

#include "QuadTree.hpp"


namespace
{
    constexpr auto  MaxLevels   = 5u;
    constexpr auto  MaxObjects  = 2u;
}


QuadTree::QuadTree(std::size_t Level, const sf::FloatRect& Bounds)
    : mObjects()
    , mChildren()
    , mBounds(Bounds)
    , mlevel(Level)
{
}

QuadTree::~QuadTree()
{
    clear();
}

void QuadTree::clear()
{
    mObjects.clear();

    for (auto&& child : mChildren)
    {
        if (child != nullptr)
        {
            child->clear();
            child.reset(nullptr);
        }
    }
}

void QuadTree::split()
{
    auto width  = mBounds.width / 2.f;
    auto height = mBounds.height / 2.f;
    auto x      = mBounds.left;
    auto y      = mBounds.top;

    mChildren[0] = std::move(std::make_unique<QuadTree>(mlevel + 1, sf::FloatRect(x + width, y, width, height)));
    mChildren[1] = std::move(std::make_unique<QuadTree>(mlevel + 1, sf::FloatRect(x, y, width, height)));
    mChildren[2] = std::move(std::make_unique<QuadTree>(mlevel + 1, sf::FloatRect(x, y + height, width, height)));
    mChildren[3] = std::move(std::make_unique<QuadTree>(mlevel + 1, sf::FloatRect(x + width, y + height, width, height)));
}

int QuadTree::getIndex(const sf::FloatRect& Rect)
{
    auto index = -1;

    auto verticalMidpoint   = mBounds.left + mBounds.width / 2.f;
    auto horizontalMidpoint = mBounds.top + mBounds.height / 2.f;

    // Object can completely fit within the top quadrants
    bool topQuadrant = (Rect.top < horizontalMidpoint && Rect.top + Rect.height < horizontalMidpoint);

    // Object can completely fit within the bottom quadrants
    bool bottomQuadrant = (Rect.top > horizontalMidpoint);

    // Object can completely fit within the left quadrants
    if (Rect.left < verticalMidpoint && Rect.left + Rect.width < verticalMidpoint)
    {
        if (topQuadrant)
        {
            index = 1;
        }
        else if (bottomQuadrant)
        {
            index = 2;
        }
    }

    // Object can completely fit within the right quadrants
    else if (Rect.left > verticalMidpoint)
    {
        if (topQuadrant)
        {
            index = 0;
        }
        else if (bottomQuadrant)
        {
            index = 3;
        }
    }

    return index;
}

void QuadTree::insert(SceneNode& object)
{
    if (mChildren[0] != nullptr)
    {
        auto index = getIndex(object.getBoundingRect());

        if (index != -1)
        {
            mChildren[index]->insert(object);

            return;
        }
    }

    mObjects.push_back(&object);

    if (mObjects.size() < MaxObjects && mlevel > MaxLevels)
        return;

    if (mChildren[0] == nullptr)
    {
        split();
    }

    for (auto i = mObjects.cbegin(); i != mObjects.cend();)
    {
        int index = getIndex((*i)->getBoundingRect());
        if (index != -1)
        {
            auto& temp(**i);
            i = mObjects.erase(i);
            mChildren[index]->insert(temp);
        }
        else
        {
            ++i;
        }
    }
}

void QuadTree::getCloseObjects(const sf::FloatRect& Bounds, ObjectsContainer& returnObjects)
{
    auto index = getIndex(Bounds);

    if (index != -1 && mChildren[0] != nullptr)
    {
        mChildren[index]->getCloseObjects(Bounds, returnObjects);
    }

    std::copy(mObjects.begin(), mObjects.end(), std::back_inserter(returnObjects));
}

Answer 1

destructor / clear()

You don't actually need the destructor. Everything will be cleaned up just fine anyway.

Your clear() function could also be simplified a bit:

void QuadTree::clear()
{
    mObjects.clear();

    for (auto& child : mChildren) // Use a &, since that's what you need...
        // Reset this node's children. everything else happens through destructors. :)
        // No need for a nullptr argument either, just use the default argument.
        child.reset(); 
}

Similar comparisons with nullptr can be avoided later too. Just use the bool conversion that unique_ptr provides.

---

split()

In your split() function, you don't need the calls to std::move.

---

getIndex()

The getIndex checks are a little weird. You check that both sides of the bounds are within the top or left quadrant, but then only check one side for the bottom and right quadrants. If the bounds can't (or shouldn't) have a negative height, you only need to check one side (maybe add an assert() to check for negative sizes). If the bounds can have a negative height, then you need to check both sides for all the quadrants.

Instead of hardcoding quadrant indices, you should use an enum, e.g.:

enum class Quadrant
{
    TopLeft, TopRight,
    BottomLeft, BottomRight,
    NotFound,
};

Alternatively, you could make the index a bitmask instead. This needs two bits, one for top / bottom, and one for left / right. The -1 failure result should also be a constant instead of hardcoded. Then your getIndex function becomes something like this:

int QuadTree::getIndex(const sf::FloatRect& Rect)
{
    assert(Rect.height >= 0.f);
    assert(Rect.width  >= 0.f);

    auto verticalMidpoint   = mBounds.left + mBounds.width / 2.f;
    auto horizontalMidpoint = mBounds.top + mBounds.height / 2.f;

    // Can the object "completely" fit within this quadrant?
    bool top = (Rect.top + Rect.height < horizontalMidpoint);
    bool bottom = (Rect.top > horizontalMidpoint);
    bool left = (Rect.left + Rect.width < verticalMidpoint);
    bool right = (Rect.left > verticalMidpoint);

    if ((top || bottom) && (left || right))
        return (top << 0) | (left << 1);

    // This is still -1, but make it a constant static variable or something!
    return IndexNotFound;
}

I would even be tempted to separate out the error code from the index entirely, make this function return a bool, and add a reference argument to return the index. Then you could use size_t for the index type instead of int (maybe add an Index typedef to the class).

Note that the checks don't actually ensure that the object does completely fit in a quadrant. It just checks which side of the center line the rect is on. This might be fine (I think it only affects the edge quadrants?) but it's something to think about.

---

insert()

I would suggest using an mHasChildren boolean value, instead of checking the first child for a nullptr every time. Set mHasChildren to false in the constructor, and change it to true in split(). If you don't want the additional bool, then put the null first element check in a hasChildren() member function.

I don't think your insert() logic is correct:

if (mObjects.size() < MaxObjects && mLevel > MaxLevels)
    return;

mLevel should never be greater than MaxLevels... Also, you need to think about exactly when you want to do the splitting and moving objects (only once!).

I would use remove_if to move / erase the objects. If you define a lambda function to return true / false if the object was moved, then you'll see a similarity with the first part of the function (getting the index and calling insert on a child). This can be abstracted to a private member function, leaving you with something like this:

// Make this private...
bool QuadTree::insertInChild(SceneNode* object)
{
    assert(mHasChildren);

    auto index = getIndex(object.getBoundingRect());

    if (index == IndexNotFound)
        return false;

    mChildren[index]->insert(object);
    return true;
}

// You might find it cleaner in the long run for this function to take a pointer too...
void QuadTree::insert(SceneNode& object)
{
    if (mHasChildren && insertInChild(&object))
        return;

    mObjects.push_back(&object);

    // This node is already split, and we can't move any objects down.
    if (mHasChildren)
        return;

    // Can't split this node, so no point checking number of objects.
    if (mlevel == MaxLevel)
        return;

    // Don't need to split this node yet.
    if (mObjects.size() < MaxObjects)
        return;

    split();

    mObjects.erase(
        std::remove_if(mObjects.begin(), mObjects.end(), 
            [this] (SceneNode* o) { return insertInChild(o); }),
            //std::bind(&QuadTree::insertInChild, this, std::placeholders::_1)), // same thing...
        mObjects.end());
}

getCloseObjects would probably be cleaner if you only call getIndex if the node actually has children:

void QuadTree::getCloseObjects(const sf::FloatRect& Bounds, ObjectsContainer& returnObjects)
{
    if (mHasChildren)
    {
        auto index = getIndex(Bounds);

        if (index != IndexNotFound)
            mChildren[index]->getCloseObjects(Bounds, returnObjects);
    }

    std::copy(mObjects.begin(), mObjects.end(), std::back_inserter(returnObjects));
}

It really depends on your use case, but you might want to increase MaxObjects... I think you only have about 62 sanctioned objects (mObjects.size() < MaxObjects and mLevel < MaxLevel) in your quadtree right now.

---

N.B. I haven't compiled or tested any of this code because I don't have SFML, so use with caution.

Answer 2

I would like to point out two issues I notice right away:

1. From your code, the ownership of SceneNode* is not clear.

   // relevant lines I'm looking at
   using ObjectsContainer = std::vector<SceneNode*>;
   ObjectsContainer mObjects;
   void insert(SceneNode& object);
   

   Now, I notice that in the insert(), you're not updating the object parameter. Perhaps you want to pass it by const reference to make the intent clear. So change it to

   void insert(const SceneNode& object);
   

   or better yet, whoever is creating the SceneObject can create a shared_ptr and pass that., so pass

   void insert(std::shared_ptr<SceneNode> object);
   

   One reason why you might want to consider passing a shared_ptr<> is that receiving an object by reference and storing its pointer makes the code brittle because the original object could be allocated on the stack or the heap and can be released by whoever created the object.

2. The entire clear() function is not necessary. See my comments in-line.

   void QuadTree::clear()
   {
       // this is not necessary. The vector will be cleared out
       // anyway. Calling clear() does not ensure that delete operator
       // will be called on the pointers. 
       mObjects.clear();
   
       // you are taking an r-value reference here, 
       // which doesn't make sense
       // also you don't need to explicitly clear the mChildren
       // vector or reset it, since the elements are unique_ptr,
       // they will be deleted automatically. This is called RAII
       for (auto&& child : mChildren)
       {
           if (child != nullptr)
           {
               child->clear();
               child.reset(nullptr);
           }
       }
   }
   

   but make sure that somebody is freeing the memory (whoever passed SceneNode object).