pathfinding work

3 files changed, 69 insertions, 0 deletions

diff --git a/test/app.hpp b/test/app.hpp
index e75c6d32..b3ea87fe 100644
--- a/test/app.hpp
+++ b/test/app.hpp
@@ -32,6 +32,7 @@ struct test_app final : private FM_APPLICATION
     static void test_loader();
     static void test_bitmask();
     static void test_path_search();
+    static void test_dijkstra();
     static void test_hash();
     static void test_path_search_node_pool();
     static void test_wall_atlas();
diff --git a/test/dijkstra.cpp b/test/dijkstra.cpp
index e69de29b..28f59d4f 100644
--- a/test/dijkstra.cpp
+++ b/test/dijkstra.cpp
@@ -0,0 +1,66 @@
+#include "app.hpp"
+#include "src/path-search.hpp"
+#include "loader/loader.hpp"
+#include <Magnum/Math/Functions.h>
+
+namespace floormat {
+
+void test_app::test_dijkstra()
+{
+    constexpr bool debug = true;
+
+    auto A = astar{};
+    auto w = world();
+
+    constexpr auto wcx = 1, wcy = 1, wtx = 8, wty = 8, wox = 0, woy = 0;
+    constexpr auto max_dist = (uint32_t)(Vector2i(Math::abs(wcx)+1, Math::abs(wcy)+1)*TILE_MAX_DIM*iTILE_SIZE2).length();
+    constexpr auto wch = chunk_coords_{wcx, wcy, 0};
+    constexpr auto wt = local_coords{wtx, wty};
+    constexpr auto wpos = global_coords{wch, wt};
+
+    auto& ch = w[wch];
+    auto metal2 = tile_image_proto{loader.tile_atlas("metal2", {2, 2}, pass_mode::blocked), 0};
+
+    for (int16_t j = wcy - 1; j <= wcy + 1; j++)
+        for (int16_t i = wcx - 1; i <= wcx + 1; i++)
+        {
+            auto &c = w[chunk_coords_{i, j, 0}];
+            for (int k : {  3, 4, 5, 6, 11, 12, 13, 14, 15, })
+            {
+                c[{ k, k }].wall_north() = metal2;
+                c[{ k, k }].wall_west() = metal2;
+            }
+        }
+
+    ch[{ wtx,   wty   }].wall_west()  = metal2;
+    ch[{ wtx,   wty   }].wall_north() = metal2;
+    ch[{ wtx+1, wty   }].wall_west()  = metal2;
+    ch[{ wtx,   wty +1}].wall_north() = metal2;
+
+    for (int16_t j = wcy - 1; j <= wcy + 1; j++)
+        for (int16_t i = wcx - 1; i <= wcx + 1; i++)
+        {
+            auto& c = w[chunk_coords_{i, j, 0}];
+            c.mark_passability_modified();
+            c.ensure_passability();
+        }
+
+    auto result = A.Dijkstra(w,
+                             {{0,0,0}, {11,9}},    // from
+                             {wpos, {wox, woy}},   // to
+                             0, max_dist, {16,16}, // size
+                             debug ? 1 : 0);
+
+    constexpr auto min = (uint32_t)(TILE_SIZE2*.5f).length() - uint32_t{1},
+                   max = (uint32_t)(TILE_SIZE2*2.f).length() + uint32_t{1};
+
+    fm_assert(!result.is_found());
+    fm_assert(!result.path().empty());
+    fm_assert(result.size() > 4);
+    fm_assert(result.cost() > 1000);
+    fm_assert(result.cost() < 3000);
+    fm_assert(result.distance() > min);
+    fm_assert(result.distance() < max);
+}
+
+} // namespace floormat
diff --git a/test/main.cpp b/test/main.cpp
index 165ac932..569d5130 100644
--- a/test/main.cpp
+++ b/test/main.cpp
@@ -36,6 +36,8 @@ int test_app::exec()
 
     test_path_search_node_pool();
     test_path_search();
+    test_dijkstra();
+
     zzz_test_misc();
 
     return 0;