ECS: 实体拥有哪些组件

要想知道哪些 实体 拥有哪些 组件, 有两种流行的实现: Archetypes (原型) 和 Sparse sets (稀疏集合)

Archetypes 原型

原型的概念相当简单，我们维护一个 组件池 , 并将拥有特定 组件 的 实体 及其所拥有的 组件 归属到对应的 组件池 中，也就是说每当向 实体 添加/删除 组件 时，我们将其移动到对应的池中，如果池尚不存在，则先创建它，这些池被称为 Archetype , 例如

Archetype0:| Position | Velocity |
    Entities   = [101, 102]
    Positions  = [ 10,  20]
    Velocities = [  3,   5]
 
Archetype1:| Position |
    Entities   = [201]
    Positions  = [  8]
 
Archetype2:| Velocity |
    Entities    = [301]
    Velocities  = [  6]

在这里，我们有三个组坚池，也就是三种 Archetype

• Archetype0
  同时拥有 | Position | Velocity | 两种组件
• Archetype1
  只拥有 | Position | 一种组件
• Archetype2
  只拥有 | Velocity | 一种组件

实体 [101, 102] 同时拥有 | Position | Velocity | 组件，所以被归类到 Archetype0
实体 [201] 只有 | Position | 组件，所以被归类到 Archetype1
实体 [301] 只有 | Velocity | 组件，所以被归类到 Archetype2

此时我们如果要查找具有 特定组件 的所有 实体，我们不再需要遍历所有的 实体，而是遍历所有的 Archetypes，也就是组件池，这样遍历的开销通常相对较小，当然满足 特定组件 要求的 Archetypes 并不只有一个，因为迭代的要求是包含 (也就是说是 至少 拥有 特定组件) 很可能会有多个 Archetypes 需要访问，但如果 Archetypes 与查询匹配，则可以保证 Archetypes 中的所有实体至少具有感兴趣的组件，因此不必再测试返回的实体，这最终会大大加快速度

这种方法有其自身的问题，每次添加或删除 组件 时，实体 及其所有 组件 都会从一个 原型 移动到另一个 原型，这在一定程度上影响了 组件 的构造和销毁的效率，如果 组件 经常在运行时被添加/删除，那么将会极大的影响性能，所以这种系统更适合分配给 实体 的 组件集 在运行时不会发生太大变化的情况

Sparse Sets 稀疏集

如果我们使用 密集数组 (dense/packed) 存储所有元素，虽然数据的排列将是紧密连续的，这有利于 cacheline 但是对于删除存储的某个元素则很有挑战，因为一旦从中间删除了某个元素，就会在数组中留下 空洞，数组将不再 dense 和连续，为了使得它保持连续，往往需要将元素进行重新排列，涉及极大的开销

• 删除带来的空洞问题

  • 如果直接删除密集数组中的一个元素，比如将它置为 nullptr 或类似的值，密集数组就会出现“空洞”，不再连续
  • 空洞会导致遍历性能下降，因为需要跳过无效的空位置

• 删除导致的高代价

  • 如果想要删除某个值并保持数组连续，就需要将数组尾部的元素移动到被删除的索引位置
  • 这种操作需要额外的开销（O(1) 替换，但需要 O(n) 查找）

为了解决这个问题，可以引入一个额外的数组，称为 稀疏数组 Sparse，这个数组中存储实的内容是实际存储数据的 密集数组 dense 的索引，并且它运行存在空洞

例如，我们有以下情况

• 稀疏数组（sparse）：记录逻辑 实体索引 到其在 密集数组 的 存储位置，如果该 稀疏集 中不含该 实体，则对应 实体索引 位置存储 无效值 (或其他可判断方式)，所以 有效实体 是不连续存储的，所以被称为 稀疏数组

  Index:   0   1   2    3   4   5    6   7   8   9
  Value:  -1   0   1   -1  -1   2   -1  -1  -1  -1

• 密集数组（packed）：直接以连续密集形式存储有效的 实体索引 以便高效遍历

  Index:   0   1   2
  Value:   1   2   5

可以发现，稀疏数组 的索引对应 实体索引，而 密集数组 的索引则什么都不对应，我们可以用 稀疏数组 高效测试当前 稀疏集 是否含有某个 实体索引 (因为不需要查找，直接访问存储值是否有效)，而用 密集数组 高效遍历所有当前 稀疏集 中所含的 实体索引 (因为连续存储，不存在空洞)

