diff options
Diffstat (limited to 'src/path-search.hpp')
| -rw-r--r-- | src/path-search.hpp | 60 |
1 files changed, 31 insertions, 29 deletions
diff --git a/src/path-search.hpp b/src/path-search.hpp index 42d99d4d..672ecc3d 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -23,6 +23,34 @@ class chunk; // todo add pathfinding sub-namespace +namespace detail_astar { + +struct chunk_cache; +static constexpr int div_factor = 4; +static constexpr auto div_size = iTILE_SIZE2 / div_factor; +static constexpr auto min_size = Vector2ui(div_size * 2); + +struct cache +{ + Vector2ui size; + Vector2i start{(int)((1u << 31) - 1)}; + Array<chunk_cache> array; + + cache(); + fm_DECLARE_DELETED_COPY_ASSIGNMENT(cache); + + size_t get_chunk_index(Vector2i chunk) const; + static size_t get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord); + static size_t get_tile_index(Vector2i pos, Vector2b offset); + static Vector2ui get_size_to_allocate(uint32_t max_dist); + + void allocate(point from, uint32_t max_dist); + void add_index(size_t chunk_index, size_t tile_index, uint32_t index); + void add_index(point pt, uint32_t index); + uint32_t lookup_index(size_t chunk_index, size_t tile_index); + chunk* try_get_chunk(world& w, chunk_coords_ ch); +}; +} // namespace detail_astar struct path_search_result; enum class path_search_continue : bool { pass = false, blocked = true }; @@ -31,10 +59,6 @@ class path_search final friend struct path_search_result; public: - static constexpr int div_factor = 4; - static constexpr auto div_size = iTILE_SIZE2 / div_factor; - static constexpr auto min_size = Vector2ui(div_size * 2); - template<typename T> requires std::is_arithmetic_v<T> struct bbox @@ -59,10 +83,9 @@ public: 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, global_coords coord, Vector2b offset, Vector2ui 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()); + static bool is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, const bbox<float>& bb, object_id own_id, const pred& p = never_continue()); }; class astar @@ -90,35 +113,14 @@ public: int debug = 0, const pred& p = path_search::never_continue()); private: - static constexpr auto div_factor = (int8_t)path_search::div_factor; - static constexpr auto initial_capacity = TILE_COUNT * 16 * div_factor*div_factor; + static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor; struct chunk_cache; - struct cache - { - Vector2ui size; - Vector2i start{(int)((1u << 31) - 1)}; - Array<chunk_cache> array; - - cache(); - fm_DECLARE_DELETED_COPY_ASSIGNMENT(cache); - - size_t get_chunk_index(Vector2i chunk) const; - static size_t get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord); - static size_t get_tile_index(Vector2i pos, Vector2b offset); - static Vector2ui get_size_to_allocate(uint32_t max_dist); - - void allocate(point from, uint32_t max_dist); - void add_index(size_t chunk_index, size_t tile_index, uint32_t index); - void add_index(point pt, uint32_t index); - uint32_t lookup_index(size_t chunk_index, size_t tile_index); - }; - void add_to_heap(uint32_t id); uint32_t pop_from_heap(); - struct cache cache; + struct detail_astar::cache cache; std::vector<visited> nodes; std::vector<uint32_t> Q; }; |