rename more search stuff

11 files changed, 228 insertions, 210 deletions

diff --git a/bench/dijkstra.cpp b/bench/dijkstra.cpp
index 925b5c31..0c47942f 100644
--- a/bench/dijkstra.cpp
+++ b/bench/dijkstra.cpp
@@ -1,5 +1,6 @@
 #include "src/search-astar.hpp"
 #include "src/search-result.hpp"
+#include "src/point.hpp"
 #include "src/world.hpp"
 #include "loader/loader.hpp"
 #include <benchmark/benchmark.h>
diff --git a/src/chunk-region.hpp b/src/chunk-region.hpp
index 579ab1ef..a7281c50 100644
--- a/src/chunk-region.hpp
+++ b/src/chunk-region.hpp
@@ -1,6 +1,6 @@
 #pragma once
 #include "chunk.hpp"
-#include "search.hpp"
+#include "search-constants.hpp"
 #include <bitset>
 
 namespace floormat {
diff --git a/src/dijkstra.cpp b/src/search-astar.cpp
index 15232f90..eb2812a2 100644
--- a/src/dijkstra.cpp
+++ b/src/search-astar.cpp
@@ -1,5 +1,7 @@
 #include "search-astar.hpp"
 #include "search-bbox.hpp"
+#include "search-constants.hpp"
+#include "search-cache.hpp"
 #include "compat/format.hpp"
 #include "compat/vector-wrapper.hpp"
 #include "compat/heap.hpp"
@@ -15,6 +17,13 @@
 
 namespace floormat {
 
+struct astar::visited
+{
+    uint32_t dist = (uint32_t)-1;
+    uint32_t prev = (uint32_t)-1;
+    point pt;
+};
+
 using visited = astar::visited;
 using Search::bbox;
 using Search::div_size;
@@ -133,6 +142,8 @@ astar::astar()
     reserve(initial_capacity);
 }
 
+astar::~astar() noexcept = default;
+
 void astar::reserve(size_t capacity)
 {
     arrayReserve(nodes, capacity);
@@ -170,7 +181,7 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
     Timeline timeline; timeline.start();
 
     clear();
-    cache.allocate(from, max_dist);
+    _cache->allocate(from, max_dist);
 
     const auto own_size = Math::max(Vector2ui(own_size_), min_size);
     constexpr auto goal_thres = (uint32_t)(div_size.length() + 1.5f);
@@ -182,10 +193,10 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
     if (from.coord().z() != 0) [[unlikely]]
         return {};
 
-    if (!path_search::is_passable(w, cache, from.coord(), from.offset(), own_size, own_id, p))
+    if (!path_search::is_passable(w, *_cache, from.coord(), from.offset(), own_size, own_id, p))
         return {};
 
-    if (!path_search::is_passable(w, cache, to.coord(), to.offset(), own_size, own_id, p))
+    if (!path_search::is_passable(w, *_cache, to.coord(), to.offset(), own_size, own_id, p))
         return {};
 
     constexpr int8_t div_min = -div_factor*2, div_max = div_factor*2;
@@ -199,10 +210,10 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
             auto bb = bbox<float>(bbox_from_pos2(from, pt, own_size));
             auto dist = distance(from, pt) + min_dist;
 
-            if (path_search::is_passable(w, cache, from.chunk3(), bb, own_id, p))
+            if (path_search::is_passable(w, *_cache, from.chunk3(), bb, own_id, p))
             {
                 auto idx = (uint32_t)nodes.size();
-                cache.add_index(pt, idx);
+                _cache->add_index(pt, idx);
                 arrayAppend(nodes, {.dist = dist, .prev = (uint32_t)-1, .pt = pt, });
                 add_to_heap(idx);
             }
@@ -242,7 +253,7 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
         {
             auto dist = cur_dist + dist_to_goal;
             if (auto bb = bbox<float>(bbox_from_pos2(to, cur_pt, own_size));
-                path_search::is_passable(w, cache, to.chunk3(), bb, own_id, p))
+                path_search::is_passable(w, *_cache, to.chunk3(), bb, own_id, p))
             {
                 goal_idx = cur_idx;
                 max_dist = dist;
@@ -257,9 +268,9 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
                 continue;
 
             const auto new_pt = object::normalize_coords(cur_pt, vec);
-            auto chunk_idx = cache.get_chunk_index(Vector2i(new_pt.chunk()));
-            auto tile_idx = cache.get_tile_index(Vector2i(new_pt.local()), new_pt.offset());
-            auto new_idx = cache.lookup_index(chunk_idx, tile_idx);
+            auto chunk_idx = _cache->get_chunk_index(Vector2i(new_pt.chunk()));
+            auto tile_idx = _cache->get_tile_index(Vector2i(new_pt.local()), new_pt.offset());
+            auto new_idx = _cache->lookup_index(chunk_idx, tile_idx);
 
             if (new_idx != (uint32_t)-1)
             {
@@ -268,14 +279,14 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
             }
 
             if (auto bb = bbox<float>(bbox_from_pos2(new_pt, cur_pt, own_size));
-                !path_search::is_passable(w, cache, new_pt.chunk3(), bb, own_id, p))
+                !path_search::is_passable(w, *_cache, new_pt.chunk3(), bb, own_id, p))
                 continue;
 
             if (new_idx == (uint32_t)-1)
             {
                 const auto sz = nodes.size();
                 new_idx = (uint32_t)sz;
-                cache.add_index(chunk_idx, tile_idx, new_idx);
+                _cache->add_index(chunk_idx, tile_idx, new_idx);
                 auto new_node = visited {
                     .dist = dist, .prev = cur_idx,
                     .pt = new_pt,
@@ -359,143 +370,3 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
 }
 
 } // namespace floormat
-
-namespace floormat::Search {
-
-struct chunk_cache
-{
-    static constexpr size_t dimensions[] = {
-        TILE_COUNT,
-        (size_t)div_factor * (size_t)div_factor,
-    };
-    static constexpr size_t size = []() constexpr -> size_t {
-        size_t x = 1;
-        for (auto i : dimensions)
-            x *= i;
-        return x;
-    }();
-    static constexpr size_t rank = arraySize(dimensions);
-
-    struct index { uint32_t value = 0; };
-    class chunk* chunk = nullptr;
-    std::array<index, size> indexes = {};
-    std::bitset<size> exists{false};
-};
-
-cache::cache() = default;
-
-Vector2ui cache::get_size_to_allocate(uint32_t max_dist)
-{
-    constexpr auto chunk_size = Vector2ui(iTILE_SIZE2) * TILE_MAX_DIM;
-    constexpr auto rounding   = chunk_size - Vector2ui(1);
-    auto nchunks = (Vector2ui(max_dist) + rounding) / chunk_size;
-    return nchunks + Vector2ui(3);
-}
-
-void cache::allocate(point from, uint32_t max_dist)
-{
-    auto off = get_size_to_allocate(max_dist);
-    start = Vector2i(from.chunk()) - Vector2i(off);
-    size = off * 2u + Vector2ui(1);
-    auto len = size.product();
-    if (len > array.size())
-        array = Array<chunk_cache>{ValueInit, len};
-    else
-        for (auto i = 0uz; i < len; i++)
-        {
-            array[i].chunk = {};
-            array[i].exists = {};
-        }
-}
-
-size_t cache::get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord)
-{
-    auto off = Vector2ui(coord - start);
-    fm_assert(off < size);
-    auto index = off.y() * size.x() + off.x();
-    fm_debug_assert(index < size.product());
-    return index;
-}
-
-size_t cache::get_chunk_index(Vector2i chunk) const { return get_chunk_index(start, size, chunk); }
-
-size_t cache::get_tile_index(Vector2i pos, Vector2b offset_)
-{
-    Vector2i offset{offset_};
-    constexpr auto tile_start = div_size * div_factor/-2;
-    offset -= tile_start;
-    fm_debug_assert(offset >= Vector2i{0, 0} && offset < div_size * div_factor);
-    auto nth_div = Vector2ui(offset) / Vector2ui(div_size);
-    const size_t idx[] = {
-        (size_t)pos.y() * TILE_MAX_DIM + (size_t)pos.x(),
-        (size_t)nth_div.y() * div_factor + (size_t)nth_div.x(),
-    };
-    size_t index = 0;
-    for (auto i = 0uz; i < chunk_cache::rank; i++)
-    {
-        size_t k = idx[i];
-        for (auto j = 0uz; j < i; j++)
-            k *= chunk_cache::dimensions[j];
-        index += k;
-    }
-    fm_debug_assert(index < chunk_cache::size);
-    return index;
-}
-
-void cache::add_index(size_t chunk_index, size_t tile_index, uint32_t index)
-{
-    fm_debug_assert(index != (uint32_t)-1);
-    auto& c = array[chunk_index];
-    fm_debug_assert(!c.exists[tile_index]);
-    c.exists[tile_index] = true;
-    c.indexes[tile_index] = {index};
-}
-
-void cache::add_index(point pt, uint32_t index)
-{
-    auto ch = get_chunk_index(Vector2i(pt.chunk()));
-    auto tile = get_tile_index(Vector2i(pt.local()), pt.offset());
-    fm_debug_assert(!array[ch].exists[tile]);
-    array[ch].exists[tile] = true;
-    array[ch].indexes[tile] = {index};
-}
-
-uint32_t cache::lookup_index(size_t chunk_index, size_t tile_index)
-{
-    auto& c = array[chunk_index];
-    if (c.exists[tile_index])
-        return c.indexes[tile_index].value;
-    else
-        return (uint32_t)-1;
-}
-
-chunk* cache::try_get_chunk(world& w, floormat::chunk_coords_ ch)
-{
-    auto idx = get_chunk_index({ch.x, ch.y});
-    auto& page = array[idx];
-    if (page.chunk == (chunk*)-1)
-        return nullptr;
-    else if (!page.chunk)
-    {
-        page.chunk = w.at(ch);
-        if (!page.chunk)
-        {
-            page.chunk = (chunk*)-1;
-            return nullptr;
-        }
-        return page.chunk;
-    }
-    else
-        return page.chunk;
-}
-
-std::array<chunk*, 8> cache::get_neighbors(world& w, chunk_coords_ ch0)
-{
-    fm_debug_assert(!size.isZero());
-    std::array<chunk*, 8> neighbors;
-    for (auto i = 0u; i < 8; i++)
-        neighbors[i] = try_get_chunk(w, ch0 + world::neighbor_offsets[i]);
-    return neighbors;
-}
-
-} // namespace floormat::Search
diff --git a/src/search-astar.hpp b/src/search-astar.hpp
index 7c48c5db..a56b7f53 100644
--- a/src/search-astar.hpp
+++ b/src/search-astar.hpp
@@ -1,56 +1,21 @@
 #pragma once
+#include "compat/safe-ptr.hpp"
 #include "search.hpp"
-#include "point.hpp"
-#include <bitset>
+#include "search-constants.hpp"
 #include <Corrade/Containers/Array.h>
 
-namespace floormat::Search {
-
-struct cache;
-struct chunk_cache;
-
-struct cache
-{
-    Vector2ui size;
-    Vector2i start{(int)((1u << 31) - 1)};
-    Array<chunk_cache> array;
-
-    cache();
-    fm_DECLARE_DELETED_COPY_ASSIGNMENT(cache);
-
-    size_t get_chunk_index(Vector2i chunk) const;
-    static size_t get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord);
-    static size_t get_tile_index(Vector2i pos, Vector2b offset);
-    static Vector2ui get_size_to_allocate(uint32_t max_dist);
-
-    void allocate(point from, uint32_t max_dist);
-    void add_index(size_t chunk_index, size_t tile_index, uint32_t index);
-    void add_index(point pt, uint32_t index);
-    uint32_t lookup_index(size_t chunk_index, size_t tile_index);
-    chunk* try_get_chunk(world& w, chunk_coords_ ch);
-
-    std::array<chunk*, 8> get_neighbors(world& w, chunk_coords_ ch0);
-};
-
-} // namespace floormat::Search
+namespace floormat::Search { struct cache; }
 
 namespace floormat {
 
 class astar
 {
 public:
-    struct visited
-    {
-        uint32_t dist = (uint32_t)-1;
-        uint32_t prev = (uint32_t)-1;
-        point pt;
-    };
-
+    struct visited;
     using pred = Search::pred;
 
-    fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar);
-
     astar();
+    ~astar() noexcept;
     void reserve(size_t capacity);
     void clear();
 
@@ -62,12 +27,10 @@ public:
 private:
     static constexpr auto initial_capacity = TILE_COUNT * 16 * Search::div_factor*Search::div_factor;
 
-    struct chunk_cache;
-
     void add_to_heap(uint32_t id);
     uint32_t pop_from_heap();
 
-    struct Search::cache cache;
+    safe_ptr<struct Search::cache> _cache;
     Array<visited> nodes;
     Array<uint32_t> Q;
 };