如果我们想要删除实体 2，则

1. 查找稀疏数组 sparse[2]，得到密集数组中的索引位置 1
2. 将密集数组的最后一个元素 5 移动到索引 1

   packed = [1, 5]

3. 更新稀疏数组
   • 将实体 5 的稀疏索引更新为 1

     sparse[5] = 1

   • 将实体 2 的稀疏索引置为无效值 -1

     sparse[2] = -1

删除后的结果

• 稀疏数组（sparse）

  Index:   0   1   2    3   4   5    6   7   8   9
  Value:  -1   0  -1   -1  -1   1   -1  -1  -1  -1

• 密集数组（packed）

  Index:   0   1
  Value:   1   5

此时密集数组仍然是连续的，删除操作的时间复杂度是 O(1)

这两个数组组成了 稀疏集 Sparse Sets，它具有以下特点

• 高效的插入和删除
  • 稀疏数组帮助在 O(1) 时间内定位数据位置
  • 密集数组通过尾部元素替换被删除位置，保证连续性，避免了内存碎片
• 快速查找
  • 查找某个实体是否存在，通过稀疏数组 O(1) 完成
• 顺序遍历高效
  • 由于密集数组始终是连续的，遍历所有元素只需 O(n)（n 是有效元素的数量，而不是稀疏数组的大小），也就说直接去遍历密集数组，而不是去遍历稀疏数组

当向 稀疏集 中增加新元素的时候，可以优先使用 空洞 位置，这样可以避免稀疏数组的扩展以致于过于稀疏，我们还可以利用空洞位置本身来存储下一个空洞位置的索引以加速新增操作，在 ECS 系统中，这可以认为是重用被删除实体的 标识符，当然实际实现会比这复杂

实体归属 Entity Ownership

使用 稀疏集，我们可以构建与上面 Archetypes 非常不同的 实体 归属机制

• 每一个 系统 对应一个独立的 稀疏集
  为每个系统分配一个独立的稀疏集合，稀疏集合仅存储系统关心的实体，具体取决于系统需要访问的 组件 的类型

  • 例如，一个处理 Position 和 Velocity 组件的物理系统，其稀疏集合只包含拥有这两个组件的实体

• 系统的注册与更新
  系统在初始化时通过 中央管理器 Central Manager 注册，在注册阶段，系统 声明它需要哪些 组件，管理器据此维护系统的 稀疏集，并在每次 实体 或 组件 状态变化后保持其更新

• 系统的实体迭代
  系统通过直接迭代其 稀疏集 中的 密集数组 Packed 来处理实体，稀疏集 中的 密集数组 存储所有关心的 实体，且这些 实体 在内存中是紧凑存储的，迭代性能极高

这种做法的优势显而易见，系统直接迭代自己拥有的 稀疏集 的 密集数组，遍历时缓存命中率高并且稀疏集合的特性使其在插入、删除和更新实体时效率也很高

但是这样做也存在一定劣势，由于使用了 中央管理器 Central Manager，系统无法直接访问组件，而是通过中央管理器按 实体 ID 查找组件，如果管理器未对组件进行缓存友好的存储设计，可能导致性能瓶颈

组件归属 Component Ownership

可以看到，由于 中央管理器 Central Manager 的存在，系统即使已经拥有了 实体归属 权，但是任然依赖 中央管理器 来获取 实体 的具体 组件 以进行实际的操作，如果 中央管理器 的 组件 内存布局不佳，亦或是存在其它优化问题，就很容易导致性能瓶颈

作为改进，可以进一步的将 组件 也归属到 系统 中，在这种情况下 系统 的 稀疏集合 不仅存储 实体，还存储 组件 实例

• 系统直接管理组件
  系统直接“拥有”并管理它需要写入的 组件，而不是通过中央管理器获取这些组件，一个组件只能被一个系统“拥有”，其他需要访问该组件的系统只能通过共享引用或其他间接方式访问
  • 归属规则: 哪个系统需要修改（写入）某个组件，哪个系统就最适合拥有该组件。
  • 去除中央管理器: 组件的实例由各个系统直接管理，省去了中央管理器这一层，减少了潜在的性能瓶颈
• 实现方式
  稀疏集合的 密集数组 packed 除了 实体 ID，还包含与这些实体对应的组件数据，这样，系统可以直接迭代密集数组，不仅访问实体，还能同时访问其关联的组件实例

这么做显然也会带来其它问题，例如将难以处理多个系统需要访问同一组件的情况，并且需要更多的设计和协调工作

