实现实体组件系统中实体与系统间高效匹配的方法

Question

实现实体组件系统中实体与系统间高效匹配的方法

c++performanceoptimizationc++14entity-component-system

22

我正在开发一个以数据为导向的实体组件系统，其中组件类型和系统签名在编译时已知。

一个实体是由多个组件聚合而成的。组件可以在运行时添加/删除。

一个组件是一个小型无逻辑类。

签名是一个在编译时确定的组件类型列表。如果实体包含签名所需的所有组件类型，则称实体与签名匹配。

以下简短的代码示例将展示用户语法以及预期使用方式：

// 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调用。

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

在编译时已知许多东西 （组件类型列表，签名类型列表等等） - 是否可以生成任何辅助数据结构来帮助“位集合”匹配？

- Vittorio Romeo

@dyp：非常抱歉，我的意思是写成std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>。向量类型在元组内重复出现的次数等于签名类型的计数。 - Vittorio Romeo

你尝试过仅在组件从实体中删除/添加时更新缓存吗？（不确定在这种情况下“管理器更新周期”是什么意思。） - dyp

@dyp：在我的设计中，新创建的实体和被销毁的实体直到调用Manager::refresh()才会真正被创建（由系统考虑）和销毁（被系统忽略）。通过循环，我指的是所有用户代码对实体和系统的操作以及refresh()调用。我不确定如何高效地动态更新缓存。当组件被移除时，我必须遍历所有向量以查找实体ID。此外，用户可能在同一周期内多次调用addComponent<T>或delComponent<T>。 - Vittorio Romeo

@dyp：缓存循环？缓存循环每次refresh()调用时运行一次。这可能会有问题，因为组件的添加/删除直到下一个“循环”才会被注册（这本身没问题，但与无缓存实现不一致）。 - Vittorio Romeo

@dyp：啊，它在forEntityMatching<Signature>内部被调用一次。用户在“循环”期间多次调用forEntityMatching - 通常每次调用都针对不同的签名。最常见的用法是每个周期为每个签名调用一次forEntityMatching。 - Vittorio Romeo

显示剩余2条评论

6个回答

5

根据组件添加/删除与签名匹配的比率，您可以尝试构建一种前缀树，存储对实体的引用。树本身是静态的，只有包含实体的叶子节点是在运行时建立的容器。这样，在添加（或删除）组件时，您只需要将实体的引用移动到正确的叶子节点即可。当搜索与签名匹配的实体时，您只需获取涵盖该签名的所有叶子节点的并集并对它们进行迭代。由于树是（几乎）静态的，因此您甚至不需要搜索这些叶子节点。另一个好处是，您的位集可以用于表示树中的路径，因此移动实体非常容易。如果组件数量导致叶子节点数不切实际，并且并非所有组件组合都被使用，则可以使用哈希表替换树，其中位集是键，值是实体引用集合。这比迭代实体集合看起来更加合理，虽然这只是一些算法思想而不是具体的东西。

- Marwan Burelle

1

不错的想法 - 我喜欢移动实体非常容易的事实。然而，直觉上，我认为这不能比我缓存实体的方法更快（在编译时生成一个[0..N)的std :: array，其中包含std :: vector，并使用签名ID作为键访问它们，例如arrayOfVectors [signatureID <Sig0>（）]，其中signatureID在编译时解析）。 - Vittorio Romeo

5

对于每种签名类型，拥有一个稀疏整数集是理论上最好的解决方案，从时间复杂度的角度来看。

稀疏整数集数据结构允许有效地连续迭代存储的整数，O(1)插入/删除整数，并且O(1)查询特定整数。

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

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

- Vittorio Romeo

@skypjack：我在我的ECS库ecst中使用它们-我没有经验性地比较它们与任何其他类似的数据结构的性能，但在各种用例中对库进行分析时，它们没有占用大量运行时间，瓶颈在其他地方。我使用它们将实体与系统匹配，而不是将组件与实体匹配。给定实体ID，可以通过访问具有该ID的“组件存储”来检索其组件。性能取决于存储方式-这可以是数组访问、哈希表访问或其他任何形式。 - Vittorio Romeo

是的，我知道它们将实体映射到系统。无论如何，每当实体的组件袋发生更改时，您不都必须更新这样的数据结构吗？我知道它们不是瓶颈。我只是好奇。 :-) - skypjack

1

是的，集合必须更新。这是我的实现方式：在“世界更新步骤”期间，所有组件发生更改或被标记为“死亡”的实体都会添加到一个线程本地的稀疏集合中。在“步骤”结束时，这些集合将被合并，并且最终集合中的所有实体都将重新匹配系统（或回收以供将来使用）。重新匹配/回收步骤可以并行完成。相关代码在此处。 - Vittorio Romeo

1

