Итератор контейнера по связанным типам

@Kertis138 · Регистрация: 25.02.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте!

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Component {}
 
class Entity {
 // некоторый контейнер с Components
}
 
class EntityManager {
 //Некоторый контейнер с Entity
 
 template <typename T> struct identity { typedef T type; };
 
 template <typename ... Components>
 void each(typename identity<std::function<void(Entity entity, Components&...)>>::type f) {
  // ???
 }
}

То есть мне нужно получить только те Entity, у которых есть в компоненты с заданными типами.

C++
1
2
3
4
5
6
7
8
class Comp1 : public Component {}
class Comp2 : public Component {}
 
EntityManager es;
// init
es.each<Comp1, Comp2>([](Entity entity, Сomp1 &c1, Comp2 &comp2) {
  // тут уже сама логика работы с компонентами найденной сущности
});

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

@Azazel-San · 21.01.2019, 14:17

Сообщение от Kertis138

То есть мне нужно получить только те Entity, у которых есть в компоненты с заданными типами.

Но ведь у вас void each ничего не возвращает, для этого "получения". Обычно такимим штуками занимается система, если я верно все понял.

Сообщение от Kertis138

Стоит задача реализовать метод менеджера сущностей для перебора всех сущностей по типу хранящихся в нем компонентов.

Задача стоит, но ее цель не ясна..

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
template <typename... RequiredComponents>
class EntitySystem {
public:
    template <typename EntityManager>
    void update(EntityManager& manager) {
        if constexpr ((EntityManager::template has_component<RequiredComponents>() && ...)) {
            for (/*условие перебора*/) {
                update_entity(...);
            }
        }
    }
};

@Kertis138 · 21.01.2019, 14:23 **[ТС]**

Сообщение от Azazel-San

Но ведь у вас void each ничего не возвращает, для этого "получения". Обычно такимим штуками занимается система, если я верно все понял.

each - получает на вход лямбду с логикой работы с компонентами. Там я моуг и обновлять компоненты и выполнять другую логику

Добавлено через 1 минуту

Сообщение от Azazel-San

Задача стоит, но ее цель не ясна..

Это некоторый аналог реализации шаблона ecs. Причем я хочу сделать перебор объектов максимально быстрым.

Добавлено через 1 минуту

Сообщение от Azazel-San

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

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

Добавлено через 1 минуту

Сообщение от Azazel-San

