Магия, бережная работа с объектами/компонентами и никакого ECS.
Разработчик Factorio поделился некоторыми подробностями работы внутренних систем, в частности, рассказал про ECS.
Большая часть игры не использует никакого подобия entity component system. ECS отлично подходит, когда нужно применить некоторое преобразование к набору данных независимо от каких-либо других переменных. К примеру, добавить вектор движения к текущей позиции. Но если у вас 5-10 переменных связаны со сменой позиции, то толку от ECS не будет.
Примером этого являются логистические и строительные роботы. У них есть много разных условий:
Хватит ли энергии у робота, чтобы совершить полное движение?
Вышла ли цель за пределы зоны логистической сети, и робот должен отменить задание, которое ему было приказано?
Есть ли вообще у него работа, которую он должен выполнять, или он просто ждёт команды?
Общая проблема такова: все эти проверки используют данные, характерные для логистических роботов. Если бы робот использовал «компонент положения/движения», этот компонент не имел бы понятия ни об одном из этих условий. Можно попытаться включить эти условия в сам компонент, но он вряд ли будет очень читабельным и, вероятно, будет не очень по производительности.
Боевая система использует два вида снарядов: хитсканы и проджектайлы.
Для отрисовки логика прогоняет видимую область экрана в несколько потоков, находя, что нужно отобразить, и собирая информацию, которая позже отправляется на GPU.
Основные моменты, благодаря которым в Factorio всё хорошо с производительностью:
Система быстрого сна/пробуждения, когда сущностям не нужно выполнять работу. Когда объект «засыпает», то он полностью исключается из цикла обновлений, пока что-то внешнее снова его не включит. Время сна/пробуждения O(1). Большинство вещей большую часть времени в ожидании изменения состояния. Например: если в сборочной машине заканчиваются ингредиенты, она просто выключается. Как только что-то добавляет ресурсы, действие помещения предметов в инвентарь уведомляет машину о том, что они были добавлены, что «пробуждает» машину.
В худшем случае никакая часть логики обновления не может превышать O(N); если обновление 5 000 машин занимает 1 миллисекунду, то 10 000 должно занять максимум 2 миллисекунды. В идеале менее 2 миллисекунд, но это редко возможно.
Уменьшение работы с кусками оперативки, которые необходимо тыкать каждый тик. Процессоры очень быстрые в наши дни, и основными ограничителями в большинстве игр-симуляторов являются загрузка памяти в CPU и выгрузка обратно в ОЗУ.
Касательно пробуждения/засыпания, используют свою реализацию doubly linked circular intrusive list:
Обновляемые объекты сами по себе являются нодами в списке, поэтому ноды не нужно аллоцировать или освобождать при добавлении или удалении объекта из списка.
Поскольку это двусвязный список, объект может за константное время проверить, прилинкован ли он в данный момент, и может за константное время отлинковать себя (взять предшествующую ноду и линкануть на следующую, взять следующую и линкануть на предыдущую, а себя в nullptr).
Поскольку список является закольцованным, «конец» всегда является самим списком, что означает, что вы можете добавлять и удалять во время итерации и всегда будете знать, когда дошли до конца.
Тестирование показало, что итерация связанного списка не медленнее, чем итерация вектора указателей.
Комментарии (54)
ksbes
25.05.2023 11:16+6Проджектайлы — снаряды, которые фигак-фигак и в продакшн!
(можно не исправлять — хорошая "описка по Фрейду")А так спасибо за статью! Интересно, но маловато
Suvitruf Автор
25.05.2023 11:16+1Я вообще думал это как пост опубликовать, но не влезает. В итоге тексты такого формата для постов слишком большие, а для полноценной статьи маловато, да =/
freeExec
25.05.2023 11:16+9Поскольку список является закольцованным,… всегда будете знать, когда дошли до конца.
Это блин как, одно следует из другого? Вообще этот пункт какая-то дичь.
bogolt
25.05.2023 11:16"Because the list is circular the 'end' is always the list itself which means you can add and remove while iterating and always know when you iterated to the end. "
Хз как у них это работает, вероятно надо смотреть имплементацию этого списка https://www.boost.org/doc/libs/1_67_0/doc/html/intrusive/list.html
osmanpasha
25.05.2023 11:16+2я так понял, список - это ссылка на первый элемент. И когда при обходе ссылка на следующий элемент равна самому списку (=первому элементу), значит, все, конец.
mayorovp
25.05.2023 11:16Не понимаю как фразу "the 'end' is always the list itself" можно понять иначе чем то, что сам список является своим последним элементом (так называемый список с заголовком).
domix32
25.05.2023 11:16указатель на хвост/конец списка является списком. Если следующий хвост пустой - то мы закончили пробег. Ну то есть это происходит из свойств односвязного списка.
DmitryKoterov
25.05.2023 11:16Это закольцованный двусвязный список: последний элемент ссылается next’ом на самый первый, а первый - prev’ом на самый последний. Так же было сделано в первых Думах.
wataru
25.05.2023 11:16+4Объект "список" также как и все остальные объекты, имеет ссылку на следующий/предыдущий. Когда список пуст, этот объект ссылается на сам себя в обе стороны. Когда список не пуст, этот объект там лежит в качестве начала и конца.
Я так понял, список сам себя итерирует. И вот когда элемент в списке стал равен this — дошли до конца.
gdt
25.05.2023 11:16Я думаю, что начав обход из ноды А - придя в ноду А опять будет очевидно, что весь список обошли до конца.
ksbes
25.05.2023 11:16+3Не очевидно, если мы произвольно вставляем/удаляем ноды во время обхода. Т.е. мы могли сначала удалить эту ноду А, а затем её вставить где-то в середине.
lain8dono
25.05.2023 11:16+1А что на счёт современных ECS с архитипами? Просто это на самом деле звучит, как некое подобие, но без сахара и с использованием двусвязанных списков без какой либо причины. Полагаю, многопоточность тоже требует некоторого ручного труда. По крайней мере нет возможности получить некоторую многопоточность в комплекте с ECS.
domix32
25.05.2023 11:16Про архетипы сложно что-то сказать, а многопоток для ECS для параллельных систем кажется вообще не проблема. А списки нужны для того чтобы быстро переносить энтити между системами и фильтровать объекты, которые сами находятся где-то в сплошном массиве в другом месте и не тратить время на ветвления, потому что предиктору процессора такое не очень нравится. Подход filter -> map -> filter -> map получается более производительным в таком случае.
lain8dono
25.05.2023 11:16Про архетипы сложно что-то сказать
Архетипы позволяют избавиться от цепочек filter-map. Это о том, чтоб НЕ хранить все компоненты сущностей в едином массиве. Для каждого сочетания компонентов своя хранилка. Профит в линейном доступе для части случаев. Улучшает производительность за счёт лучшего попадания в кеши процессора. Это помимо очевидного отсутствия необходимости итерировать по тем частям памяти, которые не содержат нужных компонентов.
а многопоток для ECS для параллельных систем кажется вообще не проблема
Не кажется. Две системы, которые не имеют зависимостей друг от друга, могут работать параллельно. Более того. Это делается автоматически при грамотно сделанном API. Плюс разумеется внутри системы итерирование тоже может быть параллельным.
domix32
25.05.2023 11:16Для каждого сочетания компонентов своя хранилка
Если речь про СОЧЕТАНИЯ компонентов, то звучит несколько подозрительно. В классической ECS каждый вид компонента хранится в отдельном массиве. Хотя возможно для случая, когда нужно делать поиск по компонентам (как Query у Bevy), то возможно это как раз про это.
lain8dono
25.05.2023 11:16Да, именно про сочетания. И bevy_ecs вполне неплохой пример такого (если смотреть на эргономику, то как минимум один из лучших). Как впрочем и ещё штук пять ECS на Rust (много их наклепали со времён specs). Хотя в bevy_ecs есть ещё хранение компонентов в HashMap (случай для редких компонентов).
wormball
25.05.2023 11:16+4Как Factorio умудряется работать без лагов с таким числом элементов на экране
А вот у меня обратный вопрос. Как Factorio умудряется тормозить на gt1030? В каком-нибудь старкрафте объектов на экране было ненамного меньше, так он на 80486 превосходно шёл.
ksbes
25.05.2023 11:16+12Потому что тормозит большей частью не на отрисовке, а на симуляции мира. Это на карточку не особо перекинешь.
wormball
25.05.2023 11:16Ну не знаю, у меня "мир" был с гулькин нос, по крайней мере по сравнению с тем, что папашки на ютубе показывают. Процессор xeon x3470.
nidalee
25.05.2023 11:16Скорее всего производительность на ядро или кеши подкачали. Для энтузиастов с мега-базами на десятки тысяч SPM даже составляют графики, на чем нынче хорошо и годно играть. Вот тут еще недавнее обсуждение.
Проблема, впрочем, не уникальная. В Satisfactory у хоста в мультиплеере тоже к концу игры FPS проседает до <20. В X4 Foundations на станциях вообще не часто бывает больше 30 FPS… На 5950Х и 4090. Загрузка процессора при этом — 1%. То самое одно ядро.
Volodichev
25.05.2023 11:16Основные расчёты в факторио идут на процессоре и за пределами экрана, поэтому мощность видеокарты имеет малое значение. Да и единиц расчёта на порядки больше, чем в старкрафте.
zebralight
25.05.2023 11:16+4что вы называете тормозами?
у меня конфиг 9100f+gt1030(ddr5)+16GB RAM - сейчас провел тест в базе с 20к логистических и 60к строительных роботов (2к и 13к сейчас активны), перерабатывается по 30к железа и меди в минуту. это для понимания размеров базы. настройки максимальные, экран 1080р. при этом игра выдает 140+ фпс.
возможно, на слабых ноутбуках со встроенными интеловскими видеокартами будут лаги в поздней стадии игры на огромных базах, но не на десктопах.
и да, игра больше зависит от процессора, ГПУ там почти не нужен, поэтому и 1030 отлично смотрится тут.
wormball
25.05.2023 11:16Так я нуб несчастный, сейчас посмотрел сохранение — роботов меньше трёх тысяч. Процессор xeon x3470. Соответственно, pci-e 2.0.
при этом игра выдает 140+ фпс.
У меня фпс больше 60 не поднимается. И когда тормозило, то опускалась либо цифра фпс, либо фпс и упс одновременно.
возможно, на слабых ноутбуках со встроенными интеловскими видеокартами
Вот у меня сейчас ровно такой (i3-1115G4), на нём не тормозит. Хотя я и не играю, быть может, ежели буду активно играть, то снова станет тормозить. Ну или попросту в новых обновлениях исправили.
mayorovp
25.05.2023 11:16Проверьте доступную память, не закончилась ли она. Если играете на винде, учитывайте не только занятую память, но и зарезервированную — несмотря на описание, винда не очень охотно избавляется от этих страниц.
Пока у меня было мало памяти, мне приходилось держать
RAMMap -Etна хоткее во время игры в факторию.
zebralight
25.05.2023 11:16ноутбук на старом 6200u, в 1080p на низких настройках графики (чтобы в ГПУ не упиралось все же), выдает 30фпс, что плюс-минус играбельно, учитывая стадию игры.
вы может играли много лет назад - тогда да, в игре было куда меньше оптимизировано и требовалось железо мощнее. ну и да, чем больше ОЗУ, тем лучше.
kahi4
25.05.2023 11:16+2А я вот на свитче играл последний раз. Размер карты точный не помню, но ракеты запускались примерно за минуту (+ я сделал супер
глупостьшину на которой было вообще все, что производилось), но Нинтендо свитч свой собственный Nintendo store без лагов отобразить не может, а факторио бегало довольно бодро, в общем -- производительность впечатлила для того, что, по сути, является не самым производительным телефоном.
saboteur_kiev
25.05.2023 11:16Эмм, вообще-то как раз в те времена можно было четко заметить разницу в скорости производительности, когда играешь один против 7 компов в начале игры и в середине, когда уже дошло до лимита юнитов у каждого противника.
А если играть по сети - так вообще тормоза.
Chaos_Optima
25.05.2023 11:16+41Текст статьи вообще не отвечает на вопрос заголовка. Не сказано почему конкретно ECS не подходит, ни что взамен используется.
Для отрисовки логика прогоняет видимую область экрана в несколько потоков, находя, что нужно отобразить, и собирая информацию, которая позже отправляется на GPU.
Как они это делают? используют квадтри или ещё какие оптимизации
Уменьшение работы с кусками оперативки, которые необходимо тыкать каждый тик.
Как они этого добились?
Про список вообще ничего не понятно, абсолютно бесполезная статья.
serginho
25.05.2023 11:16+18Читая последние дни Хабр, закрадывается ощущение, что статьи пишутся способом типа "ChatGPT, напиши статью для хабра на основе вот этой статьи"
AllexIn
25.05.2023 11:16+2+100500
Я вроде и клеточные автоматы много раз писал, и моды к крафт играм схожим с Factorio, и с компонентными системами работал.
А из статьи не понял почти ничего.
Tirael12
25.05.2023 11:16+6Где тут диз ставить статье?
У factorio много лет выходит их dev blog по пятницам и там они в деталях рассказывают какими усилиями и как они делают незамерзающую сетевую игру, как добились оптимизации по интерфейсу, как хитрят со спрайтами - на каждое разрешение - свои, как сделали production pipe line от серверов исходников к серверам сборки до тестирующих серверов (да-да, там есть внутриигровые тесты, например рай перфекционист-разработчика - смотреть какие дрова пришлось поломать чтобы наладить семафоры и маршрут путей поездов) и до серверов выгрузки (один на сайт, один в стим, и еще добавились для выгрузки для ps4 и др платформ).
Без описания всего этого - как именно они добились такой скорости в производительности - статья ни о чем!Suvitruf Автор
25.05.2023 11:16Если речь про офф блог, то уже давно постов нет.
1dNDN
25.05.2023 11:16+3Потому что разработка игры завершена, она релизнулась
Suvitruf Автор
25.05.2023 11:16Я про то, что разборы обычно делаю недавних постов/статей/видео. В принципе, если что-то из старого ещё в нашем сегменте никто не публиковал, то можно и что-то из старого перевести ????
nidalee
25.05.2023 11:16+2Не совсем. В поте лица работают над дополнением. Но поскольку раскрывать его содержимое не хотят (<...> We still don't want to be specific about many things, not even the expansion name <...>) — в дев блоги ничего не пишут.
wataru
25.05.2023 11:16+2Диз можно статье поставить сразу под ней: там есть строка со стрелочками вниз и вверх. Чуть ниже плашка с автором, там можно проголосовать в карму, не перепутайте.
Helltraitor
25.05.2023 11:16+3Но если у вас 5-10 переменных связаны со сменой позиции, то толку от ECS не будет
Почему? Берем связанные переменные и меняем их в System
ECS отлично подходит, когда нужно применить некоторое преобразование к набору данных независимо от каких-либо других переменных.
ECS предназначен для эффективной работы с множеством сущностей, причем они определяются наборами компонентов. Внутри самой системы это хорошо паралелится за счет однородности данных (все, что меняем берем вместе и спокойно меняем, а все остально еще проще обработать)
ИМХО, автор игры не справился с ECS или решил просто не использовать ее. Это превосходное, но сложное решение, которое стоит попробовать каждому игроделу
saboteur_kiev
25.05.2023 11:16+1Двусторонние списки использовали еще в прошлом веке.
Я вот не понимаю какие проблемы с обработкой тысячи объектов в нормальной десктопной игре могут быть.
Точнее не понимаю почему в статье перформанс связывают именно с двухсторонним списком.
Tsimur_S
25.05.2023 11:16+1Я вот не понимаю какие проблемы с обработкой тысячи объектов в нормальной десктопной игре могут быть.
Тысяча конвееров это где то самое-самое начало игры.
Точнее не понимаю почему в статье перформанс связывают именно с двухсторонним списком.
В статье, даже вот в этом переводе, двухсторонний список связывают с пробуждением/засыпанием этих объектов за o(1) время и без аллокаций памяти. А само наличие пробуждения/засыпания объектов уже связывают с перфомансом.
wataru
25.05.2023 11:16+1Я вот не понимаю какие проблемы с обработкой тысячи объектов
Надо обработать всю физику за время одного кадра, ведь надо новые координаты отобразить.
Если хотя бы в 60 кадров метиться, а все-все связанное с графикой происходит параллельно на соседнем ядре, то надо в 16мс все запихнуть. 4ггц — это 4 миллиарда тактов в секунду, или 64 миллиона тактов на кадр. Современные процессоры более одной операции за такт выполняют, но и операции занимают более одного такта. В среднем можно считать 1 такт = одна операция. 64 миллиона операций — это не так уж и много. Если где-то естьO(n^2)— то 8000 объектов уже их все съедят только по одной операции на пару.Даже без квадратичных алгоритмов, у вас всего-то 10000 операций на каждый объект. Ясно, что какая-нибудь сборочная машина считается быстро, а вот на ленте могут быть тысячи объектов. Жуки должны рассчитывать путь по карте, и вообще AI — сложная штука. Инсертеру надо понять, есть ли свободное место в конце — это надо знать какая там лента, надо ее опрашивать. Семафоры должны уведомить всех соседей о статусе жд полотна.
Понятно, что можно распараллелить что-то, но тут возникают задержки на синхронизацию потоков, да и ускорение это даст в 2-4 раза максимум. Т.е. сможете вы не тысячи, а 20 тысяч объектов в 60фпс уложить. Не на порядки ускорение.
anonymousmaharaj
Анапасик, и тут ты.
Suvitruf Автор
????
IsUnavailable
Перепись dtf'еров)