Что у ECS под капотом
Вступление
Всем привет, это моя первая статья на Хабр. Давно хотел попробовать что-то написать, но всё никак не решался, да и темы подходящей не было. Наконец тема подвернулась, и пришло время закрыть этот гештальт =)
В данной статье я опишу общий принцип «подкапотной» работы ECS фреймворков и некоторые проблемы, с которыми столкнулся при написании своего.
Когда я только начал узнавать про ECS, всё это казалось очень красивым, но только на бумаге, и нужно было начать что-то на нём реально писать, чтобы на собственном опыте проверить всё, о чём пишут. Успел попробовать несколько фреймворков на разных движках и языках. В основном это был великолепный entt, который я прикручивал к Godot, и LeoECS на Unity. Родной Unity фреймворк я пробовать не стал, потому что, когда начинал своё знакомство, API у него менялось чуть ли не раз в месяц, что меня отпугнуло.
В общем, получил достаточно опыта в использовании ECS на практике, но меня всё никак не покидал вопрос о том, как же оно работает под капотом. Есть пара хороших блогов о разработке ECS (от автора entt — https://skypjack.github.io/ и от автора flecs — https://ajmmertens.medium.com/), но все они давали мне недостаточно понимания как это можно сделать самому. В итоге я решил что лучший способ что-то понять — сделать это самому, поэтому мне пришлось писать свою ECS, как завещал старина Бендер =)
Писать её было принято решение на C#, так как свою игру я делаю на Unity.
На тему того, что такое ECS и как его использовать есть много отличных статей (раз, два).
Но вот как ECS устроен внутри, статей маловато, а на русском языке я не встречал ни одной. Это и будет темой данного материала.
Доступ к данным
Основной сложностью в работе ECS является доступ к данным. Если бы в игровой логике был всего один компонент, то энтити могли бы быть просто индексами массива этих компонентов, но в реальных условиях всегда будет больше одного компонента. И если часть энтити будут иметь один компонент, часть — второй, и еще часть — их оба, и всё это будет идти вперемешку, то нужна какая-то хитрая схема доступа к данным, иначе ни о какой кэш локальности речи идти и не может. Из инфы, найденной в интернете, становится понятно, что есть два основных подхода: архетипы и спарс сеты (sparse sets). Первый используют, например, Unity и flecs. Второй — entt и, насколько я понимаю, LeoECS, и его же я решил выбрать для своей ECS.
Архетипы
Для начала кратко опишу своё понимание работы архетипов: архетип — это коллекция энтити с одинаковым набором компонентов. При добавлении/удалении компонента на энтити, она, и все её компоненты, переносятся в другой архетип. Каждый архетип содержит массивы всех своих компонентов и массив энтити, а их индексы совпадают, то есть любой компонент по определённому индексу будет принадлежать энтити по тому же самому индексу. Плюсы такого подхода в простоте параллелизации, а минусы в стоимости добавления/удаления компонентов, почему я и отказался от него, ибо, по своему опыту знаю, что часто бывает удобно использовать компоненты-тэги, которые могут висеть на энтити всего пару кадров и часто добавляться/удаляться.
Спарс сеты
Второй подход — спарс сеты. Структура данных, состоящая из пары массивов: внешний — разреженный массив индексов, внутренний — массив, собственно, значений. У такого спарс сета мы спрашиваем элемент по внешнему индексу, и затем по этому индексу ищется значение во внешнем массиве. Если оно равно -1 или внешний индекс выходит за пределы внешнего массива, значит такого элемента нет. В противном же случае мы получаем индекс для внутреннего массива. Таким образом мы можем хранить сами данные компактно, без «дырок» между ними, а с дырками лишь между индексами. Для этих целей можно было бы использовать хэш-таблицу с целочисленными ключами с открытой адресацией но, насколько мне известно, в C# Dictionary использует закрытую адресацию.
Общая структура
Есть класс EcsWorld, в котором хранится массив энтити системы и пулы компонентов.
Энтити представляет собой обычный инт, в котором при помощи операций битового сдвига хранится индекс энтити и, во второй половине, её поколение.
Пул компонентов в данном случае — это класс, реализующий интерфейс IComponentsPool, чтобы пулы компонентов разных типов можно было хранить в одной коллекции.
Таких классов у меня два: это, собственно, пул компонентов (спарс сет) и пул тэгов, представляющих из себя битовую маску.
Тэги (тут терминология может различаться от фреймворка к фреймворку) — это отдельный тип компонента, который не несёт никаких данных и его наличие/отсутствие является информацией само по себе. Как пример — часто использую DeadTag, чтобы игровые системы, например, ответственные за движение, не передвигали мёртвых NPC.
Инстанс такого объекта хранить нет смысла, поэтому я просто храню битовую маску, по которой можно определить наличие/отсутствие этого компонента.
Битовая маска самописаная, вместо BitArray из стандартной библиотеки c#, потому что он не удовлетворял моим требованиям (является ссылочным типом, не имеет методов быстрой проверки наличия или отсутствия всех заданных флагов для проверки инклюдов/эсклюдов, об этом далее).
Регистрация компонентов
Каждому типу компонента соответствует индекс, получаемый при помощи трюка со статическим конструктором, который я подсмотрел в LeoECS:
static class ComponentIdCounter
{
internal static int Counter = -1;
}
public static class ComponentMeta
{
public static int Id
{
get;
private set;
}
static ComponentMeta()
{
Id = ComponentIdCounter.Counter++;
}
}
То есть, у нас есть статический счётчик и дженерик мета компонента, которая в статическом конструкторе этот счётчик инкрементит. По этому индексу и можно получить нужный пул.
Наивная реализация
В первой реализации, на этом организацию данных я, в принципе, и закончил: каждая система имеет фильтр, состоящий из двух масок:
инклюды, то есть компоненты, которые обязательно должны присутствовать на энтити, чтобы она была обработана системой, и эксклюды — компоненты, которых на ней быть не должно.
В каждом тике система пробегалась по всем энтити и выбирала соответствующие, но производительность такого подхода оказалась, мягко говоря, неудовлетворительной.
Оптимизация
Идея оптимизации заключается в том, что каждый фильтр должен иметь не только маску инклюдов/эксклюдов, но и массив отфильтрованных энтити, который будет обновляться каждый раз при добавлении/удалении компонентов. Что то отдаленно напоминающее вышеописанные архетипы.
Для этого заведем две вспомогательные структуры (одну для инклюда, одну для эксклюда) типа Dictionary
Нужно было реализовать быстрое копирование всех данных, потому что мой пет проджект использует сеть, основанную на роллбэках (Это большая тема для отдельной статьи, есть ME.ECS, в котором роллбэки реализованы из коробки, но основной пойнт был сделать свой велосипед).
Поэтому было решено использовать именно индексы, а не сами ссылки на фильтры, потому что такие словари для разных копий мира остаются одинаковыми и копировать их не нужно, что существенно ускоряет копирование мира.
Каждый раз при добавлении компонента удаляем энтити из всех фильтров по индексу типа в словаре с экслюдами, добавляем компонент в пул и добавляем его во все фильтры в словаре с инклюдами. При удалении проводим тот же самый процесс, но наоборот.
Однако, то, что на энтити отсутствует или присутствует какой-то конкретный компонент, еще не гарантирует, что она полностью удовлетворяет условиям фильтра, поэтому добавил в EcsWorld массив масок, каждая из которых соответствует энтити и при добавлении/удалении энтити из фильтра сначала идёт проверка по маске.
А дальше уже дело техники: каждая система в конструкторе регистрирует фильтр (а можно и несколько), по двум битмаскам и получает от мира индекс нужного ей фильтра, и итерируется уже по коллекции отфильтрованных энтити.
class MySystem : EcsSytem
{
int filterId;
public MySystem(EcsWorld world)
{
filterId = world.RegisterFilter(
new BitMask(Component1.Id, Component2.Id),
new BitMask(Component3.Id, Component4.Id));
}
public override void Tick()
{
world.GetFilter(filterId).Iterate((entities, count) =>
{
for (int i = 0; i < count; i++)
{
//do stuff
}
});
}
}
(код немного упрощен в угоду читаемости)
Эпилог
За кадром осталось много нюансов, но цель была передать основную суть, да и статья и так получилась объёмной.
В дальнейших планах у меня реализовать систему сортированных групп, как в entt — там можно отсортировать наборы компонентов по определённым фильтрам, так чтобы энтити и компоненты, попадающие в этот фильтр, шли строго по порядку. Но в целом даже без этого получается выигрыш в производительности.
Также планирую написать ECS на архетипах, возможно когда-нибудь напишу об этом сюда.
Ну и под конец хочу уточнить, что мой проект был создан исключительно в учебных целях, и хоть я сам делаю игру на нём, остальным же советую использовать один из популярных фреймворков: например LeoECS или, если вам так же, как и мне, нужны роллбэки, — ME.ECS. Также ходят слухи, что юнитёвый DOTS уже вполне себе продакшен-рэди и стоит попробовать его.
Ссылка на репку
