work on entity reodering

8 files changed, 129 insertions, 56 deletions

diff --git a/src/character.cpp b/src/character.cpp
index 110d2031..10ef4a34 100644
--- a/src/character.cpp
+++ b/src/character.cpp
@@ -96,26 +96,36 @@ void character::set_keys(bool L, bool R, bool U, bool D)
     b_D = D;
 }
 
-bool character::update(size_t i, float dt)
+Vector2 character::ordinal_offset(Vector2b offset) const
+{
+    return Vector2(offset);
+}
+
+entity_update_status character::update(size_t i, float dt)
 {
     auto [lr, ud, new_r] = arrows_to_dir(b_L, b_R, b_U, b_D);
 
     if (!lr & !ud)
     {
         delta = 0;
-        return false;
+        return entity_update_status::not_updated;
     }
 
     int nframes = allocate_frame_time(dt);
 
-    rotate(i, new_r);
-
-    if (!nframes)
-        return false;
+    if (nframes == 0)
+    {
+        if (r == new_r) [[unlikely]]
+            return entity_update_status::not_updated;
+        rotate(i, new_r);
+        return entity_update_status::updated;
+    }
 
     const auto vec = move_vec(lr, ud);
     c->ensure_passability();
 
+    entity_update_status ret = entity_update_status::updated;
+
     for (int k = 0; k < nframes; k++)
     {
         constexpr auto frac = Vector2(32767);
@@ -123,12 +133,22 @@ bool character::update(size_t i, float dt)
         auto offset_ = vec + Vector2(offset_frac) * inv_frac;
         offset_frac = Vector2s(Vector2(std::fmod(offset_[0], 1.f), std::fmod(offset_[1], 1.f)) * frac);
         auto off_i = Vector2i(offset_);
+        const auto old_i = i;
         if (can_move_to(off_i))
+        {
             i = move_to(i, off_i, new_r);
+            if (i != old_i)
+            {
+                //Debug{} << "move_to repositioned" << i;
+                ret = entity_update_status::updated_repositioned;
+            }
+        }
+        else
+            break;
         ++frame %= atlas->info().nframes;
     }
     //Debug{} << "pos" << Vector2i(pos.local());
-    return true;
+    return ret;
 }
 
 entity_type character::type() const noexcept { return entity_type::character; }
diff --git a/src/character.hpp b/src/character.hpp
index 24e0e173..17915df7 100644
--- a/src/character.hpp
+++ b/src/character.hpp
@@ -26,8 +26,9 @@ struct character final : entity
     entity_type type() const noexcept override;
     explicit operator character_proto() const;
 
+    entity_update_status update(size_t i, float dt) override;
     void set_keys(bool L, bool R, bool U, bool D);
-    bool update(size_t i, float dt) override;
+    Vector2 ordinal_offset(Vector2b offset) const override;
 
     String name;
     Vector2s offset_frac;
diff --git a/src/entity.cpp b/src/entity.cpp
index 8822326e..766b0093 100644
--- a/src/entity.cpp
+++ b/src/entity.cpp
@@ -4,6 +4,7 @@
 #include "anim-atlas.hpp"
 #include "RTree.hpp"
 #include "compat/exception.hpp"
+#include <cmath>
 #include <algorithm>
 
 namespace floormat {
@@ -39,36 +40,17 @@ entity::~entity() noexcept
     const_cast<object_id&>(id) = 0;
 }
 
-Vector2b entity::ordinal_offset_for_type(entity_type type, Vector2b offset)
-{
-    switch (type)
-    {
-    default:
-        fm_warn_once("unknown entity type '%zu'", size_t(type));
-        [[fallthrough]];
-    case entity_type::scenery:
-        return offset;
-    case entity_type::character:
-        return {};
-    }
-}
-
-float entity_proto::ordinal(local_coords local) const
-{
-    return entity::ordinal(local, offset, type);
-}
-
 float entity::ordinal() const
 {
-    return ordinal(coord.local(), offset, type());
+    return ordinal(coord.local(), offset);
 }
 
