diff options
Diffstat (limited to 'src/path-search.hpp')
| -rw-r--r-- | src/path-search.hpp | 108 |
1 files changed, 57 insertions, 51 deletions
diff --git a/src/path-search.hpp b/src/path-search.hpp index adcda8a0..1d48857a 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -24,21 +24,44 @@ namespace floormat { struct world; struct object; struct chunk; -struct path_search_result; +// todo add pathfinding sub-namespace + +struct path_search_result; enum class path_search_continue : bool { pass = false, blocked = true }; -struct astar +class path_search final { - fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar); + friend struct path_search_result; + +public: + static constexpr int subdivide_factor = 4; + static constexpr auto div_size = iTILE_SIZE2 / subdivide_factor; + static constexpr auto min_size = div_size / 2; + + template<typename T> struct bbox { VectorTypeFor<2, T> min, max; }; + + using pred = fu2::function_view<path_search_continue(collision_data) const>; + + static const pred& never_continue() noexcept; + static const pred& always_continue() noexcept; + + static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue()); + static bool is_passable_(chunk* c0, const std::array<world::neighbor_pair, 8>& neighbors, + Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue()); + 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 bool is_passable(world& w, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue()); +}; +class astar +{ struct visited { uint32_t dist = (uint32_t)-1; uint32_t prev = (uint32_t)-1; global_coords coord; Vector2b offset; - bool expanded = false; }; struct edge @@ -49,13 +72,39 @@ struct astar bool operator==(const edge& other) const; }; + enum class edge_status : uint8_t + { + // good, bad, I'm the man with the gun. + unknown, good, bad, + }; + struct point_hash { size_t operator()(point pt) const; }; struct edge_hash { size_t operator()(const edge& e) const; }; + std::vector<visited> nodes; + tsl::robin_map<edge, edge_status, edge_hash> edges; + tsl::robin_map<point, uint32_t, point_hash> indexes; + std::vector<uint32_t> Q; + + using pred = path_search::pred; + template<typename T> using bbox = path_search::bbox<T>; + +public: + fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar); + + static edge make_edge(const point& a, const point& b) + { + if (a < b) + return { a.coord, b.coord, a.offset, b.offset }; + else + return { b.coord, a.coord, b.offset, a.offset }; + } + void reserve(size_t capacity) { nodes.reserve(capacity); indexes.reserve(capacity); + edges.reserve(capacity); Q.reserve(capacity); } astar() @@ -68,57 +117,14 @@ struct astar { nodes.clear(); indexes.clear(); + edges.clear(); Q.clear(); } - std::vector<visited> nodes; - tsl::robin_set<edge, edge_hash> edges; - tsl::robin_map<point, uint32_t, point_hash> indexes; - std::vector<uint32_t> Q; -}; - -class path_search final -{ - friend struct path_search_result; - -public: - static constexpr int subdivide_factor = 4; - static constexpr auto div_size = iTILE_SIZE2 / subdivide_factor; - static constexpr auto min_size = div_size / 2; - - struct neighbors final - { - auto begin() const { return data.data(); } - auto end() const { return data.data() + size; } - - std::array<global_coords, 5> data; - uint8_t size = 0; - - operator ArrayView<const global_coords>() const; - }; - - template<typename T> struct bbox { VectorTypeFor<2, T> min, max; }; - - using pred = fu2::function_view<path_search_continue(collision_data) const>; - - struct astar astar; - - static const pred& never_continue() noexcept; - static const pred& always_continue() noexcept; - // todo add simple bresenham short-circuit - path_search_result Dijkstra(world& w, Vector2ub own_size, object_id own_id, point from, point to, const pred& p = never_continue()); - - static bool is_passable_1(chunk& c, Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue()); - static bool is_passable_(chunk* c0, const std::array<world::neighbor_pair, 8>& neighbors, - Vector2 min, Vector2 max, object_id own_id, const pred& p = never_continue()); - 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 bool is_passable(world& w, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue()); - - // todo move to test/path-search.cpp - static bbox<float> neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r); - static neighbors neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p = never_continue()); + path_search_result Dijkstra(world& w, Vector2ub own_size, object_id own_id, + point from, point to, uint32_t max_dist = (uint32_t)-1, + const pred& p = path_search::never_continue()); }; } // namespace floormat |