用于碰撞检测的QuadTree

Question

最近，我正在使用SFML库开发一个游戏，后来，由于碰撞检测，我遇到了性能问题。我被告知使用QuadTree结构来优化碰撞检测。我已经实现了QuadTree功能的基础，在我的游戏中它似乎工作得很好。整个项目是可用的这里。我想知道怎样才能改进它。

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

析构函数/ clear()

你其实不需要破坏者。不管怎样，一切都会被清理干净的。

您的clear()函数也可以简化一点：

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(); 
}

以后也可以避免与nullptr进行类似的比较。只需使用unique_ptr提供的bool转换即可。

split()

在拆分()函数中，不需要调用std::move。

getIndex()

getIndex检查有点奇怪。检查边界的两边是否位于上象限或左象限内，但只检查一侧的下象限和右象限。如果边界不能(或不应该)具有负高度，则只需检查一侧(可能添加assert()以检查负大小)。如果边界可以有一个负高度，那么你需要检查两边的所有象限。

与其硬编码象限索引，不如使用枚举，例如：

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

或者，您可以将索引改为位掩码。这需要两位，一位用于上/下，另一位用于左/右。-1的失败结果也应该是一个常量，而不是硬编码。然后，您的getIndex函数变成如下所示：

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;
}

我甚至会尝试将错误代码从索引中完全分离出来，让这个函数返回一个bool，并添加一个引用参数来返回索引。然后，您可以使用size_t作为索引类型，而不是int (可能会向类添加一个索引类型)。

请注意，检查实际上并不能确保对象完全符合象限。它只是检查中线的哪一边是rect的。这可能很好(我认为它只会影响边缘象限？)但这是值得考虑的事情。

插入()

我建议使用一个mHasChildren布尔值，而不是每次检查第一个子节点的nullptr。在构造函数中将mHasChildren设置为false，并在split()中将其更改为true。如果不需要额外的bool，那么将null第一个元素签入hasChildren()成员函数。

我不认为插入()逻辑是正确的：

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

mLevel不应该比MaxLevels更伟大..。此外，您需要准确地考虑何时要进行拆分和移动对象(只需要一次！)。

我会使用remove_if来移动/删除对象。如果您定义一个lambda函数来返回true / false (如果对象被移动)，那么您将看到与该函数的第一部分相似(获取索引并调用子函数的insert )。可以将其抽象为私有成员函数，让您拥有如下内容：

// 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());
}

如果只在节点实际有子节点的情况下调用getIndex，那么getIndex可能会更干净：

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));
}

它确实取决于您的用例，但您可能需要增加MaxObjects.我认为现在在您的四叉树中只有大约62个受制裁的对象(mObjects.size() < MaxObjects和mLevel < MaxLevel)。

注:我没有编译或测试这些代码，因为我没有SFML，所以要谨慎使用。

Answer 2

我想指出我现在注意到的两个问题：

1. 从您的代码中，SceneNode*的所有权并不清楚。//使用ObjectsContainer = std::vector；ObjectsContainer mObjects；void (SceneNode& object )的相关行；现在，我注意到在insert()中，没有更新对象参数。也许您想通过const引用传递它，以明确其意图。因此，将其更改为void (const& object)；或者更好的是，不管是谁创建SceneObject，都可以创建一个shared_ptr并传递它。因此，要传递一个shared_ptr<> (std：：shared_ptr对象)；您可能要考虑传递一个shared_ptr<>的原因之一是，通过引用接收一个对象并存储它的指针会使代码变得脆弱，因为可以在堆栈或堆上分配原始对象，并且可以由创建该对象的人释放。
2. 整个clear()函数是不必要的。请看我的评论。void：：clear(){ //这不是必需的。无论如何，矢量将被清除。调用clear()并不能确保对指针调用delete运算符//。mObjects.clear()；//您在这里接受r值引用，//这没有意义//也不需要显式清除mChildren //向量或重置它，因为元素是unique_ptr，//它们将被自动删除。这称为RAII for (auto&child: mChildren) { if (child != nullptr) { child->clear()；child.reset(nullptr)；}但请确保有人正在释放内存(传递SceneNode对象的人)。