Tag set 的数据结构优化
在最近实现的 ECS 库中，Tag 是一种非常重要的数据结构。它是一类特殊的 Component ，不携带数据，但会关联到同一 Entity ，最重要的用途是用于筛选。我在设计 Comonent 的数据结构时，采用了一种简单的数据结构 。它采用连续内存储存的数组，按 Entity id 有序排列。并在查询算法上做了一些优化，可以使得大部分查询时间小于 Log(N)，接近常量时间。
但是，这样做的代价是插入和删除操作都是 O(n) 的。为了避免大量的插入删除操作堆积在一起时，整体的时间复杂度变成 O(n^2) ，我禁止 Component 的删除，而删除 Entity 改为标记，待一帧结束后一起删除。这样，可以让批量删除保持在 O(n) 的复杂度。
标记操作实质上就是打 Tag 。Tag 作为一种特殊的 Component 就需要支持动态的增删（Enable/Disable) 。
好在 Tag 不携带数据，我找到一种方法可以针对这种数据结构，让平均复杂度优于 O(n) 。
因为 Tag 本质上储存的就是有序的 Entity id 数组。例如，当有 5 个 entity 1,3,5,7,9 被打上特定 tag 时，就是有这么一个长度为 5 的 id 数组，{ 1,3,5,7,9 } 。
如果我们需要 disable 5 ，传统方法就是从数组中删除 5 这一项，变成 { 1,3,7,9 } 。这个算法的复杂度是 O(n) 的，查找到 5 的比较次数为 Log(n) ，平均移动的数据为 n/2 项。
但，考虑到这个数组仅用于确定一个 id 是否存在，以及遍历这些 id 。我们可以做这样的优化：当需要删除 5 时，并不移动 5 后面的 id ，而是复制它前面或后面临近的 id 。即，把数组变成 { 1,3,3,7,9 } 或 { 1,3,7,7,9 } 。这样，删除操作就是 O(log N) 了。同时，也没有给遍历增加太多的负担。我们可以在遍历的同时，重新整理这个数组，去掉重复项。
另外，当数组集合经过若干次删除后，出现了重复 id ，之后的增加 (Enable) 新的 id 时，插入操作需要移动的条目也会相对减少。
Comments
用一个额外的标志位标记 disable 状态也可以。但我认为会略微增加查找的负担。而查找的频率是超过 enable/disable 的。
而且 tag 和普通的 component 是一致的数据结构。增加标记位的做法会影响到其它 component 的处理逻辑。
Posted by: Cloud | (11) July 30, 2021 12:43 PM
https://github.com/cloudwu/luaecs/blob/master/luaecs.c#L303-L334
可以参考 entity_disable_tag_ 函数的实现。
Posted by: Cloud | (10) July 30, 2021 09:57 AM
有效ID都用奇数，删除就ID+1，遍历处理时候跳过奇数。
Posted by: Anonymous | (9) July 29, 2021 11:50 PM
再添加个一样的数组标示是否有效可以么？
Posted by: Anonymous | (8) July 29, 2021 11:46 PM
如果删除 5，我变成 1 3 7 7 9，接下来要删除 7 怎么处理好呢？
Posted by: 菜鸟浮出水 | (7) July 29, 2021 11:16 AM
这种思路我记得在其他地方见到过，选好数组清理的阈值效果就很可以接受
Posted by: 土豆太大 | (6) July 28, 2021 06:03 PM
这想法有点巧妙. 虽然通常用-1会更简单一些, 也许怕-1会真的被分配出来用, 但再分配就会出现回绕了, 已经说明32位id不够用, 64位的话-1就很保险了.
Posted by: dwing | (5) July 28, 2021 11:52 AM
设置成 INVALID (-1) 会破坏后面的二分查找.
Posted by: Cloud | (4) July 28, 2021 10:57 AM
直接置 -1 也行啊.
当然, 如果不要求有序, 直接和最后一个元素调换, 然后置 -1 最高效.
Posted by: fenghou | (3) July 28, 2021 09:07 AM
id 唯一的时候，通过把元素变成临近元素的方式来删除，好神奇，头次见，有没有其他文献参考？
Posted by: hanxi | (2) July 28, 2021 01:29 AM
风哥威武
Posted by: Luo | (1) July 27, 2021 08:33 PM