src: add collision iterator adapter

6 files changed, 232 insertions, 30 deletions

diff --git a/src/chunk.cpp b/src/chunk.cpp
index e66b193a..f40480ee 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -1,6 +1,8 @@
 #include "chunk.hpp"
 #include "compat/LooseQuadtree-impl.h"
+#include "src/collision.hpp"
 #include "src/tile-atlas.hpp"
+#include <Magnum/Math/Vector4.h>
 
 namespace floormat {
 
@@ -8,16 +10,9 @@ bool chunk::empty(bool force) const noexcept
 {
     if (!force && !_maybe_empty)
         return false;
-
     for (std::size_t i = 0; i < TILE_COUNT; i++)
-    {
         if (_ground_atlases[i] || _wall_atlases[i*2 + 0] || _wall_atlases[i*2 + 1] || _scenery_atlases[i])
-        {
-            _maybe_empty = false;
-            return false;
-        }
-    }
-
+            return _maybe_empty = false;
     return true;
 }
 
@@ -69,17 +64,17 @@ auto chunk::ensure_passability() noexcept -> lqt&
     _lqt_bboxes.clear();
     _lqt_bboxes.reserve(32);
 
-    constexpr auto whole_tile = [](std::size_t k, pass_mode p) constexpr -> bbox {
+    constexpr auto whole_tile = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
         auto start = tile_start(k);
         return { start[0], start[1], tile_size2us[0], tile_size2us[1], p };
     };
 
-    constexpr auto wall_north = [](std::size_t k, pass_mode p) constexpr -> bbox {
+    constexpr auto wall_north = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
         auto start = tile_start(k) - Vector2s(0, 1);
         return { start[0], start[1], tile_size2us[0], 2, p };
     };
 
-    constexpr auto wall_west = [](std::size_t k, pass_mode p) constexpr -> bbox {
+    constexpr auto wall_west = [](std::size_t k, pass_mode p) constexpr -> collision_bbox {
         auto start = tile_start(k) - Vector2s(1, 0);
         return { start[0], start[1], 2, tile_size2us[1], p };
     };
@@ -107,9 +102,30 @@ auto chunk::ensure_passability() noexcept -> lqt&
     return qt;
 }
 
-void chunk::bb_extractor::ExtractBoundingBox(const chunk::bbox* x, BB* bbox)
+using namespace loose_quadtree;
+
+collision_query chunk::query_collisions(Vector4s vec) const
+{
+    const_cast<chunk&>(*this).ensure_passability();
+    BoundingBox<std::int16_t> bbox { vec[0], vec[1], vec[2], vec[3] };
+    return { _static_lqt->QueryIntersectsRegion(bbox) };
+}
+
+collision_query chunk::query_collisions(Vector2s position, Vector2us size) const
+{
+    const_cast<chunk&>(*this).ensure_passability();
+    constexpr auto half = sTILE_SIZE2/2;
+    const auto start = position - half;
+    return query_collisions(Vector4s{start[0], start[1], (Short)size[0], (Short)size[1] });
+}
+
+collision_query chunk::query_collisions(local_coords p, Vector2us size, Vector2s offset) const
 {
-    *bbox = { x->left, x->top, std::int16_t(x->width), std::int16_t(x->height) };
+    const_cast<chunk&>(*this).ensure_passability();
+    const auto pos = Vector2s(p.x, p.y) * sTILE_SIZE2 + offset;
+    const auto start = pos - Vector2s(size/2);
+    BoundingBox<std::int16_t> bbox { start[0], start[1], (Short)size[0], (Short)size[1] };
+    return { _static_lqt->QueryIntersectsRegion(bbox) };
 }
 
 chunk::chunk() noexcept : _static_lqt { std::make_unique<lqt>() } {}
diff --git a/src/chunk.hpp b/src/chunk.hpp
index d66dfdc8..a560fa21 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -7,13 +7,19 @@
 #include <vector>
 #include <memory>
 #include <Magnum/GL/Mesh.h>
-#include "compat/LooseQuadtree.h"
 
-namespace loose_quadtree { template<typename NumberT, typename ObjectT, typename BoundingBoxExtractorT> class LooseQuadtree; }
+namespace loose_quadtree {
+template<typename Number, typename Object, typename BBExtractor> class LooseQuadtree;
+template<typename Number, typename Object, typename BBExtractor> struct Query;
+} // namespace loose_quadtree
 
 namespace floormat {
 
 struct anim_atlas;
+struct collision_iterator;
+struct collision_bbox;
+struct collision_bb_extractor;
+struct collision_query;
 
 struct chunk final
 {
@@ -63,12 +69,13 @@ struct chunk final
     wall_mesh_tuple ensure_wall_mesh() noexcept;
     tile_atlas* wall_atlas_at(std::size_t i) const noexcept;
 
-    struct bbox final { std::int16_t left, top; std::uint16_t width, height; enum pass_mode pass_mode; };
-    using BB = loose_quadtree::BoundingBox<std::int16_t>;
-    struct bb_extractor { static void ExtractBoundingBox(const bbox* object, BB* bbox); };
-    using lqt = loose_quadtree::LooseQuadtree<std::int16_t, bbox, bb_extractor>;
+    using lqt = loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>;
     lqt& ensure_passability() noexcept;
 
+    collision_query query_collisions(Vector2s position, Vector2us size) const;
+    collision_query query_collisions(local_coords p, Vector2us size, Vector2s offset = {}) const;
+    collision_query query_collisions(Vector4s vec) const;
+
 private:
     std::array<std::shared_ptr<tile_atlas>, TILE_COUNT> _ground_atlases;
     std::array<std::uint8_t, TILE_COUNT> ground_indexes = {};
@@ -80,7 +87,7 @@ private:
     std::array<scenery, TILE_COUNT> _scenery_variants = {};
 
     std::unique_ptr<lqt> _static_lqt;
-    std::vector<bbox> _lqt_bboxes;
+    std::vector<collision_bbox> _lqt_bboxes;
 
     GL::Mesh ground_mesh{NoCreate}, wall_mesh{NoCreate};
     mutable bool _maybe_empty      : 1 = true,
diff --git a/src/collision.cpp b/src/collision.cpp
new file mode 100644
index 00000000..1a9c0b3f
--- /dev/null
+++ b/src/collision.cpp
@@ -0,0 +1,89 @@
+#include "collision.hpp"
+#include "compat/assert.hpp"
+#include "src/chunk.hpp"
+#include "compat/LooseQuadtree-impl.h"
+#include <utility>
+
+namespace floormat {
+
+void collision_bb_extractor::ExtractBoundingBox(const collision_bbox* x, BB* bbox)
+{
+    *bbox = { x->left, x->top, std::int16_t(x->width), std::int16_t(x->height) };
+}
+
+collision_iterator::collision_iterator() noexcept : q{nullptr} {}
+collision_iterator::collision_iterator(Query* q) noexcept : q{q} {}
+
+collision_iterator::~collision_iterator() noexcept
+{
+    if (q)
+        while (!q->EndOfQuery())
+            q->Next();
+}
+
+collision_iterator& collision_iterator::operator++() noexcept
+{
+    fm_debug_assert(q != nullptr && !q->EndOfQuery());
+    q->Next();
+    return *this;
+}
+
+auto collision_iterator::operator++(int) noexcept -> const collision_bbox*
+{
+    fm_debug_assert(q != nullptr && !q->EndOfQuery());
+    auto* bbox = q->GetCurrent();
+    fm_debug_assert(bbox != nullptr);
+    operator++();
+    return bbox;
+}
+
+auto collision_iterator::operator*() const noexcept -> const collision_bbox&
+{
+    return *operator->();
+}
+
+auto collision_iterator::operator->() const noexcept -> const collision_bbox*
+{
+    fm_debug_assert(q != nullptr && !q->EndOfQuery());
+    auto* ptr = q->GetCurrent();
+    fm_debug_assert(ptr != nullptr);
+    return ptr;
+}
+
+bool collision_iterator::operator==(const collision_iterator& other) const noexcept
+{
+    if (q && !other.q) [[likely]]
+        return q->EndOfQuery();
+    else if (!q && !other.q)
+        return true;
+    else if (!q)
+        return other.q->EndOfQuery();
+    else
+        return q == other.q;
+}
+
+collision_iterator::operator bool() const noexcept
+{
+    return q && !q->EndOfQuery();
+}
+
+collision_query::collision_query(collision_query::Query&& q) noexcept : q{std::move(q)} {}
+collision_iterator collision_query::begin() noexcept { return collision_iterator{&q}; }
+collision_iterator collision_query::end() noexcept { return collision_iterator{nullptr}; }
+
+collision_bbox::operator BB() const noexcept
+{
+    return BB{left, top, (Short)width, (Short)height};
+}
+
+bool collision_bbox::intersects(BB bb) const noexcept
+{
+    return BB(*this).Intersects(bb);
+}
+
+bool collision_bbox::intersects(collision_bbox bb) const noexcept
+{
+    return BB(*this).Intersects(bb);
+}
+
+} // namespace floormat
diff --git a/src/collision.hpp b/src/collision.hpp
new file mode 100644
index 00000000..adfec6b0
--- /dev/null
+++ b/src/collision.hpp
@@ -0,0 +1,66 @@
+#pragma once
+#include "compat/LooseQuadtree-impl.h"
+#include "src/pass-mode.hpp"
+#include <cinttypes>
+
+namespace floormat {
+
+struct collision_bbox final
+{
+    using BB = loose_quadtree::BoundingBox<std::int16_t>;
+
+    std::int16_t left, top;
+    std::uint16_t width, height;
+    enum pass_mode pass_mode;
+
+    constexpr collision_bbox();
+    constexpr collision_bbox(std::int16_t left, std::int16_t top, std::uint16_t width, std::uint16_t height, enum pass_mode p) noexcept;
+    operator BB() const noexcept;
+    bool intersects(BB bb) const noexcept;
+    bool intersects(collision_bbox bb) const noexcept;
+};
+
+constexpr collision_bbox::collision_bbox() :
+    left{0}, top{0}, width{0}, height{0}, pass_mode{pass_mode::pass}
+{}
+
+constexpr collision_bbox::collision_bbox(std::int16_t left, std::int16_t top, std::uint16_t width, std::uint16_t height, enum pass_mode p) noexcept :
+    left{left}, top{top}, width{width}, height{height}, pass_mode{p}
+{}
+
+struct collision_bb_extractor final
+{
+    using BB = loose_quadtree::BoundingBox<std::int16_t>;
+    static void ExtractBoundingBox(const collision_bbox* object, BB* bbox);
+};
+
+struct collision_iterator final
+{
+    using Query = typename loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>::Query;
+
+    explicit collision_iterator() noexcept;
+    explicit collision_iterator(Query* q) noexcept;
+    ~collision_iterator() noexcept;
+    collision_iterator& operator++() noexcept;
+    const collision_bbox* operator++(int) noexcept;
+    const collision_bbox& operator*() const noexcept;
+    const collision_bbox* operator->() const noexcept;
+    bool operator==(const collision_iterator& other) const noexcept;
+    operator bool() const noexcept;
+
+private:
+    Query* q;
+};
+
+struct collision_query
+{
+    using Query = typename loose_quadtree::LooseQuadtree<std::int16_t, collision_bbox, collision_bb_extractor>::Query;
+    collision_query(Query&& q) noexcept;
+    collision_iterator begin() noexcept;
+    static collision_iterator end() noexcept;
+
+private:
+    Query q;
+};
+
+} // namespace floormat
diff --git a/src/tile-defs.hpp b/src/tile-defs.hpp
index f40e81ff..b8ea0387 100644
--- a/src/tile-defs.hpp
+++ b/src/tile-defs.hpp
@@ -1,5 +1,6 @@
 #pragma once
 #include <cstddef>
+#include <Magnum/Math/Vector2.h>
 #include <Magnum/Math/Vector3.h>
 
 namespace floormat {
@@ -8,8 +9,10 @@ constexpr inline unsigned char TILE_MAX_DIM = 16;
 constexpr inline std::size_t TILE_COUNT = TILE_MAX_DIM*TILE_MAX_DIM;
 
 constexpr inline auto TILE_MAX_DIM20d = Magnum::Math::Vector3<double> { TILE_MAX_DIM, TILE_MAX_DIM, 0 };
-constexpr inline auto iTILE_SIZE      = Magnum::Math::Vector3<int>    { 64, 64, 64 };
-constexpr inline auto iTILE_SIZE2     = Magnum::Math::Vector2<int>    { iTILE_SIZE[0], iTILE_SIZE[1] };
+constexpr inline auto iTILE_SIZE      = Magnum::Math::Vector3<Int>    { 64, 64, 64 };
+constexpr inline auto iTILE_SIZE2     = Magnum::Math::Vector2<Int>    { iTILE_SIZE[0], iTILE_SIZE[1] };
+constexpr inline auto sTILE_SIZE2     = Magnum::Math::Vector2<Short>  { (Short)iTILE_SIZE[0], (Short)iTILE_SIZE[1] };
+constexpr inline auto usTILE_SIZE2    = Magnum::Math::Vector2<UnsignedShort> { (UnsignedShort)iTILE_SIZE[0], (UnsignedShort)iTILE_SIZE[1] };
 constexpr inline auto TILE_SIZE       = Magnum::Math::Vector3<float>  { iTILE_SIZE };
 constexpr inline auto dTILE_SIZE      = Magnum::Math::Vector3<double> { iTILE_SIZE };
 constexpr inline auto TILE_SIZE2      = Magnum::Math::Vector2<float>  { iTILE_SIZE2 };
diff --git a/test/bbox.cpp b/test/bbox.cpp
index c045d858..87921271 100644
--- a/test/bbox.cpp
+++ b/test/bbox.cpp
@@ -1,28 +1,49 @@
 #include "app.hpp"
 #include "src/chunk.hpp"
-#include "compat/LooseQuadtree-impl.h"
+#include "src/collision.hpp"
 #include <Magnum/Math/Vector2.h>
 
 namespace floormat {
 
-void test_app::test_bbox()
+static void test_simple(chunk c)
 {
-    auto c = make_test_chunk();
     auto& qt = c.ensure_passability();
     fm_assert(qt.GetSize() >= 2);
 
     using namespace loose_quadtree;
     using bbox = BoundingBox<std::int16_t>;
-    constexpr auto pos1 = Vector2s(iTILE_SIZE2 * (TILE_MAX_DIM/2) - Vector2i(0, iTILE_SIZE[1]/2)),
-                   size = Vector2s(iTILE_SIZE2);
-    constexpr auto b1 = bbox{pos1[0], pos1[1], size[0], size[1]};
-    constexpr auto pos2 = Vector2s(iTILE_SIZE2 * (Vector2i(TILE_MAX_DIM/2) - Vector2i(-1, -1)) - Vector2i(0, iTILE_SIZE[1]/2));
+    constexpr auto pos1 = sTILE_SIZE2 * (TILE_MAX_DIM/2) - Vector2s(0, sTILE_SIZE2[1]/2);
+    constexpr auto b1 = bbox{pos1[0], pos1[1], usTILE_SIZE2[0], usTILE_SIZE2[1]};
     auto q1 = qt.QueryIntersectsRegion(b1);
     fm_assert(!q1.EndOfQuery());
+    auto x1 = *q1.GetCurrent();
+    fm_assert(x1.pass_mode == pass_mode::blocked);
     do q1.Next(); while (!q1.EndOfQuery());
-    constexpr auto b2 = bbox{pos2[0], pos2[1], size[0], size[1]};
+    constexpr auto pos2 = Vector2s(iTILE_SIZE2 * (Vector2i(TILE_MAX_DIM/2) - Vector2i(-1, -1)) - Vector2i(0, iTILE_SIZE[1]/2));
+    constexpr auto b2 = bbox{pos2[0], pos2[1], usTILE_SIZE2[0], usTILE_SIZE2[1]};
     auto q2 = qt.QueryIntersectsRegion(b2);
     fm_assert(q2.EndOfQuery());
 }
 
+static void test_wrapper(chunk c)
+{
+    {
+        int i = 0;
+        for (auto b : c.query_collisions(local_coords{TILE_MAX_DIM/2, TILE_MAX_DIM/2},
+                                         usTILE_SIZE2,
+                                         Vector2s(sTILE_SIZE2[0]/2, 0)))
+        {
+            fm_assert(b.pass_mode == pass_mode::blocked);
+            i++;
+        }
+        fm_assert(i > 0);
+    }
+}
+
+void test_app::test_bbox()
+{
+    test_simple(make_test_chunk());
+    test_wrapper(make_test_chunk());
+}
+
 } // namespace floormat