entt.1 组合遍历

语法糖
,

过了好一阵子，私以为对 ECS 有了些许了解，在我看来 ECS 是一种 DOD（面向数据设计）的实现方法。而跟诸多数据库一样，entt 提供的是一种紧凑组织、高效遍历的数据框架，并加上各种模板元使代码组织简洁美观。

本文会讨论内存组织方式与遍历的方法。

registry 成员

1. pools

dense_map<id_type, std::unique_ptr<base_type>, identity>

其中的 id_type 来自 type_hash<Component>::value()，所有 Component 唯一。

通过模板泪将 Type 传入后，PRETTY_FUNCTION 也会随之变化。使用 constexpr 就可以静态地算出一个 Type 的 hash。其本质是函数签名字符串的hash。

2. assure<>()

该函数会通过传入的 Comp，在 pools 中创建对应的 component 的专属内存块，并且要求是退化后的类型 (std::decay)。

内存块类型为 sigh_storage_mixin<basic_storage<...>>，别名 storage_type<Component>。只需关注 basic_storage 类。后续有空会额外写一篇文章讨论稀疏集(sparse set)与storage之间的映射关系。

basic_view

本质上是一个 Component 池访问器，用于遍历拥有给定组件集合的实体。

遍历期间如下操作不会使遍历失效：

  • 使用遍历中的 Component 新增实体。
  • 修改迭代器指向的 Entity（比如移除 Entity 中的 正在被遍历的 Components）。
  • 销毁遍历中的 Entity。

除此之外对 pools 的改动，均将使遍历过程失效，并且发生空悬等 Undefined Behavior。

构造过程

由 entt::registry::view 生成一个 basic_view 对象。其成员只有三个对象：

1
2
3
4
5
6
// 需要遍历的pool引用
std::tuple<storage_type *> pools;
// 排除的pool引用
std::array<const base_type *, 0u> filter;
// storage_type<Component>::base_type 的公共类型
const base_type *view;

构造函数参数为若干个 pool，使用模板元来区分 Excluded Component。view 为需遍历Comp中，entity数量最小的 pool 引用。

view 构造的方式比较奇特：

1
2
3
4
5
6
view {
(std::min)(
    {&static_cast<const base_type &>(component)...},
    [] (auto *lhs, auto *rhs) { return lhs->size() < rhs->size(); }
)
}

此处的 std::min 匹配的模板是 algorithm 中的针对初始化表的最小值函数。

1
2
3
4
5
6
7
8
// file <algorithm>
// FUNCTION TEMPLATE min (for initializer_list)
template <class _Ty, class _Pr>
_NODISCARD constexpr _Ty(min)(initializer_list<_Ty> _Ilist, _Pr _Pred) {
    // return leftmost/smallest
    const _Ty* _Res = _Min_element_unchecked(_Ilist.begin(), _Ilist.end(), _Pass_fn(_Pred));
    return *_Res;
}

遍历过程

each 函数是操作 Components 的入口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<std::size_t Comp, typename Func, std::size_t... Index>
void each(Func func, std::index_sequence<Index...>) const {
    // 选择第一个 Comp 作为遍历基元
    for(const auto curr: std::get<Comp>(pools)->each()) {
        const auto entt = std::get<0>(curr);

        // 判断
           // 1. 需要遍历一个以上的Component，或entt有效
           // 如果 只遍历一个Component，则需要判断 entt 的有效性
           // 如果 遍历一个以上，则意味着当前Comp中会存在已经失效的entt，然而其他可能有效。
        if(((sizeof...(Component) != 1u) || (entt != tombstone))
           // 2. 所有 pool 中，entt 有效
           && ((Comp == Index || std::get<Index>(pools)->contains(entt)) && ...)
           // 3. 所有 filter 中，entt 无效
           && std::apply([entt](const auto *...cpool) { return (!cpool->contains(entt) && ...); }, filter)) {
            
            // 此处来适配第一项为 entity_type 的函数
            if constexpr(is_applicable_v<Func, decltype(std::tuple_cat(std::tuple<entity_type>{}, std::declval<basic_view>().get({})))>) {
                std::apply(func, std::tuple_cat(std::make_tuple(entt), dispatch_get<Comp, Index>(curr)...));
            } else {
                std::apply(func, std::tuple_cat(dispatch_get<Comp, Index>(curr)...));
            }
        }
    }
}

为啥遍历的是 std::get<Comp>(pools)->each() 而非 basic_view::view❓

答：因为需要遍历函数涉及的所有组件。函数关联的组件是整个 basic_view 的子集，不一定包含了 basic_view::view。

因此设计好用于遍历的 view 至关重要，性能消耗会来自于对集合的筛选，包括运行时检测等开销。

Scheduler

entt 本体并没有提供任何调度器。

如果需要并发，则需要结合诸如 taskflow、marl 等三方库来实现依赖检查、线程组织、上下文切换等功能。

Share