将实体与实体组件系统中的系统匹配的有效方式

Question

我正在研究一个面向数据的实体组件系统,其中组件类型和系统签名在编译时是已知的.

---

一个实体是一个组件的集合体.可以在运行时从实体添加/删除组件.

甲组件是一个小的逻辑少类.

一个签名是组件类型的编译时间列表.如果实体包含签名所需的所有组件类型,则称该实体与签名匹配.

---

一个简短的代码示例将向您展示用户语法的外观以及预期用途:

// User-defined component types.
struct Comp0 : ecs::Component { /*...*/ };
struct Comp1 : ecs::Component { /*...*/ };
struct Comp2 : ecs::Component { /*...*/ };
struct Comp3 : ecs::Component { /*...*/ };

// User-defined system signatures.
using Sig0 = ecs::Requires<Comp0>;
using Sig1 = ecs::Requires<Comp1, Comp3>;
using Sig2 = ecs::Requires<Comp1, Comp2, Comp3>;

// Store all components in a compile-time type list.
using MyComps = ecs::ComponentList
<
    Comp0, Comp1, Comp2, Comp3
>;

// Store all signatures in a compile-time type list.
using MySigs = ecs::SignatureList
<
    Sig0, Sig1, Sig2
>;

// Final type of the entity manager.
using MyManager = ecs::Manager<MyComps, MySigs>;

void example()
{
    MyManager m;

    // Create an entity and add components to it at runtime.
    auto e0 = m.createEntity();
    m.add<Comp0>(e0);
    m.add<Comp1>(e0);
    m.add<Comp3>(e0);

    // Matches.
    assert(m.matches<Sig0>(e0));

    // Matches.
    assert(m.matches<Sig1>(e0));

    // Doesn't match. (`Comp2` missing)
    assert(!m.matches<Sig2>(e0));

    // Do something with all entities matching `Sig0`.
    m.forEntitiesMatching<Sig0>([](/*...*/){/*...*/}); 
}

---

我目前正在检查实体是否使用std::bitset操作匹配签名.然而,一旦签名数量和实体数量增加,性能就会迅速降低.

伪代码:

// m.forEntitiesMatching<Sig0>
// ...gets transformed into...

for(auto& e : entities)
    if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
        callUserFunction(e);

这样可行,但如果用户forEntitiesMatching多次使用相同的签名进行呼叫,则必须再次匹配所有实体.

在缓存友好容器中可能还有一种更好的预缓存实体的方法.

我尝试使用某种类型的缓存来创建编译时映射(实现为std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>),其中键是签名类型(每个签名类型都有唯一的增量索引SignatureList),并且值是实体索引的向量.

我用以下内容填充缓存元组:

// Compile-time list iterations a-la `boost::hana`.
forEveryType<SignatureList>([](auto t)
{
    using Type = decltype(t)::Type;
    for(auto entityIndex : entities)
        if(matchesSignature<Type>(e))
            std::get<idx<Type>()>(cache).emplace_back(e);
});

并在每个经理更新周期后清除它.

不幸的是,它在我的所有测试中表现得比上面显示的"原始"循环慢.它还会有一个更大的问题:如果调用forEntitiesMatching实际删除或向实体添加组件会怎么样？缓存必须无效并重新计算以用于后续forEntitiesMatching调用.

---

有没有更快的方法将实体与签名匹配？

在编译时已知很多东西(组件类型列表,签名类型列表,......) - 是否有任何辅助数据结构可以在编译时生成,这将有助于"类似bitset"匹配？

Answer 1

根据添加/删除组件与签名匹配的比率，您可以尝试构建一种存储对实体的引用的前缀树。

树本身是静态的，只有包含实体的叶子才是运行时构建的容器。

这样，当添加（或删除）组件时，您只需将实体的引用移动到正确的叶子即可。

当搜索与签名匹配的实体时，您只需获取包含签名的所有叶子的并集并迭代它们。由于树（几乎）是静态的，因此您甚至不需要搜索这些叶子。

另一个优点：您的位集可用于表示树中的路径，因此移动实体非常容易。

如果组件的数量导致叶子数量不切实际，并且并非所有组件的组合都被使用，则可以用哈希表替换树，其中位集是键，值是实体引用集。

这更多的是算法思想，而不是具体的东西，但它似乎比迭代实体集更合理。

