a

5 files changed, 73 insertions, 34 deletions

diff --git a/src/path-search-result.cpp b/src/path-search-result.cpp
new file mode 100644
index 00000000..065f3d65
--- /dev/null
+++ b/src/path-search-result.cpp
@@ -0,0 +1,9 @@
+#include "path-search.hpp"
+#include "path-search-result.hpp"
+
+namespace floormat {
+
+path_search_result::path_search_result() = default;
+size_t path_search_result::size() const { return _size; }
+
+} // namespace floormat
diff --git a/src/path-search-result.hpp b/src/path-search-result.hpp
new file mode 100644
index 00000000..bc63a932
--- /dev/null
+++ b/src/path-search-result.hpp
@@ -0,0 +1,31 @@
+#pragma once
+#include "src/global-coords.hpp"
+
+namespace floormat {
+
+struct path_search_result final
+{
+    friend class path_search;
+    path_search_result();
+    size_t size() const;
+
+    const global_coords& operator[](size_t index) const;
+    explicit operator ArrayView<global_coords>() const;
+
+    const global_coords* begin() const;
+    const global_coords* cbegin() const;
+    const global_coords* end() const;
+    const global_coords* cend() const;
+    const global_coords* data() const;
+
+    explicit operator bool() const;
+
+private:
+    static constexpr size_t min_length = TILE_MAX_DIM*2;
+
+    path_search_result* _next = nullptr;
+    global_coords* _path = nullptr;
+    size_t _size = 0, _reserved = 0;
+};
+
+} // namespace floormat
diff --git a/src/path-search.cpp b/src/path-search.cpp
index f8d0a64f..88026ed4 100644
--- a/src/path-search.cpp
+++ b/src/path-search.cpp
@@ -124,7 +124,6 @@ static_assert(test_offsets2());
 
 } // namespace
 
-path_search_result::path_search_result() = default;
 auto path_search::never_continue() noexcept -> const pred& { return never_continue_; }
 auto path_search::always_continue() noexcept -> const pred& { return always_continue_; }
 
@@ -223,7 +222,7 @@ bool path_search::is_passable(world& w, global_coords coord, Vector2b offset, Ve
     return is_passable(w, coord, min, max, own_id, p);
 }
 
-auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r) -> bbox<float>
+auto path_search::neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r) -> bbox<float>
 {
     const auto shift = coord * iTILE_SIZE2;
     auto sz = Math::max(Vector2i(own_size), min_size);
@@ -231,7 +230,7 @@ auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Ve
     return { Vector2(min + shift), Vector2(max + shift) };
 }
 
