ECS: 层级关系

在 ECS 系统中高效的处理层级关系可能具有挑战，如果父子关系在内存中分散存储，遍历层级可能会产生大量缓存未命中，影响性能，如果需要动态调整父子关系则可能导致内存碎片化，所以一般不存在既灵活又性能最佳的通用解决方案，具体实现需要根据实际需求权衡

层级关系通常用来描述实体间的父子结构，比如

• 游戏中的场景图，一个角色是一个实体，其手臂和武器等是子实体
• UI树，窗口、按钮、文本框等以嵌套结构存在

只访问父节点

在这种情况下，只需要从 子节点 去访问 父节点，比如调整子实体的位置，使其相对于父实体，在这种情况下不需要支持动态或复杂的子节点遍历，仅需跟踪每个实体的父节点信息即可

在这种情况下，实现相对简单，我们只需要为每个 子实体 分配一个 组件，记录其父节点的实体标识符

struct relationship {
    entt::entity parent{entt::null}; // 父节点的实体标识符
    // ... 其他数据成员 ...
};

而查询父节点只需要尝试从实体 entity 获取 relationship 组件，如果其 parent 不为 entt::null，表示该实体有父节点

if (auto *comp = registry.try_get<relationship>(entity); comp && comp->parent != entt::null) {
    // 查询到父节点后执行操作
}

通过使用 EnTT 的 分组 功能，甚至可以避免 if 检测 (本质上是将具有父级的实体与其他实体分开处理)

双向访问 (子节点数有限且已知)

当需要从父节点访问子节点时，并且是在子节点 数量有限且已知 的情况下，我们需要额外记录 子节点 信息，这种需求也很常见，例如游戏角色有两只手（每只手持一个武器）和两个备用武器插槽，总共最多四个武器又或者背包中的物品数量有限且已知，比如最多 10 件

我们可以通过在 关系组件 中直接存储子节点数组来实现

struct relationship {
    std::size_t size;                     // 当前子节点数量
    std::array<entt::entity, N> children; // 固定大小的子节点数组
    entt::entity parent{entt::null};      // 父节点
    // ... 其他成员 ...
};

在一些情况下，可以将 relationship 拆分为两个独立的组件 parent 和 children

struct parent {
    entt::entity entity{entt::null}; // 父节点
    // ... 其他数据成员 ...
};
 
struct children {
    std::size_t size{};                    // 当前子节点数量
    std::array<entt::entity, N> entity{};  // 子节点数组
    // ... 其他数据成员 ...
};

拆分有其独特的优势

1. 冷热数据分离 如果访问父节点的频率远高于访问子节点的频率，分离组件有助于优化缓存命中率
2. 灵活性更高 可以针对具体需求分别优化父节点和子节点的存储与访问

访问某个节点的所有子节点并迭代它们

auto &comp = registry.get<children>(parent);
 
for (std::size_t i{}; i < comp.size; ++i) {
    const auto entity = comp.entity[i];
    // 对每个子节点执行操作
}

非约束模型 Unconstrained Model

如果实现不知道 子节点 的具体数量，上面的方案就很难工作，非约束模型 是一种在 ECS 中实现动态层级关系的方法，该模型通过一个 隐式双向链表 实现子节点的存储和管理，能够动态调整父子关系，适合处理未知数量的子节点场景

它的实现如下

struct relationship {
    std::size_t children{};                 // 当前子节点数量（可选）
    entt::entity first{entt::null};         // 第一个子节点的标识符
    entt::entity prev{entt::null};          // 前一个兄弟节点的标识符
    entt::entity next{entt::null};          // 后一个兄弟节点的标识符
    entt::entity parent{entt::null};        // 父节点的标识符
    // ... 其他成员 ...
};

其中

• children
  存储当前实体的子节点数量，它不是必须的，但可以加速遍历子节点并减少判断逻辑
• first
  指向第一个子节点的实体标识符，用于从父节点开始遍历子节点
• prev 和 next
  用于构建 隐式双向链表，允许在链表中高效地插入、删除节点
  • prev：指向当前节点的前一个兄弟节点
  • next：指向当前节点的后一个兄弟节点
• parent
  指向当前节点的父节点，用于从子节点反向访问父节点

要迭代一个实体的所有子实体，有两种办法 第一种是基于 children 字段，如果 children 字段已存储子节点数量，可以按如下方式遍历

auto &comp = registry.get<relationship>(parent);
auto curr = comp.first;
 
for (std::size_t i{}; i < comp.children; ++i) {
    // 访问当前子节点
    const auto &child_comp = registry.get<relationship>(curr);
    curr = child_comp.next;
}

第二种不使用 children 字段 如果没有 children 字段，可以通过判断 next 是否为 entt::null 来遍历