如果你想要另一个使用稀疏集的ECS（实际上是EC）的例子，我最近发布了EnTT。我使用它们来跟踪组件池中的组件。性能比其他众所周知的实体组件系统要好得多，因此它可能是这种方法带来的好处的很好的例子。内存压力或多或少相同（我已经检查过了），因为你摆脱了位掩码数组，但在每个组件池中引入了小型数组。 - skypjack

@skypjack：谢谢提醒，我会去了解一下的。 - Vittorio Romeo

显示剩余2条评论

4

你有考虑过以下解决方案吗？每个签名将具有与该签名匹配的实体容器。

当组件添加或移除时，您需要更新相关的签名容器。

现在，函数可以简单地转到签名实体容器，并为每个实体执行函数。

- Jonathan

4

另一种选项是受到@Marwan Burelle思想的影响。

每个组件将保存一个拥有该组件的实体的排序容器。

当查找与签名匹配的实体时，需要遍历实体的组件容器。

添加或删除的时间复杂度为O（nlogn），因为它需要被排序。但你只需要将其添加/删除到/从一个容器中，该容器也将包含更少的项目。

遍历项目会更加繁重，因为它是组件数量和每个组件中实体数量的乘数因素。你仍然有一个元素的乘法，但元素的数量再次较小。

我写了一个简化版作为POC。

编辑：我的旧版本有一些错误，现在希望已经修复了。

// Example program
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <functional>
#include <memory>
#include <chrono>

struct ComponentBase
{
};

struct Entity
{
    Entity(std::string&& name, uint id)
        : _id(id),
        _name(name)
    {
    }

    uint _id;
    std::string _name;
    std::map<uint, std::shared_ptr<ComponentBase>> _components;
};

template <uint ID>
struct Component : public ComponentBase
{
    static const uint _id;
    static std::map<uint, Entity*> _entities;
};

template <uint ID>
std::map<uint, Entity*> Component<ID>::_entities;

template <uint ID>
const uint Component<ID>::_id = ID;

using Comp0 = Component<0>;
using Comp1 = Component<1>;
using Comp2 = Component<2>;
using Comp3 = Component<3>;

template <typename ...TComponents>
struct Enumerator 
{
};

template <typename TComponent>
struct Enumerator<TComponent>
{
    std::map<uint, Entity*>::iterator it;
    Enumerator()
    {
        it = TComponent::_entities.begin();
    }

    bool AllMoveTo(Entity& entity)
    {
        while (HasNext() && Current()->_id < entity._id)
        {
            MoveNext();
        }

        if (!Current())
            return false;
        return Current()->_id == entity._id;
    }

    bool HasNext() const
    {
        auto it_next = it;
        ++it_next;
        bool has_next = it_next != TComponent::_entities.end();
        return has_next;
    }

    void MoveNext()
    {
        ++it;
    }

    Entity* Current() const
    {
        return it != TComponent::_entities.end() ? it->second : nullptr;
    }
};

template <typename TComponent, typename ...TComponents>
struct Enumerator<TComponent, TComponents...>
{
    std::map<uint, Entity*>::iterator it;
    Enumerator<TComponents...> rest;

    Enumerator()
    {
        it = TComponent::_entities.begin();
    }

    bool AllMoveTo(Entity& entity)
    {
        if (!rest.AllMoveTo(entity))
            return false;

        while (HasNext() && Current()->_id < entity._id)
        {
            MoveNext();
        }
        if (!Current())
            return false;
        return Current()->_id == entity._id;
    }

    bool HasNext() const
    {
        auto it_next = it;
        ++it_next;
        bool has_next = it_next != TComponent::_entities.end();
        return has_next;
    }

    void MoveNext()
    {
        ++it;
    }

    Entity* Current() const
    {
        return it != TComponent::_entities.end() ? it->second : nullptr;
    }
};

template <typename ...TComponents>
struct Requires
{

};

template <typename TComponent>
struct Requires<TComponent>
{
    static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
    {
        for (Enumerator<TComponent> enumerator; enumerator.Current(); enumerator.MoveNext())
        {
            if (!enumerator.AllMoveTo(*enumerator.Current()))
                continue;
            fun(*enumerator.Current());
        }
    }
};

template <typename TComponent, typename ...TComponents>
struct Requires<TComponent, TComponents...>
{
    static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
    { 
        for (Enumerator<TComponent, TComponents...> enumerator; enumerator.Current(); enumerator.MoveNext())
        {
            if (!enumerator.AllMoveTo(*enumerator.Current()))
                continue;
            fun(*enumerator.Current());
        }
    }
};

using Sig0 = Requires<Comp0>;
using Sig1 = Requires<Comp1, Comp3>;
using Sig2 = Requires<Comp1, Comp2, Comp3>;