template <typename... RequiredComponents>
class EntitySystem {

А если система может работать с несколькими наборами RequiredComponents?

@Azazel-San · 21.01.2019, 14:24

Сообщение от Kertis138

Там я моуг и обновлять компоненты и выполнять другую логику

Обычно таким занимается система.

Сообщение от Kertis138

Причем я хочу сделать перебор объектов максимально быстрым.

Битовые поля и маски, будет оптимальным решением.

Сообщение от Kertis138

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

Для определенных таких объектов может быть своя система, которая работает только с ними.

@Kertis138 · 21.01.2019, 14:28 **[ТС]**

Сообщение от Azazel-San

Обычно таким занимается система.

Да, я полностью с вами согласен.

Например, система хочет обработать все объекты, у которых есть компоненты с типами Comp1, Comp2

C++
1
2
3
4
5
6
7
class S1 : public System {
 void update(EntityManager es) {
    es.each<Comp1, Comp2>([](Entity entity, Сomp1 &c1, Comp2 &comp2) {
       // тут уже сама логика работы системы
    })
  }
}

Добавлено через 1 минуту

Сообщение от Azazel-San

Битовые поля и маски, будет оптимальным решением.

То есть при добавлении компонента в объект меняется битовая маска. А каким образом ее строить? Брать type_index компонента?

@Azazel-San · 21.01.2019, 14:35

Сообщение от Kertis138

А если система может работать с несколькими наборами RequiredComponents?

Можно и так я же описал:

C++
1
2
3
if constexpr ((EntityManager::template has_component<RequiredComponents>() && ...)) 
// где has_component - логика для перебора, ничего точнее подсказать не могу, 
// тк вы сами дали очень абстрактное описание

Добавлено через 2 минуты

Сообщение от Kertis138

Например, система хочет обработать все объекты, у которых есть компоненты с типами Comp1, Comp2

Я же верно понимаю вы хотите через лямбду перебрать каждый компонент на его привязаность к сущности?

@Kertis138 · 21.01.2019, 14:36 **[ТС]**

Сообщение от Azazel-San

Я же верно понимаю вы хотите через лямбду перебрать каждый компонент на его привязаность к сущности?

методы each внутри себя делает выборку нужных сущностей и уже только для нужных сущностей вызывает лямбду

@Azazel-San · 21.01.2019, 14:36

Сообщение от Kertis138

А каким образом ее строить? Брать type_index компонента?

Вариантов много. Смотря для чего, в целях обучения?

@Kertis138 · 21.01.2019, 14:41 **[ТС]**

Сообщение от Azazel-San

Вариантов много. Смотря для чего, в целях обучения?

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

Например, система SpriteRenderer работает только с теми сущностями, у которых есть компоненты - Sprite, Transformation

Добавлено через 43 секунды
Вот и стоит задача получения системами выборки сущностей по наличию в них компонентов определенного типа

@Azazel-San · 21.01.2019, 14:44

Сообщение от Kertis138

методы each внутри себя делает выборку нужных сущностей и уже только для нужных сущностей вызывает лямбду

Не проще делать для каждой сущности свою систему? Что бы избавится от такого.

@Kertis138 · 21.01.2019, 14:52 **[ТС]**

Сообщение от Azazel-San

Не проще делать для каждой сущности свою систему? Что бы избавится от такого.

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

Пример:
Нужно нарисовать процесс падения шарика с некоторой высоты.

C++
1
2
3
4
5
class Ball : Entity {....}
Ball *b = new Ball;
b->addComponent<Position>(x,y);
b->addComponent<Transform>();
b->addComponent<Texture>();

Далее в цикле (~60 раз в секунду) у каждой системы вызывается метод update(deltaTime)
И каждая система выбирает для себя нужные объекты, с которыми она может работать.
С Ball будет работать система Рендеринга, система просчета физики - уже 2 системы. А если я хочу добавить компонент с триггером обработки столкновения с землей, то появляется еще и 3я система.
Из за этого и не получается явно связать сущность с системой, потому что на одну сущность может быть много систем.
Помимо этого, есть более интересные случаи, когда новые сущности появляются в рантайме - система частиц (В данном случае постоянно геренируются и удаляется новые объекты со своей физикой и текстурами).

@Azazel-San · 21.01.2019, 15:03

Сообщение от Kertis138

Например, система SpriteRenderer работает только с теми сущностями, у которых есть компоненты - Sprite, Transformation

Ага, ну тогда делайте какой-то систем_менджер который управляет набором разных систем и делает выборку нужных для нужных сущностей с нужными компонентами.

Сообщение от Kertis138

Вот и стоит задача получения системами выборки сущностей по наличию в них компонентов определенного типа

А ну все верно, что вы меня путаете?)

@Kertis138 · 21.01.2019, 15:04 **[ТС]**

Попробую что нибудь работающее создать. Сюда скину решение, если что получится

@Kertis138 · 22.01.2019, 23:00 **[ТС]**

Получился первый прототип. Функционал там неполный (нет большинства функций, нет систем и нет событий).
Реализовал пока что только возможность получать объекты по связным типап. Но пока версия сырая.
Основная идея хранения и быстрого получения объектов - bitset.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <memory>
#include <vector>
#include <cstdint>
#include <bitset>
#include <cstdint>
#include <unordered_map>
#include <functional>
#include <iostream>
 
 
#ifndef MAX_ENTITY_COMPONENTS
#define MAX_ENTITY_COMPONENTS 5
#endif
 
