summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
-rw-r--r--editor/tests/region-test.cpp165
-rw-r--r--src/chunk-region.cpp179
-rw-r--r--src/chunk-region.hpp13
-rw-r--r--src/chunk.cpp8
-rw-r--r--src/chunk.hpp24
-rw-r--r--src/object.cpp4
-rw-r--r--src/path-search.hpp7
7 files changed, 238 insertions, 162 deletions
diff --git a/editor/tests/region-test.cpp b/editor/tests/region-test.cpp
index 6c0fea07..db890560 100644
--- a/editor/tests/region-test.cpp
+++ b/editor/tests/region-test.cpp
@@ -1,6 +1,6 @@
#include "../tests-private.hpp"
#include "src/tile-constants.hpp"
-#include "src/chunk.hpp"
+#include "src/chunk-region.hpp"
#include "src/path-search-bbox.hpp"
#include "src/object.hpp"
#include "src/world.hpp"
@@ -8,8 +8,6 @@
#include "../imgui-raii.hpp"
#include "floormat/main.hpp"
#include <bitset>
-#include <Corrade/Containers/Pointer.h>
-#include <Corrade/Containers/GrowableArray.h>
#include <Magnum/Math/Vector2.h>
#include <Magnum/Math/Functions.h>
#include <Magnum/Math/Color.h>
@@ -19,49 +17,13 @@ namespace floormat::tests {
namespace {
using namespace floormat::imgui;
+using detail_astar::div_count;
using detail_astar::div_factor;
using detail_astar::div_size;
using detail_astar::bbox;
-static_assert((iTILE_SIZE2 % div_size).isZero());
-constexpr auto div_count = iTILE_SIZE2 * TILE_MAX_DIM / div_size;
-constexpr auto chunk_bits = div_count.product(),
- visited_bits = div_count.product()*4*4;
-constexpr auto div_min = -iTILE_SIZE2/2 + div_size/2,
- div_max = iTILE_SIZE2 * TILE_MAX_DIM - iTILE_SIZE2/2 - div_size + div_size/2;
-static_assert(div_count.x() == div_count.y());
-
-constexpr bbox<Int> bbox_from_pos1(Vector2i center)
-{
- constexpr auto half = div_size/2;
- auto start = center - half;
- return { start, start + div_size };
-}
-
-constexpr bbox<Int> bbox_from_pos2(Vector2i pt, Vector2i from/*, Vector2ui size*/) // from src/dijkstra.cpp
-{
- auto bb0 = bbox_from_pos1(from/*, size*/);
- auto bb = bbox_from_pos1(pt/*, size*/);
- auto min = Math::min(bb0.min, bb.min);
- auto max = Math::max(bb0.max, bb.max);
- return { min, max };
-}
-
-constexpr bbox<Int> make_pos(Vector2i ij, Vector2i from)
-{
- auto pos = div_min + div_size * ij;
- auto pos0 = pos + from*div_size;
- return bbox_from_pos2(pos, pos0/*, Vector2ui(div_size)*/);
-}
-
-bool check_pos(chunk& c, const std::array<chunk*, 8>& nbs, Vector2i ij, Vector2i from)
-{
- auto pos = make_pos(ij, from);
- bool ret = path_search::is_passable_(&c, nbs, Vector2(pos.min), Vector2(pos.max), 0);
- //if (ret) Debug{} << "check" << ij << ij/div_factor << ij % div_factor << pos.min << pos.max << ret;
- //Debug{} << "check" << ij << pos.min << pos.max << ret;
- return ret;
-}
+constexpr auto chunk_bits = div_count.product();
+constexpr auto div_min = -iTILE_SIZE2/2 + div_size/2;
struct pending_s
{
@@ -76,54 +38,6 @@ struct result_s
bool exists : 1 = false;
};
-struct node_s
-{
- Vector2i pos;
-};
-
-struct tmp_s
-{
- Array<node_s> stack;
- std::bitset<visited_bits> visited;
- std::bitset<chunk_bits> passable;
-
- void append(Vector2i pos, int from);
- static Pointer<tmp_s> make();
- void clear();
-};
-
-void tmp_s::append(Vector2i pos, int from)
-{
- auto i = (uint32_t)pos.y() * (uint32_t)div_count.x() + (uint32_t)pos.x();
- fm_debug_assert(i < passable.size());
- if (passable[i])
- return;
- passable[i] = true;
- auto v = i*4 + (uint32_t)from;
- fm_debug_assert(v < visited.size());
- if (visited[v])
- return;
- visited[v] = true;
- arrayAppend(stack, {pos});
-}
-
-Pointer<tmp_s> tmp_s::make()
-{
- auto ptr = Pointer<tmp_s>{InPlace};
- arrayResize(ptr->stack, 0);
- arrayReserve(ptr->stack, TILE_COUNT);
- ptr->visited = {};
- ptr->passable = {};
- return ptr;
-}
-
-void tmp_s::clear()
-{
- arrayResize(stack, 0);
- visited = {};
- passable = {};
-}
-
void do_column(StringView name)
{
ImGui::TableNextRow();
@@ -136,11 +50,8 @@ struct region_test : base_test
{
result_s result;
pending_s pending;
- Pointer<tmp_s> tmp;
- tmp_s& get_tmp();
void do_region_extraction(world& w, chunk_coords_ coord);
-
~region_test() noexcept override = default;
bool handle_key(app&, const key_event&, bool) override { return {}; }
@@ -152,61 +63,6 @@ struct region_test : base_test
void update_post(app& a) override;
};
-tmp_s& region_test::get_tmp()
-{
- if (tmp)
- tmp->clear();
- else
- tmp = tmp_s::make();
- return *tmp;
-}
-
-void region_test::do_region_extraction(world& w, chunk_coords_ coord)
-{
- auto* c = w.at(coord);
- if (!c)
- {
- result.exists = false;
- pending.exists = false;
- return;
- }
-
- auto& tmp = get_tmp();
- const auto nbs = w.neighbors(coord);
-
- constexpr Vector2i fours[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
- constexpr auto last = div_count - Vector2i{1};
- //if (Vector2i pos{0, 0}; check_pos(*c, nbs, pos, fours[1])) tmp.append(pos, 1); // top
-
- for (Int i = 0; i < div_count.x(); i++)
- {
- if (Vector2i pos{i, last.y()}; check_pos(*c, nbs, pos, fours[0])) tmp.append(pos, 0); // bottom
- if (Vector2i pos{i, 0}; check_pos(*c, nbs, pos, fours[1])) tmp.append(pos, 1); // top
- if (Vector2i pos{last.x(), i}; check_pos(*c, nbs, pos, fours[2])) tmp.append(pos, 2); // right
- if (Vector2i pos{0, i}; check_pos(*c, nbs, pos, fours[3])) tmp.append(pos, 3); // left
- }
-
- while (!tmp.stack.isEmpty())
- {
- auto p = tmp.stack.back().pos;
- arrayRemoveSuffix(tmp.stack);
- for (int i = 0; i < 4; i++)
- {
- Vector2i from = fours[i], pos{p - from};
- if ((uint32_t)pos.x() >= div_count.x() || (uint32_t)pos.y() >= div_count.y()) [[unlikely]]
- continue;
- if (check_pos(*c, nbs, pos, from))
- tmp.append(pos, i);
- }
- }
-
- result = {
- .is_passable = tmp.passable,
- .c = coord,
- .exists = true,
- };
-}
-
void region_test::draw_overlay(app& a)
{
if (result.exists)
@@ -269,8 +125,6 @@ bool region_test::handle_mouse_click(app& a, const mouse_button_event& e, bool i
{
if (e.button == mouse_button_left && is_down)
{
- auto& M = a.main();
- auto& w = M.world();
if (auto pt_ = a.cursor_state().point())
{
pending = {
@@ -299,6 +153,17 @@ void region_test::update_post(app& a)
}
}
+void region_test::do_region_extraction(world& w, chunk_coords_ coord)
+{
+ if (auto* c = w.at(coord))
+ {
+ chunk::pass_region r;
+ c->make_pass_region(r);
+ result.is_passable = r.bits;
+ result.exists = true;
+ }
+}
+
} // namespace
Pointer<base_test> tests_data::make_test_region() { return Pointer<region_test>{InPlaceInit}; }
diff --git a/src/chunk-region.cpp b/src/chunk-region.cpp
new file mode 100644
index 00000000..2c290dee
--- /dev/null
+++ b/src/chunk-region.cpp
@@ -0,0 +1,179 @@
+#include "chunk-region.hpp"
+#include "path-search-bbox.hpp"
+#include "world.hpp"
+#include <Corrade/Containers/GrowableArray.h>
+#include <Magnum/Math/Functions.h>
+
+namespace floormat {
+
+namespace {
+
+using detail_astar::bbox;
+using detail_astar::div_factor;
+using detail_astar::div_size;
+using detail_astar::div_count;
+
+static_assert(div_count.x() == div_count.y());
+static_assert((iTILE_SIZE2 % div_size).isZero());
+
+constexpr auto chunk_bits = div_count.product(),
+ visited_bits = div_count.product()*4*4;
+constexpr auto div_min = -iTILE_SIZE2/2 + div_size/2,
+ div_max = iTILE_SIZE2 * TILE_MAX_DIM - iTILE_SIZE2/2 - div_size + div_size/2;
+
+constexpr bbox<Int> bbox_from_pos1(Vector2i center)
+{
+ constexpr auto half = div_size/2;
+ auto start = center - half;
+ return { start, start + div_size };
+}
+
+constexpr bbox<Int> bbox_from_pos2(Vector2i pt, Vector2i from)
+{
+ auto bb0 = bbox_from_pos1(from);
+ auto bb = bbox_from_pos1(pt);
+ auto min = Math::min(bb0.min, bb.min);
+ auto max = Math::max(bb0.max, bb.max);
+ return { min, max };
+}
+
+constexpr bbox<Int> make_pos(Vector2i ij, Vector2i from)
+{
+ auto pos = div_min + div_size * ij;
+ auto pos0 = pos + from*div_size;
+ return bbox_from_pos2(pos, pos0);
+}
+
+bool check_pos(chunk& c, const std::array<chunk*, 8>& nbs, Vector2i ij, Vector2i from)
+{
+ auto pos = make_pos(ij, from);
+ bool ret = path_search::is_passable_(&c, nbs, Vector2(pos.min), Vector2(pos.max), 0);
+ //if (ret) Debug{} << "check" << ij << ij/div_factor << ij % div_factor << pos.min << pos.max << ret;
+ //Debug{} << "check" << ij << pos.min << pos.max << ret;
+ return ret;
+}
+
+struct node_s
+{
+ Vector2i pos;
+};
+
+struct tmp_s
+{
+ Array<node_s> stack;
+ std::bitset<visited_bits> visited;
+
+ static uint32_t get_index(Vector2i pos);
+ void append(std::bitset<chunk_bits>& passable, Vector2i pos);
+ [[nodiscard]] bool check_visited(std::bitset<chunk_bits>& passable, Vector2i pos, int from);
+ void clear();
+};
+
+uint32_t tmp_s::get_index(Vector2i pos)
+{
+ return (uint32_t)pos.y() * (uint32_t)div_count.x() + (uint32_t)pos.x();
+}
+
+void tmp_s::append(std::bitset<chunk_bits>& passable, Vector2i pos)
+{
+ auto i = get_index(pos);
+ passable[i] = true;
+ arrayAppend(stack, {pos});
+}
+
+bool tmp_s::check_visited(std::bitset<chunk_bits>& passable, Vector2i pos, int from)
+{
+ auto i = get_index(pos);
+ //fm_debug_assert(i < passable.size());
+ if (passable[i])
+ return {};
+ auto v = i*4 + (uint32_t)from;
+ //fm_debug_assert(v < visited.size());
+ if (visited[v])
+ return {};
+ visited[v] = true;
+ return true;
+}
+
+void tmp_s::clear()
+{
+ arrayResize(stack, 0);
+ visited = {};
+}
+
+tmp_s& get_tmp()
+{
+ static Pointer<tmp_s> tmp = [] {
+ Pointer<tmp_s> p{InPlace};
+ arrayReserve(p->stack, 4*div_count.product());
+ return p;
+ }();
+ arrayResize(tmp->stack, 0);
+ tmp->visited = {};
+ return *tmp;
+}
+
+} // namespace
+
+void chunk::delete_pass_region(pass_region*& ptr)
+{
+ if (ptr)
+ {
+ delete ptr;
+ ptr = nullptr;
+ }
+}
+
+auto chunk::get_pass_region() -> const pass_region*
+{
+ if (!_region_modified)
+ {
+ fm_debug_assert(_region != nullptr);
+ return _region;
+ }
+
+ if (!_region)
+ _region = new pass_region;
+ else
+ _region->bits = {};
+
+ make_pass_region(*_region);
+ return _region;
+}
+
+bool chunk::is_region_modified() const noexcept { return _region_modified; }
+void chunk::mark_region_modified() noexcept { _region_modified = true; }
+
+void chunk::make_pass_region(pass_region& ret)
+{
+ auto& tmp = get_tmp();
+ const auto nbs = _world->neighbors(_coord);
+
+ constexpr Vector2i fours[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
+ constexpr auto last = div_count - Vector2i{1};
+ //if (Vector2i pos{0, 0}; check_pos(*c, nbs, pos, fours[1])) tmp.append(pos, 1); // top
+
+ for (int i = 0; i < div_count.x(); i++)
+ {
+ if (Vector2i pos{i, last.y()}; check_pos(*this, nbs, pos, fours[0])) tmp.append(ret.bits, pos); // bottom
+ if (Vector2i pos{i, 0}; check_pos(*this, nbs, pos, fours[1])) tmp.append(ret.bits, pos); // top
+ if (Vector2i pos{last.x(), i}; check_pos(*this, nbs, pos, fours[2])) tmp.append(ret.bits, pos); // right
+ if (Vector2i pos{0, i}; check_pos(*this, nbs, pos, fours[3])) tmp.append(ret.bits, pos); // left
+ }
+
+ while (!tmp.stack.isEmpty())
+ {
+ auto p = tmp.stack.back().pos;
+ arrayRemoveSuffix(tmp.stack);
+ for (int i = 0; i < 4; i++)
+ {
+ Vector2i from = fours[i], pos{p - from};
+ if ((uint32_t)pos.x() >= div_count.x() || (uint32_t)pos.y() >= div_count.y()) [[unlikely]]
+ continue;
+ if (tmp.check_visited(ret.bits, pos, i) && check_pos(*this, nbs, pos, from))
+ tmp.append(ret.bits, pos);
+ }
+ }
+}
+
+} // namespace floormat
diff --git a/src/chunk-region.hpp b/src/chunk-region.hpp
new file mode 100644
index 00000000..5720e93e
--- /dev/null
+++ b/src/chunk-region.hpp
@@ -0,0 +1,13 @@
+#pragma once
+#include "chunk.hpp"
+#include "path-search.hpp"
+#include <bitset>
+
+namespace floormat {
+
+struct chunk::pass_region
+{
+ std::bitset<detail_astar::div_count.product()> bits;
+};
+
+} // namespace floormat
diff --git a/src/chunk.cpp b/src/chunk.cpp
index 4963a9e7..1a727599 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -152,6 +152,7 @@ chunk::~chunk() noexcept
arrayResize(_objects, 0);
arrayShrink(_objects);
_rtree->RemoveAll();
+ delete_pass_region(_region);
}
chunk::chunk(chunk&&) noexcept = default;
@@ -162,10 +163,12 @@ bool chunk::bbox::operator==(const bbox& other) const noexcept = default;
void chunk::add_object_unsorted(const std::shared_ptr<object>& e)
{
_objects_sorted = false;
+ _region_modified = true;
if (!e->is_dynamic())
mark_scenery_modified();
if (bbox bb; _bbox_for_scenery(*e, bb))
_add_bbox(bb);
+ arrayReserve(_objects, 8);
arrayAppend(_objects, e);
}
@@ -173,10 +176,8 @@ void chunk::sort_objects()
{
if (_objects_sorted)
return;
-
_objects_sorted = true;
mark_scenery_modified();
-
std::sort(_objects.begin(), _objects.end(), [](const auto& a, const auto& b) {
return a->id < b->id;
});
@@ -185,10 +186,12 @@ void chunk::sort_objects()
void chunk::add_object(const std::shared_ptr<object>& e)
{
fm_assert(_objects_sorted);
+ _region_modified = true;
if (!e->is_dynamic())
mark_scenery_modified();
if (bbox bb; _bbox_for_scenery(*e, bb))
_add_bbox(bb);
+ arrayReserve(_objects, 8);
auto& es = _objects;
auto it = std::lower_bound(es.cbegin(), es.cend(), e, object_id_lessp);
arrayInsert(es, (size_t)std::distance(es.cbegin(), it), e);
@@ -197,6 +200,7 @@ void chunk::add_object(const std::shared_ptr<object>& e)
void chunk::remove_object(size_t i)
{
fm_assert(_objects_sorted);
+ _region_modified = true;
auto& es = _objects;
fm_debug_assert(i < es.size());
const auto e = es[i];
diff --git a/src/chunk.hpp b/src/chunk.hpp
index 3e142abf..5404d25b 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -27,6 +27,7 @@ public:
friend struct tile_ref;
friend struct object;
friend class world;
+ struct pass_region;
tile_ref operator[](size_t idx) noexcept;
tile_proto operator[](size_t idx) const noexcept;
@@ -62,10 +63,12 @@ public:
void mark_walls_modified() noexcept;
void mark_scenery_modified() noexcept;
void mark_passability_modified() noexcept;
+ void mark_region_modified() noexcept;
void mark_modified() noexcept;
bool is_passability_modified() const noexcept;
bool is_scenery_modified() const noexcept;
+ bool is_region_modified() const noexcept;
struct ground_mesh_tuple final {
GL::Mesh& mesh;
@@ -116,6 +119,9 @@ public:
static constexpr size_t max_wall_quad_count =
TILE_COUNT*Wall::Direction_COUNT*(Wall::Group_COUNT+4);
+ const pass_region* get_pass_region();
+ void make_pass_region(pass_region& ret);
+
private:
struct ground_stuff
{
@@ -133,23 +139,27 @@ private:
Pointer<ground_stuff> _ground;
Pointer<wall_stuff> _walls;
+ pass_region* _region = nullptr;
Array<std::shared_ptr<object>> _objects;
class world* _world;
GL::Mesh ground_mesh{NoCreate}, wall_mesh{NoCreate}, scenery_mesh{NoCreate};
Pointer<RTree> _rtree;
chunk_coords_ _coord;
- mutable bool _maybe_empty : 1 = true,
- _ground_modified : 1 = true,
- _walls_modified : 1 = true,
- _scenery_modified : 1 = true,
- _pass_modified : 1 = true,
- _teardown : 1 = false,
- _objects_sorted : 1 = true;
+ mutable bool _maybe_empty : 1 = true,
+ _ground_modified : 1 = true,
+ _walls_modified : 1 = true,
+ _scenery_modified : 1 = true,
+ _pass_modified : 1 = true,
+ _region_modified : 1 = true,
+ _teardown : 1 = false,
+ _objects_sorted : 1 = true;
void ensure_scenery_buffers(scenery_scratch_buffers bufs);
static topo_sort_data make_topo_sort_data(object& e, uint32_t mesh_idx);
+ static void delete_pass_region(pass_region*& ptr);
+
struct bbox final // NOLINT(cppcoreguidelines-pro-type-member-init)
{
object_id id;
diff --git a/src/object.cpp b/src/object.cpp
index 52244121..34659aa5 100644
--- a/src/object.cpp
+++ b/src/object.cpp
@@ -72,6 +72,7 @@ object::~object() noexcept
if (chunk::bbox bb; c->_bbox_for_scenery(*this, bb))
c->_remove_bbox(bb);
c->_world->do_kill_object(id);
+ c->mark_region_modified();
const_cast<object_id&>(id) = 0;
}
@@ -244,6 +245,7 @@ void object::move_to(size_t& i, Vector2i delta, rotation new_r)
if (coord_.chunk() == coord.chunk())
{
c->_replace_bbox(bb0, bb1, b0, b1);
+ c->mark_region_modified();
const_cast<global_coords&>(coord) = coord_;
set_bbox_(offset_, bb_offset, bb_size, pass);
const_cast<rotation&>(r) = new_r;
@@ -255,6 +257,7 @@ void object::move_to(size_t& i, Vector2i delta, rotation new_r)
c2.mark_scenery_modified();
c2._add_bbox(bb1);
c->remove_object(i);
+ c->mark_region_modified();
auto& es = c2._objects;
auto it = std::lower_bound(es.cbegin(), es.cend(), e_, object_id_lessp);
const_cast<global_coords&>(coord) = coord_;
@@ -306,6 +309,7 @@ void object::set_bbox(Vector2b offset_, Vector2b bb_offset_, Vector2ub bb_size_,
set_bbox_(offset_, bb_offset_, bb_size_, pass);
const bool b = c->_bbox_for_scenery(*this, bb);
c->_replace_bbox(bb0, bb, b0, b);
+ c->mark_region_modified();
}
bool object::can_activate(size_t) const { return false; }
diff --git a/src/path-search.hpp b/src/path-search.hpp
index c48b5532..daf3379d 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -20,9 +20,10 @@ namespace floormat::detail_astar {
template<typename T> struct bbox;
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);
+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