Привет, Хабр! Представляю вашему вниманию перевод статьи "ECS back and forth — Part 1 — Introduction" автора Michele skypjack Caini.

ECS back and forth

Часть 1 — Введение.

Когда я в первые узнал про архитектурный шаблон entity component system, я пошёл искать больше информации о нём в интернете. Но, к сожалению, тогда на эту тему не было пролито достаточно света, а ресурсов, где описывались бы разные подходы с их плюсами и минусами, не существовало. Почти каждые статья, пост, комментарии (существенная их доля) были об одной специфичной реализации и только слегка ссылались на другие примеры.

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

Почему я должен использовать ECS?

Старайтесь не быть одураченным тем, что говорят вокруг. Если вы работаете над AAA проектами на серьёзном уровне, главной причиной почему вы должны использовать такой серьёзный инструмент — это организация кода, а не (только) производительность. Конечно, производительность имеет не последнее значение, но хорошо организованная кодовая база бесценна, и с большинством игр у вас не будет проблем с производительностью, будь они написаны с использованием ОПП парадигмы либо с другой опциональной реализацией компонентного шаблона.

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

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

Введение

Для начала давайте разберёмся в том, что значит перейти с ООП в компонентный мир.

Грубо говоря, это вопрос разделения вещей. Представь все свои концепты(классы) объектов на плоскости. Здесь дварф, эльф, игровой персонаж, камень и так далее, все следуют друг за другом. И вот тут в нас остаётся только два способа разрезать это: горизонтально и вертикально.
Если вы будете резать вертикально, то получите сами концепты по себе. Другими словами, обычные ООП классы, ничего больше, ничего меньше.

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

Но как организовывать логику теперь?

Классическое ООП предлагает вам итерировать все объекты (представителей ваших классов), используя некоторый update метод. Если следовать нашему прошлому примеру, мы можем пройтись через все сущности и обновить их, как будто они колонки, работая с одной колонкой за раз.

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

Получилось ну уж слишком упрощённое описание, но надеюсь его будет достаточно для того, чтобы вы смогли прочувствовать разницу между классическим ООП и компонентно-ориентированным подходом.

ECS back and forth

Рассмотрим несколько известных путей реализации ECS.

В первой части этой серии статей, я опишу возможно менее привлекательный путь, но представляющий первый шаг к полноценному компонентному подходу. Несколько отличающуюся реализацию можно найти в великой книге Роберта Нистрома
«Game Programing Patterns». Вот ссылка на бесплатную веб-версию.

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

Но для начала, давайте погрузимся в детали, которые помогут в дальнейшем её описании.

Уникальные идентификаторы

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

Самым распространённое требование – это наличие уникальных во время выполнения программы идентификаторов компонентов. Позже мы узнаем какие проблемы они решают.

Существует множество методов генерации уникальных идентификаторов. Некоторые из них хорошо подходят для использования с библиотеками, другие — нет. Как бы там ни было, всегда можно смешать два или более методов для достижения обоих случаев.

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

Распространённый подход решения озвученной проблемы – family generator. Это смесь шаблонов и статических элементов, занимающие несколько строчек кода. Свободное ПО, использующее эту технику: entityx and EnTT.

Возможная реализация family generator.

class family {
    static std::size_t identifier() noexcept {
        static std::size_t value = 0;
        return value++;
    } 

public:
    template<typename>
    static std::size_t type() noexcept {
        static const std::size_t value = identifier();
        return value;
    }
};

Пример генерации уникального идентификатора для данного типа:

const auto id = family::type<my_type>();

Минус этого метода заключается в использовании статических локальных переменных и методов. Поэтому он не очень хорошо работает на некоторых платформах. Но, с другой стороны, он довольно прост в использовании и понимании.

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

С начала: ассоциативные массивы и иерархии

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

Проще говоря, объекты всё ещё существуют, но их типы в привычном нам виде каким-то образом замещаются наборами компонентов, содержащиеся в них.

Но как это работает на самом деле?

Банальный подход, который отлично справляется со своей задачей, предлагает превратить наш игровой объект в ассоциативный массив компонентов. Системы будут проходиться по всем игровым объектам и проверять, имеет ли текущий объект нужный набор компонентов, перед тем как начать работу. Здесь bitset может использоваться для ускорения фазы поиска.

Если вы предпочитаете не использовать ассоциативные массивы, то компоненты можно хранить в динамическом массиве, в векторе. Благодаря family generator уникальный идентификатор типа компонента представляет собой позицию в массиве, индекс. Благодаря этому мы не тратим время на поиск компонентов.

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

void my_nth_system(std::vector<game_objects> &objects) {
    for(auto &&object: objects) {
        if(object.has<position, velocity>()) {
            auto &pos = object.get<position>();
            auto &vel = object.get<velocity>();

            // ...
        }
    }
}

