1 files changed, 57 insertions, 33 deletions

diff --git a/src/path-search.hpp b/src/path-search.hpp
index 29c32a22..5a8a0f9e 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -4,16 +4,18 @@
 #include "rotation.hpp"
 #include "world.hpp"
 #include "compat/function2.fwd.hpp"
-#include "path-search-astar.hpp"
 #include "path-search-result.hpp"
+#include "compat/int-hash.hpp"
+#include <bit>
 #include <array>
-#include <Corrade/Containers/Array.h>
 #include <Magnum/Math/Vector2.h>
 #include <Magnum/DimensionTraits.h>
+#include <tsl/robin_hash.h>
 
 namespace Corrade::Containers {
-template<typename T> class Optional;
-template<typename T, typename U> class Pair;
+//template<typename T> class Optional;
+//template<typename T, typename U> class Pair;
+template<typename T> class ArrayView;
 } // namespace Corrade::Containers
 
 namespace floormat {
@@ -23,21 +25,60 @@ struct object;
 struct chunk;
 
 struct path_search_result;
-class path_search;
-
-struct astar_edge;
-struct astar_hash;
-struct astar;
 
 enum class path_search_continue : bool { pass = false, blocked = true };
 
+struct astar
+{
+    fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar);
+
+    struct position
+    {
+        global_coords coord;
+        Vector2b offset;
+
+        bool operator==(const position&) const = default;
+    };
+    struct visited
+    {
+        uint32_t dist = (uint32_t)-1;
+        uint32_t prev = (uint32_t)-1;
+        global_coords coord;
+        Vector2b offset;
+        bool expanded = false;
+    };
+    struct hash_op
+    {
+        size_t operator()(position coord) const;
+    };
+    void reserve(size_t capacity)
+    {
+        nodes.reserve(capacity);
+        indexes.reserve(capacity);
+        Q.reserve(capacity);
+    }
+    astar()
+    {
+        constexpr auto capacity = TILE_COUNT * 16;
+        indexes.max_load_factor(.4f);
+        reserve(capacity);
+    }
+    void clear()
+    {
+        nodes.clear();
+        indexes.clear();
+        Q.clear();
+    }
+
+    std::vector<visited> nodes;
+    tsl::robin_map<position, uint32_t, hash_op> indexes;
+    std::vector<uint32_t> Q;
+};
+
 class path_search final
 {
     friend struct path_search_result;
 
-    // todo bucketize by array length
-    struct astar astar;
-
 public:
     static constexpr int subdivide_factor = 4;
     static constexpr auto div_size = iTILE_SIZE2 / subdivide_factor;
@@ -54,28 +95,12 @@ public:
         operator ArrayView<const global_coords>() const;
     };
 
-#if 0
-    struct chunk_tiles_cache
-    {
-        std::bitset<tile_count> can_go_north{true}, can_go_west{true};
-    };
-
-    struct chunk_cache
-    {
-        Array<chunk_tiles_cache> array;
-        Vector2i start, size; // in chunks
-    };
-#endif
-
-    struct obj_position { Vector2 center, size; };
-
     template<typename T> struct bbox { VectorTypeFor<2, T> min, max; };
 
-#if 0
-    chunk_cache cache;
-#endif
-
     using pred = fu2::function_view<path_search_continue(collision_data) const>;
+
+    struct astar astar;
+
     static const pred& never_continue() noexcept;
     static const pred& always_continue() noexcept;
 
@@ -90,9 +115,8 @@ public:
     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, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue());
 
+    // todo move to test/path-search.cpp
     static bbox<float> neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r);
-    template<typename T> requires std::is_arithmetic_v<T> static bbox<T> bbox_union(bbox<T> bb, Vector2i coord, Vector2b offset, Vector2ub size);
-    static bbox<int> bbox_union(bbox<int> bb1, bbox<int> bb2);
     static neighbors neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p = never_continue());
 };