auto &comp = registry.get<relationship>(parent);
auto curr = comp.first;
 
while (curr != entt::null) {
    // 访问当前子节点
    const auto &child_comp = registry.get<relationship>(curr);
    curr = child_comp.next;
}

排序

上面的方法都非常好，但是它们都无法保证实体的子实体在内存中彼此接近，因此迭代它们可能会导致一些额外的跳跃，并且在遍历访问时，无法保证父节点出现在子节点之前，也就是说遍历的顺序是无法保证的，我们一般希望从根节点开始逐层向下访问，即 广度优先 breadth-first

解决问题的一种方法是对组件池进行全局排序，确保父节点总是排在子节点之前，并且将父节点和子节点尽可能紧密排列，减少内存跳跃，优化访问性能

registry.sort<relationship>([&registry](const entt::entity lhs, const entt::entity rhs) {
    const auto &clhs = registry.get<relationship>(lhs);
    const auto &crhs = registry.get<relationship>(rhs);
    return crhs.parent == lhs || clhs.next == rhs
        || (!(clhs.parent == rhs || crhs.next == lhs) && (clhs.parent < crhs.parent || (clhs.parent == crhs.parent && &clhs < &crhs)));
});

这段代码将对组件池 relationship 进行排序，通过一个排序规则（lambda 函数）来定义两个实体 lhs 和 rhs 的排列关系，排序算法会调用传递的 lambda，每次传入比较两个实体（lhs 和 rhs），并根据 lambda 的返回值来决定是否将 lhs 排在 rhs 之前

• true：表示 lhs 应排在 rhs 之前
• false：表示 lhs 应排在 rhs 之后

而上面 lambda 中的逻辑是

1. 确保父节点始终排在子节点之前

   crhs.parent == lhs

   如果 rhs 的父节点是 lhs，则 lhs 必须排在 rhs 之前，返回 true
2. 在同一个父节点的子节点中，按照 next 指针定义的顺序排列

   clhs.next == rhs

   如果 lhs 的下一个兄弟节点是 rhs，则 lhs 必须排在 rhs 之前，这将维护兄弟节点的相对顺序
3. 排除前两种情况

   !(clhs.parent == rhs || crhs.next == lhs)

   用于排除上述两种情况，以进行接下来的特殊判断
4. 确保不同父节点下的实体按父节点的标识符顺序排列

   clhs.parent < crhs.parent

   如果 lhs 和 rhs 不同父节点，则按照父节点的标识符排序，较小的父节点优先
5. 为同一个父节点的子节点提供排列方式

   clhs.parent == crhs.parent && &clhs < &crhs

   如果 lhs 和 rhs 共享相同的父节点，则比较组件的地址（&clhs 和 &crhs）以确定顺序，这是为了在二者没有 next 指针关系时也提供具有确定性的排列方式

这里 lambda 函数充当了 自定义比较器 的功能，排序算法 (例如快速、堆、归并等) 通过调用 自定义比较器 来判断两个元素之间的顺序，从而确定整个数据集合的排列

对于我们的排序情况，最终完成了以下逻辑

• 父节点 优先，总是确保父节点总是排在子节点之前
• 兄弟节点 按 next 字段排序，保证兄弟节点的顺序一致
• 同层节点 按 parent 字段排序，同一父节点的子节点紧密排列

这样排序后的优势是，遍历整个层级关系时非常高效，因为它满足了 广度优先 搜索的条件，即

• 层级优先：从树的根节点开始，一层一层向下遍历，当前层的所有节点都在下一层的节点之前被访问
• 兄弟节点顺序：同一层级的兄弟节点按顺序依次访问

但排序的代价较高，特别是当实体数量较多时，全局排序的复杂度为 $O(N\log N)$

局部排序：只排序被更新的实体

事实上，每一次都对完整的层级关系进行排序是不必要的，我们可以只需要排序那些 局部变换被改变 的组件，这种做法是一种增量更新策略，只处理受影响的部分可以显著提高性能

一般来说，实体具有 局部变换 Local Transform 和 全局变换 Global Transform

• 局部变换 它定义实体相对于其 父节点 的变换，如果 父节点 没有改变，局部变换 通常不需要重新计算
• 全局变换
  定义实体在整个场景中的 最终变换，它是 父节点 的 全局变换 与该实体的 局部变换 的组合结果，如果 父节点 或 局部变换 发生改变，则需要重新计算

所以我们可以发现，全局变换 的更新依赖于父节点的状态，因此，当局部变换被改变时，只需要重新更新

1. 改变了局部变换的实体本身
2. 该实体的所有子节点（因为其全局变换依赖于父节点）

例如，假设有如下层级关系

e1 (根节点)
├── e2
├── e3
│   ├── e4
│   └── e5
└── e6

