summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
-rw-r--r--src/path-search.cpp151
-rw-r--r--src/path-search.hpp15
2 files changed, 98 insertions, 68 deletions
diff --git a/src/path-search.cpp b/src/path-search.cpp
index c86cd076..20c7f157 100644
--- a/src/path-search.cpp
+++ b/src/path-search.cpp
@@ -13,10 +13,80 @@
namespace floormat {
namespace {
+
+constexpr auto div = path_search::subdivide_factor;
+constexpr int div_BITS = 2;
+static_assert(1 << div_BITS == div);
+
+using bbox = path_search::bbox;
+
constexpr auto never_continue_1 = [](collision_data) constexpr { return path_search_continue::blocked; };
constexpr auto never_continue_ = path_search::pred{never_continue_1};
constexpr auto always_continue_1 = [](collision_data) constexpr { return path_search_continue::pass; };
constexpr auto always_continue_ = path_search::pred{always_continue_1};
+
+constexpr Pair<Vector2i, Vector2i> get_value(Vector2i sz, Vector2ub div, rotation r)
+{
+ fm_debug_assert(div == Vector2ub{div});
+
+ constexpr auto half_tile = iTILE_SIZE2/2;
+ constexpr int offset_W = iTILE_SIZE2.x(), offset_N = iTILE_SIZE2.y();
+
+ const auto r_ = (uint8_t)r;
+ CORRADE_ASSUME(r_ <= (uint8_t)rotation_COUNT);
+
+ switch (r_)
+ {
+ case (uint8_t)rotation::N: {
+ const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1;
+ auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N );
+ auto max_N = Vector2i(min_N.x() + sz.x(), 0 );
+ return {min_N, max_N};
+ }
+ case (uint8_t)rotation::S: {
+ const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1;
+ auto min_S = Vector2i(-half_tile.x() + space_NS, 0 );
+ auto max_S = Vector2i(min_S.x() + sz.x(), offset_N );
+ return {min_S, max_S};
+ }
+ case (uint8_t)rotation::W: {
+ const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1;
+ auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE );
+ auto max_W = Vector2i(0, min_W.y() + sz.y() );
+ return {min_W, max_W};
+ }
+ case (uint8_t)rotation::E: {
+ const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1;
+ auto min_E = Vector2i(0, -half_tile.y() + 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(-(sz.x() >> 1), -(sz.y() >> 1) );
+ auto max_C = min_C + sz;
+ return {min_C, max_C};
+ }
+ default:
+ fm_abort("wrong 4-way rotation enum '%d'", (int)r);
+ }
+};
+
+constexpr Vector2i tile_subdiv_at(Vector2i subdiv)
+{
+ constexpr auto tile_start_offset = iTILE_SIZE2/-2;
+ constexpr auto shift = iTILE_SIZE2/div;
+ static_assert(shift * div == iTILE_SIZE2);
+ fm_debug_assert(Vector2ui(subdiv) < Vector2ui{(unsigned)div});
+ return tile_start_offset + shift * subdiv;
+};
+
+struct chunk_subdiv_array { Vector2i min[div], max[div]; };
+
+constexpr chunk_subdiv_array make_chunk_subdiv_array()
+{
+ return {};
+}
+
} // namespace
path_search_result::path_search_result() = default;
@@ -117,91 +187,48 @@ bool path_search::is_passable(world& w, global_coords coord, Vector2b offset, Ve
return is_passable(w, coord, min, max, own_id, p);
}
-auto path_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, Vector2ub div, rotation r) -> bbox
{
- constexpr auto get_value = [](Vector2i sz, rotation r) constexpr -> Pair<Vector2i, Vector2i>
- {
- constexpr auto half_tile = iTILE_SIZE2/2;
- constexpr int offset_W = iTILE_SIZE2.x(), offset_N = iTILE_SIZE2.y();
-
- const auto r_ = (uint8_t)r;
- CORRADE_ASSUME(r_ <= (uint8_t)rotation_COUNT);
-
- switch (r_)
- {
- case (uint8_t)rotation::N: {
- const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1;
- auto min_N = Vector2i(-half_tile.x() + space_NS, -offset_N );
- auto max_N = Vector2i(min_N.x() + sz.x(), 0 );
- return {min_N, max_N};
- }
- case (uint8_t)rotation::S: {
- const auto space_NS = iTILE_SIZE2.x() - sz.x() >> 1;
- auto min_S = Vector2i(-half_tile.x() + space_NS, 0 );
- auto max_S = Vector2i(min_S.x() + sz.x(), offset_N );
- return {min_S, max_S};
- }
- case (uint8_t)rotation::W: {
- const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1;
- auto min_W = Vector2i(-offset_W, -half_tile.y() + space_WE );
- auto max_W = Vector2i(0, min_W.y() + sz.y() );
- return {min_W, max_W};
- }
- case (uint8_t)rotation::E: {
- const auto space_WE = iTILE_SIZE2.y() - sz.y() >> 1;
- auto min_E = Vector2i(0, -half_tile.y() + 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(-(sz.x() >> 1), -(sz.y() >> 1) );
- auto max_C = min_C + sz;
- return {min_C, max_C};
- }
- default:
- fm_abort("wrong 4-way rotation enum '%d'", (int)r);
- }
- };
-
constexpr auto min_size = iTILE_SIZE2*1/4;
static_assert(min_size.x() % 2 == 0);
+ static_assert(min_size.x() >= subdivide_factor && min_size.y() >= subdivide_factor);
#if 1
- if constexpr(true)
+ if constexpr(std::is_constant_evaluated())
{
constexpr auto sz_ = min_size;
constexpr Vector2i shift = Vector2i(0, 0) * iTILE_SIZE2 + Vector2i(0, 0);
{
- constexpr auto N = get_value(sz_, rotation::N);
+ constexpr auto N = get_value(sz_, {1,1}, 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(); }
+ { [[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(sz_, rotation::E);
+ constexpr auto E = get_value(sz_, {1,1}, 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(); }
+ { [[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(sz_, rotation::S);
+ constexpr auto S = get_value(sz_, {1,1}, 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(); }
+ { [[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(sz_, rotation::W);
+ constexpr auto W = get_value(sz_, {1,1}, 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(); }
+ { [[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
const auto shift = coord * iTILE_SIZE2;
auto sz = Math::max(Vector2i(own_size), min_size);
- auto [min, max] = get_value(sz, r);
+ auto [min, max] = get_value(sz, div, r);
return { Vector2(min + shift), Vector2(max + shift) };
}
@@ -231,7 +258,7 @@ auto path_search::get_walkable_neighbor_tiles(world& w, global_coords coord, Vec
for (auto [off, dir] : nbs)
{
- auto [min, max] = make_neighbor_tile_bbox(pos, size, dir);
+ auto [min, max] = make_neighbor_tile_bbox(pos, size, {1,1}, dir);
if (is_passable(w, ch, min, max, own_id, p))
ns.neighbors[ns.size++] = coord + off;
}
@@ -268,8 +295,8 @@ void path_search::fill_cache_(world& w, chunk_coords_ coord, Vector2ub own_size,
for (auto i = 0uz; i < TILE_COUNT; i++)
{
auto pos = Vector2i(local_coords{i});
- auto bb_N = make_neighbor_tile_bbox(pos, own_size, rotation::N),
- bb_W = make_neighbor_tile_bbox(pos, own_size, rotation::W);
+ auto bb_N = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::N),
+ bb_W = make_neighbor_tile_bbox(pos, own_size, {1,1}, rotation::W);
bool b_N = is_passable_(c, nb, bb_N.min, bb_N.max, own_id, p),
b_W = is_passable_(c, nb, bb_W.min, bb_W.max, own_id, p);
bits.can_go_north[i] = b_N;
diff --git a/src/path-search.hpp b/src/path-search.hpp
index bb72d87e..92d113cf 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -52,6 +52,13 @@ enum class path_search_continue : bool { pass = false, blocked = true };
class path_search final
{
+ // todo bucketize by array length
+ path_search_result* pool = nullptr;
+
+public:
+ static constexpr int subdivide_factor = 4;
+ static constexpr size_t tile_count = Vector2i(subdivide_factor * TILE_MAX_DIM).product();
+
struct neighbors final
{
auto begin() const { return neighbors.data(); }
@@ -63,7 +70,7 @@ class path_search final
struct chunk_tiles_cache
{
- std::bitset<TILE_COUNT> can_go_north{true}, can_go_west{true};
+ std::bitset<tile_count> can_go_north{true}, can_go_west{true};
};
struct chunk_cache
@@ -74,10 +81,6 @@ class path_search final
struct obj_position { Vector2 center, size; };
- // todo bucketize by array length
- path_search_result* pool = nullptr;
-
-public:
chunk_cache cache;
Array<global_coords> output;
@@ -102,7 +105,7 @@ public:
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 bbox make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, rotation r);
+ static bbox make_neighbor_tile_bbox(Vector2i coord, Vector2ub own_size, Vector2ub div, rotation r);
static bbox bbox_union(bbox bb, Vector2i coord, Vector2b offset, Vector2ub size);
static neighbors get_walkable_neighbor_tiles(world& w, global_coords coord, Vector2ub size, object_id own_id, const pred& p = never_continue());
};