From e264037a78005abfb39edaed05c6014dc5230413 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Thu, 14 Sep 2023 01:08:08 +0200 Subject: simplify path_search --- src/path-search.cpp | 88 ++++++++++++++++++++++++++-------------------------- src/path-search.hpp | 22 ++++++------- test/path-search.cpp | 27 ++++++++-------- 3 files changed, 69 insertions(+), 68 deletions(-) diff --git a/src/path-search.cpp b/src/path-search.cpp index 936ee6bf..e4d8c1cf 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -11,9 +11,9 @@ namespace floormat { -search_result::~search_result() = default; +path_search_result::path_search_result() = default; -void search::ensure_allocated(chunk_coords a, chunk_coords b) +void path_search::ensure_allocated(chunk_coords a, chunk_coords b) { 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); @@ -30,7 +30,7 @@ void search::ensure_allocated(chunk_coords a, chunk_coords b) x = {}; } -bool search::is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id) +bool path_search::is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id) { auto& rt = *c.rtree(); bool is_passable = true; @@ -47,7 +47,7 @@ bool search::is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id) return is_passable; } -bool search::is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, object_id own_id) +bool path_search::is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, object_id own_id) { if (auto* c = w.at(ch0)) // it's not correct to return true if c == nullptr @@ -77,7 +77,7 @@ bool search::is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, return true; } -bool search::is_passable(world& w, global_coords coord, Vector2b offset, Vector2ub size_, object_id own_id) +bool path_search::is_passable(world& w, global_coords coord, Vector2b offset, Vector2ub size_, object_id own_id) { auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset); auto size = Vector2(size_); @@ -85,15 +85,13 @@ bool search::is_passable(world& w, global_coords coord, Vector2b offset, Vector2 return is_passable(w, coord, min, max, own_id); } -auto 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, rotation r) -> bbox { - constexpr auto get_value = [](Vector2i coord, Vector2i sz, rotation r) constexpr -> Pair { + 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(); - auto tile_center = coord * iTILE_SIZE2; - auto tile_start = tile_center - half_tile; - auto empty_space_NS = (iTILE_SIZE2.x() - sz.x()) / 2; auto empty_space_WE = (iTILE_SIZE2.y() - sz.y()) / 2; @@ -103,27 +101,27 @@ auto search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, rotatio switch (r_) { case (uint8_t)rotation::N: { - auto min_N = Vector2i(tile_start.x() + empty_space_NS, tile_center.y() - offset_N ); - auto max_N = Vector2i(min_N.x() + sz.x(), tile_center.y() ); + auto min_N = Vector2i(-half_tile.x() + empty_space_NS, -offset_N ); + auto max_N = Vector2i(min_N.x() + sz.x(), 0 ); return {min_N, max_N}; } case (uint8_t)rotation::S: { - auto min_S = Vector2i(tile_start.x() + empty_space_NS, tile_center.y() ); - auto max_S = Vector2i(min_S.x() + sz.x(), tile_center.y() + offset_N ); + auto min_S = Vector2i(-half_tile.x() + empty_space_NS, 0 ); + auto max_S = Vector2i(min_S.x() + sz.x(), offset_N ); return {min_S, max_S}; } case (uint8_t)rotation::W: { - auto min_W = Vector2i(tile_center.x() - offset_W, tile_start.y() + empty_space_WE ); - auto max_W = Vector2i(tile_center.x(), min_W.y() + sz.y() ); + auto min_W = Vector2i(-offset_W, -half_tile.y() + empty_space_WE ); + auto max_W = Vector2i(0, min_W.y() + sz.y() ); return {min_W, max_W}; - } + } case (uint8_t)rotation::E: { - auto min_E = Vector2i(tile_center.x(), tile_start.y() + empty_space_WE ); - auto max_E = Vector2i(tile_center.x() + offset_W, min_E.y() + sz.y() ); + auto min_E = Vector2i(0, -half_tile.y() + empty_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(tile_center.x() - (sz.x() >> 1), tile_center.y() - (sz.y() >> 1)); + auto min_C = Vector2i(-(sz.x() >> 1), - (sz.y() >> 1) ); auto max_C = min_C + sz; return {min_C, max_C}; } @@ -132,48 +130,50 @@ auto search::make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, rotatio } }; + constexpr auto min_size = iTILE_SIZE2*3/4; + static_assert(min_size.x() % 2 == 0); + #if 0 if constexpr(true) { constexpr auto sz_ = min_size; - constexpr Vector2i coord_ = Vector2i(1, 2); + constexpr Vector2i shift = Vector2i(1, 2) * iTILE_SIZE2; { - constexpr auto N = get_value(coord_, sz_, rotation::N); - constexpr auto min_N = N.first(), max_N = N.second(); - { [[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 N = get_value(sz_, 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(coord_, sz_, rotation::E); - constexpr auto min_E = E.first(), max_E = E.second(); - { [[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 E = get_value(sz_, 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(coord_, sz_, rotation::S); - constexpr auto min_S = S.first(), max_S = S.second(); - { [[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 S = get_value(sz_, 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(coord_, sz_, rotation::W); - constexpr auto min_W = W.first(), max_W = W.second(); - { [[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(); } + constexpr auto W = get_value(sz_, 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 - constexpr auto min_size = iTILE_SIZE2*3/4; - static_assert(min_size.x() % 2 == 0); - + const auto shift = coord * iTILE_SIZE2; auto sz = Math::max(Vector2i(own_size), min_size); - auto [min, max] = get_value(coord, sz, r); - return { Vector2(min), Vector2(max) }; + auto [min, max] = get_value(sz, r); + return { Vector2(min + shift), Vector2(max + shift) }; } -Optional search::operator()(world& w, object_id own_id, +Optional +path_search::operator()(world& w, object_id own_id, global_coords from, Vector2b from_offset, Vector2ub size, global_coords to, Vector2b to_offset) { @@ -193,7 +193,7 @@ Optional search::operator()(world& w, object_id own_id, return {}; } -Optional search::operator()(world& w, const object& obj, global_coords to, Vector2b to_offset) +Optional path_search::operator()(world& w, const object& obj, global_coords to, Vector2b to_offset) { constexpr auto full_tile = Vector2ub(iTILE_SIZE2*3/4); auto size = Math::max(obj.bbox_size, full_tile); diff --git a/src/path-search.hpp b/src/path-search.hpp index 651b719e..68cf41a4 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -22,13 +22,13 @@ struct world; struct object; struct chunk; -struct search_result; -class search; +struct path_search_result; +class path_search; -struct search_result final +struct path_search_result final { - friend class search; - ~search_result(); + friend class path_search; + path_search_result(); size_t size() const; const global_coords& operator[](size_t index) const; @@ -41,14 +41,14 @@ struct search_result final const global_coords* data() const; private: - mutable search_result* _next; + mutable path_search_result* _next; std::unique_ptr _path; size_t _size; }; -class search final +class path_search final { - struct neighbors + struct neighbors final { auto begin() const { return neighbors.data(); } auto end() const { return neighbors.data() + size; } @@ -74,7 +74,7 @@ class search final Array output; // todo bucketize by array length - search_result* pool = nullptr; + path_search_result* pool = nullptr; void ensure_allocated(chunk_coords a, chunk_coords b); @@ -83,8 +83,8 @@ public: // todo remember to check from.z() == to.z() // todo add simple bresenham short-circuit - Optional operator()(world& w, object_id own_id, global_coords from, Vector2b from_offset, Vector2ub size, global_coords to, Vector2b to_offset); - Optional operator()(world& w, const object& obj, global_coords to, Vector2b to_offset); + Optional operator()(world& w, object_id own_id, global_coords from, Vector2b from_offset, Vector2ub size, global_coords to, Vector2b to_offset); + Optional operator()(world& w, const object& obj, global_coords to, Vector2b to_offset); static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id); static bool is_passable(world& w, chunk_coords_ ch0, Vector2 min, Vector2 max, object_id own_id); diff --git a/test/path-search.cpp b/test/path-search.cpp index 0fdd80b5..ff09a5c9 100644 --- a/test/path-search.cpp +++ b/test/path-search.cpp @@ -11,16 +11,16 @@ namespace { void test_bbox() { - constexpr auto sample = [](chunk& c, search::bbox bb) { - return search::is_passable_1(c, bb.min, bb.max, (object_id)-1); + constexpr auto is_passable_1 = [](chunk& c, path_search::bbox bb) { + return path_search::is_passable_1(c, bb.min, bb.max, (object_id)-1); }; - constexpr auto sample2 = [](world& w, chunk_coords_ ch, search::bbox bb) { - return search::is_passable(w, ch, bb.min, bb.max, (object_id)-1); + constexpr auto is_passable = [](world& w, chunk_coords_ ch, path_search::bbox bb) { + return path_search::is_passable(w, ch, bb.min, bb.max, (object_id)-1); }; constexpr auto bbox = [](Vector2i coord, rotation r) { - return search::make_neighbor_tile_bbox(coord, {}, r); + return path_search::make_neighbor_tile_bbox(coord, {}, r); }; const auto metal2 = loader.tile_atlas("metal2", {2, 2}, pass_mode::blocked); @@ -29,6 +29,7 @@ void test_bbox() { constexpr auto coord1 = chunk_coords_{1, 1, 0}, coord2 = chunk_coords_{1, 2, 0}; + constexpr auto _15 = TILE_MAX_DIM-1; using enum rotation; { auto w = world(); @@ -36,15 +37,15 @@ void test_bbox() [[maybe_unused]] auto& c11 = w[coord1]; c12[{0, 0}].wall_north() = {metal2, 0}; - fm_assert( !sample(c12, bbox({0, 0}, N)) ); - fm_assert( sample(c12, bbox({0, 0}, E)) ); - fm_assert( sample(c12, bbox({0, 0}, S)) ); - fm_assert( sample(c12, bbox({0, 0}, W)) ); + fm_assert( !is_passable_1(c12, bbox({}, N)) ); + fm_assert( is_passable_1(c12, bbox({}, E)) ); + fm_assert( is_passable_1(c12, bbox({}, S)) ); + fm_assert( is_passable_1(c12, bbox({}, W)) ); - fm_assert( sample2(w, coord1, bbox({0, TILE_MAX_DIM-1}, N)) ); - fm_assert( sample2(w, coord1, bbox({0, TILE_MAX_DIM-1}, E)) ); - fm_assert( !sample2(w, coord1, bbox({0, TILE_MAX_DIM-1}, S)) ); - fm_assert( sample2(w, coord1, bbox({0, TILE_MAX_DIM-1}, W)) ); + fm_assert( is_passable(w, coord1, bbox({0, _15}, N)) ); + fm_assert( is_passable(w, coord1, bbox({0, _15}, E)) ); + fm_assert( !is_passable(w, coord1, bbox({0, _15}, S)) ); + fm_assert( is_passable(w, coord1, bbox({0, _15}, W)) ); } } // todo use test chunk -- cgit v1.2.3