Answer 2

为每个签名类型设置一个稀疏整数是理论上最好的解决方案（就时间复杂度而言）。

该稀疏整数集合数据结构允许有效的连续O(N)迭代在存储整数，O(1)插入/移除的整数，并O(1)查询一个特定的整数。

每个签名的稀疏整数集将存储与该特定签名关联的所有实体 ID。

示例：Diana是一个开源 C 和 C++ ECS 库，它利用稀疏整数集来跟踪系统中的实体。每个系统都有自己的稀疏整数集实例。

Answer 3

为了匹配，您一次要检查每种组件类型吗？您应该能够通过在一条指令中针对位掩码检查签名的所有组件是否可用来浏览实体。

例如，我们可以使用：

const uint64_t signature = 0xD; // 0b1101

...以检查是否存在组件0、1和3。

for(const auto& ent: entities)
{
     if (ent.components & signature)
          // the entity has components 0, 1, and 3.
}

如果您的实体连续存储在数组中，那应该快得快。从性能角度来看，无论一次检查3种组件类型还是50种组件类型都没有关系。我不会在ECS中使用这种代表，但是即使您有一百万个实体，也绝对不需要花费很长时间。一眨眼就可以完成。

这几乎是最快的实用方法，可以看到哪些实体在存储最小数量的状态的同时提供给定的一组组件-我之所以不使用此代表的唯一原因是因为我的ECS围绕着人们注册新组件的插件体系结构通过插件和脚本在运行时对类型和系统进行分类，因此我无法有效地预测将有多少个组件类型。如果我有一个像您这样的编译时系统，该系统旨在预先预测所有这些内容，那么绝对可以认为这是可行的方法。只是不要一次检查一点。

使用上述解决方案，您应该能够轻松地每秒处理几百万个组件一百次。有人采用CPU图像过滤器来实现相似的速率，该处理将许多像素乘以每秒多次，并且这些过滤器比bitwise and每次迭代的单个分支和单个分支要完成的工作要多得多。

除非您有一些只想处理的系统，例如一百万个实体中的十二个，否则我什至不会理会这个超级便宜的顺序循环。但是到那时，您可能会缓存那些罕见情况，即一个系统几乎不处理该系统本地的任何实体，而不是尝试集中缓存内容。只需确保感兴趣的系统可以发现何时将实体添加到系统或从系统中删除实体，以使它们可以使本地缓存无效。

同样，对于这些签名，您不一定需要花哨的元编程。归根结底，您并没有真正使用模板元编程来保存任何内容，因为它无法避免循环遍历实体以进行检查，因为实体列表仅在运行时才知道。在理论上，这里没有什么值得在编译时进行优化的东西。你可以做这样的：

static const uint64_t motion_id = 1 << 0;
static const uint64_t sprite_id = 1 << 1;
static const uint64_t sound_id = 1 << 2;
static const uint64_t particle_id = 1 << 3;
...

// Signature to check for entities with motion, sprite, and 
// particle components.
static const uint64_t sig = motion_id | sprite_id | particle_id;

如果您使用与实体相关的位来指示实体具有的组件，则建议您设置系统可以处理的组件类型总数的上限（例如：64个可能足够，128个是船载），这样您就可以一次性检查是否有组件与此类位掩码相对。

[...]如果对forEntitiesMatching的调用实际上删除或向实体添加了组件，该怎么办？

例如，如果您有一个在每一帧添加/删除组件的系统，那么我什至不必费心去缓存。上面的版本应该能够快速遍历实体。

按顺序遍历所有实体的最坏情况是，如果您的系统仅处理这些实体的3％。如果您的引擎设计具有这样的系统，那会有些尴尬，但是您可能只是在添加/删除组件时通知他们它们特别感兴趣，此时它们可以使实体缓存失效，然后在下次系统时重新缓存开始。希望您没有一个系统在每个单一框架中添加或删除组件，而这种类型的组件占组件的3％。如果您确实遇到了最坏的情况，那么最好不要去理会缓存。缓存是没有用的，它只会在每一帧都被丢弃，以一种奇特的方式尝试更新它可能并不会给您带来很多好处。

例如，处理50％或更多实体的其他系统甚至不应该考虑缓存，因为间接的级别可能不值得，只是顺序地遍历所有实体并对bitwise and每个实体进行廉价处理。