Гибкая ECS с кастомными layout-профилями: как я строил ECSS внутри своего игрового движка

[kipar]

Было бы интересно посмотреть бенчмарки "плохого случая" - когда есть скажем 10к энтитей, у 5000 есть компонент А, у 5000 есть компонент B, но только у 100 есть и компонент и А и В. Насколько быстрой в этом случае будет итерация по сущностям содержащим и А и В. entt в этом случае предлагает связанные группы, другие неархетипные ecs на этом случае ломаются или вводят фильтры содержащие список сущностей.

[wagnerks]

Привет! Добавлю такой кейс и поисследую возможные оптимизации

у меня итерация идёт по первому компоненту из списка в for, и в таком кейсе будет 5000 итераций

Второй компонент может быть nullptr, это можно проверить простым ифом

[kipar]

у меня итерация идёт по первому компоненту из списка в for, и в таком кейсе будет 5000 итераций

Стандартная оптимизация - итерироваться по тому из компонентов, которых меньше. Тогда если в мире будет 5000 компонентов А и 200 компонентов B, то придется делать всего 200 итераций.
Но для "плохого случая" она не поможет, да.

[wagnerks]

привет
https://wagnerks.github.io/ecss_benchmarks/
добавил sparse iteration в бенчмарки, можете глянуть :)

[kipar]

// Velocity first = iterate smaller set (n/50), lookup Position

неидеально конечно, от "тру" ецс я бы ждал что она сама определит какой пул короче, ну и действительно "плохой" случай, когда итерации по наименьшему пулу недостаточно все-таки не рассмотрен.
Да, возможно он не всегда нужен - вполне может оказаться что в игре таких ситуаций и нет. Просто надо понимать что и entt (если там использовать группы компонентов) и flecs с ее архетипами уделают на этом случае ецс которая этим не озаботилась в разы если не на порядки.

[wagnerks]

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

[StepanStulov]

Видел во времена Adobe Flash фреймворки ECS-ные, где такое «пересечение» компонентов называлось “aspect”. Системы там работали не с конкретными типами компонентов, а с аспектами - множествами типов компонентов. Например физика работала с сочетанием трансформа и габаритов. А рендеринг с сочетанием трансформа и меша. И там было всё оптимизировано чтобы системы получали доступ именно с спискам аспектов а не к спискам компонентов. Это позволяло легко наслаивать системы друг на друга в определенном порядке. Название фреймворка уже не найду. Но мне понравилась гибкость. Маппинг был не 1 система к 1 типу компонента, а более сложная: 1 система к 1 аспекту как коллекции N типов компонентов. Очень гибко. Мне кажется движки типа Unity внутри как-то так и работают.

[domix32]

std::map<Transform> t;

главное чтобы вы понимали, что в таком виде оно не очень ecs. std::map представляет собой бинарное дерево, то есть ноды дерева расположены где-то в случайном месте памяти. ECS же старается сделать так чтобы одинаковые компоненты лежали как можно ближе друг дргу для cache locality. В классическом SoA оно выглядело бы как-то так

Transform t[];
PhysicsComp p[];
IsRenderable r[];
Mesh m[];

То есть некоторые линейные массивы, последовательная обработка которых отлично предсказывалась процессорным branch predictor. В случае map такого не будет происходить, т.к. обход бинарного дерева не будет проходить по последовательной памяти, а по веткам дерева. std::unordered_map или std::flat_map могут исправить эту ситуацию.

Ну и отдельно стоит заметить, что любой std::*map обычно принимает два шаблонных параметра - тип ключа и тип собственно элемента, так что ваш пример не соберётся.

Ну и обновление в ECS обычно происходит на уровне систем, а не на уровне энтитей.

for (auto [_,tran]: t) tran.tick(); // update transform system
for (auto [_,phys]: p) phys.tick(); // update physics system
/*the rest of systems*/

[wagnerks]

Привет!

Абсолютно верное уточнение что map это не array, сразу после блока с кодом я об этом пишу :)

Этот пример был призван проиллюстрировать реальный способ поиска компонента по его id, но естественно это не оптимальный подход.

Это cpp подобный псевдокод, он не должен собираться, он лишь показывает концепцию.

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

В следующий раз добавлю пометку "псевдокод", спасибо за фидбек!

[here-we-go-again]

А что есть почитать по теме, как делать правильно?

[wagnerks]

Я бы не брался говорить что есть прям правильный и неправильный путь

Есть оптимальные и нет.

Главное, на мой взгляд, в ecs- это организовать быструю итерацию по компонентам и быстрый доступ к данным.

Система это просто функция которая обновляет данные в компонентах. Сущность - просто хэндл, вокруг которого компоненты объединены.

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

Можно почитать документацию по entt или flecs, например, что бы получить какое то представление. У моей ecss тоже есть документация, ее можно найти в гитхабе. Это даст представление.

[StepanStulov]

Мне кажется ECS-ность не требует линейной укладки в памяти, хотя конечно фреймворки чаще делают так чем не так. Это просто архитектурная альтернатива OOP, чтобы линейное наследование «не мешалось под ногами» и у гейм-дизайнеров была возможность перекомбинировать компоненты не ломая хрупкие иерархии наследования. Есть вполне успешные ECS фреймворки на куче (C# Entitas, если я не ошибаюсь). Хотя конечно кто-то назовет их ECS-like, а не полноценными ECS. Но это уже серая зона. ECS это скорее архитектурный паттерн, тогда как линейная укладка в памяти это деталь некоторых имплементаций.

[domix32]

ECS придуман для линейной обработки. Линейная укладка данных просто ускоряет эту работу. Но это не значит, что все данные непременно линейные, просто для дальнейшей обработки обычно делают подготовку данных. Никто не строит деревьев для обработки, даже наоборот - уплощают всё что можно сделать плоским. В Quake например есть шаг с запросами к BSP-дереву, подготавливающий меши для рендеринга на экран. Но BSP сам по себе изначально построен как древо геометрии, но сами компоненты при этом остаются в плоской структуре - данные мешей топологически отсортированы и лежат в последовательном блоке памяти, а листья дерева указывают на сдвиги по этому массиву.

В случае с std::map такого не происходит и добавление новой ноды в дерево аллоцирует память в абсолютно произвольной памяти, что приводит как к фрагментации памяти, особенно если ещё есть и удаления, и замедлению доступа, т.к. придётся сделать больше непрямых вызовов. Именно поэтом в играх не используют стандартные нелинейные контейнеры, предпочитая заменять их на имплементации flat_map и flat_set - поведение такое же как и у деревьев, но память гарантированно остаётся линейной.

Есть вполне успешные ECS фреймворки на куче

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