a

3 files changed, 83 insertions, 60 deletions

diff --git a/src/dijkstra.cpp b/src/dijkstra.cpp
index 69711453..64830c7d 100644
--- a/src/dijkstra.cpp
+++ b/src/dijkstra.cpp
@@ -14,11 +14,10 @@ namespace floormat {
 
 template<typename T> using bbox = path_search::bbox<T>;
 using visited = astar::visited;
+using namespace floormat::detail_astar;
 
 namespace {
 
-constexpr auto div_size = path_search::div_size;
-
 constexpr bbox<Int> bbox_from_pos1(point pt, Vector2ui size)
 {
     auto center = Vector2i(pt.local()) * iTILE_SIZE2 + Vector2i(pt.offset());
@@ -168,7 +167,6 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
     clear();
     cache.allocate(from, max_dist);
 
-    constexpr auto min_size = Vector2ui{div_size};
     const auto own_size = Math::max(Vector2ui(own_size_), min_size);
     constexpr auto goal_thres = (uint32_t)(div_size.length() + 1.5f);
 
@@ -196,7 +194,7 @@ 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, 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);
@@ -239,7 +237,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, 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;
@@ -265,7 +263,7 @@ 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, 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)
@@ -355,7 +353,7 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to,
     return result;
 }
 
-struct astar::chunk_cache
+struct detail_astar::chunk_cache
 {
     static constexpr size_t dimensions[] = {
         TILE_COUNT,
@@ -370,13 +368,14 @@ struct astar::chunk_cache
     static constexpr size_t rank = sizeof(dimensions)/sizeof(dimensions[0]);
 
     struct index { uint32_t value = 0; };
+    class chunk* chunk = nullptr;
     std::array<index, size> indexes = {};
     std::bitset<size> exists{false};
 };
 
-astar::cache::cache() = default;
+detail_astar::cache::cache() = default;
 
-Vector2ui astar::cache::get_size_to_allocate(uint32_t max_dist)
+Vector2ui detail_astar::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);
@@ -384,7 +383,7 @@ Vector2ui astar::cache::get_size_to_allocate(uint32_t max_dist)
     return nchunks + Vector2ui(3);
 }
 
-void astar::cache::allocate(point from, uint32_t max_dist)
+void detail_astar::cache::allocate(point from, uint32_t max_dist)
 {
     auto off = get_size_to_allocate(max_dist);
     start = Vector2i(from.chunk()) - Vector2i(off);
@@ -397,7 +396,7 @@ void astar::cache::allocate(point from, uint32_t max_dist)
             array[i].exists = {};
 }
 
-size_t astar::cache::get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord)
+size_t detail_astar::cache::get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord)
 {
     auto off = Vector2ui(coord - start);
     fm_assert(off < size);
@@ -406,9 +405,9 @@ size_t astar::cache::get_chunk_index(Vector2i start, Vector2ui size, Vector2i co
     return index;
 }
 
-size_t astar::cache::get_chunk_index(Vector2i chunk) const { return get_chunk_index(start, size, chunk); }
+size_t detail_astar::cache::get_chunk_index(Vector2i chunk) const { return get_chunk_index(start, size, chunk); }
 
-size_t astar::cache::get_tile_index(Vector2i pos, Vector2b offset_)
+size_t detail_astar::cache::get_tile_index(Vector2i pos, Vector2b offset_)
 {
     Vector2i offset{offset_};
     constexpr auto tile_start = div_size * div_factor/-2;
@@ -431,7 +430,7 @@ size_t astar::cache::get_tile_index(Vector2i pos, Vector2b offset_)
     return index;
 }
 
-void astar::cache::add_index(size_t chunk_index, size_t tile_index, uint32_t index)
+void detail_astar::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];
@@ -440,7 +439,7 @@ void astar::cache::add_index(size_t chunk_index, size_t tile_index, uint32_t ind
     c.indexes[tile_index] = {index};
 }
 
-void astar::cache::add_index(point pt, uint32_t index)
+void detail_astar::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());
@@ -449,7 +448,7 @@ void astar::cache::add_index(point pt, uint32_t index)
     array[ch].indexes[tile] = {index};
 }
 
-uint32_t astar::cache::lookup_index(size_t chunk_index, size_t tile_index)
+uint32_t detail_astar::cache::lookup_index(size_t chunk_index, size_t tile_index)
 {
     auto& c = array[chunk_index];
     if (c.exists[tile_index])
@@ -458,4 +457,24 @@ uint32_t astar::cache::lookup_index(size_t chunk_index, size_t tile_index)
         return (uint32_t)-1;
 }
 
+chunk* detail_astar::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;
+}
+
 } // namespace floormat
