a

8 files changed, 118 insertions, 81 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index b3118d5f..37bfac1b 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -238,7 +238,6 @@ function(fm_add_install_executable self)
             install(FILES $<TARGET_PDB_FILE:${self}> DESTINATION bin)
         endif()
     endif()
-
 endfunction()
 
 add_subdirectory(src)
diff --git a/editor/app.hpp b/editor/app.hpp
index 15e9d7a7..0a94fce8 100644
--- a/editor/app.hpp
+++ b/editor/app.hpp
@@ -154,8 +154,8 @@ private:
     void clear_non_global_keys();
     void clear_non_repeated_keys();
 
-    [[nodiscard]] bool tests_handle_key(const key_event& e);
-    [[nodiscard]] bool tests_handle_mouse_click(const mouse_button_event& e);
+    [[nodiscard]] bool tests_handle_key(const key_event& e, bool is_down);
+    [[nodiscard]] bool tests_handle_mouse_click(const mouse_button_event& e, bool is_down);
     [[nodiscard]] bool tests_handle_mouse_move(const mouse_move_event& e);
     void tests_pre_update();
     void tests_post_update();
diff --git a/editor/events.cpp b/editor/events.cpp
index 83039bcb..b0a9f590 100644
--- a/editor/events.cpp
+++ b/editor/events.cpp
@@ -87,7 +87,7 @@ void app::on_mouse_up_down(const mouse_button_event& event, bool is_down) noexce
 
     if ((cursor.in_imgui = is_down ? _imgui.handleMousePressEvent(e) : _imgui.handleMouseReleaseEvent(e)))
         void();
-    else if (_editor.mode() == editor_mode::tests && tests_handle_mouse_click(event))
+    else if (_editor.mode() == editor_mode::tests && tests_handle_mouse_click(event, is_down))
         void();
     else
         do_mouse_up_down(button, is_down, fixup_mods(event.mods));
@@ -190,7 +190,7 @@ void app::on_key_up_down(const key_event& event, bool is_down) noexcept
     static_assert(key_GLOBAL >= key_NO_REPEAT);
 
     if (x == key_COUNT && (is_down ? _imgui.handleKeyPressEvent(e) : _imgui.handleKeyReleaseEvent(e)) ||
-        (x == key_COUNT || x == key_escape) && _editor.mode() == editor_mode::tests && tests_handle_key(event))
+        (x == key_COUNT || x == key_escape) && _editor.mode() == editor_mode::tests && tests_handle_key(event, is_down))
         clear_non_global_keys();
     else if (x >= key_NO_REPEAT)
         is_down && !event.is_repeated ? do_key(x, mods) : void();
diff --git a/editor/tests-private.hpp b/editor/tests-private.hpp
index 5c229696..0300c8a5 100644
--- a/editor/tests-private.hpp
+++ b/editor/tests-private.hpp
@@ -2,6 +2,7 @@
 #include "tests.hpp"
 #include "compat/defs.hpp"
 #include "src/point.hpp"
+#include "src/object-id.hpp"
 #include "floormat/events.hpp"
 #include <Corrade/Containers/StringView.h>
 #include <vector>
@@ -19,8 +20,8 @@ struct base_test
     fm_DECLARE_DEFAULT_MOVE_ASSIGNMENT_(base_test);
     fm_DECLARE_DELETED_COPY_ASSIGNMENT(base_test);
 
-    virtual bool handle_key(app& a, const key_event& e) = 0;
-    virtual bool handle_mouse_click(app& a, const mouse_button_event& e) = 0;
+    virtual bool handle_key(app& a, const key_event& e, bool is_down) = 0;
+    virtual bool handle_mouse_click(app& a, const mouse_button_event& e, bool is_down) = 0;
     virtual bool handle_mouse_move(app& a, const mouse_move_event& e) = 0;
     virtual void draw_overlay(app& a) = 0;
     virtual void update_pre(app& a) = 0;
