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

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

シグネチャ マッチングに対するコンポーネントの追加/削除の比率に応じて、エンティティへの参照を格納する一種のプレフィックス ツリーの構築を試みることができます。

ツリー自体は静的であり、エンティティを含むリーフのみがランタイム ビルド コンテナーです。

このように、コンポーネントを追加 (または削除) するときに、エンティティの参照を正しいリーフに移動するだけで済みます。

署名に一致するエンティティを検索するときは、署名を含む葉の結合をすべて取得し、それらを反復処理するだけです。また、ツリーは (ほとんど) 静的であるため、これらの葉を検索する必要さえありません。

もう 1 つの良い点: ビットセットを使用してツリー内のパスを表すことができるため、エンティティの移動は非常に簡単です。

コンポーネントの数が非現実的な数の葉を誘発し、すべてのコンポーネントの組み合わせが使用されているわけではない場合、ビットセットがキーで値がエンティティ参照のセットであるハッシュテーブルにツリーを置き換えることができます。

これは具体的なものというよりもアルゴリズム的なアイデアですが、一連のエンティティを反復処理するよりも合理的なようです。

于 2015-09-04T16:14:19.953 に答える
4

次の解決策を検討しましたか? 各署名には、その署名に一致するエンティティのコンテナーがあります。

コンポーネントが追加または削除されたら、関連する署名コンテナーを更新する必要があります。

これで、関数は単純に署名エンティティ コンテナーに移動し、エンティティごとに関数を実行できます。

于 2015-08-17T20:41:23.097 に答える
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 に答える