sort entities by id rather than draw order

10 files changed, 108 insertions, 111 deletions

diff --git a/src/character.cpp b/src/character.cpp
index 10ef4a34..f43c976b 100644
--- a/src/character.cpp
+++ b/src/character.cpp
@@ -101,31 +101,31 @@ Vector2 character::ordinal_offset(Vector2b offset) const
     return Vector2(offset);
 }
 
-entity_update_status character::update(size_t i, float dt)
+bool 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 entity_update_status::not_updated;
+        return false;
     }
 
     int nframes = allocate_frame_time(dt);
 
+    auto coord_ = coord;
+
     if (nframes == 0)
     {
         if (r == new_r) [[unlikely]]
-            return entity_update_status::not_updated;
+            return false;
         rotate(i, new_r);
-        return entity_update_status::updated;
+        return coord.chunk() != coord_.chunk();
     }
 
     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);
@@ -133,22 +133,13 @@ entity_update_status 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 ret;
+    return coord.chunk() != coord_.chunk();
 }
 
 entity_type character::type() const noexcept { return entity_type::character; }
diff --git a/src/character.hpp b/src/character.hpp
index 17915df7..f39b14ae 100644
--- a/src/character.hpp
+++ b/src/character.hpp
@@ -26,7 +26,7 @@ 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;
+    bool update(size_t i, float dt) override;
     void set_keys(bool L, bool R, bool U, bool D);
     Vector2 ordinal_offset(Vector2b offset) const override;
 
diff --git a/src/chunk-collision.cpp b/src/chunk-collision.cpp
index fedfd877..b233a112 100644
--- a/src/chunk-collision.cpp
+++ b/src/chunk-collision.cpp
@@ -152,7 +152,7 @@ void chunk::_replace_bbox(const bbox& x0, const bbox& x1, bool b0, bool b1)
 
 bool chunk::can_place_entity(const entity_proto& proto, local_coords pos)
 {
-    (void)ensure_scenery_mesh();
+    (void)ensure_scenery_mesh({});
 
     const auto center = Vector2(pos)*TILE_SIZE2 + Vector2(proto.offset) + Vector2(proto.bbox_offset),
                min = center - Vector2(proto.bbox_size/2), max = min + Vector2(proto.bbox_size);
diff --git a/src/chunk-render.cpp b/src/chunk-render.cpp
index 7f4761e0..27a0367c 100644
--- a/src/chunk-render.cpp
+++ b/src/chunk-render.cpp
@@ -104,17 +104,55 @@ auto chunk::ensure_wall_mesh() noexcept -> wall_mesh_tuple
     return { wall_mesh, wall_indexes, count };
 }
 
-auto chunk::ensure_scenery_mesh() noexcept -> scenery_mesh_tuple
+void chunk::ensure_scenery_draw_array(Array<draw_entity>& array)
 {
+    const size_t len_ = _entities.size();
+
+    if (len_ <= array.size())
+        return;
+
+    size_t len;
+
+    if (len_ > 1 << 17)
+        len = len_;
+    else
+        len = std::bit_ceil(len_);
+
+    array = Array<draw_entity>{len};
+}
+
+auto chunk::ensure_scenery_mesh(Array<draw_entity>&& array) noexcept -> scenery_mesh_tuple
+{
+    return ensure_scenery_mesh(static_cast<Array<draw_entity>&>(array));
+}
+
+auto chunk::ensure_scenery_mesh(Array<draw_entity>& array) noexcept -> scenery_mesh_tuple
+{
+    constexpr auto entity_ord_lessp = [](const auto& a, const auto& b) {
+      return a.ord < b.ord;
+    };
+
     fm_assert(_entities_sorted);
 
+    const auto size = _entities.size();
+
+    {
+        ensure_scenery_draw_array(array);
+        for (auto i = 0uz; const auto& e : _entities)
+            array[i++] = { e.get(), e->ordinal() };
+        std::sort(array.begin(), array.begin() + size, entity_ord_lessp);
+        //do { Debug{} << "scenery-mesh: sorting" << size; fflush(stdout); } while (false);
+    }
+
+    const auto es = ArrayView<draw_entity>{array, size};
+
     if (_scenery_modified)
     {
         _scenery_modified = false;
 
         const auto count = fm_begin(
             size_t ret = 0;
-            for (const auto& e : _entities)
+            for (const auto& [e, ord] : es)
                 ret += !e->is_dynamic();
             return ret;
         );
@@ -124,7 +162,7 @@ auto chunk::ensure_scenery_mesh() noexcept -> scenery_mesh_tuple
         scenery_vertexes.clear();
         scenery_vertexes.reserve(count);
 
-        for (const auto& e : _entities)
+        for (const auto& [e, ord] : es)
         {
             if (e->atlas->info().fps > 0)
                 continue;
@@ -152,7 +190,10 @@ auto chunk::ensure_scenery_mesh() noexcept -> scenery_mesh_tuple
             .setCount(int32_t(6 * count));
         scenery_mesh = Utility::move(mesh);
     }
-    return { scenery_mesh, };
+
+    fm_assert(!size || es);
+
+    return { scenery_mesh, es, size };
 }
 
 } // namespace floormat