diff --git a/src/search-cache.cpp b/src/search-cache.cpp
new file mode 100644
index 00000000..fae54107
--- /dev/null
+++ b/src/search-cache.cpp
@@ -0,0 +1,145 @@
+#include "search-cache.hpp"
+#include "search-constants.hpp"
+#include "world.hpp"
+#include <array>
+#include <bitset>
+
+namespace floormat::Search {
+
+struct cache::chunk_cache
+{
+    static constexpr size_t dimensions[] = {
+        TILE_COUNT,
+        (size_t)div_factor * (size_t)div_factor,
+    };
+    static constexpr size_t size = []() constexpr -> size_t {
+        size_t x = 1;
+        for (auto i : dimensions)
+            x *= i;
+        return x;
+    }();
+    static constexpr size_t rank = arraySize(dimensions);
+
+    struct index { uint32_t value = 0; };
+    class chunk* chunk = nullptr;
+    std::array<index, size> indexes = {};
+    std::bitset<size> exists{false};
+};
+
+cache::cache() = default;
+
+Vector2ui cache::get_size_to_allocate(uint32_t max_dist)
+{
+    constexpr auto chunk_size = Vector2ui(iTILE_SIZE2) * TILE_MAX_DIM;
+    constexpr auto rounding   = chunk_size - Vector2ui(1);
+    auto nchunks = (Vector2ui(max_dist) + rounding) / chunk_size;
+    return nchunks + Vector2ui(3);
+}
+
+void cache::allocate(point from, uint32_t max_dist)
+{
+    auto off = get_size_to_allocate(max_dist);
+    start = Vector2i(from.chunk()) - Vector2i(off);
+    size = off * 2u + Vector2ui(1);
+    auto len = size.product();
+    if (len > array.size())
+        array = Array<chunk_cache>{ValueInit, len};
+    else
+        for (auto i = 0uz; i < len; i++)
+        {
+            array[i].chunk = {};
+            array[i].exists = {};
+        }
+}
+
+size_t cache::get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord)
+{
+    auto off = Vector2ui(coord - start);
+    fm_assert(off < size);
+    auto index = off.y() * size.x() + off.x();
+    fm_debug_assert(index < size.product());
+    return index;
+}
+
+size_t cache::get_chunk_index(Vector2i chunk) const { return get_chunk_index(start, size, chunk); }
+
+size_t cache::get_tile_index(Vector2i pos, Vector2b offset_)
+{
+    Vector2i offset{offset_};
+    constexpr auto tile_start = div_size * div_factor/-2;
+    offset -= tile_start;
+    fm_debug_assert(offset >= Vector2i{0, 0} && offset < div_size * div_factor);
+    auto nth_div = Vector2ui(offset) / Vector2ui(div_size);
+    const size_t idx[] = {
+        (size_t)pos.y() * TILE_MAX_DIM + (size_t)pos.x(),
+        (size_t)nth_div.y() * div_factor + (size_t)nth_div.x(),
+    };
+    size_t index = 0;
+    for (auto i = 0uz; i < chunk_cache::rank; i++)
+    {
+        size_t k = idx[i];
+        for (auto j = 0uz; j < i; j++)
+            k *= chunk_cache::dimensions[j];
+        index += k;
+    }
+    fm_debug_assert(index < chunk_cache::size);
+    return index;
+}
+
+void cache::add_index(size_t chunk_index, size_t tile_index, uint32_t index)
+{
+    fm_debug_assert(index != (uint32_t)-1);
+    auto& c = array[chunk_index];
+    fm_debug_assert(!c.exists[tile_index]);
+    c.exists[tile_index] = true;
+    c.indexes[tile_index] = {index};
+}
+
+void cache::add_index(point pt, uint32_t index)
+{
+    auto ch = get_chunk_index(Vector2i(pt.chunk()));
+    auto tile = get_tile_index(Vector2i(pt.local()), pt.offset());
+    fm_debug_assert(!array[ch].exists[tile]);
+    array[ch].exists[tile] = true;
+    array[ch].indexes[tile] = {index};
+}
+
+uint32_t cache::lookup_index(size_t chunk_index, size_t tile_index)
+{
+    auto& c = array[chunk_index];
+    if (c.exists[tile_index])
+        return c.indexes[tile_index].value;
+    else
+        return (uint32_t)-1;
+}
+
+chunk* cache::try_get_chunk(world& w, floormat::chunk_coords_ ch)
+{
+    auto idx = get_chunk_index({ch.x, ch.y});
+    auto& page = array[idx];
+    if (page.chunk == (chunk*)-1)
+        return nullptr;
+    else if (!page.chunk)
+    {
+        page.chunk = w.at(ch);
+        if (!page.chunk)
+        {
+            page.chunk = (chunk*)-1;
+            return nullptr;
+        }
+        return page.chunk;
+    }
+    else
+        return page.chunk;
+}
+
+std::array<chunk*, 8> cache::get_neighbors(world& w, chunk_coords_ ch0)
+{
+    fm_debug_assert(!size.isZero());
+    std::array<chunk*, 8> neighbors;
+    for (auto i = 0u; i < 8; i++)
+        neighbors[i] = try_get_chunk(w, ch0 + world::neighbor_offsets[i]);
+    return neighbors;
+}
+
+} // namespace floormat::Search
diff --git a/src/search-cache.hpp b/src/search-cache.hpp
new file mode 100644
index 00000000..c205e36f
--- /dev/null
+++ b/src/search-cache.hpp
@@ -0,0 +1,36 @@
+#pragma once
+#include "compat/defs.hpp"
+#include "point.hpp"
+#include <Corrade/Containers/Array.h>
+#include <Magnum/Math/Vector2.h>
+
+namespace floormat { class world; class chunk; }
+
+namespace floormat::Search {
+
+struct cache
+{
+    struct chunk_cache;
+
+    Vector2ui size;
+    Vector2i start{(int)((1u << 31) - 1)};
+    Array<chunk_cache> array;
+
+    cache();
+    fm_DECLARE_DELETED_COPY_ASSIGNMENT(cache);
+
+    size_t get_chunk_index(Vector2i chunk) const;
+    static size_t get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord);
+    static size_t get_tile_index(Vector2i pos, Vector2b offset);
+    static Vector2ui get_size_to_allocate(uint32_t max_dist);
+
+    void allocate(point from, uint32_t max_dist);
+    void add_index(size_t chunk_index, size_t tile_index, uint32_t index);
+    void add_index(point pt, uint32_t index);
+    uint32_t lookup_index(size_t chunk_index, size_t tile_index);
+    chunk* try_get_chunk(world& w, chunk_coords_ ch);
+
+    std::array<chunk*, 8> get_neighbors(world& w, chunk_coords_ ch0);
+};
+
+} // namespace floormat::Search
diff --git a/src/search-constants.hpp b/src/search-constants.hpp
new file mode 100644
index 00000000..6696e255
--- /dev/null
+++ b/src/search-constants.hpp
@@ -0,0 +1,11 @@
+#pragma once
+#include "tile-constants.hpp"
+
+namespace floormat::Search {
+
+constexpr inline int div_factor = 4;
+constexpr inline auto div_size = iTILE_SIZE2 / div_factor;
+constexpr inline auto min_size = Vector2ui(div_size * 2);
+constexpr inline auto div_count = iTILE_SIZE2 * TILE_MAX_DIM / div_size;
+
+} // namespace floormat::Search
diff --git a/src/search.cpp b/src/search.cpp
index f879260b..af32e7a3 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1,6 +1,7 @@
 #include "search.hpp"
 #include "search-bbox.hpp"
 #include "search-astar.hpp"
