c++ Эффективный способ сопоставления объектов с системами в системе компонентов объекта




performance optimization (5)

В зависимости от соотношения добавления / удаления компонентов к сопоставлению сигнатур, вы можете попытаться создать своего рода дерево префиксов, хранящее ссылки на сущности.

Само дерево статично, только листья, содержащие сущности, являются контейнерами, построенными во время выполнения.

Таким образом, при добавлении (или удалении) компонентов вам просто нужно переместить ссылку на сущность на правильный лист.

При поиске сущностей, соответствующих сигнатуре, вам просто нужно взять все объединения листьев, включающих сигнатуру, и перебрать их. А поскольку дерево (почти) статично, вам даже не нужно искать эти листья.

Еще один приятный момент: ваш битрейт может использоваться для представления пути в дереве, поэтому перемещение объекта довольно легко.

Если число компонентов приводит к нереалистичному количеству листьев, и не все комбинации компонентов используются, вы можете заменить дерево на хеш-таблицу, где битовый набор является ключом, а значение является набором ссылок на сущности.

Это скорее алгоритмические идеи, чем конкретные вещи, но это кажется более разумным, чем итерация по множеству сущностей.

Я работаю над системой компонентов, ориентированной на данные, где типы компонентов и системные сигнатуры известны во время компиляции.

Сущность - это совокупность компонентов. Компоненты могут быть добавлены / удалены из объектов во время выполнения.

Компонент - это небольшой класс без логики.

Подпись - это список типов компонентов во время компиляции. Считается, что сущность соответствует подписи, если она содержит все типы компонентов, требуемые подписью.

Пример короткого кода покажет вам, как выглядит синтаксис пользователя и каково его предполагаемое использование:

// 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 .

Есть ли более быстрый способ сопоставления сущностей с подписями?

Многое известно во время компиляции (список типов компонентов, список типов сигнатур, ...) - есть ли какая-либо вспомогательная структура данных, которая может быть сгенерирована во время компиляции, которая поможет с "подобным битам" сопоставлением ?


Еще один вариант, на который немного повлияла идея @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;
}

Наличие разреженного целого числа, установленного для типа подписи, является теоретически лучшим решением (с точки зрения сложности времени) .

Структура данных с разреженным целочисленным набором данных обеспечивает эффективную непрерывную итерацию O(N) по сохраненным целым числам, O(1) вставку / удаление целых чисел и запрос O(1) для конкретного целого числа.

Набор разреженных целых чисел для подписи будет хранить все идентификаторы сущностей, связанные с этой конкретной подписью.

Пример: Diana , библиотека ECS C и C ++ с открытым исходным кодом, использует разреженный набор целых чисел для отслеживания сущностей в системах. Каждая система имеет свой собственный экземпляр разреженного набора целых чисел .


Что касается псевдокода:

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);
}

Рассматривали ли вы следующее решение? Каждая подпись будет иметь контейнер объектов, соответствующих этой подписи.

Когда компонент добавлен или удален, вам необходимо обновить соответствующий контейнер подписи.

Теперь функция может просто перейти в контейнер объекта подписи и выполнить функцию для каждого объекта.







entity-component-system