ECS & Hierarchies

本文总结自 [ECS back and forth: Part 4](ECS back and forth (skypjack.github.io))，使用生物通用神经网络翻译成简体中文，并伴有添油加醋之嫌。
文中会使用 entt 作为 ECS 库用于代码示例。

层级结构（Hierarchies）通常的做法是用一个指针来储存父子关系。在各大游戏引擎都可以见到它，或它的变种。

用 ECS 这种面向数据的编程模式来实现这种随机储存的结构，注定没有一个完美的解决方案，我们需按照实际场景来决定数据组织方式。要么使用灵活，要么性能友好，二者不可兼得。

遵循“过早的优化是万恶之源”原则，我会设立几个场景或目标，从需求出发，使用 ECS 思路来进行实现。

访问父对象

层级结构的一种经典实现便是树，其一个基本需求，便是从叶子节点向父节点遍历（比如更新 Transform）。

我们只需要一个“指针”来指向父节点：

struct relationship {
	entt::entity parent{entt::null};
	// something else...
}

这个组件包含了一个 Entity Id 成员，供我们访问父实体的所有组件。

auto* comp = registry.try_get<relationship>(entity);
bool bHaveParent = comp && comp->parent != entt::null;

另外，如果能控制它只附加在 有父节点 的实体上，这里的 parent 甚至不用初始化。利用 entt::group 对其遍历，也能得到极高的性能表现。

访问子对象：定长策略

当反过来，从根开始遍历叶子节点的时候，事情开始复杂了。但在真正复杂之前，我们先看一个约束条件：假定每个节点所拥有的子对象数量是有限的。这种约束下已久可以简单实现，可称之为 定长策略。

举个几例子：卡牌游戏中，手牌数量通常有一个最大上限；工厂类一个设备通常对应有限个输出口；MMO 的角色装扮也仅有几个槽位。所以如果能够接受这个约束，是偌大的一件好事。

一旦有此约束，我们只需要稍稍修改一下 relationship 组件，添加一个长度确定的列表，表示所有子节点：

struct relationship {
	std::size_t size;
	std::array<entt::entity, N> children;
	entt::entity parent{entt::null};
	// something else...
}

或者将它拆解为几个小组件，附加给不同的实体：

struct relation_parent {
	entt::entity entity{entt::null};
};

struct relation_children {
	std::size_t size;
	std::array<entt::entity, N> children;
};

不用多说，在这种模式下，更新子节点的同时也需要对应更新其父节点，这个写操作难以并发处理。但反过来，同一线程遍历所有子项，也只需要一个 for：

auto& comp = registry.get<relation_children>(parent);

for (std::size_T i{}; i < comp.size; ++i) {
	const auto entity = comp.entity[i];
	// ...
}

但是如果我们实在是无法事先获知子对象的最大个数，应当如何是好？

访问子对象：无约束策略

在子对象个数不明确的情况下，可以用稍微复杂一点的类型来处理：链表。

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：父项的子项列表中后一个邻居
• parent：父项实体

children 其实不是必须的，有时需要统计数量时，可以直接遍历链表，这个变量只是空间换时间的一个取舍。

first 作为入口， prev 与 next 作为邻接指针，它们共同构成了双向链表结构，用于在子项链表中遍历。为防止我么拿到的是子项列表的中间项，导致不知道向前还是向后遍历，甚至可以把这个链表做成 循环 的。

这样我们就可以用子项个数来简化遍历条件：

auto &comp = registry.get<relationship>(parent);
auto curr = comp.first;

for(std::size_t i{}; i < comp.children; ++i) {
    curr = registry.get<relationship>(curr).next;
}

这种方案的一大好处是：我们无需构造一个动态申请内存的数组（没错就是你，std::vector）来储存子项列表。当然坏处也是显而易见，正对应着链表的缺点：每个子项的内存空间不是连续的。

就为了几纳秒？

指针访问充满了随机性：它是在使用一个当前寄存器的内容来读取另一个遥远空间的内容。

比如 Unreal 中 WorldOutline 里面的 Transform 传递关系（不如说 Unreal 中所有对象都随机储存在堆内存），靠指针来访问、靠计数来销毁……这必然频繁产生缓存失效。

既然我们用上了 ECS，必然是要想方设法解决这个缓存失效问题。

下面提及的内容，很可能是完全没必要的。就为了节省耗时几纳秒的内存跳转，是否值得花更大的成本？当下的很多程序根本不会考虑这个问题！当然如果你感兴趣，或者真的就为了极致优化，我们马上继续探讨~

池排序

如果内存比较分散，那我排序不就好了！

还真是，我们可以依据 parent 来排序整个层级架构：

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)));
});

这样一来，我们可以保证每一个父项都在子项前面，并且子项都是连续的，直到根节点为止（想象一下 Windows 里的文件夹结构）。

但是全量排序消耗也太大了，每创建一个实体，每切换一次层级，难道都要全排序一遍吗？所幸的是，不需要。我们只需要关注那一个被添加、移除、移动的实体即可。

其实，我们甚至可以忽略某些变化，代价也仅仅是访问这一个元素时产生的内存跳转。

为了实现局部更新，我们引入一个新的组件 dirty，标记一个实体需要被重排序。一旦实体发生变化，我们就往上附加。

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

并在后续的 System 中，更新这一次的变化。

registry.sort<dirty>([](auto &&...) { /* ... */ });
registry.view<dirty>().each([&registry](const auto entity) {
    const auto &instance = registry.get<transform>(entity);
    /* ... */
});

利用原型模式

Flecs 使用原型模式构造层级结构（原型结构的描述上一篇文章讲过，或者参考 UnityDots）。

它将每个对象的子层级都作为单独的一个组件来储存。

在 entt 里，组件标识符是由组件名称转化而来的数字 type_hash_v<Comp>；flecs 里，组件标识符除了名称之外，有 1 位比特专门储存层级信息，并将 CHILDOF | EntityId 直接作为组件表示符。

举个例子：A 是 B 的父对象。结果是：

• 实体 A 不发生变化
• 实体 B 添加了一个组件，名为“A 的子项” CHILDOF | Entity_A

这样一来，所有 “A 的子项”组件确实紧密排列，也可以很方便的遍历。

结语

本文介绍了两种层级结构的实现方案，以及优劣与复杂度，也探讨了减少缓存命中的思路。总而言之，层级结构不存在一个放之四海而皆准的解决方案。

你可以择一实现，也可以另辟蹊径，最终目标还是在满足基本功能之上，尽可能减少工作量、提升性能。