From 50e42d74c9b25e2ec4c6b9fd3434f431c0b5c3d9 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sun, 25 Feb 2024 04:45:17 +0100 Subject: rename path_search -> search --- src/astar.hpp | 14 ++--- src/chunk-region.cpp | 12 ++--- src/chunk-region.hpp | 4 +- src/chunk.hpp | 4 +- src/dijkstra.cpp | 14 ++--- src/path-search-bbox.hpp | 25 --------- src/path-search-node.hpp | 24 --------- src/path-search-pred.hpp | 18 ------- src/path-search-result.cpp | 99 ----------------------------------- src/path-search-result.hpp | 50 ------------------ src/path-search.cpp | 127 --------------------------------------------- src/path-search.hpp | 49 ----------------- src/search-bbox.hpp | 25 +++++++++ src/search-node.hpp | 24 +++++++++ src/search-pred.hpp | 18 +++++++ src/search-result.cpp | 99 +++++++++++++++++++++++++++++++++++ src/search-result.hpp | 50 ++++++++++++++++++ src/search.cpp | 127 +++++++++++++++++++++++++++++++++++++++++++++ src/search.hpp | 49 +++++++++++++++++ 19 files changed, 416 insertions(+), 416 deletions(-) delete mode 100644 src/path-search-bbox.hpp delete mode 100644 src/path-search-node.hpp delete mode 100644 src/path-search-pred.hpp delete mode 100644 src/path-search-result.cpp delete mode 100644 src/path-search-result.hpp delete mode 100644 src/path-search.cpp delete mode 100644 src/path-search.hpp create mode 100644 src/search-bbox.hpp create mode 100644 src/search-node.hpp create mode 100644 src/search-pred.hpp create mode 100644 src/search-result.cpp create mode 100644 src/search-result.hpp create mode 100644 src/search.cpp create mode 100644 src/search.hpp (limited to 'src') diff --git a/src/astar.hpp b/src/astar.hpp index 0a46ec6d..7c48c5db 100644 --- a/src/astar.hpp +++ b/src/astar.hpp @@ -1,10 +1,10 @@ #pragma once -#include "path-search.hpp" +#include "search.hpp" #include "point.hpp" #include #include -namespace floormat::detail_astar { +namespace floormat::Search { struct cache; struct chunk_cache; @@ -32,7 +32,7 @@ struct cache std::array get_neighbors(world& w, chunk_coords_ ch0); }; -} // namespace floormat::detail_astar +} // namespace floormat::Search namespace floormat { @@ -46,7 +46,7 @@ public: point pt; }; - using pred = detail_astar::pred; + using pred = Search::pred; fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar); @@ -57,17 +57,17 @@ public: // todo add simple bresenham short-circuit path_search_result Dijkstra(world& w, point from, point to, object_id own_id, uint32_t max_dist, Vector2ub own_size, - int debug = 0, const pred& p = detail_astar::never_continue()); + int debug = 0, const pred& p = Search::never_continue()); private: - static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor; + static constexpr auto initial_capacity = TILE_COUNT * 16 * Search::div_factor*Search::div_factor; struct chunk_cache; void add_to_heap(uint32_t id); uint32_t pop_from_heap(); - struct detail_astar::cache cache; + struct Search::cache cache; Array nodes; Array Q; }; diff --git a/src/chunk-region.cpp b/src/chunk-region.cpp index 54696bc0..228b1052 100644 --- a/src/chunk-region.cpp +++ b/src/chunk-region.cpp @@ -1,5 +1,5 @@ #include "chunk-region.hpp" -#include "path-search-bbox.hpp" +#include "search-bbox.hpp" #include "world.hpp" #include "collision.hpp" #include "object.hpp" @@ -13,11 +13,11 @@ namespace floormat { namespace { -using detail_astar::bbox; -using detail_astar::div_factor; -using detail_astar::div_size; -using detail_astar::div_count; -using detail_astar::pred; +using Search::bbox; +using Search::div_factor; +using Search::div_size; +using Search::div_count; +using Search::pred; static_assert(div_count.x() == div_count.y()); static_assert((iTILE_SIZE2 % div_size).isZero()); diff --git a/src/chunk-region.hpp b/src/chunk-region.hpp index 5720e93e..579ab1ef 100644 --- a/src/chunk-region.hpp +++ b/src/chunk-region.hpp @@ -1,13 +1,13 @@ #pragma once #include "chunk.hpp" -#include "path-search.hpp" +#include "search.hpp" #include namespace floormat { struct chunk::pass_region { - std::bitset bits; + std::bitset bits; }; } // namespace floormat diff --git a/src/chunk.hpp b/src/chunk.hpp index 217bd35a..682482f7 100644 --- a/src/chunk.hpp +++ b/src/chunk.hpp @@ -5,7 +5,7 @@ #include "src/RTree-fwd.h" #include "global-coords.hpp" #include "wall-defs.hpp" -#include "path-search-pred.hpp" +#include "search-pred.hpp" #include #include #include @@ -121,7 +121,7 @@ public: const pass_region* get_pass_region(); void make_pass_region(pass_region& ret); - void make_pass_region(pass_region& ret, const detail_astar::pred& f); + void make_pass_region(pass_region& ret, const Search::pred& f); private: struct ground_stuff diff --git a/src/dijkstra.cpp b/src/dijkstra.cpp index 11c85d01..1f353e30 100644 --- a/src/dijkstra.cpp +++ b/src/dijkstra.cpp @@ -1,5 +1,5 @@ #include "astar.hpp" -#include "path-search-bbox.hpp" +#include "search-bbox.hpp" #include "compat/format.hpp" #include "compat/vector-wrapper.hpp" #include "compat/heap.hpp" @@ -16,10 +16,10 @@ namespace floormat { using visited = astar::visited; -using detail_astar::bbox; -using detail_astar::div_size; -using detail_astar::div_factor; -using detail_astar::min_size; +using Search::bbox; +using Search::div_size; +using Search::div_factor; +using Search::min_size; namespace { @@ -360,7 +360,7 @@ path_search_result astar::Dijkstra(world& w, const point from, const point to, } // namespace floormat -namespace floormat::detail_astar { +namespace floormat::Search { struct chunk_cache { @@ -498,4 +498,4 @@ std::array cache::get_neighbors(world& w, chunk_coords_ ch0) return neighbors; } -} // namespace floormat::detail_astar +} // namespace floormat::Search diff --git a/src/path-search-bbox.hpp b/src/path-search-bbox.hpp deleted file mode 100644 index 05ed726d..00000000 --- a/src/path-search-bbox.hpp +++ /dev/null @@ -1,25 +0,0 @@ -#pragma once -#include "path-search.hpp" -#include -#include -#include - -namespace floormat::detail_astar { - -template struct bbox -{ - static_assert(std::is_arithmetic_v); - - VectorTypeFor<2, T> min, max; - - constexpr bool operator==(const bbox&) const = default; - - template - requires std::is_arithmetic_v - explicit constexpr operator bbox() const { - using Vec = VectorTypeFor<2, U>; - return bbox{ Vec(min), Vec(max) }; - } -}; - -} // namespace floormat::detail_astar diff --git a/src/path-search-node.hpp b/src/path-search-node.hpp deleted file mode 100644 index ecad6a77..00000000 --- a/src/path-search-node.hpp +++ /dev/null @@ -1,24 +0,0 @@ -#pragma once -#include "compat/defs.hpp" -#include "path-search-result.hpp" -#include -#include - -namespace floormat { - -struct path_search_result::node -{ - friend struct path_search_result; - friend struct test_app; - - node() noexcept; - fm_DECLARE_DELETED_COPY_ASSIGNMENT(node); - fm_DECLARE_DEFAULT_MOVE_ASSIGNMENT_(node); - - std::vector vec; - -private: - Pointer _next; -}; - -} // namespace floormat diff --git a/src/path-search-pred.hpp b/src/path-search-pred.hpp deleted file mode 100644 index f0f99c3e..00000000 --- a/src/path-search-pred.hpp +++ /dev/null @@ -1,18 +0,0 @@ -#pragma once -#include "compat/function2.fwd.hpp" -#include "collision.hpp" - -namespace floormat { - -enum class path_search_continue : bool { pass = false, blocked = true }; - -} // namespace floormat - -namespace floormat::detail_astar { - -using pred = fu2::function_view; - -const pred& never_continue() noexcept; -const pred& always_continue() noexcept; - -} // namespace floormat::detail_astar diff --git a/src/path-search-result.cpp b/src/path-search-result.cpp deleted file mode 100644 index afc4bf59..00000000 --- a/src/path-search-result.cpp +++ /dev/null @@ -1,99 +0,0 @@ -#include "path-search-result.hpp" -//#include "path-search.hpp" -#include "compat/assert.hpp" -#include "compat/vector-wrapper.hpp" -#include "path-search-node.hpp" -#include "src/point.hpp" -#include -#include - -namespace floormat { - -namespace { - -constexpr size_t min_length = TILE_MAX_DIM*2; - -} // namespace - -Pointer path_search_result::_pool; // NOLINT - -path_search_result::path_search_result() -{ - if (_pool) - { - auto ptr = std::move(_pool); - fm_debug_assert(ptr->vec.empty()); - auto next = std::move(ptr->_next); - _node = std::move(ptr); - _pool = std::move(next); - } - else - { - _node = Pointer{InPlaceInit}; - _node->vec.reserve(min_length); - } -} - -path_search_result::~path_search_result() noexcept -{ - if (_node && _node->vec.capacity() > 0) [[likely]] - { - _node->vec.clear(); - _node->_next = std::move(_pool); - _pool = std::move(_node); - } -} - -path_search_result::path_search_result(const path_search_result& x) noexcept -{ - fm_debug_assert(x._node); - auto self = path_search_result{}; - self._node->vec = x._node->vec; - _node = std::move(self._node); - _cost = x._cost; -} - -path_search_result& path_search_result::operator=(const path_search_result& x) noexcept -{ - fm_debug_assert(_node); - fm_debug_assert(!_node->_next); - if (&x != this) - _node->vec = x._node->vec; - _cost = x._cost; - return *this; -} - -path_search_result::path_search_result(path_search_result&&) noexcept = default; -path_search_result& path_search_result::operator=(path_search_result&&) noexcept = default; - -size_t path_search_result::size() const { return _node->vec.size(); } -path_search_result::node::node() noexcept = default; -float path_search_result::time() const { return _time; } - -uint32_t path_search_result::cost() const { return _cost; } -void path_search_result::set_cost(uint32_t value) { _cost = value; } -void path_search_result::set_time(float time) { _time = time; } -bool path_search_result::is_found() const { return _found; } -void path_search_result::set_found(bool value) { _found = value; } -uint32_t path_search_result::distance() const { return _distance; } -void path_search_result::set_distance(uint32_t dist) { _distance = dist; } - -auto path_search_result::data() const -> const point* { return _node->vec.data(); } -path_search_result::operator bool() const { return !_node->vec.empty(); } - -path_search_result::operator ArrayView() const -{ - fm_debug_assert(_node); - return {_node->vec.data(), _node->vec.size()}; -} - -const point& path_search_result::operator[](size_t index) const -{ - fm_debug_assert(_node); - fm_debug_assert(index < _node->vec.size()); - return data()[index]; -} -vector_wrapper path_search_result::raw_path() { fm_assert(_node); return {_node->vec}; } -ArrayView path_search_result::path() const { fm_assert(_node); return {_node->vec.data(), _node->vec.size()}; } - -} // namespace floormat diff --git a/src/path-search-result.hpp b/src/path-search-result.hpp deleted file mode 100644 index d29fdc44..00000000 --- a/src/path-search-result.hpp +++ /dev/null @@ -1,50 +0,0 @@ -#pragma once -#include "compat/defs.hpp" -#include "compat/vector-wrapper-fwd.hpp" -#include "src/global-coords.hpp" -#include - -namespace floormat { - -struct point; - -struct path_search_result final -{ - friend struct test_app; - - const point* data() const; - const point& operator[](size_t index) const; - size_t size() const; - uint32_t cost() const; - void set_cost(uint32_t value); - float time() const; - void set_time(float time); - bool is_found() const; - void set_found(bool value); - uint32_t distance() const; - void set_distance(uint32_t dist); - - vector_wrapper raw_path(); - ArrayView path() const; - explicit operator ArrayView() const; - explicit operator bool() const; - - path_search_result(); - path_search_result(const path_search_result& x) noexcept; - path_search_result& operator=(const path_search_result& x) noexcept; - path_search_result(path_search_result&&) noexcept; - path_search_result& operator=(path_search_result&&) noexcept; - ~path_search_result() noexcept; - -private: - struct node; - - static Pointer _pool; // NOLINT(*-avoid-non-const-global-variables) - - Pointer _node; - float _time = 0; - uint32_t _cost = 0, _distance = (uint32_t)-1; - bool _found : 1 = false; -}; - -} // namespace floormat diff --git a/src/path-search.cpp b/src/path-search.cpp deleted file mode 100644 index a41c2820..00000000 --- a/src/path-search.cpp +++ /dev/null @@ -1,127 +0,0 @@ -#include "path-search.hpp" -#include "path-search-bbox.hpp" -#include "astar.hpp" -#include "global-coords.hpp" -#include "world.hpp" -#include "pass-mode.hpp" -#include "RTree-search.hpp" -#include "compat/function2.hpp" -#include - -namespace floormat::detail_astar { - -namespace { -constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; }; -constexpr auto never_continue_ = pred{never_continue_1}; -constexpr auto always_continue_1 = [](collision_data) constexpr { return path_search_continue::pass; }; -constexpr auto always_continue_ = pred{always_continue_1}; -} // namespace - -const pred& never_continue() noexcept { return never_continue_; } -const pred& always_continue() noexcept { return always_continue_; } -//static_assert(1 << 2 == div_factor); - -} // namespace floormat::detail_astar - -namespace floormat { - -using namespace detail_astar; - -bool path_search::is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p) -{ - constexpr auto bbox_size = Vector2{0xff, 0xff}; - constexpr auto chunk_bounds = bbox{ - -TILE_SIZE2/2 - bbox_size/2, - TILE_MAX_DIM*TILE_SIZE2 - TILE_SIZE2/2 + bbox_size, - }; - if (!rect_intersects(min, max, chunk_bounds.min, chunk_bounds.max)) - return true; - - auto& rt = *c.rtree(); - bool is_passable = true; - rt.Search(min.data(), max.data(), [&](uint64_t data, const auto& r) - { - auto x = std::bit_cast(data); - if (x.data != own_id && x.pass != (uint64_t)pass_mode::pass) - { - if (rect_intersects(min, max, {r.m_min[0], r.m_min[1]}, {r.m_max[0], r.m_max[1]})) - if (p(x) != path_search_continue::pass) - { - is_passable = false; - //[[maybe_unused]] auto obj = c.world().find_object(x.data); - return false; - } - } - return true; - }); - return is_passable; -} - -bool path_search::is_passable_(chunk* c0, const std::array& neighbors, - Vector2 min, Vector2 max, object_id own_id, const pred& p) -{ - fm_debug_assert(max >= min); - - if (c0) - // it's not correct to return true if c == nullptr - // because neighbors can still contain bounding boxes for that tile - if (!is_passable_1(*c0, min, max, own_id, p)) - return false; - - for (auto i = 0uz; i < 8; i++) - { - auto nb = world::neighbor_offsets[i]; - auto* c2 = neighbors[i]; - - if (c2) - { - static_assert(std::size(world::neighbor_offsets) == 8); - constexpr auto chunk_size = iTILE_SIZE2 * TILE_MAX_DIM; - const auto off = Vector2(nb)*Vector2(chunk_size); - const auto min_ = min - off, max_ = max - off; - - if (!is_passable_1(*c2, min_, max_, own_id, p)) - return false; - } - } - - return true; -} - -bool path_search::is_passable(world& w, global_coords coord, - Vector2b offset, Vector2ui size_, - object_id own_id, const pred& p) -{ - auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset); - auto size = Vector2(size_); - auto min = Vector2(center) - size*.5f, max = min + size; - return is_passable(w, coord, {min, max}, own_id, p); -} - -bool path_search::is_passable(world& w, struct detail_astar::cache& cache, global_coords coord, - Vector2b offset, Vector2ui size_, - object_id own_id, const pred& p) -{ - auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset); - auto size = Vector2(size_); - auto min = Vector2(center) - size*.5f, max = min + size; - return is_passable(w, cache, coord, {min, max}, own_id, p); -} - -bool path_search::is_passable(world& w, chunk_coords_ ch, const bbox& bb, - object_id own_id, const pred& p) -{ - auto* c = w.at(ch); - auto neighbors = w.neighbors(ch); - return is_passable_(c, neighbors, bb.min, bb.max, own_id, p); -} - -bool path_search::is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, - const bbox& bb, object_id own_id, const pred& p) -{ - auto* c = cache.try_get_chunk(w, ch0); - auto nbs = cache.get_neighbors(w, ch0); - return is_passable_(c, nbs, bb.min, bb.max, own_id, p); -} - -} // namespace floormat diff --git a/src/path-search.hpp b/src/path-search.hpp deleted file mode 100644 index 05516676..00000000 --- a/src/path-search.hpp +++ /dev/null @@ -1,49 +0,0 @@ -#pragma once -#include "tile-constants.hpp" -#include "global-coords.hpp" -#include "object-id.hpp" -#include "path-search-result.hpp" -#include "path-search-pred.hpp" -#include - -namespace floormat { -class world; -struct object; -class chunk; -} // namespace floormat - -// todo add pathfinding sub-namespace - -namespace floormat::detail_astar { - -template struct bbox; -struct cache; -struct chunk_cache; -constexpr inline int div_factor = 4; -constexpr inline auto div_size = iTILE_SIZE2 / div_factor; -constexpr inline auto min_size = Vector2ui(div_size * 2); -constexpr inline auto div_count = iTILE_SIZE2 * TILE_MAX_DIM / detail_astar::div_size; - -} // namespace floormat::detail_astar - -namespace floormat { - -struct path_search_result; - -class path_search final -{ - friend struct path_search_result; - template using bbox = detail_astar::bbox; - using pred = detail_astar::pred; - -public: - static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p = detail_astar::never_continue()); - static bool is_passable_(chunk* c0, const std::array& neighbors, - Vector2 min, Vector2 max, object_id own_id, const pred& p = detail_astar::never_continue()); - static bool is_passable(world& w, global_coords coord, Vector2b offset, Vector2ui size, object_id own_id, const pred& p = detail_astar::never_continue()); - static bool is_passable(world& w, struct detail_astar::cache& cache, global_coords coord, Vector2b offset, Vector2ui size, object_id own_id, const pred& p = detail_astar::never_continue()); - static bool is_passable(world& w, chunk_coords_ ch0, const bbox& bb, object_id own_id, const pred& p = detail_astar::never_continue()); - static bool is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, const bbox& bb, object_id own_id, const pred& p = detail_astar::never_continue()); -}; - -} // namespace floormat diff --git a/src/search-bbox.hpp b/src/search-bbox.hpp new file mode 100644 index 00000000..0d211daf --- /dev/null +++ b/src/search-bbox.hpp @@ -0,0 +1,25 @@ +#pragma once +#include "search.hpp" +#include +#include +#include + +namespace floormat::Search { + +template struct bbox +{ + static_assert(std::is_arithmetic_v); + + VectorTypeFor<2, T> min, max; + + constexpr bool operator==(const bbox&) const = default; + + template + requires std::is_arithmetic_v + explicit constexpr operator bbox() const { + using Vec = VectorTypeFor<2, U>; + return bbox{ Vec(min), Vec(max) }; + } +}; + +} // namespace floormat::Search diff --git a/src/search-node.hpp b/src/search-node.hpp new file mode 100644 index 00000000..c2977f84 --- /dev/null +++ b/src/search-node.hpp @@ -0,0 +1,24 @@ +#pragma once +#include "compat/defs.hpp" +#include "search-result.hpp" +#include +#include + +namespace floormat { + +struct path_search_result::node +{ + friend struct path_search_result; + friend struct test_app; + + node() noexcept; + fm_DECLARE_DELETED_COPY_ASSIGNMENT(node); + fm_DECLARE_DEFAULT_MOVE_ASSIGNMENT_(node); + + std::vector vec; + +private: + Pointer _next; +}; + +} // namespace floormat diff --git a/src/search-pred.hpp b/src/search-pred.hpp new file mode 100644 index 00000000..c2967549 --- /dev/null +++ b/src/search-pred.hpp @@ -0,0 +1,18 @@ +#pragma once +#include "compat/function2.fwd.hpp" +#include "collision.hpp" + +namespace floormat { + +enum class path_search_continue : bool { pass = false, blocked = true }; + +} // namespace floormat + +namespace floormat::Search { + +using pred = fu2::function_view; + +const pred& never_continue() noexcept; +const pred& always_continue() noexcept; + +} // namespace floormat::Search diff --git a/src/search-result.cpp b/src/search-result.cpp new file mode 100644 index 00000000..ba94b6f0 --- /dev/null +++ b/src/search-result.cpp @@ -0,0 +1,99 @@ +#include "search-result.hpp" +//#include "search.hpp" +#include "compat/assert.hpp" +#include "compat/vector-wrapper.hpp" +#include "search-node.hpp" +#include "src/point.hpp" +#include +#include + +namespace floormat { + +namespace { + +constexpr size_t min_length = TILE_MAX_DIM*2; + +} // namespace + +Pointer path_search_result::_pool; // NOLINT + +path_search_result::path_search_result() +{ + if (_pool) + { + auto ptr = std::move(_pool); + fm_debug_assert(ptr->vec.empty()); + auto next = std::move(ptr->_next); + _node = std::move(ptr); + _pool = std::move(next); + } + else + { + _node = Pointer{InPlaceInit}; + _node->vec.reserve(min_length); + } +} + +path_search_result::~path_search_result() noexcept +{ + if (_node && _node->vec.capacity() > 0) [[likely]] + { + _node->vec.clear(); + _node->_next = std::move(_pool); + _pool = std::move(_node); + } +} + +path_search_result::path_search_result(const path_search_result& x) noexcept +{ + fm_debug_assert(x._node); + auto self = path_search_result{}; + self._node->vec = x._node->vec; + _node = std::move(self._node); + _cost = x._cost; +} + +path_search_result& path_search_result::operator=(const path_search_result& x) noexcept +{ + fm_debug_assert(_node); + fm_debug_assert(!_node->_next); + if (&x != this) + _node->vec = x._node->vec; + _cost = x._cost; + return *this; +} + +path_search_result::path_search_result(path_search_result&&) noexcept = default; +path_search_result& path_search_result::operator=(path_search_result&&) noexcept = default; + +size_t path_search_result::size() const { return _node->vec.size(); } +path_search_result::node::node() noexcept = default; +float path_search_result::time() const { return _time; } + +uint32_t path_search_result::cost() const { return _cost; } +void path_search_result::set_cost(uint32_t value) { _cost = value; } +void path_search_result::set_time(float time) { _time = time; } +bool path_search_result::is_found() const { return _found; } +void path_search_result::set_found(bool value) { _found = value; } +uint32_t path_search_result::distance() const { return _distance; } +void path_search_result::set_distance(uint32_t dist) { _distance = dist; } + +auto path_search_result::data() const -> const point* { return _node->vec.data(); } +path_search_result::operator bool() const { return !_node->vec.empty(); } + +path_search_result::operator ArrayView() const +{ + fm_debug_assert(_node); + return {_node->vec.data(), _node->vec.size()}; +} + +const point& path_search_result::operator[](size_t index) const +{ + fm_debug_assert(_node); + fm_debug_assert(index < _node->vec.size()); + return data()[index]; +} +vector_wrapper path_search_result::raw_path() { fm_assert(_node); return {_node->vec}; } +ArrayView path_search_result::path() const { fm_assert(_node); return {_node->vec.data(), _node->vec.size()}; } + +} // namespace floormat diff --git a/src/search-result.hpp b/src/search-result.hpp new file mode 100644 index 00000000..d29fdc44 --- /dev/null +++ b/src/search-result.hpp @@ -0,0 +1,50 @@ +#pragma once +#include "compat/defs.hpp" +#include "compat/vector-wrapper-fwd.hpp" +#include "src/global-coords.hpp" +#include + +namespace floormat { + +struct point; + +struct path_search_result final +{ + friend struct test_app; + + const point* data() const; + const point& operator[](size_t index) const; + size_t size() const; + uint32_t cost() const; + void set_cost(uint32_t value); + float time() const; + void set_time(float time); + bool is_found() const; + void set_found(bool value); + uint32_t distance() const; + void set_distance(uint32_t dist); + + vector_wrapper raw_path(); + ArrayView path() const; + explicit operator ArrayView() const; + explicit operator bool() const; + + path_search_result(); + path_search_result(const path_search_result& x) noexcept; + path_search_result& operator=(const path_search_result& x) noexcept; + path_search_result(path_search_result&&) noexcept; + path_search_result& operator=(path_search_result&&) noexcept; + ~path_search_result() noexcept; + +private: + struct node; + + static Pointer _pool; // NOLINT(*-avoid-non-const-global-variables) + + Pointer _node; + float _time = 0; + uint32_t _cost = 0, _distance = (uint32_t)-1; + bool _found : 1 = false; +}; + +} // namespace floormat diff --git a/src/search.cpp b/src/search.cpp new file mode 100644 index 00000000..9f497134 --- /dev/null +++ b/src/search.cpp @@ -0,0 +1,127 @@ +#include "search.hpp" +#include "search-bbox.hpp" +#include "astar.hpp" +#include "global-coords.hpp" +#include "world.hpp" +#include "pass-mode.hpp" +#include "RTree-search.hpp" +#include "compat/function2.hpp" +#include + +namespace floormat::Search { + +namespace { +constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; }; +constexpr auto never_continue_ = pred{never_continue_1}; +constexpr auto always_continue_1 = [](collision_data) constexpr { return path_search_continue::pass; }; +constexpr auto always_continue_ = pred{always_continue_1}; +} // namespace + +const pred& never_continue() noexcept { return never_continue_; } +const pred& always_continue() noexcept { return always_continue_; } +//static_assert(1 << 2 == div_factor); + +} // namespace floormat::Search + +namespace floormat { + +using namespace Search; + +bool path_search::is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p) +{ + constexpr auto bbox_size = Vector2{0xff, 0xff}; + constexpr auto chunk_bounds = bbox{ + -TILE_SIZE2/2 - bbox_size/2, + TILE_MAX_DIM*TILE_SIZE2 - TILE_SIZE2/2 + bbox_size, + }; + if (!rect_intersects(min, max, chunk_bounds.min, chunk_bounds.max)) + return true; + + auto& rt = *c.rtree(); + bool is_passable = true; + rt.Search(min.data(), max.data(), [&](uint64_t data, const auto& r) + { + auto x = std::bit_cast(data); + if (x.data != own_id && x.pass != (uint64_t)pass_mode::pass) + { + if (rect_intersects(min, max, {r.m_min[0], r.m_min[1]}, {r.m_max[0], r.m_max[1]})) + if (p(x) != path_search_continue::pass) + { + is_passable = false; + //[[maybe_unused]] auto obj = c.world().find_object(x.data); + return false; + } + } + return true; + }); + return is_passable; +} + +bool path_search::is_passable_(chunk* c0, const std::array& neighbors, + Vector2 min, Vector2 max, object_id own_id, const pred& p) +{ + fm_debug_assert(max >= min); + + if (c0) + // it's not correct to return true if c == nullptr + // because neighbors can still contain bounding boxes for that tile + if (!is_passable_1(*c0, min, max, own_id, p)) + return false; + + for (auto i = 0uz; i < 8; i++) + { + auto nb = world::neighbor_offsets[i]; + auto* c2 = neighbors[i]; + + if (c2) + { + static_assert(std::size(world::neighbor_offsets) == 8); + constexpr auto chunk_size = iTILE_SIZE2 * TILE_MAX_DIM; + const auto off = Vector2(nb)*Vector2(chunk_size); + const auto min_ = min - off, max_ = max - off; + + if (!is_passable_1(*c2, min_, max_, own_id, p)) + return false; + } + } + + return true; +} + +bool path_search::is_passable(world& w, global_coords coord, + Vector2b offset, Vector2ui size_, + object_id own_id, const pred& p) +{ + auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset); + auto size = Vector2(size_); + auto min = Vector2(center) - size*.5f, max = min + size; + return is_passable(w, coord, {min, max}, own_id, p); +} + +bool path_search::is_passable(world& w, struct Search::cache& cache, global_coords coord, + Vector2b offset, Vector2ui size_, + object_id own_id, const pred& p) +{ + auto center = iTILE_SIZE2 * Vector2i(coord.local()) + Vector2i(offset); + auto size = Vector2(size_); + auto min = Vector2(center) - size*.5f, max = min + size; + return is_passable(w, cache, coord, {min, max}, own_id, p); +} + +bool path_search::is_passable(world& w, chunk_coords_ ch, const bbox& bb, + object_id own_id, const pred& p) +{ + auto* c = w.at(ch); + auto neighbors = w.neighbors(ch); + return is_passable_(c, neighbors, bb.min, bb.max, own_id, p); +} + +bool path_search::is_passable(world& w, struct Search::cache& cache, chunk_coords_ ch0, + const bbox& bb, object_id own_id, const pred& p) +{ + auto* c = cache.try_get_chunk(w, ch0); + auto nbs = cache.get_neighbors(w, ch0); + return is_passable_(c, nbs, bb.min, bb.max, own_id, p); +} + +} // namespace floormat diff --git a/src/search.hpp b/src/search.hpp new file mode 100644 index 00000000..024c8613 --- /dev/null +++ b/src/search.hpp @@ -0,0 +1,49 @@ +#pragma once +#include "tile-constants.hpp" +#include "global-coords.hpp" +#include "object-id.hpp" +#include "search-result.hpp" +#include "search-pred.hpp" +#include + +namespace floormat { +class world; +struct object; +class chunk; +} // namespace floormat + +// todo add pathfinding sub-namespace + +namespace floormat::Search { + +template struct bbox; +struct cache; +struct chunk_cache; +constexpr inline int div_factor = 4; +constexpr inline auto div_size = iTILE_SIZE2 / div_factor; +constexpr inline auto min_size = Vector2ui(div_size * 2); +constexpr inline auto div_count = iTILE_SIZE2 * TILE_MAX_DIM / Search::div_size; + +} // namespace floormat::Search + +namespace floormat { + +struct path_search_result; + +class path_search final +{ + friend struct path_search_result; + template using bbox = Search::bbox; + using pred = Search::pred; + +public: + static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p = Search::never_continue()); + static bool is_passable_(chunk* c0, const std::array& neighbors, + Vector2 min, Vector2 max, object_id own_id, const pred& p = Search::never_continue()); + static bool is_passable(world& w, global_coords coord, Vector2b offset, Vector2ui size, object_id own_id, const pred& p = Search::never_continue()); + static bool is_passable(world& w, struct Search::cache& cache, global_coords coord, Vector2b offset, Vector2ui size, object_id own_id, const pred& p = Search::never_continue()); + static bool is_passable(world& w, chunk_coords_ ch0, const bbox& bb, object_id own_id, const pred& p = Search::never_continue()); + static bool is_passable(world& w, struct Search::cache& cache, chunk_coords_ ch0, const bbox& bb, object_id own_id, const pred& p = Search::never_continue()); +}; + +} // namespace floormat -- cgit v1.2.3