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

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

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

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

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

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

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

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

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

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

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

Иметь набор разреженных целых за тип подписи является теоретически лучшее решение (с точки зрения сложности времени).

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

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

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

Для соответствия вы проверяете для каждого типа компонента один бит за раз? Вы должны иметь возможность просматривать объекты, проверяя, доступны ли все компоненты для подписи в одной инструкции по битовой маске.

Например, мы можем использовать:

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 над каждым.