Плюсы этой реализации немногочисленны, но совершенно очевидны: её просто внедрить и поддерживать и её легко понять тем, кто приходит из ООП мира. Более того, она использует типичный список объектов, с которым мы знакомы из ООП.

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

Этот подход также обладает большим количеством минусов. Прежде всего, компоненты разбросаны по памяти и прежде, чем получить доступ ко всем компонентам одного типа, приходится делать несколько прыжков в ней. Однако самая большая проблема заключается в том, что вы никогда не знаете, какие игровые объекты обладают нужными компонентами, и, следовательно, вы должны проходиться по всем ним в каждой системе и проверять наличие нужных компонентов у объекта. Само собой разумеется, это всё совсем не приветствуется с точки зрения производительности. В реальности, такой подход может быстро ухудшить производительность для игр среднего размера, когда количество объектов растет.

Важная вещь, которую я не успел упомянуть – концепты ваших объектов больше не являются частью вашей кодовой базы. Вы заметили это? Больше не существует класса эльфа или сущности игрового персонажа. Теперь мы имеем простые игровые объекты, наполненные компонентами разных типов. Звучит интересно, не так ли? Несмотря на это, такое решение всё ещё находится на половине пути между ООП и полным компонентно-ориентированным подходом, мы уже можем оценить некоторые преимущества использования компонентов.

На пути к решению без использования объектов: сущности — это индексы

Следующий шаг на пути к полной компонентной модели – избавиться от игровых объектов.

В предыдущем примере игровые объекты были не более чем контейнерами для компонентов. Наши игровые объекты были определены как класс с небольшим интерфейсом, который облегчал работу с его составляющими. Компоненты были расположены в ассоциативном или динамическом массиве и каждый игровой объект имел свой набор компонентов. Должно быть довольно легко избавиться от этих обёрток и немного изменить компоновку, чтобы компоненты одного типа хранились вместе. Это будет наш следующий шаг на пути.

Сперва, нам необходимо дать имя нашим игровым объектам, и мы-то знаем, что выбор имени — одна из самых простых задач в программировании :). Поскольку ранее мы помещали игровые объекты в вектор, мы могли бы использовать индекс объекта в качестве его имени. Теперь первый объект имеет наименование 0, второй – 1, и так далее. Давайте назовём объекты сущностями, и мы имеем, что первая группа компонентов назначена сущности 0, а вторая группа компонентов назначена сущности 1.

Заметили в этом шаблон? Если мы перевернём проблему с ног на голову, то укладывая наши компоненты в упакованные массивы, один массив на каждый тип компонента, то на позиции 0 в каждом массиве будут лежать компоненты для сущности 0, на позиции 1 каждого массива будут лежать компоненты для сущности 1, и так далее. В общем, если мы имеем N сущностей и M разделённых массивов компонентов, то мы можем использовать саму сущность в качестве индекса для доступа к её данным в разных массивах.

У нас больше нет игровых объектов. Вместо этого, мы имеем сущности в виде чисел и экземпляры компонентов, каждый из которых размещен в своем собственном массиве. Идентификаторы сущностей также являются индексами, используемыми для извлечения экземпляров компонентов. Это более-менее вся идея, лежащая в основе entityx, довольно известной библиотеки ECS в C++.

Обычно к сущностям в этой реализации добавляется bitset для проверки наличия компонентов у них. Это решение ускоряет поиск и действует как обходной путь для другой проблемы. Рассмотрим случай, когда компонент C назначен сущности N > 0. В это случае массив для компонентов C будет изменён так, чтобы вместить по крайней мере N компонентов. Однако мы никогда не назначали C для сущности 0, хотя экземпляр уже существует в памяти. Как мы определим валидность компонента? Bitsets – это общий ответ на этот вопрос.

Одним из плюсов этой модели является то, что итерации выполняются довольно быстро, даже ещё быстрее, если bitsets используются для ускорения поиска.

Но, к сожалению, у этого подхода есть и некоторые недостатки. Очевидно, что мы теряем много памяти, в случае, когда массивы разряжены, и, по-видимому, нет простого способа избежать этого. Этот случай влечёт за собой так же менее очевидный недостаток, а именно: большое количество кеш-пропусков из-за того, что мы извлекаем из памяти также дыры, которые соседствуют с действующими компонентами. Еще одним минусом является то, что мы до сих пор не знаем, какие сущности обладают какими компонентами, и поэтому нам приходится пробегаться через их всех в каждой системе, чтобы проверить, соответствуют ли сущности требованиям. Использование bitset может смягчить этот аспект, но это не устранит проблему полностью.

Что дальше?

Я надеюсь, что это краткое введение помогло вам начать путешествие из ООП к компонентному миру. То, что мы видели до сих пор, хорошо подходит для игр малого и среднего размера, но не подходит, когда число объектов и компонентов растет, а производительность действительно имеет значение.

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

Дайте мне знать, если вам это помогло

Я надеюсь, вам понравилось то, что вы прочитали.

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

Спасибо.