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调用重新计算。

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

很多事情在编译时是已知的（组件类型列表，签名类型列表，......） -是否有任何可以在编译时生成的辅助数据结构有助于“类似位集”的匹配?

4

6 回答 6

8

对于匹配，您是否一次检查每个组件类型？您应该能够通过检查签名的所有组件是否在一条指令中针对位掩码可用来遍历实体。

例如，我们可能会使用：

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的。

于 2017-12-21T05:26:25.370 回答
5

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

稀疏整数集数据结构允许对存储的整数进行有效的连续O(N)迭代、整数的O(1)插入/删除以及O(1)查询特定整数。

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

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

于 2016-01-07T00:48:28.817 回答
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;
}
于 2015-09-09T10:58:25.860 回答
4

您是否考虑过以下解决方案？每个签名将有一个与该签名匹配的实体容器。

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

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

于 2015-08-17T20:41:23.097 回答
4

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

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

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

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

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

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

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

于 2015-09-04T16:14:19.953 回答
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);
}
于 2015-08-16T13:41:29.507 回答