在初始状态下，实体的全局变换已经计算完成，没有局部变换被改变

现在，假设只改变了 e3 的局部变换

• 受影响的实体：e3 及其子节点 e4 和 e5
• 未受影响的实体：e1, e2, e6

增量更新过程

1. 标记
   • 给 e3 添加 dirty 组件
   • e4 和 e5 不直接标记，但它们的更新会由 e3 的状态触发
2. 筛选
   筛选出 dirty 的脏实体们 [e3, e4, e5]，忽略未受影响的实体
3. 局部排序
   按父子关系对 [e3, e4, e5] 排序，排序后为 [e3, e4, e5]（已经符合父子顺序）
4. 更新
   遍历排序后的实体，更新 e3 的全局变换，然后依次更新 e4 和 e5
5. 清理
   移除 e3 的 dirty 标记

可以发现，如果选择不排序，需要从一个受影响的实体（如 e3）开始，遍历其所有子节点 (如 e4 和 e5)，进行一次树形结构的广度优先搜索来更新受影响的所有节点，为此我们需要额外维护一个 队列 Queue

1. 从根节点开始：把需要更新的实体（例如 e3）加入队列
2. 逐层遍历子节点：依次处理队列中的实体，并将其子节点加入队列
3. 更新变换：根据父节点的全局变换更新当前节点的全局变换

这种方法也是只更新部分子树的局部更新，但是它需要额外的队列开销以及可能产生不连续访问，需要在内存中跳跃，相比之下，排序以后只需要线性遍历排序后的实体池 (并且可能一次排序，多次遍历)，这对于缓存是友好的

所以具体选择排序还是直接执行 BFS，取决于场景的更新范围和频率 ($M$ 是受影响实体个数)

• 更新范围大
  选择局部排序，便于线性遍历，并且可重复使用(例如在多个系统中或多帧中迭代) $O(M\log M)$
• 更新范围小
  选择广度优先搜索，只处理受影响的小部分，但无法重复使用，每次需要使用队列动态计算 $O(M)$

如果不需要逐层访问，也可以选择使用 深度优先 DFS 遍历，但是要注意，如果树的 深度 过深，为了避免系统栈溢出 (使用递归)，可能需要使用额外的显式栈

事实上，上面的 dirty 组件标记方法，在进行脏传播时也需要用到 深度优先 遍历，具体来说，我们可以通过监听 本地变换 local transform 组件的 替换 或 构造 事件来自动附加 dirty 组件

entt::connect<dirty>(registry.on_replace<transform>());
entt::connect<dirty>(registry.on_construct<transform>());

当 transform 组件被替换或创建时，自动将 dirty 组件附加到对应的实体，除此之外，我们还需要将其所有 子节点 都标记为脏，也就是都附加 dirty，以表明它们也需要重新计算 世界变换，也就是说我们需要实现脏传播

一种简单的办法是在附加 dirty 组件的同时，改变其 子节点 的 transform 组件，这样又会触发 子节点 本身被附加dirty 组件，并以此递归，当然这种方法和我们不改变 子节点 的 transform 组件，而是直接递归的遍历所有 子节点 附加 dirty 组件是等价的

void markChildrenDirty(entt::registry &registry, entt::entity parent) {
    auto child = registry.get<relationship>(parent).first;      // 获取第一个子节点
    while (child != entt::null) {
        if (!registry.all_of<dirty>(child)) {
            registry.emplace<dirty>(child);                     // 附加 dirty 组件
        }
        markChildrenDirty(registry, child);                     // 递归标记子节点
        child = registry.get<relationship>(child).next;         // 遍历兄弟节点
    }
}

这种递归是隐式的利用了 系统栈，当树的深度过深时，有可能导致 栈溢出，我们可以改用 显式栈 进行这个 深度优先搜索 DFS

registry.on_replace<transform>().connect([](entt::registry &registry, entt::entity root) {
    std::stack<entt::entity> stack;
    stack.push(root);
 
    while (!stack.empty()) {
        entt::entity parent = stack.top();
        stack.pop();
 
        const auto &relationship = registry.get<relationship>(parent);
        auto child = relationship.first;
 
        while (child != entt::null) {
            auto &childTransform = registry.get<transform>(child);
            childTransform.global = registry.get<transform>(parent).global * childTransform.local;
            stack.push(child);  // 子节点压入栈
            child = registry.get<relationship>(child).next;
        }
    }
});

当然也可以使用 广度优先搜索 BFS 来逐层遍历标脏，在这种情况下，我们需要一个 队列