namespace Engine {
    class EntityManager;
 
    class Entity {
        typedef uint64_t EntityId;
    public:
        Entity() = default;
 
        EntityId getId() const;
        bool operator==(const Entity &other) const;
        bool operator!=(const Entity &other) const;
 
        void destroy();
 
        template<class T, class ...Args>
        void assign(Args && ... args);
 
    private:
        EntityId mId;
        EntityManager* mpManager = nullptr;
        friend class EntityManager;
    };
 
    class Component {};
 
    class ComponentHandle {
        public:
        Component* c1;
 
        template<class C>
        C* get() {
            return static_cast<C*>(c1);
        }
    };
 
    class EntityManager {
        typedef std::bitset<MAX_ENTITY_COMPONENTS> ComponentMask;
        typedef size_t ComponentId;
        typedef std::unordered_map<ComponentId, ComponentHandle> EntityComponents;
    public:
        EntityManager();
        std::shared_ptr<Entity> createEntity();
        void destroy(Entity::EntityId);
 
        template<class T, class ...Args>
        void addComponent(Entity::EntityId,  Args ...args);
 
        template<class T>
        void removeComponent(Entity::EntityId);
 
        template <typename T> struct identity { typedef T type; };
        template <typename ... Components>
        void each(typename identity<std::function<void(Components*...)>>::type f) {
            auto neededMask = make_mask<Components...>();
 
            for(auto mask=mEntitiesMask.begin(); mask != mEntitiesMask.end(); mask++) {
                if (neededMask != (*mask & neededMask))
                    continue;
 
                Entity e;
                e.mpManager = this;
                auto id = static_cast<Entity::EntityId>(std::distance(mEntitiesMask.begin(), mask));
                e.mId = id;
                f(mEntitiesComponents[id][getComponentId<Components>()].template get<Components>()...); //Не очень красиво
            }
        }
 
 
        template<class C>
        ComponentMask make_mask() {
            ComponentMask mask;
            mask.set(getComponentId<C>());
            return mask;
        }
 
        template<class C1, class C2, class ...Components>
        ComponentMask make_mask() {
            return make_mask<C1>() | make_mask<C2, Components...>();
        }
 
 
 
    private:
        template<class T>
        ComponentId getComponentId();
    private:
        std::vector<ComponentMask> mEntitiesMask; //Наличие компонентов в каждом объекте
        std::vector<EntityComponents> mEntitiesComponents; //Компоненты для каждого объекта.
        std::vector<Entity::EntityId> mFreeEntityId; //Свободные ячейки при удалении объекта
        Entity::EntityId mEntityIndex;
        ComponentId mComponentIndex;
    };
}
 
template<class T, class... Args>
void Engine::Entity::assign(Args &&... args) {
    mpManager->addComponent<T>(mId, std::forward<Args>(args)...);
}
 
template<class T, class ...Args>
void Engine::EntityManager::addComponent(Entity::EntityId id, Args ...args) {
    auto componentId = getComponentId<typename std::remove_const<T>::type>();
    auto ch = ComponentHandle();
    ch.c1 = new T(std::forward<Args>(args)...);
    mEntitiesComponents[id].insert( { componentId, ch } );
    mEntitiesMask[id].set(componentId);
}
 
template<class T>
Engine::EntityManager::ComponentId Engine::EntityManager::getComponentId() {
    static auto v = mComponentIndex++;
    return v;
}
 
template<class T>
void Engine::EntityManager::removeComponent(Engine::Entity::EntityId id) {
    auto componentId = getComponentId<T>();
    mEntitiesComponents[id].erase(componentId);
    mEntitiesMask[id].reset(componentId);
}
 
using namespace Engine;
 
bool Engine::Entity::operator==(const Engine::Entity &other) const {
    return false;
}
 