• 外部组件访问
  如果一个系统需要访问由另一个系统“拥有”的组件，它可以通过 实体标识符 entity identifiers 实现，实体标识符用于在其他系统的稀疏集合中查找对应组件的索引，并从它们的密集数组中检索组件数据

例如一个实际情况如下
稀疏集合 + 中央管理器

1. 一个 RenderSystem 注册时声明需要 Transform 和 Renderable 组件
2. 中央管理器创建一个稀疏集合，包含拥有 Transform 和 Renderable 的实体
3. 系统通过稀疏集合的密集数组迭代实体，并从中央管理器中获取组件

组件归属模型

1. RenderSystem 拥有 Renderable 组件
2. 系统直接存储并管理这些组件，无需中央管理器
3. 如果 PhysicsSystem 也需要 Renderable 组件，则只能通过引用的方式访问

组件归属 的想法在我看来可能过于激进，类似 EnTT 这类 ECS 系统通过 Group 来实现类似的功能

• 在 EnTT 中，分组 Group 通过将某些 组件 的实例存储在 密集数组 中，同时结合必要的间接访问来优化性能
• 系统 并不拥有 组件，而是通过 分组 来高效管理和访问所需的 实体 和 组件

稀疏集 作为 组件池

在 ECS 中使用 稀疏集 也可以与 系统 无关，那就是直接将它们用于 组件池

我们可以为每一种 组件 建立一个独立的 组件池 Component Pool

• 稀疏数组 用来快速定位某个 实体 是否拥有该 组件 及其在 密集数组 中的索引
• 密集数组 紧凑存储所有 实体 对应的 组件 实例，没有空洞

可以发现，在这种情况下，判断某个 实体 是否拥有某个 组件 非常容易，只需要通过 实体 ID 查找 稀疏数组，如果 稀疏数组 返回有效索引，说明 实体 拥有该 组件

而迭代某种 组件 的所有实例也很容易，直接遍历 密集数组 即可，所有组件实例都存储在连续内存中，非常高效，因为如果 稀疏数组 用 实体 ID 作为索引，稀疏集 的 密集数组 中实际上也包含了 实体 ID，迭代 组件 和对应的 实体 同样快速

但当需要同时迭代多个组件时，问题就变得复杂，因为每个组件池是完全独立的，我们需要找到拥有指定组件集合的实体，并高效地访问它们的组件实例，多组件迭代有几种解决方案

• 基于最短池的动态查询

  • 步骤
  1. 找出最短的组件池（即包含实体最少的那个池）
  2. 遍历该池的实体，对每个实体检查其他组件池是否包含该实体
  3. 如果所有池都包含该实体，返回该实体及其组件实例；否则跳过该实体
  • 优势: 实现简单，适合大多数游戏和应用场景，由于只遍历最短的池，可以大幅减少不必要的检查
  • 劣势: 每次查询时都需要动态检查，无法提前确定哪些实体符合条件，对每个实体的检查需要一定的间接访问，性能略有下降

• 预计算稀疏集合

  • 步骤
  1. 创建一个额外的稀疏集，专门存储拥有目标组件集合的实体
  2. 每当实体的组件集合发生变化时，更新这个稀疏集合
     • 如果实体新增了目标组件集合，加入稀疏集
     • 如果实体失去了某个目标组件，从稀疏集中移除
  • 优势: 在运行时，稀疏集合中只包含符合条件的实体，迭代时性能非常高，适合需要频繁查询特定组件集合的场景
  • 劣势: 由于需要实时维护这个额外的稀疏集，增加了一定的复杂性和内存开销，仍然需要通过 实体 ID 间接访问组件实例，存在一定的性能损耗

• 数组排序与压缩 (EnTT 的 Group)

  • 步骤
  1. 将所有实体按拥有组件的集合进行排序，使得拥有指定组件集合的实体位于密集数组的顶部，其他实体排在后面
  2. 组件数据的密集数组也按相同顺序排列，这样拥有指定组件集合的实体和组件实例都被紧凑存储在数组开头
  • 优势: 迭代性能最高，因为实体和组件在内存中完全连续，不需要任何检查或间接访问，这类似于 Archetype 模型，但避免了 Archetype 在不同内存块之间的跳跃开销
  • 劣势: 只能为一个组件集合排序，无法同时为多个不同的查询场景提供最优性能，如果组件集合对应的排序需求经常变化，会导致排序开销