diff --git a/src/path-search.cpp b/src/path-search.cpp
index 94da7f10..739826be 100644
--- a/src/path-search.cpp
+++ b/src/path-search.cpp
@@ -7,11 +7,12 @@
 
 namespace floormat {
 
+using namespace detail_astar;
+
 namespace {
 
-constexpr auto div = path_search::div_factor;
 constexpr int div_BITS = 2;
-static_assert(1 << div_BITS == div);
+static_assert(1 << div_BITS == div_factor);
 
 constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; };
 constexpr auto never_continue_ = path_search::pred{never_continue_1};
@@ -84,31 +85,32 @@ bool path_search::is_passable_(chunk* c0, const std::array<world::neighbor_pair,
     return true;
 }
 
-bool path_search::is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, object_id own_id, const pred& p)
-{
-    auto* c = w.at(ch0);
-    auto neighbors = w.neighbors(ch0);
-    return is_passable_(c, neighbors, min, max, own_id, p);
-}
-
 bool path_search::is_passable(world& w, global_coords coord, Vector2b offset, Vector2ui size_,
                               object_id own_id, const pred& p)
 {
     auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset);
     auto size = Vector2(size_);
     auto min = Vector2(center) - size*.5f, max = min + size;
-    return is_passable(w, coord, min, max, own_id, p);
+    return is_passable(w, coord, {min, max}, own_id, p);
 }
 
-bool path_search::is_passable(world& w, global_coords coord, Vector2b offset, Vector2ub size,
-                              object_id own_id, const pred& p)
+bool path_search::is_passable(world& w, chunk_coords_ ch, const bbox<float>& bb, object_id own_id, const pred& p)
 {
-    return is_passable(w, coord, offset, Vector2ui(size), own_id, p);
+    auto* c = w.at(ch);
+    auto neighbors = w.neighbors(ch);
+    return is_passable_(c, neighbors, bb.min, bb.max, own_id, p);
 }
 
-bool path_search::is_passable(world& w, chunk_coords_ ch, const bbox<float>& bb, object_id own_id, const pred& p)
+bool path_search::is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p)
 {
-    return is_passable(w, ch, bb.min, bb.max, own_id, p);
+    fm_debug_assert(!cache.size.isZero());
+    std::array<world::neighbor_pair, 8> neighbors;
+    for (auto i = 0uz; const auto& x : world::neighbor_offsets)
+    {
+        auto ch = ch0 + x;
+        neighbors[i++] = { cache.try_get_chunk(w, ch), ch0 };
+    }
+    return is_passable_(cache.try_get_chunk(w, ch0), neighbors, bb.min, bb.max, own_id, p);
 }
 
 } // namespace floormat
diff --git a/src/path-search.hpp b/src/path-search.hpp
index 42d99d4d..672ecc3d 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -23,6 +23,34 @@ class chunk;
 
 // todo add pathfinding sub-namespace
 
+namespace detail_astar {
+
+struct chunk_cache;
+static constexpr int div_factor = 4;
+static constexpr auto div_size = iTILE_SIZE2 / div_factor;
+static constexpr auto min_size = Vector2ui(div_size * 2);
+
+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);
+};
+} // namespace detail_astar
 struct path_search_result;
 enum class path_search_continue : bool { pass = false, blocked = true };
 
@@ -31,10 +59,6 @@ class path_search final
     friend struct path_search_result;
 
 public:
-    static constexpr int div_factor = 4;
-    static constexpr auto div_size = iTILE_SIZE2 / div_factor;
-    static constexpr auto min_size = Vector2ui(div_size * 2);
-
     template<typename T>
     requires std::is_arithmetic_v<T>
     struct bbox
@@ -59,10 +83,9 @@ public:
     static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue());
     static bool is_passable_(chunk* c0, const std::array<world::neighbor_pair, 8>& neighbors,
                              Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue());
-    static bool is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue());
-    static bool is_passable(world& w, global_coords coord, Vector2b offset, Vector2ub size, object_id own_id, const pred& p = never_continue());
     static bool is_passable(world& w, global_coords coord, Vector2b offset, Vector2ui size, object_id own_id, const pred& p = never_continue());
     static bool is_passable(world& w, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue());
+    static bool is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue());
 };
 
 class astar
@@ -90,35 +113,14 @@ public:
                                 int debug = 0, const pred& p = path_search::never_continue());
 
 private:
-    static constexpr auto div_factor = (int8_t)path_search::div_factor;
-    static constexpr auto initial_capacity = TILE_COUNT * 16 * div_factor*div_factor;
+    static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor;
 
     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);
-    };
-
     void add_to_heap(uint32_t id);
     uint32_t pop_from_heap();
 
-    struct cache cache;
+    struct detail_astar::cache cache;
     std::vector<visited> nodes;
     std::vector<uint32_t> Q;
 };