-float entity::ordinal(local_coords xy, Vector2b offset, entity_type type)
+float entity::ordinal(local_coords xy, Vector2b offset) const
 {
     constexpr auto inv_tile_size = 1.f/TILE_SIZE2;
     constexpr float width = TILE_MAX_DIM+1;
-    offset = ordinal_offset_for_type(type, offset);
-    auto vec = Vector2(xy) + Vector2(offset)*inv_tile_size;
+    auto offset_ = ordinal_offset(offset);
+    auto vec = Vector2(xy) + offset_*inv_tile_size;
     return vec[1]*width + vec[0];
 }
 
@@ -82,8 +64,15 @@ size_t entity::index() const
     auto& c = chunk();
     auto& es = c._entities;
     auto it = std::lower_bound(es.cbegin(), es.cend(), nullptr, [ord = ordinal()](const auto& a, const auto&) { return a->ordinal() < ord; });
-    fm_assert(it != es.cend());
+    if (it == es.cend())
+        goto slow;
     it = std::find_if(it, es.cend(), [id = id](const auto& x) { return x->id == id; });
+    if (it == es.cend())
+        goto slow;
+    return (size_t)std::distance(es.cbegin(), it);
+slow:
+    fm_warn_once("BUG: wrong entity sort order");
+    it = std::find_if(es.cbegin(), es.cend(), [id = id](const auto& x) { return x->id == id; });
     fm_assert(it != es.cend());
     return (size_t)std::distance(es.cbegin(), it);
 }
@@ -181,26 +170,17 @@ size_t entity::move_to(size_t i, Vector2i delta, rotation new_r)
     const auto bb_size   = rotate_size(bbox_size, r, new_r);
     bool b0 = c->_bbox_for_scenery(*this, bb0),
          b1 = c->_bbox_for_scenery(*this, coord_.local(), offset_, bb_offset, bb_size, bb1);
-    const auto ord = ordinal(coord_.local(), offset_, type());
+    const auto ord = ordinal(coord_.local(), offset_);
 
     if (coord_.chunk() == coord.chunk())
     {
         c->_replace_bbox(bb0, bb1, b0, b1);
-        auto it_ = std::lower_bound(es.cbegin(), es.cend(), e_, [=](const auto& a, const auto&) { return a->ordinal() < ord; });
         const_cast<global_coords&>(coord) = coord_;
         set_bbox_(offset_, bb_offset, bb_size, pass);
         const_cast<rotation&>(r) = new_r;
-        auto pos1 = std::distance(es.cbegin(), it_);
-        if ((size_t)pos1 > i)
-            pos1--;
         //for (auto i = 0_uz; const auto& x : es) fm_debug("%zu %s %f", i++, x->atlas->name().data(), x->ordinal());
-        if ((size_t)pos1 != i)
-        {
-            //fm_debug("insert (%hd;%hd|%hhd;%hhd) %td -> %zu | %f", coord_.chunk().x, coord_.chunk().y, coord_.local().x, coord_.local().y, pos1, es.size(), e.ordinal());
-            es.erase(es.cbegin() + (ptrdiff_t)i);
-            es.insert(es.cbegin() + pos1, std::move(e_));
-        }
-        return size_t(pos1);
+        //fm_debug("insert (%hd;%hd|%hhd;%hhd) %td -> %zu | %f", coord_.chunk().x, coord_.chunk().y, coord_.local().x, coord_.local().y, pos1, es.size(), e.ordinal());
+        return reposition(i);
     }
     else
     {
@@ -265,6 +245,44 @@ bool entity::is_dynamic() const
     return atlas->info().fps > 0;
 }
 
