QuadTree/Collisions

[reworks-org]

Implement quadtree for rendering and collision.

[reworks-org]

m_quadtree.clear(); m_output.clear();

        m_quadtree.resize(SL_HANDLE.window()->get_width(), SL_HANDLE.window()->get_height());
        scene->m_world.operate<components::Renderable>([&](const ecs::Entity entity, components::Renderable* renderable) {
            m_quadtree.insert({.m_aabb = &renderable->get_aabb(), .m_entity = entity, .m_type = renderable->m_type});
        });

        m_quadtree.query({.m_aabb = &scene->m_camera.get_aabb()}, m_output);

[reworks-org]

m_quadtree.clear(); m_output.clear();

        if (!scene->get_active_map())
        {
            m_quadtree.resize(SL_HANDLE.window()->get_width(), SL_HANDLE.window()->get_height());
        }
        else
        {
            m_quadtree.resize(scene->get_active_map()->get_width(), scene->get_active_map()->get_height());
        }

        scene->m_world.operate<components::RigidBody, components::Renderable>(
            [&](const ecs::Entity entity, components::RigidBody* body, components::Renderable* renderable) {
                m_quadtree.insert({.m_aabb = &renderable->get_aabb(), .m_entity = entity});
            });

        m_quadtree.query({.m_aabb = &scene->m_camera.get_aabb(), .m_entity = 0}, m_output);

[reworks-org]

/// /// QuadTree.hpp /// galaxy /// /// Refer to LICENSE.txt for more details. ///

ifndef GALAXY_MATH_QUADTREEHPP

define GALAXY_MATH_QUADTREEHPP

include

include

include

include "galaxy/ecs/Entity.hpp"

include "galaxy/graphics/Renderables.hpp"

include "galaxy/math/AABB.hpp"

include "galaxy/math/Rect.hpp"

namespace galaxy { namespace math { /// /// 2D spacial partitioning. /// class Quadtree final { public: /// /// Entity with AABB. /// struct Object final { /// /// Entity AABB from Renderable component. /// AABB* m_aabb;

            ///
            /// Entity AABB belongs to.
            ///
            ecs::Entity m_entity;

            ///
            /// Renderable type.
            ///
            graphics::Renderables m_type;
        };

        ///
        /// Argument constructor.
        ///
        /// \param level Level of this quadtree. First is 0.
        /// \param bounds Quadtree bounds.
        /// \param max_objects Optional. Max objects in a quadtree before splitting.
        /// \param max_levels Optional. Total number of levels allowed in a quadtree.
        ///
        Quadtree(const int level, const Rect<float>& bounds, int max_objects = 10, int max_levels = 5) noexcept;

        ///
        /// Destructor.
        ///
        ~Quadtree() noexcept;

        ///
        /// Resize quadtree bounds.
        ///
        /// \param width New quadtree width.
        /// \param height New quadtree height.
        ///
        void resize(const int width, const int height) noexcept;

        ///
        /// \brief Insert an object into the quadtree.
        ///
        /// If the node exceeds the capacity, it will split and add all objects to their corresponding nodes.
        ///
        /// \param object Object to be inserted.
        ///
        void insert(const Quadtree::Object& object);

        ///
        /// Return all entities in the same spacial partition.
        ///
        /// \param object Object to check.
        /// \param output Array of objects that are in the same spacial partition.
        ///
        void query(const Quadtree::Object& object, std::vector<Quadtree::Object*>& output);

        ///
        /// Clears the quadtree.
        ///
        void clear();

    private:
        ///
        /// Constructor.
        ///
        Quadtree() = delete;

        ///
        /// Splits the quadtree into 4 sub-trees.
        ///
        void split();

        ///
        /// Determine which node the object belongs to.
        ///
        /// \param object Object to query its spacial index.
        ///
        /// \return Index of object. -1 means object cannot completely fit within a child tree and is part of the parent tree.
        ///
        [[nodiscard]] const int get_index(const Quadtree::Object& object);

    private:
        ///
        /// Current tree level.
        ///
        int m_level;

        ///
        /// Tree bounds.
        ///
        Rect<float> m_bounds;

        ///
        /// Max objects in a partition.
        ///
        int m_max_objects;

        ///
        /// Max levels in the tree.
        ///
        int m_max_levels;

        ///
        /// List of stored objects.
        ///
        std::vector<Quadtree::Object> m_objects;

        ///
        /// Sub-trees.
        ///
        std::array<std::unique_ptr<Quadtree>, 4> m_nodes;
    };
} // namespace math

} // namespace galaxy

endif

[reworks-org]

/// /// QuadTree.cpp /// galaxy /// /// Refer to LICENSE.txt for more details. ///

