From 24b89cc7d168d93c154a22f8bc95c8a3afc2f54a Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Sat, 24 Feb 2024 01:23:36 +0100 Subject: move astar header to its own file --- src/astar.hpp | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/dijkstra.cpp | 2 +- src/path-search.cpp | 1 + src/path-search.hpp | 70 +++++------------------------------------------- 4 files changed, 84 insertions(+), 65 deletions(-) create mode 100644 src/astar.hpp (limited to 'src') diff --git a/src/astar.hpp b/src/astar.hpp new file mode 100644 index 00000000..78e5b070 --- /dev/null +++ b/src/astar.hpp @@ -0,0 +1,76 @@ +#pragma once +#include "path-search.hpp" +#include "point.hpp" +#include +#include + +namespace floormat::detail_astar { + +struct cache; +struct chunk_cache; + +struct cache +{ + Vector2ui size; + Vector2i start{(int)((1u << 31) - 1)}; + Array 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); + + std::array get_neighbors(world& w, chunk_coords_ ch0); +}; + +} // namespace floormat::detail_astar + +namespace floormat { + +class astar +{ +public: + struct visited + { + uint32_t dist = (uint32_t)-1; + uint32_t prev = (uint32_t)-1; + point pt; + }; + + using pred = path_search::pred; + template using bbox = path_search::bbox; + + fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar); + + astar(); + void reserve(size_t capacity); + void clear(); + + // 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 = path_search::never_continue()); + +private: + static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor; + + struct chunk_cache; + + void add_to_heap(uint32_t id); + uint32_t pop_from_heap(); + + struct detail_astar::cache cache; + Array nodes; + Array Q; +}; + +} // namespace floormat diff --git a/src/dijkstra.cpp b/src/dijkstra.cpp index 9fa348b3..f3b07172 100644 --- a/src/dijkstra.cpp +++ b/src/dijkstra.cpp @@ -1,4 +1,4 @@ -#include "path-search.hpp" +#include "astar.hpp" #include "compat/format.hpp" #include "compat/vector-wrapper.hpp" #include "compat/heap.hpp" diff --git a/src/path-search.cpp b/src/path-search.cpp index 2b93ad14..f9ea1a29 100644 --- a/src/path-search.cpp +++ b/src/path-search.cpp @@ -1,4 +1,5 @@ #include "path-search.hpp" +#include "astar.hpp" #include "global-coords.hpp" #include "world.hpp" #include "pass-mode.hpp" diff --git a/src/path-search.hpp b/src/path-search.hpp index 210d1a73..3a32dbff 100644 --- a/src/path-search.hpp +++ b/src/path-search.hpp @@ -2,57 +2,34 @@ #include "tile-constants.hpp" #include "global-coords.hpp" #include "object-id.hpp" -#include "rotation.hpp" #include "world.hpp" #include "compat/function2.fwd.hpp" #include "path-search-result.hpp" -#include "compat/int-hash.hpp" -#include "point.hpp" -#include +#include #include -#include -#include #include #include namespace floormat { - class world; struct object; class chunk; +} // namespace floormat // todo add pathfinding sub-namespace -namespace detail_astar { +namespace floormat::detail_astar { +struct cache; 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 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); +} // namespace floormat::detail_astar - 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 floormat { - std::array get_neighbors(world& w, chunk_coords_ ch0); -}; -} // namespace detail_astar struct path_search_result; enum class path_search_continue : bool { pass = false, blocked = true }; @@ -91,41 +68,6 @@ public: static bool is_passable(world& w, struct detail_astar::cache& cache, chunk_coords_ ch0, const bbox& bb, object_id own_id, const pred& p = never_continue()); }; -class astar -{ -public: - struct visited - { - uint32_t dist = (uint32_t)-1; - uint32_t prev = (uint32_t)-1; - point pt; - }; - - using pred = path_search::pred; - template using bbox = path_search::bbox; - - fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar); - - astar(); - void reserve(size_t capacity); - void clear(); - - // 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 = path_search::never_continue()); -private: - static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor; - - struct chunk_cache; - - void add_to_heap(uint32_t id); - uint32_t pop_from_heap(); - - struct detail_astar::cache cache; - Array nodes; - Array Q; -}; } // namespace floormat -- cgit v1.2.3