Вступление

Всем привет, это моя первая статья на Хабр. Давно хотел попробовать что-то написать, но всё никак не решался, да и темы подходящей не было. Наконец тема подвернулась, и пришло время закрыть этот гештальт =)

ECS (Entity Component System)- архитектурный паттерн, применяемый в геймдеве.

В данной статье я опишу общий принцип "подкапотной" работы 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<T>
    {
        public static int Id
        {
            get;
            private set;
        }

        static ComponentMeta()
        {
            Id = ComponentIdCounter.Counter++;
        }
    }

То есть, у нас есть статический счётчик и дженерик мета компонента, которая в статическом конструкторе этот счётчик инкрементит. По этому индексу и можно получить нужный пул.

Наивная реализация

В первой реализации, на этом организацию данных я, в принципе, и закончил: каждая система имеет фильтр, состоящий из двух масок:

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

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

Оптимизация

Идея оптимизации заключается в том, что каждый фильтр должен иметь не только маску инклюдов/эксклюдов, но и массив отфильтрованных энтити, который будет обновляться каждый раз при добавлении/удалении компонентов. Что то отдаленно напоминающее вышеописанные архетипы.

Для этого заведем две вспомогательные структуры (одну для инклюда, одну для эксклюда) типа Dictionary<int, HashSet<int>>, в которых по айди данного компонента будут находиться сеты всех фильтров имеющих данный компонент:

Нужно было реализовать быстрое копирование всех данных, потому что мой пет проджект использует сеть, основанную на роллбэках (Это большая тема для отдельной статьи, есть 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 уже вполне себе продакшен-рэди и стоит попробовать его.

Ссылка на репку