-auto path_search::get_walkable_neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p) -> neighbors
+auto path_search::neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p) -> neighbors
 {
     auto ch = chunk_coords_{ coord.chunk(), coord.z() };
     auto pos = Vector2i(coord.local());
@@ -239,7 +238,7 @@ auto path_search::get_walkable_neighbor_tiles(world& w, global_coords coord, Vec
     size = Math::max(size, min_size);
 
 #if 0
-    if (auto [min, max] = make_neighbor_tile_bbox(pos, size, rotation_COUNT);
+    if (auto [min, max] = neighbor_tile_bbox(pos, size, rotation_COUNT);
         !is_passable(w, ch, min, max, own_id))
         return {};
 #endif
@@ -259,7 +258,7 @@ auto path_search::get_walkable_neighbor_tiles(world& w, global_coords coord, Vec
 
     for (auto [off, dir] : nbs)
     {
-        auto [min, max] = make_neighbor_tile_bbox(pos, size, {1,1}, dir);
+        auto [min, max] = neighbor_tile_bbox(pos, size, { 1, 1 }, dir);
         if (is_passable(w, ch, min, max, own_id, p))
             ns.neighbors[ns.size++] = coord + off;
     }
@@ -337,7 +336,7 @@ void path_search::fill_cache(world& w, Vector2i cmin, Vector2i cmax, int8_t z,
             fill_cache_(w, {(int16_t)x, (int16_t)y, z}, own_size, own_id, p);
 }
 
-Optional<path_search_result> path_search::dijkstra(world& w, Vector2ub own_size, object_id own_id,
+Optional<path_search_result> path_search::Dijkstra(world& w, Vector2ub own_size, object_id own_id,
                                                    global_coords from, Vector2b from_offset,
                                                    global_coords to, Vector2b to_offset,
                                                    const pred& p)
@@ -365,7 +364,7 @@ Optional<path_search_result> path_search::dijkstra(world& w, Vector2ub own_size,
     return {};
 }
 
-Optional<path_search_result> path_search::dijkstra(world& w, const object& obj,
+Optional<path_search_result> path_search::Dijkstra(world& w, const object& obj,
                                                    global_coords to, Vector2b to_offset,
                                                    const pred& p)
 {
@@ -377,7 +376,7 @@ Optional<path_search_result> path_search::dijkstra(world& w, const object& obj,
     // maybe add handling to subtract bbox_offset from the returned path.
     // for that it needs to be passed into callees separately.
     fm_assert(obj.bbox_offset.isZero());
-    return dijkstra(w, size, obj.id, obj.coord, obj.offset, to, to_offset, p);
+    return Dijkstra(w, size, obj.id, obj.coord, obj.offset, to, to_offset, p);
 }
 
 } // namespace floormat
diff --git a/src/path-search.hpp b/src/path-search.hpp
index 23401106..05abc941 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -5,6 +5,7 @@
 #include "rotation.hpp"
 #include "world.hpp"
 #include "compat/function2.fwd.hpp"
+#include "path-search-result.hpp"
 #include <memory>
 #include <array>
 #include <vector>
@@ -27,31 +28,32 @@ struct chunk;
 struct path_search_result;
 class path_search;
 
-struct path_search_result final
+struct search_astar final
 {
-    friend class path_search;
-    path_search_result();
-
-    size_t size() const;
-    const global_coords& operator[](size_t index) const;
-    explicit operator ArrayView<global_coords>() const;
-
-    const global_coords* begin() const;
-    const global_coords* cbegin() const;
-    const global_coords* end() const;
-    const global_coords* cend() const;
-    const global_coords* data() const;
-
-private:
-    mutable path_search_result* _next = nullptr;
-    std::unique_ptr<global_coords[]> _path;
-    size_t _size = 0;
+    struct vertex_tuple
+    {
+        static constexpr auto INF = (uint32_t)-1;
+
+        const chunk *c1 = nullptr, *c2 = nullptr;
+        uint32_t dist = 0;
+    };
+
+    [[nodiscard]] bool reserve(chunk_coords_ c1, chunk_coords_ c2);
+    void insert(const chunk& c1, const chunk& c2);
+    vertex_tuple delete_min();
+    void add_edges();
+    bool find(chunk_coords_);
+
+    std::vector<vertex_tuple> Q;
+    std::vector<global_coords> output;
 };
 
 enum class path_search_continue : bool { pass = false, blocked = true };
 
 class path_search final
 {
+    friend struct path_search_result;
+
     // todo bucketize by array length
     path_search_result* pool = nullptr;
 
@@ -85,8 +87,6 @@ public:
     template<typename T> struct bbox { VectorTypeFor<2, T> min, max; };
 
     chunk_cache cache;
-    Array<global_coords> output;
-
 
     using pred = fu2::function_view<path_search_continue(collision_data) const>;
     static const pred& never_continue() noexcept;
@@ -98,8 +98,8 @@ public:
 
     // todo remember to check from.z() == to.z()
     // todo add simple bresenham short-circuit
-    Optional<path_search_result> dijkstra(world& w, Vector2ub own_size, object_id own_id, global_coords from, Vector2b from_offset, global_coords to, Vector2b to_offset, const pred& p = never_continue());
-    Optional<path_search_result> dijkstra(world& w, const object& obj, global_coords to, Vector2b to_offset, const pred& p = never_continue());
+    Optional<path_search_result> Dijkstra(world& w, Vector2ub own_size, object_id own_id, global_coords from, Vector2b from_offset, global_coords to, Vector2b to_offset, const pred& p = never_continue());
+    Optional<path_search_result> Dijkstra(world& w, const object& obj, global_coords to, Vector2b to_offset, const pred& p = never_continue());
 
     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,
@@ -107,9 +107,9 @@ public:
     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 bbox<float> make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r);
+    static bbox<float> neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r);
     static bbox<float> bbox_union(bbox<float> bb, Vector2i coord, Vector2b offset, Vector2ub size);
-    static neighbors get_walkable_neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p = never_continue());
+    static neighbors neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p = never_continue());
 };
 
 } // namespace floormat
diff --git a/test/path-search.cpp b/test/path-search.cpp
index 49d7c7b9..269c8c79 100644
--- a/test/path-search.cpp
+++ b/test/path-search.cpp
@@ -24,11 +24,11 @@ void test_bbox()
     };
 
     static constexpr auto bbox = [](Vector2i coord, rotation r) {
-        return path_search::make_neighbor_tile_bbox(coord, {}, {1,1}, r);
+        return path_search::neighbor_tile_bbox(coord, {}, { 1, 1 }, r);
     };
 
     constexpr auto neighbor_tiles = [](world& w, chunk_coords_ ch, Vector2i pos) {
-        return path_search::get_walkable_neighbor_tiles(w, {ch, pos}, {}, (object_id)-1);
+        return path_search::neighbor_tiles(w, { ch, pos }, {}, (object_id)-1);
     };
 
     const auto metal2 = loader.tile_atlas("metal2", {2, 2}, pass_mode::blocked);