void markChildrenDirtyBFS(entt::registry &registry, entt::entity root) {
    std::queue<entt::entity> queue;
    queue.push(root);
 
    while (!queue.empty()) {
        auto parent = queue.front();
        queue.pop();
 
        auto child = registry.get<relationship>(parent).first;
        while (child != entt::null) {
            if (!registry.all_of<dirty>(child)) {
                registry.emplace<dirty>(child);  // 附加 dirty 组件
            }
            queue.push(child);  // 将子节点加入队列
            child = registry.get<relationship>(child).next;
        }
    }
}

一般来说，BFS 效率更高，但是内存占用更大

标脏完成之后，我们就可以对所有具有 dirty 组件的实体进行排序，并线性遍历排序结果来更新变换，有两种办法

• 基于 视图 View 对带有 dirty 组件的实体进行排序

registry.sort<dirty>([](const auto lhs, const auto rhs) {
    // 自定义排序逻辑 确保父节点优先
    /* ... */
});
 
// 遍历排序后的实体并执行更新
registry.view<dirty>().each([&registry](const auto entity) {
    const auto &instance = registry.get<transform>(entity);
    // 更新逻辑
    /* ... */
});

• 基于 分组 Group 创建包含 dirty 和 transform 的分组

auto group = registry.group<dirty, transform>();
 
group.sort([](const auto lhs, const auto rhs) {
    // 自定义排序逻辑
    /* ... */
});
 
group.each([](const auto entity, auto &transform) {
    // 更新逻辑
    /* ... */
});

这样做的优势是分组后可以直接访问 transform 组件，无需额外查询，提高性能

相比起全局排序，局部排序的复杂度更低，是 $O(M\log M)$，其中 $M$ 是需要更新的实体数量，如果只有少量实体需要更新，性能将提升显著

执行完排序和更新逻辑以后，我们不要忘记要清除所有 dirty 组件，为下一次更新做准备

registry.reset<dirty>();

基于原型 archetype 的 ECS 系统的层级排序

在基于 原型 模型的 ECS 系统中，组件存储在多个数组中，每种组件组合（即一种原型）都有独立的存储位置，这导致了 碎片化 Fragmentation，具体来说是指组件被分散存储在多个数组中，这通常会导致缓存命中率降低和遍历性能下降

在层级结构中，父子关系需要保持明确的顺序（如广度优先遍历），而基于 原型 的 ECS 实现中，实体可能分散在多个原型中，这使得排序更加复杂

智能碎片化

我们可以通过为每个实体分配特定的 原型，并将父子关系编码到 原型 类型中，如此就可以利用 原型 间的碎片化来实现层级，因为 原型 中明确编码了父子关系，使得可以基于父子关系对 原型 进行排序，使得与我们在按广度优先方式下降是的顺序一致

ecs_entity_t parent_1   = ecs_new(world, Position);
ecs_entity_t parent_2   = ecs_new(world, Position);
 
ecs_entity_t child_1    = ecs_new_child(world, parent_1, Position);
ecs_entity_t child_2    = ecs_new_child(world, parent_2, Position);
ecs_entity_t grandchild = ecs_new_child(world, child_2, Position);

上面的代码将生成 4 个 原型

• [Position]
• [Position, CHILDOF | parent_1]
• [Position, CHILDOF | parent_2]
• [Position, CHILDOF | child_2]

这里 CHILDOF 是一种 关系标签 relationship tag，用于表示实体之间的 父子关系，它不需要显式存储指针，而是通过 组件类型 来表达这种关系

然后我们可以对 原型 进行排序，父实体优先，子实体按层级依次排列，我们通过 CASCADE 关键字注释 深度 Depth Annotation，为每个 原型 分配一个 深度值

• [Position] => 0
• [Position, CHILDOF | parent_1] => 1
• [Position, CHILDOF | parent_2] => 1
• [Position, CHILDOF | child_2] => 2

然后遍历时通过 CASCADE.Position，可以让系统按深度从低到高遍历原型，这样在处理层级时就能保证

• 父节点在子节点之前更新（例如更新变换矩阵时）
• 每个原型内部的实体仍然是紧密排列的（packed array），有利于缓存命中率

ECS_SYSTEM(world, Transform, EcsOnUpdate, Position, CASCADE.Position);

并且我们在新增或删除实体时无需对整个数组重新排序，因为实体的父子关系已经通过原型和深度值编码在内

但是如果层级中有大量父节点，每个父节点都创建独立的原型，这会导致碎片化严重，如上例中，如果有上千个父节点，每个父节点都生成一个 [Position, CHILDOF | parent_X] 原型，可能导致大量原型和碎片化，为了解决这个问题，我们可以将同一深度、相同组件的实体合并到同一个原型中

• 例如，将所有 Position 组件且深度为 1 的实体放到一个原型 [Position, Depth_1] 中，而不是为每个父节点生成单独的原型

这将减少原型数量，降低碎片化程度，提高迭代性能，但新增或删除组件的操作可能略有性能开销