a

3 files changed, 36 insertions, 11 deletions

diff --git a/src/path-search-dijkstra.cpp b/src/path-search-dijkstra.cpp
index bcf34cb5..e88461dd 100644
--- a/src/path-search-dijkstra.cpp
+++ b/src/path-search-dijkstra.cpp
@@ -145,13 +145,14 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
 
     if (!from_offset.isZero())
     {
+        uint32_t idx = 1;
         // todo also add 4 subdivisions within the tile the same way
         auto bb = bbox_union(start_bbox, Vector2i(from.local()), {}, own_size);
         if (path_search::is_passable(w, chunk_coords_{from}, bb, own_id, p))
         {
-            indexes[{from, {}}] = 1;
+            indexes[{from, {}}] = idx;
             nodes.push_back({.dist = from_offset_len, .prev = 0, .coord = from, .offset = {}});
-            Q.push_back(1);
+            Q.push_back(idx++);
             std::push_heap(Q.begin(), Q.end(), heap_comparator);
         }
     }
@@ -162,18 +163,16 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
         const auto id = Q.back();
         Q.pop_back();
 
-        fm_debug_assert(id < nodes.size());
-        auto& node = nodes[id];
-        fm_debug_assert(node.dist != (uint32_t)-1);
+        auto node = box{nodes, id};
 
         //Debug{} << "node" << id << "|" << node.coord.to_signed3() << node.offset << "|" << node.dist;
 
-        const auto bb0 = bbox_from_pos(Vector2(node.coord.local()), node.offset, own_size);
+        const auto bb0 = bbox_from_pos(Vector2(node->coord.local()), node->offset, own_size);
 
         for (auto [vec, len] : directions)
         {
-            auto [new_coord, new_offset] = object::normalize_coords(node.coord, node.offset, vec);
-            const auto dist = node.dist + len;
+            auto [new_coord, new_offset] = object::normalize_coords(node->coord, node->offset, vec);
+            const auto dist = node->dist + len;
             if (dist >= max_dist)
                 continue;
 
@@ -221,7 +220,7 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
         }
     }
 
-    Debug {} << "done";
+    //Debug {} << "done!" << nodes.size() << "nodes";
 
     // todo...
     return result;
diff --git a/src/path-search.hpp b/src/path-search.hpp
index b37afa34..b6c3f38c 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -72,6 +72,21 @@ class astar
         bool operator==(const edge& other) const;
     };
 
+    class box
+    {
+        std::vector<visited>& vec; // NOLINT
+        uint32_t id;
+
+    public:
+        fm_DECLARE_DELETED_COPY_ASSIGNMENT(box);
+        fm_DECLARE_DELETED_MOVE_ASSIGNMENT(box);
+
+        visited& operator*() { return vec[id]; }
+        visited* operator->() { return &vec[id]; }
+
+        box(std::vector<visited>& vec, uint32_t id) : vec{vec}, id{id} {}
+    };
+
     enum class edge_status : uint8_t
     {
         // good, bad, I'm the man with the gun.
diff --git a/test/dijkstra.cpp b/test/dijkstra.cpp
index d34e28bf..c19a7fcb 100644
--- a/test/dijkstra.cpp
+++ b/test/dijkstra.cpp
@@ -1,5 +1,6 @@
 #include "app.hpp"
 #include "path-search.hpp"
+#include <chrono>
 
 namespace floormat {
 
@@ -8,8 +9,18 @@ void test_app::test_dijkstra()
     auto w = world();
     auto a = astar();
 
-    a.Dijkstra(w, {}, 0, {{0, 0, 0}, {}}, {{1, 1, 0}, {}},
-               1*TILE_MAX_DIM*iTILE_SIZE2.x());
+    using namespace std::chrono;
+    using clock = high_resolution_clock;
+
+    const auto t0 =  clock::now();
+
+    for (int i = 0; i < 10; i++)
+    {
+        a.Dijkstra(w, {}, 0, {{0, 0, 0}, {}}, {{1, 1, 0}, {}},
+                       1*TILE_MAX_DIM*iTILE_SIZE2.x());
+    }
+    const auto tm = clock::now() - t0;
+    Debug{} << "test took" << std::chrono::duration_cast<milliseconds>(tm).count() << "ms.";
 }
 
 } // namespace floormat