Как искать объекты с конкретными компонентами в системе компонентов сущностей?

Question

Как искать объекты с конкретными компонентами в системе компонентов сущностей?

В моей текущей реализации я храню компоненты в
std::unordered_map< entity_id, std::unordered_map<type_index, Component *> >.

Так что, если системе нужен доступ к объектам с определенными компонентами, то какой наиболее эффективный способ доступа к ним.

Я в настоящее время есть 2 идеи:

1. перебирать карты и пропустить объекты, которые не имеют этих компонентов.
2. Создайте «mappers» или «views», которые содержат указатель на объект и обновляют их каждый раз, когда компонент назначается или удаляется из объекта.

Я видел несколько подходов с битмасками и т. Д., Но это не кажется масштабируемым.

Answer 1

Ваша ситуация требует std :: unordered_multimap.

Метод «find» возвращает итератор для первого элемента, который соответствует ключу в multimap. Метод equal_range возвратит вам пару, содержащую итераторы для первого и последнего объекта, соответствующие вашему ключу.

Фактически то, что unordered_multimap позволяет создавать, это база данных с ключом в памяти, которая хранит кучу объектов для одного и того же ключа.

Если ваши «запросы» будут более сложными, чем «дать мне все объекты с компонентом T» и превратить во что-то вроде «дайте мне все компоненты, у которых есть компоненты T и B одновременно», вам лучше подходит для создания класса, который имеет unordered_multimap в качестве члена и имеет кучу полезных методов для запроса материала.

Еще по теме:

• http://www.cplusplus.com/reference/unordered_map/unordered_multimap/equal_range/
• unordered_multimap - iterating the result of find() yields elements with different value (несколько связанный с этим вопрос - принятый ответ может быть полезным)

Answer 2

Как я сделать это включает в себя хранение индекса обратно к объект из компонента (32 бита). Это добавляет немного служебных данных памяти, но общая нагрузка на память компонента в шахте составляет около 8 байтов, что обычно не так уж плохо для моих случаев использования и около 4 байтов на сущность.

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

Например, если вы ищете объекты с двумя типами компонентов, Motion и Sprite, то мы начинаем с итерации через компоненты движения и установки связанных битов для объектов, которые им принадлежат.

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

Это дает вам пересечение множеств в линейное время и с очень маленьким m (очень, очень дешево работайте на итерации, поскольку мы просто отмечаем и проверяем немного - намного, намного, намного дешевле, чем хеш-таблица, например). Я могу на самом деле выполнить набор пересечений между двумя наборами с 100 миллионами элементов каждый в течение секунды, используя эту технику. В качестве бонуса, с некоторыми незначительными усилиями, вы можете заставить его вернуть объекты в отсортированном порядке для типов кэширования доступа, если вы используете битсет для захвата индексов объектов, принадлежащих двум или более компонентам.

Есть способы сделать это лучше, чем линейное время (Log(N)/Log(64)), хотя он становится значительно более привлекательным, когда вы можете фактически выполнить множество пересечений между двумя наборами, содержащими сто миллионов элементов каждый за миллисекундой. Вот подсказка: