Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
1

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

21.01.2019, 13:55. Просмотров 470. Ответов 13

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

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

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) {
  // тут уже сама логика работы с компонентами найденной сущности
});
Подскажите возможные варианты хранения сущностей и компонентов, чтобы максимально быстро извлекать нужные сущности по связным компонентам?
Находил довольно сложные реализации с битовыми масками, но не совсем понял саму суть.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.01.2019, 13:55
Ответы с готовыми решениями:

Итератор для контейнера
Собственно, интересует такой вопрос: &quot;Как создать собственный класс-итератор для контейнера?&quot;....

Итератор контейнера set
Здравствуйте! Каким образом можно изменить значение итератора set на n (кроме вызова ++ n раз)....

STL итератор на конец контейнера
Подскажите пожалуйста у меня задача сделать дерево и слизать интерфейс с STL std::map. Вопрос в...

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

13
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 14:17 2
Цитата Сообщение от 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(...);
            }
        }
    }
};
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 14:23  [ТС] 3
Цитата Сообщение от Azazel-San Посмотреть сообщение
Но ведь у вас void each ничего не возвращает, для этого "получения". Обычно такимим штуками занимается система, если я верно все понял.
each - получает на вход лямбду с логикой работы с компонентами. Там я моуг и обновлять компоненты и выполнять другую логику

Добавлено через 1 минуту
Цитата Сообщение от Azazel-San Посмотреть сообщение
Задача стоит, но ее цель не ясна..
Это некоторый аналог реализации шаблона ecs. Причем я хочу сделать перебор объектов максимально быстрым.

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

Добавлено через 1 минуту
Цитата Сообщение от Azazel-San Посмотреть сообщение
template <typename... RequiredComponents>
class EntitySystem {
А если система может работать с несколькими наборами RequiredComponents?
0
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 14:24 4
Цитата Сообщение от Kertis138 Посмотреть сообщение
Там я моуг и обновлять компоненты и выполнять другую логику
Обычно таким занимается система.
Цитата Сообщение от Kertis138 Посмотреть сообщение
Причем я хочу сделать перебор объектов максимально быстрым.
Битовые поля и маски, будет оптимальным решением.
Цитата Сообщение от Kertis138 Посмотреть сообщение
Если есть много систем и каждая хочет работать только с определенными объектами, у которых есть нужные компоненты, то появлется задача поиска таких объектов.
Для определенных таких объектов может быть своя система, которая работает только с ними.
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 14:28  [ТС] 5
Цитата Сообщение от 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 компонента?
0
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 14:35 6
Цитата Сообщение от Kertis138 Посмотреть сообщение
А если система может работать с несколькими наборами RequiredComponents?
Можно и так я же описал:
C++
1
2
3
if constexpr ((EntityManager::template has_component<RequiredComponents>() && ...)) 
// где has_component - логика для перебора, ничего точнее подсказать не могу, 
// тк вы сами дали очень абстрактное описание
Добавлено через 2 минуты
Цитата Сообщение от Kertis138 Посмотреть сообщение
Например, система хочет обработать все объекты, у которых есть компоненты с типами Comp1, Comp2
Я же верно понимаю вы хотите через лямбду перебрать каждый компонент на его привязаность к сущности?
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 14:36  [ТС] 7
Цитата Сообщение от Azazel-San Посмотреть сообщение
Я же верно понимаю вы хотите через лямбду перебрать каждый компонент на его привязаность к сущности?
методы each внутри себя делает выборку нужных сущностей и уже только для нужных сущностей вызывает лямбду
0
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 14:36 8
Цитата Сообщение от Kertis138 Посмотреть сообщение
А каким образом ее строить? Брать type_index компонента?
Вариантов много. Смотря для чего, в целях обучения?
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 14:41  [ТС] 9
Цитата Сообщение от Azazel-San Посмотреть сообщение
Вариантов много. Смотря для чего, в целях обучения?
В целях обучения хочу написать программу для моделирования 2д процессов. Выбрал шаблон ecs.
По сути, логика очень похоже на логику работы игровых движков.
Есть различные системы, в которых заложена вся логика работы приложения. Сущности и компоненты - только контейнеры.
Каждая система работает только с определенными объектами.

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

Добавлено через 43 секунды
Вот и стоит задача получения системами выборки сущностей по наличию в них компонентов определенного типа
0
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 14:44 10
Цитата Сообщение от Kertis138 Посмотреть сообщение
методы each внутри себя делает выборку нужных сущностей и уже только для нужных сущностей вызывает лямбду
Не проще делать для каждой сущности свою систему? Что бы избавится от такого.
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 14:52  [ТС] 11
Цитата Сообщение от 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я система.
Из за этого и не получается явно связать сущность с системой, потому что на одну сущность может быть много систем.
Помимо этого, есть более интересные случаи, когда новые сущности появляются в рантайме - система частиц (В данном случае постоянно геренируются и удаляется новые объекты со своей физикой и текстурами).
0
Mental handicap
1241 / 619 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
21.01.2019, 15:03 12
Цитата Сообщение от Kertis138 Посмотреть сообщение
Например, система SpriteRenderer работает только с теми сущностями, у которых есть компоненты - Sprite, Transformation
Ага, ну тогда делайте какой-то систем_менджер который управляет набором разных систем и делает выборку нужных для нужных сущностей с нужными компонентами.
Цитата Сообщение от Kertis138 Посмотреть сообщение
Вот и стоит задача получения системами выборки сущностей по наличию в них компонентов определенного типа
А ну все верно, что вы меня путаете?)
1
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
21.01.2019, 15:04  [ТС] 13
Попробую что нибудь работающее создать. Сюда скину решение, если что получится
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 319
22.01.2019, 23:00  [ТС] 14
Получился первый прототип. Функционал там неполный (нет большинства функций, нет систем и нет событий).
Реализовал пока что только возможность получать объекты по связным типап. Но пока версия сырая.
Основная идея хранения и быстрого получения объектов - 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 будет напрямую обращаться к нужным объектам без перебора всех элементов.
Единственно - расчитать принадлежность объекта к группе - это сравнение битовых масок, что может быть ен быстрым.
Что думаете по поводу такого варианта?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.01.2019, 23:00

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Итератор контейнера внутреннего класса шаблона
Следующий код компилируется: struct A { struct B {}; vector&lt;B&gt; vec; vector&lt;B&gt;::iterator...

Вывод контейнера указателей через потоковый итератор
Доброго дня всем. Собственно: std::list&lt;int*&gt; list; list.push_back(new int(45));...

Как сделать, чтобы итератор указывал на определенный элемент контейнера?
как сделать, чтобы итератор указывал на, допустим, пятый элемент контейнера (вектора)

В шаблонном классе, один из параметров которого контейнер, объявить итератор этого контейнера
Собсно #include &lt;windows.h&gt; #include &lt;iterator&gt; #include &lt;vector&gt; using namespace std; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.