@@ -34,16 +35,28 @@ protected:
 
 struct path_test : base_test
 {
-    bool handle_key(app& a, const key_event& e) override;
-    bool handle_mouse_click(app& a, const mouse_button_event& e) override;
+    bool handle_key(app& a, const key_event& e, bool is_down) override;
+    bool handle_mouse_click(app& a, const mouse_button_event& e, bool is_down) override;
     bool handle_mouse_move(app& a, const mouse_move_event& e) override;
     void draw_overlay(app& a) override;
     void update_pre(app& a) override;
     void update_post(app& a) override;
 
-    point from;
-    std::vector<point> path;
-    bool active = false;
+    struct pending_s
+    {
+        point from, to;
+        object_id own_id;
+        uint32_t max_dist;
+        Vector2ub own_size;
+    } pending = {};
+
+    struct result_s
+    {
+        point from;
+        std::vector<point> path;
+    } result;
+
+    bool has_result : 1 = false, has_pending : 1 = false;
 };
 
 using variant = std::variant<std::monostate, tests::path_test>;
diff --git a/editor/tests.cpp b/editor/tests.cpp
index 706c15eb..a7e86a3f 100644
--- a/editor/tests.cpp
+++ b/editor/tests.cpp
@@ -51,17 +51,17 @@ void app::tests_post_update()
     }, tests());
 }
 
-bool app::tests_handle_mouse_click(const mouse_button_event& e)
+bool app::tests_handle_mouse_click(const mouse_button_event& e, bool is_down)
 {
     update_cursor_tile(cursor.pixel);
 
     return std::visit(overloaded {
         [](std::monostate) { return false; },
-        [&](base_test& x) { return x.handle_mouse_click(*this, e); }
+        [&](base_test& x) { return x.handle_mouse_click(*this, e, is_down); }
     }, tests());
 }
 
-bool app::tests_handle_key(const key_event& e)
+bool app::tests_handle_key(const key_event& e, bool is_down)
 {
     switch (e.key)
     {
@@ -71,7 +71,7 @@ bool app::tests_handle_key(const key_event& e)
     default:
         return std::visit(overloaded {
             [](std::monostate) { return false; },
-            [&](base_test& x) { return x.handle_key(*this, e); }
+            [&](base_test& x) { return x.handle_key(*this, e, is_down); }
         }, tests());
     }
 }
diff --git a/editor/tests/path.cpp b/editor/tests/path.cpp
index 3b015e27..f6ebc1cb 100644
--- a/editor/tests/path.cpp
+++ b/editor/tests/path.cpp
@@ -3,49 +3,48 @@
 #include "floormat/main.hpp"
 #include "src/path-search.hpp"
 #include "src/critter.hpp"
