From cc84805daaef03a1b0d03a6a2dad2fb527f8103c Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sat, 30 Sep 2023 13:44:44 +0200 Subject: reformat --- src/path-search.cpp | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index 2a5d60f4..c86cd076 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -131,30 +131,30 @@ auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, ro { case (uint8_t)rotation::N: { const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N ); - auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); + auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N ); + auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); return {min_N, max_N}; } case (uint8_t)rotation::S: { const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_S = Vector2i(-half_tile.x() + space_NS, 0 ); - auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); + auto min_S = Vector2i(-half_tile.x() + space_NS, 0 ); + auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); return {min_S, max_S}; } case (uint8_t)rotation::W: { const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE ); - auto max_W = Vector2i(0, min_W.y() + sz.y() ); + auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE ); + auto max_W = Vector2i(0, min_W.y() + sz.y() ); return {min_W, max_W}; } case (uint8_t)rotation::E: { const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_E = Vector2i(0, -half_tile.y() + space_WE ); - auto max_E = Vector2i(offset_W, min_E.y() + sz.y() ); + auto min_E = Vector2i(0, -half_tile.y() + space_WE ); + auto max_E = Vector2i(offset_W, min_E.y() + sz.y() ); return {min_E, max_E}; } case (uint8_t)rotation_COUNT: { - auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); + auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); auto max_C = min_C + sz; return {min_C, max_C}; } @@ -163,14 +163,14 @@ auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, ro } }; - constexpr auto min_size = iTILE_SIZE2*3/4; + constexpr auto min_size = iTILE_SIZE2*1/4; static_assert(min_size.x() % 2 == 0); -#if 0 +#if 1 if constexpr(true) { constexpr auto sz_ = min_size; - constexpr Vector2i shift = Vector2i(1, 2) * iTILE_SIZE2; + constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0); { constexpr auto N = get_value(sz_, rotation::N); -- cgit v1.2.3 From 245e8bd04bde678a19961cf04ad80eaf3375cfae Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Wed, 4 Oct 2023 19:05:43 +0200 Subject: doc: add astar subdivide visualizalization aid --- doc/astar-subdivide.png | Bin 0 -> 40978 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 doc/astar-subdivide.png diff --git a/doc/astar-subdivide.png b/doc/astar-subdivide.png new file mode 100644 index 00000000..0b588e3f Binary files /dev/null and b/doc/astar-subdivide.png differ -- cgit v1.2.3 From 5291d3d5d102bf639467ce9c2f7865c80db86679 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Wed, 4 Oct 2023 19:05:54 +0200 Subject: doc: add occlusion map visualization aid --- doc/occlusion-map.png | Bin 0 -> 21574 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 doc/occlusion-map.png diff --git a/doc/occlusion-map.png b/doc/occlusion-map.png new file mode 100644 index 00000000..7ce5759b Binary files /dev/null and b/doc/occlusion-map.png differ -- cgit v1.2.3 From abb9739f418a8d4a48abf120de35ab0c179b5aa8 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Wed, 4 Oct 2023 19:06:09 +0200 Subject: buffer flush --- src/path-search.cpp | 151 +++++++++++++++++++++++++++++++--------------------- src/path-search.hpp | 15 +++--- 2 files changed, 98 insertions(+), 68 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index c86cd076..20c7f157 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -13,10 +13,80 @@ namespace floormat { namespace { + +constexpr auto div = path_search::subdivide_factor; +constexpr int div_BITS = 2; +static_assert(1 << div_BITS == div); + +using bbox = path_search::bbox; + constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; }; constexpr auto never_continue_ = path_search::pred{never_continue_1}; constexpr auto always_continue_1 = [](collision_data) constexpr { return path_search_continue::pass; }; constexpr auto always_continue_ = path_search::pred{always_continue_1}; + +constexpr Pair get_value(Vector2i sz, Vector2ub div, rotation r) +{ + fm_debug_assert(div == Vector2ub{div}); + + constexpr auto half_tile = iTILE_SIZE2/2; + constexpr int offset_W = iTILE_SIZE2.x(), offset_N = iTILE_SIZE2.y(); + + const auto r_ = (uint8_t)r; + CORRADE_ASSUME(r_ <= (uint8_t)rotation_COUNT); + + switch (r_) + { + case (uint8_t)rotation::N: { + const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; + auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N ); + auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); + return {min_N, max_N}; + } + case (uint8_t)rotation::S: { + const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; + auto min_S = Vector2i(-half_tile.x() + space_NS, 0 ); + auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); + return {min_S, max_S}; + } + case (uint8_t)rotation::W: { + const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; + auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE ); + auto max_W = Vector2i(0, min_W.y() + sz.y() ); + return {min_W, max_W}; + } + case (uint8_t)rotation::E: { + const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; + auto min_E = Vector2i(0, -half_tile.y() + space_WE ); + auto max_E = Vector2i(offset_W, min_E.y() + sz.y() ); + return {min_E, max_E}; + } + case (uint8_t)rotation_COUNT: { + auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); + auto max_C = min_C + sz; + return {min_C, max_C}; + } + default: + fm_abort("wrong 4-way rotation enum '%d'", (int)r); + } +}; + +constexpr Vector2i tile_subdiv_at(Vector2i subdiv) +{ + constexpr auto tile_start_offset = iTILE_SIZE2/-2; + constexpr auto shift = iTILE_SIZE2/div; + static_assert(shift * div == iTILE_SIZE2); + fm_debug_assert(Vector2ui(subdiv) < Vector2ui{(unsigned)div}); + return tile_start_offset + shift * subdiv; +}; + +struct chunk_subdiv_array { Vector2i min[div], max[div]; }; + +constexpr chunk_subdiv_array make_chunk_subdiv_array() +{ + return {}; +} + } // namespace path_search_result::path_search_result() = default; @@ -117,91 +187,48 @@ 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, rotation r) -> bbox +auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r) -> bbox { - constexpr auto get_value = [](Vector2i sz, rotation r) constexpr -> Pair - { - constexpr auto half_tile = iTILE_SIZE2/2; - constexpr int offset_W = iTILE_SIZE2.x(), offset_N = iTILE_SIZE2.y(); - - const auto r_ = (uint8_t)r; - CORRADE_ASSUME(r_ <= (uint8_t)rotation_COUNT); - - switch (r_) - { - case (uint8_t)rotation::N: { - const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N ); - auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); - return {min_N, max_N}; - } - case (uint8_t)rotation::S: { - const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_S = Vector2i(-half_tile.x() + space_NS, 0 ); - auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); - return {min_S, max_S}; - } - case (uint8_t)rotation::W: { - const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE ); - auto max_W = Vector2i(0, min_W.y() + sz.y() ); - return {min_W, max_W}; - } - case (uint8_t)rotation::E: { - const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_E = Vector2i(0, -half_tile.y() + space_WE ); - auto max_E = Vector2i(offset_W, min_E.y() + sz.y() ); - return {min_E, max_E}; - } - case (uint8_t)rotation_COUNT: { - auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); - auto max_C = min_C + sz; - return {min_C, max_C}; - } - default: - fm_abort("wrong 4-way rotation enum '%d'", (int)r); - } - }; - constexpr auto min_size = iTILE_SIZE2*1/4; static_assert(min_size.x() % 2 == 0); + static_assert(min_size.x() >= subdivide_factor && min_size.y() >= subdivide_factor); #if 1 - if constexpr(true) + if constexpr(std::is_constant_evaluated()) { constexpr auto sz_ = min_size; constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0); { - constexpr auto N = get_value(sz_, rotation::N); + constexpr auto N = get_value(sz_, {1,1}, rotation::N); constexpr auto min_N = N.first() + shift, max_N = N.second() + shift; - { [[maybe_unused]] constexpr auto N_x = min_N.x(), N_y = min_N.y(); } - { [[maybe_unused]] constexpr auto N_x = max_N.x(), N_y = max_N.y(); } + { [[maybe_unused]] constexpr auto N_x = min_N.x(), N_y = min_N.y(); } + { [[maybe_unused]] constexpr auto N_x = max_N.x(), N_y = max_N.y(); } } { - constexpr auto E = get_value(sz_, rotation::E); + constexpr auto E = get_value(sz_, {1,1}, rotation::E); constexpr auto min_E = E.first() + shift, max_E = E.second() + shift; - { [[maybe_unused]] constexpr auto E_x = min_E.x(), E_y = min_E.y(); } - { [[maybe_unused]] constexpr auto E_x = max_E.x(), E_y = max_E.y(); } + { [[maybe_unused]] constexpr auto E_x = min_E.x(), E_y = min_E.y(); } + { [[maybe_unused]] constexpr auto E_x = max_E.x(), E_y = max_E.y(); } } { - constexpr auto S = get_value(sz_, rotation::S); + constexpr auto S = get_value(sz_, {1,1}, rotation::S); constexpr auto min_S = S.first() + shift, max_S = S.second() + shift; - { [[maybe_unused]] constexpr auto S_x = min_S.x(), S_y = min_S.y(); } - { [[maybe_unused]] constexpr auto S_x = max_S.x(), S_y = max_S.y(); } + { [[maybe_unused]] constexpr auto S_x = min_S.x(), S_y = min_S.y(); } + { [[maybe_unused]] constexpr auto S_x = max_S.x(), S_y = max_S.y(); } } { - constexpr auto W = get_value(sz_, rotation::W); + constexpr auto W = get_value(sz_, {1,1}, rotation::W); constexpr auto min_W = W.first() + shift, max_W = W.second() + shift; - { [[maybe_unused]] constexpr auto W_x = min_W.x(), W_y = min_W.y(); } - { [[maybe_unused]] constexpr auto W_x = max_W.x(), W_y = max_W.y(); } + { [[maybe_unused]] constexpr auto W_x = min_W.x(), W_y = min_W.y(); } + { [[maybe_unused]] constexpr auto W_x = max_W.x(), W_y = max_W.y(); } } } #endif const auto shift = coord * iTILE_SIZE2; auto sz = Math::max(Vector2i(own_size), min_size); - auto [min, max] = get_value(sz, r); + auto [min, max] = get_value(sz, div, r); return { Vector2(min + shift), Vector2(max + shift) }; } @@ -231,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, dir); + auto [min, max] = make_neighbor_tile_bbox(pos, size, {1,1}, dir); if (is_passable(w, ch, min, max, own_id, p)) ns.neighbors[ns.size++] = coord + off; } @@ -268,8 +295,8 @@ void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size, for (auto i = 0uz; i < TILE_COUNT; i++) { auto pos = Vector2i(local_coords{i}); - auto bb_N = make_neighbor_tile_bbox(pos, own_size, rotation::N), - bb_W = make_neighbor_tile_bbox(pos, own_size, rotation::W); + auto bb_N = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::N), + bb_W = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::W); bool b_N = is_passable_(c, nb, bb_N.min, bb_N.max, own_id, p), b_W = is_passable_(c, nb, bb_W.min, bb_W.max, own_id, p); bits.can_go_north[i] = b_N; diff --git a/src/path-search.hpp b/src/path-search.hpp index bb72d87e..92d113cf 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -52,6 +52,13 @@ enum class path_search_continue : bool { pass = false, blocked = true }; class path_search final { + // todo bucketize by array length + path_search_result* pool = nullptr; + +public: + static constexpr int subdivide_factor = 4; + static constexpr size_t tile_count = Vector2i(subdivide_factor * TILE_MAX_DIM).product(); + struct neighbors final { auto begin() const { return neighbors.data(); } @@ -63,7 +70,7 @@ class path_search final struct chunk_tiles_cache { - std::bitset can_go_north{true}, can_go_west{true}; + std::bitset can_go_north{true}, can_go_west{true}; }; struct chunk_cache @@ -74,10 +81,6 @@ class path_search final struct obj_position { Vector2 center, size; }; - // todo bucketize by array length - path_search_result* pool = nullptr; - -public: chunk_cache cache; Array output; @@ -102,7 +105,7 @@ 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 make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, rotation r); + static bbox make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r); static bbox bbox_union(bbox 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()); }; -- cgit v1.2.3 From 113a87ae7008dde7277ac6bf9d4abf68b71039cc Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Wed, 4 Oct 2023 23:11:51 +0200 Subject: test: add hash test --- test/path-search.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/test/path-search.cpp b/test/path-search.cpp index ce2430f7..e54474cf 100644 --- a/test/path-search.cpp +++ b/test/path-search.cpp @@ -21,7 +21,7 @@ void test_bbox() }; static constexpr auto bbox = [](Vector2i coord, rotation r) { - return path_search::make_neighbor_tile_bbox(coord, {}, r); + return path_search::make_neighbor_tile_bbox(coord, {}, {1,1}, r); }; constexpr auto neighbor_tiles = [](world& w, chunk_coords_ ch, Vector2i pos) { -- cgit v1.2.3 From 0b81ff9ce2ad1d59ca424b76eefa3f8ce19f04b9 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 00:52:34 +0200 Subject: wip --- src/path-search.cpp | 72 ++++++++++++++++++++++++++--------------------------- 1 file changed, 35 insertions(+), 37 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index 20c7f157..2b9be03d 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -27,10 +27,8 @@ constexpr auto always_continue_ = path_search::pred{always_continue_1}; constexpr Pair get_value(Vector2i sz, Vector2ub div, rotation r) { - fm_debug_assert(div == Vector2ub{div}); - - constexpr auto half_tile = iTILE_SIZE2/2; - constexpr int offset_W = iTILE_SIZE2.x(), offset_N = iTILE_SIZE2.y(); + const auto half_tile = iTILE_SIZE2/2/(int)div.x(); + const int offset_W = iTILE_SIZE2.x()/(int)div.x(), offset_N = iTILE_SIZE2.y()/(int)div.y(); const auto r_ = (uint8_t)r; CORRADE_ASSUME(r_ <= (uint8_t)rotation_COUNT); @@ -71,6 +69,39 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio } }; +[[maybe_unused]] constexpr bool test_offsets() +{ + constexpr auto min_size = iTILE_SIZE2*1/4; + static_assert(min_size.x() % 2 == 0); + static_assert(min_size.x() >= div && min_size.y() >= div); + constexpr auto sz_ = min_size; + constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0); + + [[maybe_unused]] constexpr auto N = get_value(sz_, {1,1}, rotation::N); + [[maybe_unused]] constexpr auto min_N = N.first() + shift, max_N = N.second() + shift; + [[maybe_unused]] constexpr auto N_min_x = min_N.x(), N_min_y = min_N.y(); + [[maybe_unused]] constexpr auto N_max_x = max_N.x(), N_max_y = max_N.y(); + + [[maybe_unused]] constexpr auto E = get_value(sz_, {1,1}, rotation::E); + [[maybe_unused]] constexpr auto min_E = E.first() + shift, max_E = E.second() + shift; + [[maybe_unused]] constexpr auto E_min_x = min_E.x(), E_min_y = min_E.y(); + [[maybe_unused]] constexpr auto E_max_x = max_E.x(), E_max_y = max_E.y(); + + [[maybe_unused]] constexpr auto S = get_value(sz_, {1,1}, rotation::S); + [[maybe_unused]] constexpr auto min_S = S.first() + shift, max_S = S.second() + shift; + [[maybe_unused]] constexpr auto S_min_x = min_S.x(), S_min_y = min_S.y(); + [[maybe_unused]] constexpr auto S_max_x = max_S.x(), S_max_y = max_S.y(); + + [[maybe_unused]] constexpr auto W = get_value(sz_, {1,1}, rotation::W); + [[maybe_unused]] constexpr auto min_W = W.first() + shift, max_W = W.second() + shift; + [[maybe_unused]] constexpr auto W_min_x = min_W.x(), W_min_y = min_W.y(); + [[maybe_unused]] constexpr auto W_max_x = max_W.x(), W_max_y = max_W.y(); + + return true; +} + +static_assert(test_offsets()); + constexpr Vector2i tile_subdiv_at(Vector2i subdiv) { constexpr auto tile_start_offset = iTILE_SIZE2/-2; @@ -193,39 +224,6 @@ auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Ve static_assert(min_size.x() % 2 == 0); static_assert(min_size.x() >= subdivide_factor && min_size.y() >= subdivide_factor); -#if 1 - if constexpr(std::is_constant_evaluated()) - { - constexpr auto sz_ = min_size; - constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0); - - { - constexpr auto N = get_value(sz_, {1,1}, rotation::N); - constexpr auto min_N = N.first() + shift, max_N = N.second() + shift; - { [[maybe_unused]] constexpr auto N_x = min_N.x(), N_y = min_N.y(); } - { [[maybe_unused]] constexpr auto N_x = max_N.x(), N_y = max_N.y(); } - } - { - constexpr auto E = get_value(sz_, {1,1}, rotation::E); - constexpr auto min_E = E.first() + shift, max_E = E.second() + shift; - { [[maybe_unused]] constexpr auto E_x = min_E.x(), E_y = min_E.y(); } - { [[maybe_unused]] constexpr auto E_x = max_E.x(), E_y = max_E.y(); } - } - { - constexpr auto S = get_value(sz_, {1,1}, rotation::S); - constexpr auto min_S = S.first() + shift, max_S = S.second() + shift; - { [[maybe_unused]] constexpr auto S_x = min_S.x(), S_y = min_S.y(); } - { [[maybe_unused]] constexpr auto S_x = max_S.x(), S_y = max_S.y(); } - } - { - constexpr auto W = get_value(sz_, {1,1}, rotation::W); - constexpr auto min_W = W.first() + shift, max_W = W.second() + shift; - { [[maybe_unused]] constexpr auto W_x = min_W.x(), W_y = min_W.y(); } - { [[maybe_unused]] constexpr auto W_x = max_W.x(), W_y = max_W.y(); } - } - } -#endif - const auto shift = coord * iTILE_SIZE2; auto sz = Math::max(Vector2i(own_size), min_size); auto [min, max] = get_value(sz, div, r); -- cgit v1.2.3 From a9005d0e8b75feaaf87dc57416d26c771de373ef Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 02:28:19 +0200 Subject: wip --- src/path-search.cpp | 53 ++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 38 insertions(+), 15 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index 2b9be03d..915a41ad 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -27,7 +27,6 @@ constexpr auto always_continue_ = path_search::pred{always_continue_1}; constexpr Pair get_value(Vector2i sz, Vector2ub div, rotation r) { - const auto half_tile = iTILE_SIZE2/2/(int)div.x(); const int offset_W = iTILE_SIZE2.x()/(int)div.x(), offset_N = iTILE_SIZE2.y()/(int)div.y(); const auto r_ = (uint8_t)r; @@ -36,31 +35,27 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio switch (r_) { case (uint8_t)rotation::N: { - const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N ); - auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); + auto min_N = Vector2i(-sz.x()/2, -offset_N - sz.y()/2 ); + auto max_N = Vector2i(min_N.x() + sz.x(), sz.y() - sz.y()/2 ); return {min_N, max_N}; } case (uint8_t)rotation::S: { - const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1; - auto min_S = Vector2i(-half_tile.x() + space_NS, 0 ); - auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); + auto min_S = Vector2i(-sz.x()/2, -sz.y() ); + auto max_S = Vector2i(min_S.x() + sz.x(), offset_N + sz.y() - sz.y()/2 ); return {min_S, max_S}; } case (uint8_t)rotation::W: { - const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE ); - auto max_W = Vector2i(0, min_W.y() + sz.y() ); + auto min_W = Vector2i(-offset_W - sz.x()/2, -sz.y()/2 ); + auto max_W = Vector2i(sz.x() - sz.x()/2, min_W.y() + sz.y() ); return {min_W, max_W}; } case (uint8_t)rotation::E: { - const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1; - auto min_E = Vector2i(0, -half_tile.y() + space_WE ); - auto max_E = Vector2i(offset_W, min_E.y() + sz.y() ); + auto min_E = Vector2i(sz.x()/2, -sz.y()/2 ); + auto max_E = Vector2i(offset_W + sz.x() - sz.x()/2, min_E.y() + sz.y() - sz.y()/2 ); return {min_E, max_E}; } case (uint8_t)rotation_COUNT: { - auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); + auto min_C = Vector2i(-(sz.x() >> 1), -(sz.y() >> 1) ); auto max_C = min_C + sz; return {min_C, max_C}; } @@ -71,7 +66,7 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio [[maybe_unused]] constexpr bool test_offsets() { - constexpr auto min_size = iTILE_SIZE2*1/4; + constexpr auto min_size = iTILE_SIZE2/2; static_assert(min_size.x() % 2 == 0); static_assert(min_size.x() >= div && min_size.y() >= div); constexpr auto sz_ = min_size; @@ -102,6 +97,34 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio static_assert(test_offsets()); +[[maybe_unused]] constexpr bool test_offsets2() +{ + using enum rotation; + constexpr auto tile_start = iTILE_SIZE2/-2; + constexpr auto sz = Vector2i(8, 16); + + { + constexpr auto bb = get_value(sz, Vector2ub(div), N); + constexpr auto min = tile_start + bb.first(), max = tile_start + bb.second(); + static_assert(min.x() == -32 - sz.x()/2); + static_assert(max.x() == -32 + sz.x()/2); + static_assert(min.y() == -48 - sz.y()/2); + static_assert(max.y() == -32 + sz.y()/2); + } + { + constexpr auto bb = get_value(sz, Vector2ub(div), W); + constexpr auto min = tile_start + bb.first(), max = tile_start + bb.second(); + static_assert(min.x() == -32 - 16 - sz.x()/2); + static_assert(max.x() == -32 + sz.x()/2); + static_assert(min.y() == -32 - sz.y()/2); + static_assert(max.y() == -32 + sz.y()/2); + } + + return true; +} + +static_assert(test_offsets2()); + constexpr Vector2i tile_subdiv_at(Vector2i subdiv) { constexpr auto tile_start_offset = iTILE_SIZE2/-2; -- cgit v1.2.3 From 292f7db6ab16cefb23a72566ad8e07f4e697915c Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 14:09:24 +0200 Subject: wip astar neighbor bitmask seems to work now --- src/path-search.cpp | 78 +++++++++++++++++++++++++++++--------------------- src/path-search.hpp | 9 ++++-- test/path-search.cpp | 81 +++++++++++++++++++++++++++++++++------------------- 3 files changed, 104 insertions(+), 64 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index 915a41ad..dfcf0c3c 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -18,7 +18,7 @@ constexpr auto div = path_search::subdivide_factor; constexpr int div_BITS = 2; static_assert(1 << div_BITS == div); -using bbox = path_search::bbox; +static_assert(path_search::min_size.x() % 2 == 0 && path_search::min_size.x() * div * 2 == iTILE_SIZE2.x()); constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; }; constexpr auto never_continue_ = path_search::pred{never_continue_1}; @@ -50,8 +50,8 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio return {min_W, max_W}; } case (uint8_t)rotation::E: { - auto min_E = Vector2i(sz.x()/2, -sz.y()/2 ); - auto max_E = Vector2i(offset_W + sz.x() - sz.x()/2, min_E.y() + sz.y() - sz.y()/2 ); + auto min_E = Vector2i(-sz.x()/2, -sz.y()/2 ); + auto max_E = Vector2i(offset_W + sz.x() - sz.x()/2, min_E.y() + sz.y() ); return {min_E, max_E}; } case (uint8_t)rotation_COUNT: { @@ -66,10 +66,7 @@ constexpr Pair get_value(Vector2i sz, Vector2ub div, rotatio [[maybe_unused]] constexpr bool test_offsets() { - constexpr auto min_size = iTILE_SIZE2/2; - static_assert(min_size.x() % 2 == 0); - static_assert(min_size.x() >= div && min_size.y() >= div); - constexpr auto sz_ = min_size; + constexpr auto sz_ = path_search::min_size; constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0); [[maybe_unused]] constexpr auto N = get_value(sz_, {1,1}, rotation::N); @@ -125,15 +122,6 @@ static_assert(test_offsets()); static_assert(test_offsets2()); -constexpr Vector2i tile_subdiv_at(Vector2i subdiv) -{ - constexpr auto tile_start_offset = iTILE_SIZE2/-2; - constexpr auto shift = iTILE_SIZE2/div; - static_assert(shift * div == iTILE_SIZE2); - fm_debug_assert(Vector2ui(subdiv) < Vector2ui{(unsigned)div}); - return tile_start_offset + shift * subdiv; -}; - struct chunk_subdiv_array { Vector2i min[div], max[div]; }; constexpr chunk_subdiv_array make_chunk_subdiv_array() @@ -149,7 +137,7 @@ auto path_search::always_continue() noexcept -> const pred& { return always_cont void path_search::ensure_allocated(chunk_coords a, chunk_coords b) { - auto new_size = Math::abs(a - b) + Vector2i(3); + auto new_size = (Math::abs(a - b) + Vector2i(3)); auto new_start = Vector2i(std::min(a.x, b.x), std::min(a.y, b.y)) - Vector2i(1); auto size1 = new_size.product(); fm_debug_assert(size1 > 0); @@ -241,12 +229,8 @@ 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 +auto path_search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r) -> bbox { - constexpr auto min_size = iTILE_SIZE2*1/4; - static_assert(min_size.x() % 2 == 0); - static_assert(min_size.x() >= subdivide_factor && min_size.y() >= subdivide_factor); - const auto shift = coord * iTILE_SIZE2; auto sz = Math::max(Vector2i(own_size), min_size); auto [min, max] = get_value(sz, div, r); @@ -287,7 +271,7 @@ auto path_search::get_walkable_neighbor_tiles(world& w, global_coords coord, Vec return ns; } -auto path_search::bbox_union(bbox bb, Vector2i coord, Vector2b offset, Vector2ub size) -> bbox +auto path_search::bbox_union(bbox bb, Vector2i coord, Vector2b offset, Vector2ub size) -> bbox { auto center = coord * iTILE_SIZE2 + Vector2i(offset); auto min = center - Vector2i(size / 2u); @@ -298,13 +282,16 @@ auto path_search::bbox_union(bbox bb, Vector2i coord, Vector2b offset, Vector2ub }; } -void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size, object_id own_id, const pred& p) +void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size_, object_id own_id, const pred& p) { + auto own_size = Math::max(Vector2i(own_size_), path_search::min_size); + int32_t x = coord.x, y = coord.y; int8_t z = coord.z; auto off = Vector2i(x - cache.start.x(), y - cache.start.y()); fm_debug_assert(off >= Vector2i{} && off < cache.size); + static_assert(iTILE_SIZE2 / div * div == iTILE_SIZE2); auto ch = chunk_coords_{(int16_t)x, (int16_t)y, z}; auto* c = w.at(ch); auto nb = w.neighbors(ch); @@ -312,16 +299,43 @@ void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size, if (!c && std::all_of(nb.begin(), nb.end(), [](const auto& c) { return c.c == nullptr; })) return; + const auto [min_N_, max_N_] = get_value(Vector2i(own_size), Vector2ub(div), rotation::N); + const auto [min_W_, max_W_] = get_value(Vector2i(own_size), Vector2ub(div), rotation::W); + + const auto min_N = Vector2(min_N_), max_N = Vector2(max_N_), + min_W = Vector2(min_W_), max_W = Vector2(max_W_); + + enum : unsigned { N, E, S, W }; + + constexpr auto tile_start = TILE_SIZE2/-2; + constexpr auto part_size = Vector2(iTILE_SIZE2/Vector2i(div)); + auto& bits = cache.array[off.y()*cache.size.x()+off.x()]; - for (auto i = 0uz; i < TILE_COUNT; i++) + constexpr auto stride = TILE_MAX_DIM*(size_t)div; + + for (auto j = 0uz; j < TILE_MAX_DIM; j++) { - auto pos = Vector2i(local_coords{i}); - auto bb_N = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::N), - bb_W = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::W); - bool b_N = is_passable_(c, nb, bb_N.min, bb_N.max, own_id, p), - b_W = is_passable_(c, nb, bb_W.min, bb_W.max, own_id, p); - bits.can_go_north[i] = b_N; - bits.can_go_west[i] = b_W; + for (auto i = 0uz; i < TILE_MAX_DIM; i++) + { + const auto pos_ = tile_start + Vector2(i, j) * TILE_SIZE2; + + for (auto ky = 0uz; ky < div; ky++) + { + for (auto kx = 0uz; kx < div; kx++) + { + auto pos = pos_ + part_size*Vector2(kx, ky); + auto bb_N = bbox { pos + min_N, pos + max_N }; + auto bb_W = bbox { pos + min_W, pos + max_W }; + bool b_N = is_passable_(c, nb, bb_N.min, bb_N.max, own_id, p), + b_W = is_passable_(c, nb, bb_W.min, bb_W.max, own_id, p); + auto jj = j * div + ky, ii = i * div + kx; + auto index = jj * stride + ii; + fm_debug_assert(index < bits.can_go_north.size()); + bits.can_go_north[index] = b_N; + bits.can_go_west[index] = b_W; + } + } + } } } diff --git a/src/path-search.hpp b/src/path-search.hpp index 92d113cf..775cb618 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -12,6 +12,8 @@ #include #include #include +#include + namespace Corrade::Containers { template class Optional; @@ -57,6 +59,7 @@ class path_search final public: static constexpr int subdivide_factor = 4; + static constexpr auto min_size = iTILE_SIZE2 / subdivide_factor / 2; static constexpr size_t tile_count = Vector2i(subdivide_factor * TILE_MAX_DIM).product(); struct neighbors final @@ -84,7 +87,7 @@ public: chunk_cache cache; Array output; - struct bbox { Vector2 min, max; }; + template struct bbox { VectorTypeFor<2, T> min, max; }; using pred = fu2::function_view; static const pred& never_continue() noexcept; @@ -105,8 +108,8 @@ 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 make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r); - static bbox bbox_union(bbox bb, Vector2i coord, Vector2b offset, Vector2ub size); + static bbox make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r); + static bbox bbox_union(bbox 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()); }; diff --git a/test/path-search.cpp b/test/path-search.cpp index e54474cf..ecd631e4 100644 --- a/test/path-search.cpp +++ b/test/path-search.cpp @@ -10,13 +10,16 @@ namespace floormat { namespace { +constexpr auto div = path_search::subdivide_factor; +template using bbox = path_search::bbox; + void test_bbox() { - static constexpr auto is_passable_1 = [](chunk& c, path_search::bbox bb) { + static constexpr auto is_passable_1 = [](chunk& c, bbox bb) { return path_search::is_passable_1(c, bb.min, bb.max, (object_id)-1); }; - static constexpr auto is_passable = [](world& w, chunk_coords_ ch, path_search::bbox bb) { + static constexpr auto is_passable = [](world& w, chunk_coords_ ch, bbox bb) { return path_search::is_passable(w, ch, bb.min, bb.max, (object_id)-1); }; @@ -132,37 +135,57 @@ void test_bbox() fm_assert(ch_ >= Vector2i{} && ch_ < search.cache.size); return ch_.y()*search.cache.size.x() + ch_.x(); }; - static constexpr auto t_idx = [](local_coords tile) constexpr { - return (size_t)tile.y * TILE_MAX_DIM + (size_t)tile.x; + static constexpr auto t_idx = [](local_coords tile, Vector2i subdiv) constexpr { + constexpr auto stride = TILE_MAX_DIM * (size_t)div; + auto jj = tile.y * (size_t)div + (size_t)subdiv.y(); + auto ii = tile.x * (size_t)div + (size_t)subdiv.x(); + return jj * stride + ii; }; - constexpr auto check_N = [&](path_search& search, chunk_coords ch, local_coords tile) { - return search.cache.array[c_idx(search, ch)].can_go_north[t_idx(tile)]; + constexpr auto check_N = [&](path_search& search, chunk_coords ch, local_coords tile, Vector2i subdiv) { + auto c = c_idx(search, ch); + auto t = t_idx(tile, subdiv); + return search.cache.array[c].can_go_north[t]; }; - constexpr auto check_W = [&](path_search& search, chunk_coords ch, local_coords tile) { - return search.cache.array[c_idx(search, ch)].can_go_west[t_idx(tile)]; + constexpr auto check_W = [&](path_search& search, chunk_coords ch, local_coords tile, Vector2i subdiv) { + auto c = c_idx(search, ch); + auto t = t_idx(tile, subdiv); + return search.cache.array[c].can_go_west[t]; }; - fm_assert( !check_N(search, {}, { 0, 0} )); - fm_assert( !check_W(search, {}, { 0, 0} )); - fm_assert( check_N(search, {}, { 0, 1} )); - fm_assert( check_W(search, {}, { 1, 0} )); - - fm_assert( check_W(search, {}, {K-1, K } )); - fm_assert( check_N(search, {}, {K-1, K } )); - fm_assert( check_W(search, {}, {K, K-1} )); - fm_assert( check_N(search, {}, {K, K-1} )); - - fm_assert( !check_N(search, {}, {K, K } )); - fm_assert( !check_W(search, {}, {K, K } )); - fm_assert( !check_W(search, {}, {K+1, K } )); - fm_assert( check_N(search, {}, {K+1, K } )); - fm_assert( !check_N(search, {}, {K, K+1} )); - fm_assert( check_W(search, {}, {K, K+1} )); - - fm_assert( check_N(search, {}, {K+2, K } )); - fm_assert( check_W(search, {}, {K+2, K } )); - fm_assert( check_N(search, {}, {K, K+2} )); - fm_assert( check_W(search, {}, {K, K+2} )); + static_assert(div == 4); + constexpr Vector2i s00 = {0,0}, s01 = {0,2}, s10 = {2,0}, s11 = {2,2}, s22 = {3,3}; + + fm_assert( !check_N(search, {}, { 0, 0}, s10 )); + fm_assert( !check_W(search, {}, { 0, 0}, s01 )); + fm_assert( check_N(search, {}, { 0, 1}, s10 )); + fm_assert( check_W(search, {}, { 1, 0}, s01 )); + + fm_assert( !check_N(search, {}, { 0, 1}, s00 )); + fm_assert( !check_W(search, {}, { 1, 0}, s00 )); + + fm_assert( check_W(search, {}, {K-1, K }, s01 )); + fm_assert( check_N(search, {}, {K-1, K }, s10 )); + fm_assert( check_W(search, {}, {K, K-1}, s01 )); + fm_assert( check_N(search, {}, {K, K-1}, s10 )); + + fm_assert( check_W(search, {}, {K-1, K }, s22 )); + fm_assert( check_N(search, {}, {K-1, K }, s22 )); + fm_assert( check_W(search, {}, {K, K-1}, s22 )); + fm_assert( check_N(search, {}, {K, K-1}, s22 )); + + fm_assert( !check_N(search, {}, {K, K }, s10 )); + fm_assert( !check_W(search, {}, {K, K }, s01 )); + fm_assert( check_N(search, {}, {K, K }, s11 )); + fm_assert( check_W(search, {}, {K, K }, s11 )); + + fm_assert( !check_W(search, {}, {K+1, K }, s01 )); + fm_assert( check_N(search, {}, {K+1, K }, s10 )); + fm_assert( !check_N(search, {}, {K, K+1}, s10 )); + fm_assert( check_W(search, {}, {K, K+1}, s01 )); + fm_assert( check_N(search, {}, {K+2, K }, s10 )); + fm_assert( check_W(search, {}, {K+2, K }, s01 )); + fm_assert( check_N(search, {}, {K, K+2}, s10 )); + fm_assert( check_W(search, {}, {K, K+2}, s01 )); } } -- cgit v1.2.3 From f95753fff7238ff54e493797163c388330b02e32 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 14:44:20 +0200 Subject: doc: fix errors in A* subdivide graph --- doc/astar-subdivide.png | Bin 40978 -> 41156 bytes 1 file changed, 0 insertions(+), 0 deletions(-) diff --git a/doc/astar-subdivide.png b/doc/astar-subdivide.png index 0b588e3f..7fd3118f 100644 Binary files a/doc/astar-subdivide.png and b/doc/astar-subdivide.png differ -- cgit v1.2.3 From 64d881a31e84f1008f51756aafb0a1eb095e1520 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 14:44:48 +0200 Subject: kill assert in a loop --- src/path-search.cpp | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index dfcf0c3c..83804d70 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -305,8 +305,6 @@ void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size_ const auto min_N = Vector2(min_N_), max_N = Vector2(max_N_), min_W = Vector2(min_W_), max_W = Vector2(max_W_); - enum : unsigned { N, E, S, W }; - constexpr auto tile_start = TILE_SIZE2/-2; constexpr auto part_size = Vector2(iTILE_SIZE2/Vector2i(div)); @@ -330,7 +328,7 @@ void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size_ b_W = is_passable_(c, nb, bb_W.min, bb_W.max, own_id, p); auto jj = j * div + ky, ii = i * div + kx; auto index = jj * stride + ii; - fm_debug_assert(index < bits.can_go_north.size()); + //fm_debug_assert(index < bits.can_go_north.size()); bits.can_go_north[index] = b_N; bits.can_go_west[index] = b_W; } -- cgit v1.2.3 From 89284c258ef85d57410057ecc9c8c477e051b72c Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 5 Oct 2023 14:45:29 +0200 Subject: add gitignore for .pdn files --- doc/.gitignore | 1 + 1 file changed, 1 insertion(+) create mode 100644 doc/.gitignore diff --git a/doc/.gitignore b/doc/.gitignore new file mode 100644 index 00000000..84b61228 --- /dev/null +++ b/doc/.gitignore @@ -0,0 +1 @@ +*.pdn -- cgit v1.2.3