ECS: 组 Group

当将 稀疏集 用作 组件池 的时候，通常有以下三个具体部分组成

• 稀疏数组 Sparse Array
  也称为 反向数组 Reverse Array，用于通过 实体 ID 快速找到其在密集数组中的索引
• 密集数组 Packed Array 也称为 直接数组 Direct Array，紧凑存储实际存在的实体，没有空洞，是迭代操作的核心部分，顺序访问速度极快（缓存友好）
• 组件数组 Component Array 存储与实体对应的组件数据，与密集数组按照相同顺序排序，保证索引一致，当密集数组中元素被交换时，组件数组的对应元素也需要同步交换

这种结构有以下优势

• 单组件迭代性能极高（因为密集数组和组件数组内存紧凑，顺序访问时缓存命中率高）
• 随机访问性能也非常好（利用稀疏数组快速定位组件）

但是当需要同时迭代多个 组件 的时候，也就是多个 稀疏集 时，会遇到一些问题

• 稀疏集 之间排序不一致
  每个 稀疏集 可以按自己的顺序对 密集数组 和 组件数组 进行排序，如果多个 稀疏集 的排序不同，在迭代时可能导致缓存未命中，性能受影响
  • 解决方案：可以按某个 参考稀疏集 对其他 稀疏集 进行排序（例如，按 实体 ID 排序），尽管这种排序操作相对高效，但它只能部分缓解问题，不能完全解决排序不一致的问题
• 未知共同实体的数量
  我们无法提前知道有多少 实体 同时拥有多个 组件 我们唯一能确定的是，这个数量不会超过最短密集数组的大小，这种不确定性使得多组件迭代变得复杂
  • 比如，如果组件 A 和组件 B 的 稀疏集 分别有 1000 个和 100 个实体，那么最多有 100 个实体同时拥有 A 和 B，当然，如果短数组 B 的长度远小于长数组，那么性能提升已经非常显著

虽然上述问题都能够解决或被忍受，但是在某些关键路径上，开发者可能需要进一步优化迭代性能，组 Group 就是一种进一步优化的技术

分组 Groups

分组 的核心是将拥有 指定组件 的 实体 紧密排列在 稀疏集 的 密集数组 顶部，并保持这些 组件 按照相同的顺序存储

假设有两个 稀疏集 分别用于存储 组件 A 和 组件 B，我们要创建一个 (A, B) 组，这个分组只包含同时拥有 A 和 B 的 实体，我们将通过动态调整 密集数组 的顺序，将这些 实体 和对应的 组件 排列在数组的开头，同时保证两个 稀疏集 排序一致

假设初始状态如下 (因为稀疏数组与此无关所以不列出它)

A Packed    : [e3|e7|e8|e6]
A Component : [A0|A1|A2|A3]
     group ____^
 
B Packed    : [e4|e5]
B Component : [B0|B1]
     group ____^

可以看到在初始状态下，group 中没有元素，它指向了第一个可用位置，等待向组中添加元素

现在，我们为实体 e7 添加组件 B

A Packed    : [e3|e7|e8|e6]
A Component : [A0|A1|A2|A3]
     group ____^
 
B Packed    : [e4|e5|e7]
B Component : [B0|B1|B2]
     group ____^

可以看到，e7 已经被添加到 B Packed 数组中，并且在 B Component 数组中添加了相应的组件 B2

接着，我们要做的是，在两个 组件池 中同时将刚刚修改的实体 e7 与 group 当前指向的 实体 交换位置，并将 group 推进至下一个元素

A packed    : [e7|e3|e8|e6] <-- swap e7 with e3
A component : [A1|A0|A2|A3]
     group _______^
 
B packed    : [e7|e5|e4] <-- swap e7 with e4
B component : [B2|B1|B0]
     group _______^

同理，我们可以向实体 e4 添加组件 A，group 将再次增长 (下图将新增到末尾和交换位置一次性表示)

A packed    : [e7|e4|e8|e6|e3]
A component : [A1|A4|A2|A3|A0]
     group __________^
 
B packed    : [e7|e4|e5]
B component : [B2|B0|B1]
     group __________^

那么从组中的 实体 上移除 组件 呢？

假设我们想将实体 e7 移除组件 B，首先我们需要将实体 e7 与当前组中包含的最后一个实体交换位置，也就是和 e4 交换位置

A packed    : [e4|e7|e3|e8|e6] <-- swap e7 with e4
A component : [A4|A1|A0|A2|A3]
     group __________^
 
B packed    : [e4|e7|e5]  <-- swap e7 with e4
B component : [B0|B2|B1]
     group __________^

注意 group 指向的并不是当前组中包含的最后一个实体，而是此时向组中添加新元素时应该使用的位置

然后我们需要更新 group ，使其前移指向 e7 (可以认为 group 指向属于该组的最后一个元素之后的元素)

A packed    : [e4|e7|e3|e8|e6] <-- reduce the size of the group
A component : [A4|A1|A0|A2|A3]
     group _______^
 