+#include "shaders/shader.hpp"
+#include "../imgui-raii.hpp"
+#include "src/camera-offset.hpp"
 
 namespace floormat::tests {
 
-bool path_test::handle_key(app& a, const key_event& e)
+bool path_test::handle_key(app& a, const key_event& e, bool is_down)
 {
+    (void)a; (void)e; (void)is_down;
     return false;
 }
 
-bool path_test::handle_mouse_click(app& a, const mouse_button_event& e)
+bool path_test::handle_mouse_click(app& a, const mouse_button_event& e, bool is_down)
 {
+    if (is_down)
+        return false;
+
     switch (e.button)
     {
     case mouse_button_left: {
         auto& M = a.main();
         auto& w = M.world();
-        auto& astar = M.astar();
         auto C = a.ensure_player_character(w);
         if (auto pt = a.cursor_state().point())
         {
             constexpr auto chunk_size = iTILE_SIZE2 * TILE_MAX_DIM;
             auto pt0 = C->position();
-            auto vec = (pt->coord() - pt0.coord()) * iTILE_SIZE2 * 2 + chunk_size * 3;
+            auto vec = (pt->coord() - pt0.coord()) * iTILE_SIZE2 + chunk_size * 1;
             auto dist = (uint32_t)vec.length();
-            auto res = astar.Dijkstra(w, *pt, pt0, C->id, dist, C->bbox_size, 1);
-            if (res)
-            {
-                active = true;
-                from = pt0;
-                path = res.path();
-            }
-            else
-            {
-                active = false;
-                from = {};
-                path = {};
-            }
+
+            has_pending = true;
+            pending = { .from = pt0, .to = *pt, .own_id = C->id,
+                        .max_dist = dist, .own_size = C->bbox_size, };
         }
         return true;
     }
     case mouse_button_right:
-        if (active)
+        if (has_pending | has_result)
         {
-            *this = {};
+            has_pending = has_result = false;
+            pending = {};
+            result = {};
             return true;
         }
         return false;
@@ -56,22 +55,66 @@ bool path_test::handle_mouse_click(app& a, const mouse_button_event& e)
 
 bool path_test::handle_mouse_move(app& a, const mouse_move_event& e)
 {
+    (void)a; (void)e;
     return false;
 }
 
 void path_test::draw_overlay(app& a)
 {
+    if (!has_result)
+        return;
+
+    const auto win_size = a.main().window_size();
+    const auto line_color = ImGui::ColorConvertFloat4ToU32({0, 0, 1, 1});
+    const auto dot_color = ImGui::ColorConvertFloat4ToU32({1, 0, 0, 1});
+    constexpr float line_thickness = 3, dot_radius = 5;
+    auto& shader = a.main().shader();
+    ImDrawList& draw = *ImGui::GetForegroundDrawList();
 
+    constexpr auto get_screen_pos = [](tile_shader& shader, point pt, Vector2i win_size) {
+        auto c3 = pt.chunk3();
+        auto c2 = pt.chunk();
+        with_shifted_camera_offset co{shader, c3, c2, c2 };
+        auto world_pos = TILE_SIZE20 * Vector3(pt.local()) + Vector3(Vector2(pt.offset()), 0);
+        return Vector2(shader.camera_offset()) + Vector2(win_size)*.5f + shader.project(world_pos);
+    };
+
+    auto last = get_screen_pos(shader, result.from, win_size);
+    draw.AddCircleFilled({last.x(), last.y()}, dot_radius, dot_color);
+
+    for (auto pt : result.path)
+    {
+        auto pos = get_screen_pos(shader, pt, win_size);
+        draw.AddLine({pos.x(), pos.y()}, {last.x(), last.y()}, line_color, line_thickness);
+        draw.AddCircleFilled({pos.x(), pos.y()}, dot_radius, dot_color);
+        last = pos;
+    }
 }
 
 void path_test::update_pre(app& a)
 {
+    if (!has_pending)
+        return;
+
+    has_result = false;
+    has_pending = false;
+
+    auto& M = a.main();
+    auto& w = M.world();
+    auto& astar = M.astar();
 
+    auto res = astar.Dijkstra(w, pending.from, pending.to, pending.own_id, pending.max_dist, pending.own_size, 1);
+    if (res)
+    {
+        has_result = true;
+        result.from = pending.from;
+        result.path = res.path();
+    }
 }
 
 void path_test::update_post(app& a)
 {
-
+    (void)a;
 }
 
 } // namespace floormat::tests
diff --git a/src/path-search-dijkstra.cpp b/src/path-search-dijkstra.cpp
index 5012cb54..995229af 100644
--- a/src/path-search-dijkstra.cpp
+++ b/src/path-search-dijkstra.cpp
@@ -67,9 +67,17 @@ struct heap_comparator
 inline uint32_t distance(point a, point b)
 {
     Vector2i dist;
-    dist += Math::abs(a.coord() - b.coord())*iTILE_SIZE2;
-    dist += Vector2i(a.offset() - b.offset());
-    return (uint32_t)Math::sqrt(dist.dot());
+    dist += (a.coord() - b.coord())*iTILE_SIZE2;
+    dist += Vector2i(a.offset()) - Vector2i(b.offset());
+    return (uint32_t)Math::sqrt(Math::abs(dist).dot());
+}
+
+inline uint32_t distance_l2(point a, point b)
+{
+    Vector2i dist;
+    dist += (a.coord() - b.coord())*iTILE_SIZE2;
+    dist += Vector2i(a.offset()) - Vector2i(b.offset());
+    return (uint32_t)Math::abs(dist).sum();
 }
 
 } // namespace
@@ -117,7 +125,7 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
 
     constexpr auto min_size = Vector2ui{div_size*3/2};
     const auto own_size = Math::max(Vector2ui(own_size_), min_size);
-    constexpr auto goal_thres = (div_size*3/2).length();
+    constexpr auto goal_thres = (uint32_t)(div_size.length() + 1.5f);
 
     const auto [from, from_offset] = from_;
     const auto [to, to_offset] = to_;
@@ -167,8 +175,6 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
     uint32_t closest_path_len = 0;
     auto goal_idx = (uint32_t)-1;
     const auto goal_bb = bbox_from_pos(Vector2(to_.local()), to_offset, own_size);
-    const auto goal_chunk_idx = cache.get_chunk_index(Vector2i(to_.chunk()));
-    const auto goal_tile_idx = cache.get_tile_index(Vector2i(to_.local()), to_offset);
 
     while (!Q.empty())
     {
@@ -197,42 +203,18 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
                         << " pos:" << closest_pos;
 #endif
 
-        if (auto dist_to_goal = distance(cur_pt, to_); dist_to_goal < goal_thres) [[unlikely]]
+        if (auto dist_to_goal = distance_l2(cur_pt, to_); dist_to_goal < goal_thres) [[unlikely]]
         {
-            if (auto dist = cur_dist + dist_to_goal; dist < max_dist)
+            //if (auto dist = cur_dist + dist_to_goal; dist < max_dist)
             {
+                auto dist = cur_dist;
                 auto vec = Vector2(cur_pt.coord() - to_.coord()) * TILE_SIZE2 + Vector2(cur_pt.offset() - to_.offset());
                 auto bb1 = bbox<float>{goal_bb.min + vec, goal_bb.max + vec};
                 auto bb = bbox_union(goal_bb, bb1);
 
-                if (goal_idx != (uint32_t)-1)
-                    if (dist >= nodes[goal_idx].dist)
-                        continue;
-
                 if (path_search::is_passable(w, to_.chunk3(), bb, own_id, p))
                 {
-                    if (goal_idx == (uint32_t)-1)
-                    {
-                        goal_idx = cache.lookup_index(goal_chunk_idx, goal_tile_idx);
-                    }
-                    if (goal_idx == (uint32_t)-1)
-                    {
-                        goal_idx = (uint32_t)nodes.size();
-                        cache.add_index(goal_chunk_idx, goal_tile_idx, goal_idx);
-                        auto new_node = visited {
-                            .dist = dist, .prev = id,
-                            .pt = to_,
-                        };
-                        nodes.push_back(new_node);
-                        auto idx = cache.lookup_index(goal_chunk_idx, goal_tile_idx);
-                        fm_assert(idx == goal_idx);
-                    }
-                    else
-                    {
-                        auto& n = nodes[goal_idx];
-                        n.dist = dist;
-                        n.prev = id;
-                    }
+                    goal_idx = id;
                     max_dist = dist;
                     continue; // path can only get longer
                 }
@@ -247,9 +229,6 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
 
             const auto new_pt = object::normalize_coords(cur_pt, vec);
             const auto [new_coord, new_offset] = new_pt;
-
-            bool fresh = true;
-
             auto chunk_idx = cache.get_chunk_index(Vector2i(new_pt.chunk()));
             auto tile_idx = cache.get_tile_index(Vector2i(new_pt.local()), new_offset);
             auto new_idx = cache.lookup_index(chunk_idx, tile_idx);
@@ -258,7 +237,6 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
             {
                 if (nodes[new_idx].dist <= dist)
                     continue;
-                fresh = false;
             }
 
             {   const auto bb0 = bbox_from_pos(Vector2(cur_pt.local()), cur_pt.offset(), own_size);
@@ -269,7 +247,7 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
                     continue;
             }
 
-            if (fresh)
+            if (new_idx == (uint32_t)-1)
             {
                 const auto sz = nodes.size();
                 new_idx = (uint32_t)sz;
@@ -289,8 +267,7 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
 
 #ifndef FM_NO_DEBUG
             if (debug >= 3) [[unlikely]]
-                DBG_nospace << (fresh ? "" : " old")
-                            << " path:" << dist
+                DBG_nospace << " path:" << dist
                             << " pos:" << Vector3i(new_coord)
                             << ";" << new_offset;
 #endif
@@ -322,15 +299,19 @@ path_search_result astar::Dijkstra(world& w, const point from_, const point to_,
 
     if (auto i = goal_idx; i != (uint32_t)-1)
     {
-        do {
+        if (to_ != nodes[goal_idx].pt)
+            path.push_back(to_);
+
+        do
+        {
             const auto& node = nodes[i];
             path.push_back(node.pt);
             i = node.prev;
+        }
+        while (i !=(uint32_t)-1);
 
-        } while(i !=(uint32_t)-1);
-
-        result.set_cost(nodes[goal_idx].dist);
         std::reverse(path.begin(), path.end());
+        result.set_cost(nodes[goal_idx].dist);
     }
 
     return result;
diff --git a/src/point.cpp b/src/point.cpp
index 772286cc..a6e27f66 100644
--- a/src/point.cpp
+++ b/src/point.cpp
@@ -18,6 +18,7 @@ size_t point::hash() const
 
 Debug& operator<<(Debug& dbg, const point& pt)
 {
+    dbg << "";
     const auto flags = dbg.flags();
     dbg.setFlags(flags | Debug::Flag::NoSpace);