+size_t entity::reposition(size_t i)
+{
+    const auto ord = ordinal();
+    const auto fn = [=](const auto& a, const auto&) { return a->ordinal() < ord; };
+    auto& es = c->_entities;
+    fm_assert(i < es.size());
+    auto e_ = es[i];
+    fm_assert(&*e_ == this);
+    const auto old_it = es.cbegin() + ptrdiff_t(i);
+    if (auto it = std::lower_bound(es.cbegin(), old_it, e_, fn);
+        it != old_it)
+    {
+        auto pos = std::distance(es.cbegin(), it);
+        //Debug{} << "repos: backward to" << std::distance(es.cbegin(), it) << "from" << i;
+        es.erase(old_it);
+        es.insert(es.cbegin() + pos, e_);
+        i = (size_t)pos;
+        goto done;
+    }
+    if (auto it = std::lower_bound(old_it, es.cend(), e_, fn);
+        it != old_it)
+    {
+        --it;
+        auto pos = std::distance(es.cbegin(), it);
+        //Debug{} << "repos: forward to" << std::distance(es.cbegin(), it) << "from" << i;
+        es.erase(old_it);
+        es.insert(es.cbegin() + pos, e_);
+        goto done;
+    }
+
+    //Debug{} << "repos: no need to move" << i;
+    return i;
+done:
+    if (!is_dynamic())
+        c->mark_scenery_modified();
+    return (size_t)i;
+}
+
 entity_type entity::type_of() const noexcept
 {
     return type();
diff --git a/src/entity.hpp b/src/entity.hpp
index d759cbd1..ade975e4 100644
--- a/src/entity.hpp
+++ b/src/entity.hpp
@@ -25,7 +25,6 @@ struct entity_proto
     rotation r       : rotation_BITS  = rotation::N;
     pass_mode pass   : pass_mode_BITS = pass_mode::see_through;
 
-    float ordinal(local_coords coord) const;
     entity_proto& operator=(const entity_proto&);
     entity_proto();
     entity_proto(const entity_proto&);
@@ -36,11 +35,16 @@ struct entity_proto
     entity_type type_of() const noexcept;
 };
 