B packed    : [e4|e7|e5] <-- reduce the size of the group
B component : [B0|B2|B1]
     group _______^

最后，由于实体 e7 不再拥有组件 B，所以我们将它和 B 组件池 的最后一个元素交换位置，并将其 弹出 B 组件池，这是保持 *稠密数组 持续稠密的最好方式

A packed    : [e4|e7|e3|e8|e6]
A component : [A4|A1|A0|A2|A3]
     group _______^
 
B packed    : [e4|e5] <-- swap e7 with e5, then pop out e7 and its component
B component : [B0|B1]
     group _______^

可以发现，当我们为 实体 增加或删除 组件 时，它可能会成为某个 组 的一部分，又或是退出某个 组，不管是进入还是退出 组，我们最终都能得到紧密打包的 实体 和 组件，以及在不同 组件池 中按照相同顺序排列的同组实体及其组件

这样的结果使得我们只需要从第一个元素到最后一个元素迭代它们，没有跳转，没有间接访问，没有测试，只需选择元素并返回它们

总的来说，分组 有以下优劣
优势

• 高效的顺序迭代
  分组的设计确保分组范围内的实体和组件在内存中是连续存储的，迭代时只需顺序访问这些数组，完全避免了无关实体的检查、跨数组的跳跃或间接访问
• 缓存友好
  分组将相关的实体和组件排列在顶部，提升了缓存命中率，从而显著优化了批量操作（如渲染、物理计算等）的性能
• 动态维护
  分组通过简单的交换操作动态维护分组范围的紧密性，且仅在实体进入或退出分组时需要更新，不会对普通的组件添加或删除操作造成额外开销

劣势

• 组件的归属问题
  每个组件只能归属于一个分组，这是因为分组依赖于稀疏集合的排序，如果同一组件被多个分组共享，就需要为每个分组维护不同的排序，这会显著增加复杂性并降低性能
• 构造和销毁的开销
  当实体进入或退出分组时，需要调整稀疏集合的排序，带来一定的开销，但这种开销只在实体改变分组状态时产生，并不影响组件的普通操作，因此在实际应用中通常可以忽略
• 单一排序的限制
  分组只能为一个特定的组件集合排序，如果同一组件需要在多个场景中以不同顺序进行迭代，需要在性能和灵活性之间权衡

EnTT 的三种分组类型

通过权衡性能和灵活性，可以使用三种不同的分组方案

完全拥有组 Full-Owning Groups

完全拥有组 完全控制其包含的组件池

• 例如对于一个 (A, B) 的 完全拥有组 组将拥有组件 A 和 B 的存储，组负责将拥有的组件在 密集数组 中排列，并保持所有组件的顺序一致

这种分组方案的迭代性能是最高的，因为每种组件的密集数组都紧密排列，符合条件的实体和组件存储在数组顶部，迭代时只需从数组的头部到尾部顺序访问，无需跳跃或检查，所以它的缓存命中率最高，因为所有实体和组件按相同顺序存储，一般可以用于需要最高性能的关键路径代码，如物理系统或渲染系统中常用的组件组合

它的代价是一个 组件池 只能归属于一个 完全拥有组，这意味着某个 组件 不能同时被多个 完全拥有组 共享

部分拥有组 Partial-Owning Groups

部分拥有组 拥有其中一部分组件，而另一些组件则被标记为 自由类型 Free-Type

• 例如一个 (B, C) 的 部分拥有组 ，组件 C 由该组完全控制并排序，而组件 B 是 自由类型 (这是因为 B 的控制权已经属于上面的 完全拥有组 (A, B) 了)，仅用于定义分组，但不受分组控制

这种分组方案对于拥有的组件 (例如上面例子里的 C)，其 密集数组 按照分组要求排序，迭代性能接近 完全拥有组，但是对于 自由类型 组件（如例子中的 B），需要支付通过 稀疏集 按 实体索引 访问其数据的代价，不过 自由类型 组件的访问任然无需测试是否存在，因为分组已经保证了实体拥有这些组件，这可以用于某些性能敏感场景，但需要允许组件池被部分共享，例如一个组件需要同时参与多个分组

它的代价是需要支付 自由类型 组件的 间接访问 开销，但通常这种开销较低

非拥有组 Non-Owning Groups

非拥有组 不控制任何组件池，它通过一个额外的 稀疏集 记录符合条件的 实体，并将这些实体的 ID 紧密存储在 稀疏集 的 密集数组 中

• 例如在 完全拥有组 (A, B) 和 部分拥有组 (B, C) 之外，还需要一个组 (A, C)，那么我们只能记录所有同时拥有组件 A 和 C 的实体并不执行任何额外的排序操作了，这就是 非拥有组 (A, C)

这种分组方案需要通过 实体 ID 从 组件池 中间接访问组件数据，它并不拥有任何 组件 的控制权或进行任何排列，无法优化组件的迭代，一般用于非关键路径场景

它的代价显然是需要支付间接访问组件的性能开销，有点像一个记录符合特定组件要求的额外查找表