+#include "search-cache.hpp"
 #include "global-coords.hpp"
 #include "world.hpp"
 #include "pass-mode.hpp"
diff --git a/src/search.hpp b/src/search.hpp
index 024c8613..b70dc049 100644
--- a/src/search.hpp
+++ b/src/search.hpp
@@ -6,28 +6,16 @@
 #include "search-pred.hpp"
 #include <array>
 
-namespace floormat {
-class world;
-struct object;
-class chunk;
-} // namespace floormat
-
-// todo add pathfinding sub-namespace
-
 namespace floormat::Search {
-
 template<typename T> struct bbox;
 struct cache;
-struct chunk_cache;
-constexpr inline int div_factor = 4;
-constexpr inline auto div_size = iTILE_SIZE2 / div_factor;
-constexpr inline auto min_size = Vector2ui(div_size * 2);
-constexpr inline auto div_count = iTILE_SIZE2 * TILE_MAX_DIM / Search::div_size;
-
 } // namespace floormat::Search
 
 namespace floormat {
 
+class world;
+struct object;
+class chunk;
 struct path_search_result;
 
 class path_search final
diff --git a/test/dijkstra.cpp b/test/dijkstra.cpp
index fe73a468..f5b9ad1f 100644
--- a/test/dijkstra.cpp
+++ b/test/dijkstra.cpp
@@ -1,5 +1,6 @@
 #include "app.hpp"
 #include "src/search-astar.hpp"
+#include "src/point.hpp"
 #include "src/world.hpp"
 #include "loader/loader.hpp"
 #include "loader/wall-cell.hpp"
diff --git a/test/path-search.cpp b/test/path-search.cpp
index 1d9df3f3..069960c1 100644
--- a/test/path-search.cpp
+++ b/test/path-search.cpp
@@ -6,6 +6,7 @@
 #include "src/world.hpp"
 #include "src/scenery.hpp"
 #include "src/search-bbox.hpp"
+#include "src/search-constants.hpp"
 #include <Magnum/Math/Functions.h>
 
 namespace floormat {