diff --git a/src/chunk.cpp b/src/chunk.cpp
index d660d2c8..2c65ccae 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -8,7 +8,9 @@ namespace floormat {
 
 namespace {
 
-size_t _reload_no_ = 0;
+constexpr auto entity_id_lessp = [](const auto& a, const auto& b) { return a->id < b->id; };
+
+size_t _reload_no_ = 0; // NOLINT
 
 bool is_log_quiet()
 {
@@ -123,7 +125,7 @@ void chunk::sort_entities()
     mark_scenery_modified();
 
     std::sort(_entities.begin(), _entities.end(), [](const auto& a, const auto& b) {
-        return a->ordinal() < b->ordinal();
+        return a->id < b->id;
     });
 }
 
@@ -134,25 +136,23 @@ void chunk::add_entity(const std::shared_ptr<entity>& e)
         mark_scenery_modified();
     if (bbox bb; _bbox_for_scenery(*e, bb))
         _add_bbox(bb);
-
-    _entities.reserve(_entities.size() + 1);
-    auto it = std::lower_bound(_entities.cbegin(), _entities.cend(), e, [ord = e->ordinal()](const auto& a, const auto&) {
-        return a->ordinal() < ord;
-    });
+    auto& es = _entities;
+    es.reserve(es.size() + 1);
+    auto it = std::lower_bound(es.cbegin(), es.cend(), e, entity_id_lessp);
     _entities.insert(it, e);
 }
 
 void chunk::remove_entity(size_t i)
 {
     fm_assert(_entities_sorted);
-    fm_debug_assert(i < _entities.size());
-    const auto& e = _entities[i];
+    auto& es = _entities;
+    fm_debug_assert(i < es.size());
+    const auto& e = es[i];
     if (!e->is_dynamic())
         mark_scenery_modified();
     if (bbox bb; _bbox_for_scenery(*e, bb))
         _remove_bbox(bb);
-
-    _entities.erase(_entities.cbegin() + ptrdiff_t(i));
+    es.erase(es.cbegin() + ptrdiff_t(i));
 }
 
 const std::vector<std::shared_ptr<entity>>& chunk::entities() const
diff --git a/src/chunk.hpp b/src/chunk.hpp
index f279433e..c7183d2c 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -2,6 +2,7 @@
 #include "object-id.hpp"
 #include "tile.hpp"
 #include "tile-iterator.hpp"
+#include <Corrade/Containers/Array.h>
 #include <type_traits>
 #include <array>
 #include <memory>
@@ -77,9 +78,11 @@ struct chunk final
         const ArrayView<const uint16_t> ids;
         const size_t size;
     };
-
+    struct draw_entity { entity* e; float ord; };
     struct scenery_mesh_tuple final {
         GL::Mesh& mesh;
+        ArrayView<draw_entity> array;
+        size_t size;
     };
 
     struct vertex {
@@ -94,7 +97,8 @@ struct chunk final
     tile_atlas* ground_atlas_at(size_t i) const noexcept;
     wall_mesh_tuple ensure_wall_mesh() noexcept;
     tile_atlas* wall_atlas_at(size_t i) const noexcept;
-    scenery_mesh_tuple ensure_scenery_mesh() noexcept;
+    scenery_mesh_tuple ensure_scenery_mesh(Array<draw_entity>&& array) noexcept;
+    scenery_mesh_tuple ensure_scenery_mesh(Array<draw_entity>& array) noexcept;
 
     void ensure_passability() noexcept;
     RTree* rtree() noexcept;
@@ -125,13 +129,15 @@ private:
 
     RTree _rtree;
 
-    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,
-                 _entities_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,
+                 _teardown              : 1 = false,
+                 _entities_sorted       : 1 = true;
+
+    void ensure_scenery_draw_array(Array<draw_entity>& array);
 
     struct bbox final // NOLINT(cppcoreguidelines-pro-type-member-init)
     {
diff --git a/src/entity.cpp b/src/entity.cpp
index 0d8b246b..971b532d 100644
--- a/src/entity.cpp
+++ b/src/entity.cpp
@@ -9,6 +9,12 @@
 
 namespace floormat {
 
+namespace {
+
+constexpr auto entity_id_lessp = [](const auto& a, const auto& b) { return a->id < b->id; };
+
+} // namespace
+
 bool entity_proto::operator==(const entity_proto&) const = default;
 entity_proto& entity_proto::operator=(const entity_proto&) = default;
 entity_proto::~entity_proto() noexcept = default;
@@ -62,18 +68,11 @@ struct chunk& entity::chunk() const
 size_t entity::index() const
 {
     auto& c = chunk();
+    const auto fn = [id = id](const auto& a, const auto&) { return a->id < id; };
     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; });
-    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; });
+    auto it = std::lower_bound(es.cbegin(), es.cend(), nullptr, fn);
     fm_assert(it != es.cend());
+    fm_assert((*it)->id == id);
     return (size_t)std::distance(es.cbegin(), it);
 }
 