+enum class entity_update_status : unsigned char {
+    not_updated, updated, updated_repositioned, updated_repositioning,
+};
+
 struct entity
 {
     fm_DECLARE_DELETED_COPY_ASSIGNMENT(entity);
 
     const object_id id = 0;
+    uint64_t last_update = 0;
     struct chunk* const c;
     std::shared_ptr<anim_atlas> atlas;
     const global_coords coord;
@@ -52,9 +56,9 @@ struct entity
 
     virtual ~entity() noexcept;
 
-    static Vector2b ordinal_offset_for_type(entity_type type, Vector2b offset);
+    virtual Vector2 ordinal_offset(Vector2b offset) const = 0;
     float ordinal() const;
-    static float ordinal(local_coords xy, Vector2b offset, entity_type type);
+    float ordinal(local_coords xy, Vector2b offset) const;
     struct chunk& chunk() const;
     size_t index() const;
 
@@ -63,7 +67,7 @@ struct entity
     virtual entity_type type() const noexcept = 0;
     virtual bool can_activate(size_t i) const;
     virtual bool activate(size_t i);
-    virtual bool update(size_t i, float dt) = 0;
+    virtual entity_update_status update(size_t i, float dt) = 0;
     virtual void rotate(size_t i, rotation r);
     virtual bool can_rotate(global_coords coord, rotation new_r, rotation old_r, Vector2b offset, Vector2b bbox_offset, Vector2ub bbox_size);
     virtual bool can_move_to(Vector2i delta, global_coords coord, Vector2b offset, Vector2b bbox_offset, Vector2ub bbox_aize);
@@ -73,6 +77,7 @@ struct entity
     static Pair<global_coords, Vector2b> normalize_coords(global_coords coord, Vector2b cur_offset, Vector2i delta);
 
     bool is_dynamic() const;
+    size_t reposition(size_t i);
     bool can_rotate(rotation new_r);
     bool can_move_to(Vector2i delta);
     size_t move_to(size_t i, Vector2i delta, rotation new_r);
diff --git a/src/scenery.cpp b/src/scenery.cpp
index bfa69142..fe1618af 100644
--- a/src/scenery.cpp
+++ b/src/scenery.cpp
@@ -3,6 +3,7 @@
 #include "chunk.hpp"
 #include "compat/assert.hpp"
 #include "world.hpp"
+#include "src/rotation.inl"
 #include <algorithm>
 
 namespace floormat {
@@ -22,19 +23,19 @@ bool scenery::can_activate(size_t) const
     return atlas && interactive;
 }
 
-bool scenery::update(size_t, float dt)
+entity_update_status scenery::update(size_t, float dt)
 {
     auto& s = *this;
     if (!s.active)
-        return false;
+        return entity_update_status::not_updated;
 
     switch (s.sc_type)
     {
     default:
     case scenery_type::none:
     case scenery_type::generic:
-        return false;
-    case scenery_type::door:
+        return entity_update_status::not_updated;
+    case scenery_type::door: {
         fm_assert(atlas);
         auto& anim = *atlas;
         const auto hz = uint8_t(atlas->info().fps);
@@ -47,10 +48,12 @@ bool scenery::update(size_t, float dt)
         const auto n = (uint8_t)std::clamp(delta_ / frame_time, 0, 255);
         s.delta = (uint16_t)std::clamp(delta_ - frame_time*n, 0, 65535);
         fm_debug_assert(s.delta >= 0);
+        if (n == 0)
+            return entity_update_status::not_updated;
         const int8_t dir = s.closing ? 1 : -1;
         const int fr = s.frame + dir*n;
         s.active = fr > 0 && fr < nframes-1;
-        pass_mode p;
+        pass_mode old_pass = pass, p;
         if (fr <= 0)
             p = pass_mode::pass;
         else if (fr >= nframes-1)
@@ -58,11 +61,32 @@ bool scenery::update(size_t, float dt)
         else
             p = pass_mode::see_through;
         set_bbox(offset, bbox_offset, bbox_size, p);
-        s.frame = (uint16_t)std::clamp(fr, 0, nframes-1);
+        const auto new_frame = (uint16_t)std::clamp(fr, 0, nframes-1);
+        //Debug{} << "frame" << new_frame << nframes-1;
+        s.frame = new_frame;
         if (!s.active)
             s.delta = s.closing = 0;
-        return true;
+        //if ((p == pass_mode::pass) != (old_pass == pass_mode::pass)) Debug{} << "update: need reposition" << (s.frame == 0 ? "-1" : "1");
+        return (p == pass_mode::pass) != (old_pass == pass_mode::pass)
+               ? entity_update_status::updated_repositioning
+               : entity_update_status::updated;
+    }
+    }
+}
+
+Vector2 scenery::ordinal_offset(Vector2b offset) const
+{
+    if (sc_type == scenery_type::door)
+    {
+        constexpr auto vec0 = Vector2b(-iTILE_SIZE2[0], -iTILE_SIZE[1]/2+1);
+        constexpr auto vec1 = Vector2b(0, -iTILE_SIZE[1]/2+1);
+        const auto vec0_ = rotate_point(vec0, rotation::N, r);
+        const auto vec1_ = rotate_point(vec1, rotation::N, r);
+        const auto vec = frame == 0 ? vec0_ : vec1_;
+        return Vector2(offset) + Vector2(vec);
     }
+    else
+        return Vector2(offset);
 }
 
 bool scenery::activate(size_t)
diff --git a/src/scenery.hpp b/src/scenery.hpp
index b52ddded..b21a416e 100644
--- a/src/scenery.hpp
+++ b/src/scenery.hpp
@@ -41,7 +41,8 @@ struct scenery final : entity
     unsigned char closing     : 1 = false;
     unsigned char interactive : 1 = false;
 
-    bool update(size_t i, float dt) override;
+    entity_update_status update(size_t i, float dt) override;
+    Vector2 ordinal_offset(Vector2b offset) const override;
     bool can_activate(size_t i) const override;
     bool activate(size_t i) override;
 
diff --git a/src/world.cpp b/src/world.cpp
index 8c564007..9d669e62 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -21,6 +21,7 @@ world& world::operator=(world&& w) noexcept
         _chunks = std::move(w._chunks);
         _entities = std::move(w._entities);
         _entity_counter = w._entity_counter;
+        _current_frame = w._current_frame;
         w._entity_counter = 0;
 
         for (auto& [id, c] : _chunks)
diff --git a/src/world.hpp b/src/world.hpp
index d269acf6..b057b854 100644
--- a/src/world.hpp
+++ b/src/world.hpp
@@ -33,6 +33,7 @@ private:
     size_t _collect_every = 64;
     std::shared_ptr<char> _unique_id = std::make_shared<char>('A');
     object_id _entity_counter = 0;
+    uint64_t _current_frame = 1; // zero is special for struct entity
     bool _teardown : 1 = false;
 
     explicit world(size_t capacity);
@@ -66,6 +67,8 @@ public:
     static world deserialize(StringView filename);
     void set_collect_threshold(size_t value) { _collect_every = value; }
     size_t collect_threshold() const noexcept { return _collect_every; }
+    auto frame_no() const { return _current_frame; }
+    auto increment_frame_no() { return _current_frame++; }
 
     template<typename T, bool sorted = true, typename... Xs>
     requires requires(chunk& c) {