a

3 files changed, 30 insertions, 15 deletions

diff --git a/src/path-search-astar.cpp b/src/path-search-astar.cpp
index 03225a33..e8aac080 100644
--- a/src/path-search-astar.cpp
+++ b/src/path-search-astar.cpp
@@ -46,22 +46,26 @@ astar_edge astar_edge::swapped() const
     return e;
 }
 
-astar_edge::astar_edge() {}
-
 bool operator<(const astar_edge_tuple& a, const astar_edge_tuple& b)
 {
     return b.dist < a.dist;
 }
 
-void astar::reserve(size_t count)
+astar::astar()
 {
-    Q.reserve(count);
-    seen.reserve(2*count);
+    mins.max_load_factor(0.25f);
+    reserve(4096);
 }
 
 bool astar::add_visited(const astar_edge& value)
 {
-    return seen.insert(value).second && seen.insert(value.swapped()).second;
+    if (seen.insert(value).second)
+    {
+        auto ret = seen.insert(value.swapped()).second;
+        fm_debug_assert(ret);
+        return true;
+    }
+    return false;
 }
 
 void astar::push(const astar_edge& value, uint32_t dist)
@@ -78,10 +82,17 @@ astar_edge_tuple astar::pop()
     return ret;
 }
 
+void astar::reserve(size_t count)
+{
+    Q.reserve(count);
+    seen.reserve(2*count);
+}
+
 void astar::clear()
 {
     Q.clear();
     seen.clear();
+    mins.clear();
 }
 
 } // namespace floormat
diff --git a/src/path-search-astar.hpp b/src/path-search-astar.hpp
index 9da51d24..bb3089b2 100644
--- a/src/path-search-astar.hpp
+++ b/src/path-search-astar.hpp
@@ -2,8 +2,8 @@
 #include "compat/defs.hpp"
 #include "global-coords.hpp"
 #include <vector>
-
 #include <tsl/robin_set.h>
+#include <tsl/robin_map.h>
 
 namespace floormat {
 
@@ -30,9 +30,6 @@ struct astar_edge
     int8_t from_offx, from_offy, to_offx, to_offy;
 
     static constexpr auto INF = (uint32_t)-1;
-
-private:
-    astar_edge();
 };
 
 struct astar_edge_tuple
@@ -46,19 +43,24 @@ struct astar_edge_tuple
 
 struct astar final
 {
-    void reserve(size_t count);
-    bool empty() const { return Q.empty(); }
+    astar();
     [[nodiscard]] bool add_visited(const astar_edge& value);
     void push(const astar_edge& value, uint32_t dist);
     astar_edge_tuple pop();
+
+    bool empty() const { return Q.empty(); }
+    void reserve(size_t count);
     void clear();
 
 private:
+    struct edge_min { astar_edge prev; uint32_t len; };
+
     static constexpr bool StoreHash = true; // todo benchmark it
     tsl::robin_set<astar_edge,
                    astar_hash, std::equal_to<>,
                    std::allocator<astar_edge>,
                    StoreHash> seen;
+    tsl::robin_map<astar_edge, edge_min, astar_hash> mins;
     std::vector<astar_edge_tuple> Q;
 };
 
diff --git a/src/path-search-dijkstra.cpp b/src/path-search-dijkstra.cpp
index 44da9ebe..8d877784 100644
--- a/src/path-search-dijkstra.cpp
+++ b/src/path-search-dijkstra.cpp
@@ -112,15 +112,17 @@ path_search_result path_search::Dijkstra(world& w, Vector2ub own_size, object_id
         auto [cur, dist0] = astar.pop();
         if (!astar.add_visited(cur))
             continue;
+        for (auto [dir, len] : dirs)
+        {
+
+        }
     }
 
     // todo...
     return result;
 }
 
-path_search_result path_search::Dijkstra(world& w, const object& obj,
-                                         global_coords to, Vector2b to_offset,
-                                         const pred& p)
+path_search_result path_search::Dijkstra(world& w, const object& obj, global_coords to, Vector2b to_offset, const pred& p)
 {
     constexpr auto full_tile = Vector2ub(iTILE_SIZE2*3/4);
     auto size = Math::max(obj.bbox_size, full_tile);