@@ -95,12 +94,14 @@ bool entity::can_rotate(rotation new_r)
 void entity::rotate(size_t, rotation new_r)
 {
     fm_assert(atlas->check_rotation(new_r));
+    // todo normalize coords
     auto offset_ = !is_dynamic() ? rotate_point(offset, r, new_r) : offset; // todo add boolean for this condition
     auto bbox_offset_ = rotate_point(bbox_offset, r, new_r);
     auto bbox_size_ = rotate_size(bbox_size, r, new_r);
     set_bbox(offset_, bbox_offset_, bbox_size_, pass);
     if (r != new_r && !is_dynamic())
         c->mark_scenery_modified();
+
     const_cast<rotation&>(r) = new_r;
 }
 
@@ -160,6 +161,8 @@ size_t entity::move_to(size_t i, Vector2i delta, rotation new_r)
     auto& es = c->_entities;
     fm_debug_assert(i < es.size());
     auto e_ = es[i];
+
+    fm_assert(&*e_ == this);
     auto& w = *c->_world;
     const auto [coord_, offset_] = normalize_coords(coord, offset, delta);
 
@@ -174,7 +177,6 @@ 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_);
 
     if (coord_.chunk() == coord.chunk())
     {
@@ -184,7 +186,7 @@ size_t entity::move_to(size_t i, Vector2i delta, rotation new_r)
         const_cast<rotation&>(r) = new_r;
         //for (auto i = 0_uz; const auto& x : es) fm_debug("%zu %s %f", i++, x->atlas->name().data(), x->ordinal());
         //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);
+        return i;
     }
     else
     {
@@ -195,7 +197,7 @@ size_t entity::move_to(size_t i, Vector2i delta, rotation new_r)
         c2._add_bbox(bb1);
         c->remove_entity(i);
         auto& es = c2._entities;
-        auto it = std::lower_bound(es.cbegin(), es.cend(), e_, [=](const auto& a, const auto&) { return a->ordinal() < ord; });
+        auto it = std::lower_bound(es.cbegin(), es.cend(), e_, entity_id_lessp);
         auto ret = (size_t)std::distance(es.cbegin(), it);
         const_cast<global_coords&>(coord) = coord_;
         set_bbox_(offset_, bb_offset, bb_size, pass);
@@ -231,8 +233,9 @@ entity::operator entity_proto() const
 
 void entity::set_bbox(Vector2b offset_, Vector2b bbox_offset_, Vector2ub bbox_size_, pass_mode pass)
 {
-    if (offset != offset_ && !is_dynamic())
-        c->mark_scenery_modified();
+    if (offset != offset_)
+        if (!is_dynamic())
+            c->mark_scenery_modified();
 
     chunk::bbox bb0, bb;
     const bool b0 = c->_bbox_for_scenery(*this, bb0);
@@ -249,44 +252,6 @@ 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 ade975e4..b8c52f58 100644
--- a/src/entity.hpp
+++ b/src/entity.hpp
@@ -35,10 +35,6 @@ 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);
@@ -67,7 +63,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 entity_update_status update(size_t i, float dt) = 0;
+    virtual bool 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);
@@ -77,10 +73,9 @@ 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);
+    [[nodiscard]] size_t move_to(size_t i, Vector2i delta, rotation new_r);
 
     friend struct world;
 
diff --git a/src/scenery.cpp b/src/scenery.cpp
index fe1618af..3253f623 100644
--- a/src/scenery.cpp
+++ b/src/scenery.cpp
@@ -23,18 +23,18 @@ bool scenery::can_activate(size_t) const
     return atlas && interactive;
 }
 
-entity_update_status scenery::update(size_t, float dt)
+bool scenery::update(size_t, float dt)
 {
     auto& s = *this;
     if (!s.active)
-        return entity_update_status::not_updated;
+        return false;
 
     switch (s.sc_type)
     {
     default:
     case scenery_type::none:
     case scenery_type::generic:
-        return entity_update_status::not_updated;
+        return false;
     case scenery_type::door: {
         fm_assert(atlas);
         auto& anim = *atlas;
@@ -49,11 +49,11 @@ entity_update_status scenery::update(size_t, float dt)
         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;
+            return false;
         const int8_t dir = s.closing ? 1 : -1;
         const int fr = s.frame + dir*n;
         s.active = fr > 0 && fr < nframes-1;
-        pass_mode old_pass = pass, p;
+        pass_mode p;
         if (fr <= 0)
             p = pass_mode::pass;
         else if (fr >= nframes-1)
@@ -67,11 +67,10 @@ entity_update_status scenery::update(size_t, float dt)
         if (!s.active)
             s.delta = s.closing = 0;
         //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;
     }
     }
+
+    return false;
 }
 
 Vector2 scenery::ordinal_offset(Vector2b offset) const
diff --git a/src/scenery.hpp b/src/scenery.hpp
index b21a416e..f7cf3ed7 100644
--- a/src/scenery.hpp
+++ b/src/scenery.hpp
@@ -41,7 +41,7 @@ struct scenery final : entity
     unsigned char closing     : 1 = false;
     unsigned char interactive : 1 = false;
 
-    entity_update_status update(size_t i, float dt) override;
+    bool 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;