struct Manager
{
    uint _next_entity_id;

    Manager()
    {
        _next_entity_id = 0;
    }

    Entity createEntity() 
    { 
        uint id = _next_entity_id++;
        return Entity("entity " + std::to_string(id), id); 
    };

    template <typename Component>
    void add(Entity& e)
    {
        e._components[Component::_id] = std::make_shared<Component>();
        Component::_entities.emplace(e._id, &e);
    }

    template <typename Component>
    void remove(Entity& e)
    {
        e._components.erase(Component::_id);
        Component::_entities.erase(e._id);
    }

    template <typename Signature>
    void for_entities_with_signature(const std::function<void(Entity&)>& fun)
    {
        Signature::run_on_matching_entries(fun);
    }

};

int main()
{
    Manager m;
    uint item_count = 100000;
    std::vector<Entity> entities;
    for (size_t item = 0; item < item_count; ++item)
    {
        entities.push_back(m.createEntity());
    }

    for (size_t item = 0; item < item_count; ++item)
    {
        //if (rand() % 2 == 0)
            m.add<Comp0>(entities[item]);
        //if (rand() % 2 == 0)
            m.add<Comp1>(entities[item]);
        //if (rand() % 2 == 0)
            m.add<Comp2>(entities[item]);
        //if (rand() % 2 == 0)
            m.add<Comp3>(entities[item]);
    }

    size_t sig0_count = 0;
    size_t sig1_count = 0;
    size_t sig2_count = 0;

    auto start = std::chrono::system_clock::now();
    m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });    
    m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
    m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });

    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "first run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;

    for (size_t item = 0; item < item_count; ++item)
    {
        if (rand() % 2 == 0)
            m.remove<Comp0>(entities[item]);
        if (rand() % 2 == 0)
            m.remove<Comp1>(entities[item]);
        if (rand() % 2 == 0)
            m.remove<Comp2>(entities[item]);
        if (rand() % 2 == 0)
            m.remove<Comp3>(entities[item]);
    }

    sig0_count = sig1_count = sig2_count = 0;

    start = std::chrono::system_clock::now();
    m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });    
    m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
    m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });

    duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "second run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
}

- Jonathan

2

关于伪代码：

for(auto& e : entities)
    for(const auto& s : signatures)
         if((e.bitset & s.bitset) == s.bitset)
             callUserFunction(e);

我不确定为什么你需要内部循环。

如果在函数中有所需的签名，那么您可以获取该签名的位集，无需遍历所有签名。

template <typename T>
void forEntitiesMatching(const std::function<void(Entity& e)>& fun)
{
    for(auto& e : entities)
        if((e.bitset & T::get_bitset()) == T::get_bitset())
             fun(e);
}

- Jonathan

我在提问时犯了一个错误。我的循环实际上看起来像你写的那个。不确定当我写伪代码时脑子出了什么问题，抱歉！ - Vittorio Romeo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4842163 · Accepted Answer

在匹配时，您是逐位检查每种组件类型吗？您应该能够通过针对位掩码检查一个指令中是否有符号的所有组件来扫描实体。

例如，我们可以使用：

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，但即使你有100万个实体，这也不应该花费很长时间。这应该在眨眼之间完成。

这几乎是最快的实用方法，可以看到哪些实体提供了给定的组件集，同时存储最少量的状态。唯一的原因是我的ECS围绕插件架构旋转，人们通过插件和脚本在运行时注册新的组件类型和系统，所以我无法有效地预测将有多少组件类型的上限。如果我有像你这样的编译时系统，它是设计的事先预测所有这些东西的，那么我肯定认为这是正确的方法。只是不要逐位检查。

使用以上解决方案，您应该能够轻松处理数百次每秒的数百万个组件。有些人可以达到类似的速率，应用CPU图像过滤器处理那么多像素乘以那么多次每秒，并且这些过滤器需要做的工作比单个按位和迭代的分支要多得多。

如果没有一些系统只想处理100万个实体中的一打实体，我甚至不会费心缓存这个超便宜的顺序循环。但在那时，您可以潜在地缓存那些罕见情况下，其中一个系统几乎只处理本地于该系统的实体，而不是尝试集中缓存事物。只要确保感兴趣的系统能够找到何时将实体添加到系统或从系统中删除，以便他们可以使其本地缓存无效即可。

此外，对于这些签名，你不一定需要花哨的元编程。归根结底，使用模板元编程并不能节省任何东西，因为它无法避免循环通过实体检查某些东西，因为只有在运行时才知道实体列表。在这里，没有什么理论上值得优化的编译时方面。你可以像做以下操作：

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%或更多的实体，可能甚至不必费心缓存，因为间接层级的水平可能不值得超过顺序遍历所有实体并在每个实体上进行廉价的按位与运算。