bool Engine::Entity::operator!=(const Engine::Entity &other) const {
    return false;
}
 
Engine::Entity::EntityId Engine::Entity::getId() const {
    return mId;
}
 
void Engine::Entity::destroy() {
    mpManager->destroy(mId);
}
 
 
std::shared_ptr<Entity> EntityManager::createEntity() {
    auto entity = std::make_shared<Entity>();
 
    Entity::EntityId index;
    if (mFreeEntityId.empty()) {
        index = mEntityIndex++;
        if (mEntitiesMask.size() <= index)
            mEntitiesMask.resize(index+1); //+1? Оптимально ли?
        if (mEntitiesComponents.size() <= index)
            mEntitiesComponents.resize(index+1);
    } else {
        index = mFreeEntityId.back();
        mFreeEntityId.pop_back();
    }
    entity->mId = index;
    entity->mpManager = this;
    mEntitiesMask[index].reset();
 
    return entity;
}
 
EntityManager::EntityManager() : mEntityIndex(0), mComponentIndex(0) {}
 
void EntityManager::destroy(Entity::EntityId id) {
    mEntitiesMask[id].reset();
    //Удаление компонентов ToDo:
    mEntitiesComponents[id].clear();
    mFreeEntityId.push_back(id);
}

Вот пример:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "ecs/EntityManager.h"
 
class A1 : public Engine::Component {};
class A2 : public Engine::Component {};
class A3 : public Engine::Component {};
 
int main()
{
    Engine::EntityManager em;
    auto e1 = em.createEntity();
    e1->assign<A1>();
    e1->assign<A2>();
 
    auto e2 = em.createEntity();
    e2->assign<A1>();
    e2->assign<A3>();
 
    auto e3 = em.createEntity();
    e3->assign<A2>();
    e3->assign<A3>();
 
    em.each<A1, A2>([](A1*, A2*) {
        std::cout << "A1, A2" << std::endl;
    });
 
    em.each<A3>([]( A3*) {
        std::cout << "A3" << std::endl;
    });
 
    em.each<A1, A2, A3>([](A1*, A2*, A3*) {
        std::cout << "A1, A2, A3" << std::endl;
    });
}

На выходе верный ответ:
A1, A2
A3
A3

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

C++
1
2
3
4
//Имеем
std::bitset<N> mask;
std::vector<int, std::bitset<N>> container;
//Как выбрать МАКСИМАЛЬНО БЫСТРО все такие индексы - index из container, чтобы выполнялось условие (mask == (mask &container[index]).

Первое, что приходит на ум - это анализировать все системы при инициализации приложения и смотреть, какие группы std::bitset<N> они хотят получать в своей логике. А при добавлении элементов в container каким то образом делать вычисления для дальнейшей выборки.

Добавлено через 5 минут

Сообщение от Azazel-San

Можно и так я же описал:

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

Добавлено через 8 минут
Получается, что метод each работает от O(N).
Хочется получить O(1) при условии, что добавление + удаление компонента - это дополнительные вычисления.
Например:
Пусть система при инициализации выдвигает набор битовых масок (То есть по сути - это и есть определяющая объектов, так как объект является контейнеров компонентов).
Тогда пусть у нас будет вектор, где каждая ячейка - группа. А группа - это набор битовых масок от систем.
Получается, что при добавлении или удалении компонента (а это бывает не часто, значит не критично) мы определяем принадлежность объекта к группе.
В итоге each будет напрямую обращаться к нужным объектам без перебора всех элементов.
Единственно - расчитать принадлежность объекта к группе - это сравнение битовых масок, что может быть ен быстрым.
Что думаете по поводу такого варианта?

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@Kertis138 6 / 6 / 1 Регистрация: 25.02.2016 Сообщений: 342
	21.01.2019, 15:04 [ТС]
	Попробую что нибудь работающее создать. Сюда скину решение, если что получится 0