include "QuadTree.hpp"

namespace galaxy { namespace math { Quadtree::Quadtree(const int level, const Rect& bounds, int max_objects, int max_levels) noexcept : m_level {level} , m_bounds {bounds} , m_max_objects {max_objects} , m_max_levels {max_levels} { m_objects.reserve(m_max_objects); }

    Quadtree::~Quadtree() noexcept
    {
        clear();
    }

    void Quadtree::resize(const int width, const int height) noexcept
    {
        m_bounds.m_width  = width;
        m_bounds.m_height = height;
    }

    void Quadtree::insert(const Quadtree::Object& object)
    {
        if (m_nodes[0] != nullptr)
        {
            const auto index = get_index(object);
            if (index != -1)
            {
                m_nodes[index]->insert(object);
                return;
            }
        }

        m_objects.push_back(object);

        if (m_objects.size() > m_max_objects && m_level < m_max_levels)
        {
            if (m_nodes[0] == nullptr)
            {
                split();
            }

            for (auto it = m_objects.begin(); it != m_objects.end();)
            {
                const auto index = get_index(*it);
                if (index != -1)
                {
                    m_nodes[index]->insert(*it);
                    it = m_objects.erase(it);
                }
                else
                {
                    ++it;
                }
            }
        }
    }

    void Quadtree::query(const Quadtree::Object& object, std::vector<Quadtree::Object*>& output)
    {
        const auto index = get_index(object);
        if (index != -1 && m_nodes[0] != nullptr)
        {
            m_nodes[index]->query(object, output);
        }

        output.reserve(output.size() + m_objects.size());
        for (auto& object : m_objects)
        {
            output.push_back(&object);
        }
    }

    void Quadtree::clear()
    {
        m_objects.clear();

        for (auto& node : m_nodes)
        {
            node.reset();
            node = nullptr;
        }
    }

    void Quadtree::split()
    {
        Rect<float> new_bounds;

        new_bounds.m_x      = m_bounds.m_x + (m_bounds.m_width / 2.0f);
        new_bounds.m_y      = m_bounds.m_y;
        new_bounds.m_width  = m_bounds.m_width / 2.0f;
        new_bounds.m_height = m_bounds.m_height / 2.0f;
        m_nodes[0]          = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);

        new_bounds.m_x      = m_bounds.m_x;
        new_bounds.m_y      = m_bounds.m_y;
        new_bounds.m_width  = m_bounds.m_width / 2.0f;
        new_bounds.m_height = m_bounds.m_height / 2.0f;
        m_nodes[1]          = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);

        new_bounds.m_x      = m_bounds.m_x;
        new_bounds.m_y      = m_bounds.m_y + (m_bounds.m_height / 2.0f);
        new_bounds.m_width  = m_bounds.m_width / 2.0f;
        new_bounds.m_height = m_bounds.m_height / 2.0f;
        m_nodes[2]          = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);

        new_bounds.m_x      = m_bounds.m_x + (m_bounds.m_width / 2.0f);
        new_bounds.m_y      = m_bounds.m_y + (m_bounds.m_height / 2.0f);
        new_bounds.m_width  = m_bounds.m_width / 2.0f;
        new_bounds.m_height = m_bounds.m_height / 2.0f;
        m_nodes[3]          = std::make_unique<Quadtree>(m_level + 1, new_bounds, m_max_objects, m_max_levels);
    }

    const int Quadtree::get_index(const Quadtree::Object& object)
    {
        int index = -1;

        const double vert_midpoint = object.m_aabb->min().x + (object.m_aabb->size().x / 2.0f);
        const double hori_midpoint = object.m_aabb->min().y + (object.m_aabb->size().y / 2.0f);

        const bool fits_in_top    = (object.m_aabb->min().y < hori_midpoint && object.m_aabb->min().y + object.m_aabb->size().y < hori_midpoint);
        const bool fits_in_bottom = (object.m_aabb->min().y > hori_midpoint);

        if (object.m_aabb->min().x < vert_midpoint && object.m_aabb->min().x + object.m_aabb->size().x < vert_midpoint)
        {
            if (fits_in_top)
            {
                index = 1;
            }
            else if (fits_in_bottom)
            {
                index = 2;
            }
        }
        else if (object.m_aabb->min().x > vert_midpoint)
        {
            if (fits_in_top)
            {
                index = 0;
            }
            else if (fits_in_bottom)
            {
                index = 3;
            }
        }

        return index;
    }
} // namespace math

} // namespace galaxy

[reworks-org]

https://pvigier.github.io/2019/08/11/vagabond-2d-physics-engine.html https://github.com/pvigier/Quadtree https://github.com/RandyGaul/cute_headers