[Перевод] Решаем проблему качества в Factorio при помощи матриц

Я играю в Factorio как любой нормальный человек: для планирования фабрики пишу код матричных вычислений.

Но до этого мы ещё доберёмся. Если же вам не терпится, можете просмотреть мой новый онлайн-калькулятор.

Введение в Factorio и качество

Factorio практически стала создателем жанра видеоигр «строительство фабрики»: мы играем за персонажа, который собирает ресурсы и комбинирует их для изготовления всё более сложных изделий, которые, в свою очередь, позволяют заниматься ещё более сложным изготовлением. По описанию это походит на Minecraft и на многие другие игры-выживалки, но фабрикостроительные игры отличает от них упор на автоматизацию: очень скоро всё производство начинает выполняться не вручную персонажем, а всё большим количеством механизмов с различными видами логистики, например, конвейерными лентами, перемещающими изделия между механизмами. Разработчики некоторых игр этого жанра пошли ещё дальше и полностью избавились от персонажа игрока.

В процессе разблокировки новых внутриигровых «технологий» Factorio предоставляет всё больше механизмов, совершенствующих производство. Один из них — это модули: производственные машины, имеющие определённое (ограниченное) количество слотов для приёма различных видов модулей, влияющих на их характеристики: модули скорости ускоряют работу машины ценой повышенного энергопотребления, модули продуктивности повышают выпуск продукции из того же количества ингредиентов ценой скорости и энергии и так далее.

Выпущенное в 2024 году расширение Space Age добавило новые игровые механики, в том числе и качество (Quality): у каждого изделия и рецепта теперь есть пять уровней качества: ⚀ обычное, ⚁ необычное, ⚂ редкое, ⚃ эпическое и ⚄ легендарное. Каждый уровень (в зависимости от конкретного изделия) повышает характеристики, например, ускоряя производственные машины или повышая производительность модулей продуктивности. Высококачественные изделия можно изготавливать непосредственно из ингредиентов того же качества, однако единственный способ повышения качества — это применение новых модулей качества.

Модули влияют на вероятность Q повышения качества. Для каждого процесса изготовления вероятность повышения уровня качества после первого равна 10%. Мы можем составить таблицу вероятностей качества выпуска в зависимости от качества сырья:

Например, максимальная вероятность повышения качества в машине с четырьмя слотами для модулей равна 24,8%:

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

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

Чтобы фабрика не прекратила работу при переполнении складов, в Space Age появился переработчик (recycler): новая машина, уничтожающая любое изделие и возвращающая (обычно) 25% от его ингредиентов. Это позволяет игрокам проектировать «апсайклинговые» структуры, которые циклически производят и выполняют переработку с модулями качества, пока изделия не достигнут нужного качества ценой потребления гораздо большего количества ингредиентов:

Источник: Factorio blog

Инструменты планирования фабрики

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

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

Но я люблю планировать заранее: сколько машин каждого типа мне понадобится? Какой объём выпуска продукции можно ожидать? Где возникнут узкие места? Цикличность структур повышения качества сильно усложняет прикидки и вычисления при помощи старых инструментов.

Матричные вычисления

Представьте:

• Некоторые ингредиенты (например, железные плиты) поступают из какой-то произвольной производственной цепочки, в которой могут присутствовать модули качества. Каждый ингредиент имеет вероятность нахождения на одном из уровней качества: ⚀ обычное, ⚁ необычное, ⚂ редкое, ⚃ эпическое и ⚄ легендарное.

• Достаточное количество сборочных машин с каждым уровнем рецепта для изготовления из всех ингредиентов какого-то изделия (например, труб). У этих машин есть модули качества, поэтому вероятность повышения качества равна 10%.

Давайте изучим все возможные исходы для одного изделия:

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

(Символ пробела можно рассматривать как косвенное деление на 100.)

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

Теперь нашу систему линейных уравнений можно переписать в виде одного уравнения, где вектор умножается на переходную матрицу, соответствующую таблице из wiki:

Пограничный случай нулевой вероятности повышения качества означает отсутствие перехода между уровнями. Соответствующей переходной матрицей будет единичная матрица:

Может показаться, что мы почти ничего не добились, но теперь многоэтапный процесс можно выполнять при помощи последовательного умножения матриц. Например, добыча железной руды имеет вероятность повышения качества 7,5%, затем выплавка из них железных плит имеет вероятность 5%, а последующее изготовление труб — 10%. При отсутствии бонуса продуктивности мы получаем следующие вероятности конечных изделий:

Стратегии обеспечения качества

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

«Азартные игры»: оппортунистическое качество без переработки

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

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

Здесь применён один этап и отсутствует цикл, поэтому расчёт выполнить проще всего: ожидаемое распределение уровней изделий — это первая строка переходной матрицы Tquality(q) или таблицы вероятностей из wiki.

«Отмывка»: цикл с чистой переработкой

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

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

После преобразования этого вектора сумма новых вероятностей может оказаться меньше единицы. Подразумеваемый оставшийся случай — это полное отсутствие изделия. Например, переработчик, в 75% случаев производящий ничего, можно представить, умножив вектор вероятностей на 1/4.

Фильтрацию по качеству тоже можно представить в виде матричного умножения. В случае получения редкого и более высокого качества:

Общий эффект одной итерации цикла — фильтрация для сохранения изделия и переработки с качеством:

Теперь рассмотрим все возможные способы вывода изделия из системы:

• Если оно изначально имело достаточный уровень качества для мгновенного вывода: вектор вероятностей

  

• Оно прошло через цикл переработки ровно один раз:

  

• Оно прошло через переработку ровно дважды:

  

• и так далее.

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

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

Долговременный средний выход

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

Поэтому вместо вероятностей для отдельного изделия рассмотрим средний коэффициент в течение достаточно долгого периода времени для изделий, проходящих через определённую часть системы; это снова будет 5-компонентный вектор уровней качества. Эти векторы можно умножить на те же переходные матрицы, что и выше. В случае цикла с «отмывкой» соответствующими векторами будут:

• Подаваемые в систему изделия fresh с любым распределением качества; в этом случае на основании модулей качества добывающего бура.

• Изделия fromRecycling.

• Все изделия, проходящие через разделитель.

• Изделия extracted по уровню их качества, в этом примере редкому или выше.

• Изделия toRecycle с качеством q, которые не выведены из системы.

q и fresh мы будем считать фиксированными параметрами, а другие векторы — неизвестными, которые нужно найти.

Система сходится к динамическому равновесию, в котором для долговременных средних справедливы следующие уравнения:

Можно выполнить преобразование и подстановку:

Выполним транспонирование, чтобы получить векторы-столбцы вместо векторов-строк и привести к классическому виду:

Добавим новые обозначения:

Теперь у нас есть равновесие в виде системы линейных уравнений классического вида A·x=b, из которого можно при помощи метода Гаусса найти x. Из x можно легко вычислить splitter, затем toRecycle (чтобы знать количество требуемых переработчиков) и extracted (для получения общего выхода системы).

Если представленный выше пример системы масштабировать до добычи 100 единиц руды в секунду, то параметры будут такими:

А решение методом Гаусса — таким:

Выполнив преобразование из секунд, получим, что коэффициенты вывода близки к 90 в минуту для редкого качества, 9 в минуту для эпического и 1 в минуту для легендарного.

Другой пример:

• Добавляем в систему изделия fresh только обычного качества, теперь в какой-то произвольной единице:

  

• Перерабатываем с наилучшими доступными модулями качества: q=24,8%.

• Выводим из системы только изделия легендарного качества.

Решив уравнение, получим:

То есть в случае изделий, перерабатываемых сами в себя, «брутфорс»-отмывка потребляет в среднем

входящих изделий на каждый легендарный результат. Это соответствует коэффициенту, вычисленному другими исследователями. Требуемые мощности переработки почти в 4/3 раз больше от частоты поступления fresh.

«Апсайклинг»: цикл производства + переработки

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

Для большинства рецептов изготовления требуется несколько ингредиентов в разных количествах, но мы абстрагируемся от этого и в качестве базовой единицы наших измерений будем использовать «множество ингредиентов для одного производства». В этом примере каждая машина, производящая строительных роботов, может потреблять 4 электросхемы в секунду и 2 каркаса летающих роботов в секунду, но мы будем называть это «2 ингредиента в секунду».

То есть мы измеряем долговременные средние коэффициенты ингредиентов и изделий, каждое на пяти уровнях качества, но они встречаются только в отдельных частях системы, поэтому мы можем продолжать пользоваться 5-компонентными векторами без необходимости 10-компонентых вычислений. (По крайней мере, пока...)

Пример системы: новые ингредиенты доставляются роботами в синий сундук запроса, а выводятся легендарные изделия. В общем случае, мы можем представить ингредиенты или продукты с любым распределением качества, производимые где-то ещё и добавляемые в систему. Аналогично, мы можем решить выводить из системы изделия или ингредиенты (или и то, и другое) любого уровня качества. (Иногда полезнее, чтобы высокое качество имел ингредиент, а не изделие, но апсайклинг этого конкретного изделия может давать лучший выход, чем другие способы.)

То есть для ингредиентов у нас получатся следующие 5-компонентные векторы-строки:

• freshI добавляются в систему с любым распределением качества.

• Ингредиенты fromRecycling.

• totalI.

• extractedI по уровню качества, в этом примере любое.

• Ингредиенты toCraft для изготовления новых изделий.

А для изделий:

• freshP добавляются в систему с любым распределением качества.

• Изделия fromCrafting.

• totalP.

• extractedP по уровню качества, в этом случае легендарный.

• Изделия toRecycle.

freshI и freshP мы считаем фиксированными параметрами, а другие векторы будут неизвестными, которые нужно найти.

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

Мы учитываем productivityBonus производства, который в этом примере равен 0%, но может быть больше для некоторых производственных машин или с модулями продуктивности. Кроме того, вероятность повышения качества может быть разной при изготовлении и переработке (например, при изготовлении с модулями продуктивности или в зависимости от количества слотов модулей машины).

Чтобы сделать выражение короче, введём обозначения:

Система сходится к равновесию, где:

Можно выполнить преобразование и подстановку:

Давайте введём ещё пару обозначений:

Мы снова преобразовали задачу в стандартный вид A·x=b, где :

Нахождение x даст нам totalP, а подставив его в исходные уравнения равновесия, мы получим всё остальное.

В примере выше, отмасштабированном под произвольную единицу, параметры будут такими:

А решение по методу Гаусса — таким:

На практике, узким местом такой системы становится скорость производства изделий обычного качества: 360 в минуту. Поэтому давайте умножим всё на 360/toCraftunit⚀

В итоге, эта система производит в среднем почти 2 легендарных строительных робота в минуту, потребляя примерно 309 наборов ингредиентов (309 каркасов + 618 схем) в минуту.

Бонус продуктивности для некоторых изделий в Space Age можно повысить при помощи многократных исследований. В игре есть жёсткое ограничение в +300% бонуса, поэтому производство с последующей переработкой возвращает максимум то количество ингредиентов, с которого мы начинали, но не больше.

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

Наша модель прогнозирует следующее:

Неожиданно оказывается, что коэффициенты для промежуточных уровней качества одинаковы.

Максимальный бонус продуктивности позволяет превратить изделие обычного качества в легендарное совершенно без потери ресурсов ценой использования большого количества машин и модулей для получения существенного объёма выпуска.

«Космическое казино»: цикл повторной переработки астероидов

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

Три типа обломков (металлические, углеродные и оксидные) дают разные ресурсы; в разных частях солнечной системы частота их появления различается. Обломки астероидов можно «перерабатывать» ради вероятности получения другого типа (или ничего).

Если допустить, что для каждого рецепта есть достаточное количество дробильных машин, можно представить этот процесс математически в виде умножения вектора-строки на квадратную переходную матрицу 3×3:

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

На этот раз конвейеры будут транспортировать обломки любого из трёх типов, каждый на одном из пяти уровней качества, что даёт 15 возможных изделий. Мы представим это при помощи 15-компонентных векторов-строк и переходных матриц 15×15. Последние мы составим в виде блочных матриц, состоящих из девяти блоков 5×5:

Математика остаётся той же, что и для отмывки, если не считать более высокой размерности; в итоге мы получаем систему линейных уравнений A·x=b, где:

У дробильных машин есть два слота под модули, поэтому наивысшая вероятность повышения качества при переработке равна q=12,4%. У сборщиков астероидов нет слотов под модули, поэтому только собранные осколки всегда имеют обычное качество. Мы составим 15-компонентный вектор fresh из его 3 компонентов для коэффициента обычного качества каждого типа астероидов (металлического, углеродного, оксидного). Например, на орбите Наувиса:

Допустим, что мы выводим из системы только легендарные оксидные обломки, а всё остальное перерабатываем. Решение уравнения даёт два дополняющих 15-компонентных векторов-строк toReprocess и extracted, которые можно преобразовать в таблицы 3×5

Пример: на орбите Наувиса мы выводим из системы легендарные оксидные осколки и перерабатываем всё остальное:

Можно заметить следующее:

• С повышением уровня качества распределение типов астероидов быстро сходится к 1/3 на каждый. Распределение вводимых в систему fresh несущественно влияет на распределение обломков легендарного качества, проходящих через систему.

• При выводе одного типа легендарных астероидов выпуск легендарных примерно равен 1/71,5≈1,4% от общего вводимого fresh. Это гораздо лучше, чем примерно 1/2726 в случае «отмывки», то есть чистой переработки, поскольку при переработке обломков вводимое в систему сырьё уничтожается только в 20% случаев (при переработке изделий — в 75% случаев).

Другие стратегии

Существуют и другие способы получения качественных изделий, не совсем умещающиеся в перечисленные выше категории (особенно стоит отметить The LDS Shuffle), и я уверен, что игроки придумают новые. Но если из-за цикла вычислить их поведение становится сложно, можно использовать те же приёмы:

• Представить выпуск различных видов изделий в виде векторов.

• Представить линейные преобразования (изготовление, переработку, …) в виде матричного умножения.

• Представить динамическое равновесие в виде матричного уравнения.

• Решить уравнение, по необходимости с помощью метода Гаусса.

Создание интерактивного калькулятора

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

Я по привычке взялся за Rust. nalgebra отлично подходит для тех матричных вычислений, которые мы выполняем. В нём есть различные солверы систем линейных уравнений A·x=b, но они требуют, чтобы скалярный тип матричных и векторных компонентов были числами f32 или f64, а базовая библиотека при этом гораздо более обобщённая.

На практике, числа с плавающей запятой вполне подошли бы, но это аппроксимация с фиксированной запятой, поэтому на каждом этапе вычислений потенциально может добавляться погрешность. Разве не будет здорово получать точный результат, если это возможно? Размеры матриц и количество операций постоянно и относительно малы, поэтому оптимизировать скорость кода не требуется.

В конечном итоге, все операции представляют собой сложение, вычитание, умножение или деление, поэтому если все наши параметры рациональны, то таким же будет и результат. num_rational представляет рациональные числа в виде пары (обобщённых) целых чисел. Если понадобится, я могу воспользоваться библиотекой BigInt с бесконечной точностью, но оказалось, что встроенного i128 с проверками переполнения достаточно для матриц 15×15. (i64 достаточно для 5×5.)

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

Мой код на Rust можно компилировать на WebAssembly, но тогда пришлось бы:

• Создать также весь GUI на Rust + wasm. Это возможно, но инструментарий пока неидеален.

• Или создать GUI на JavaScript или TypeScript (воспользовавшись преимуществами качественных инструментов), связав его с wasm для выполнения вычислений. Но поскольку из-за большого количества параметров поверхность API оказывалась большой, поэтому реализация такой связи была бы не столь увлекательной.

Поэтому в конечном итоге я переписал всё на TypeScript. BigInt в него встроен, в Factoriolab уже есть хорошая опенсорсная библиотека rational, а написать обобщённую библиотеку для работы с матрицами не так сложно.

Что касается создания интерактивного GUI в браузере, то в последний раз я занимался подобным, когда jQuery ещё был новой хайповой технологией. Мне не хотелось изучать React, поэтому я остановился на такой схеме:

• VanJS для минимальной реактивности.

• Vite для манипуляций с TypeScript и сервером разработки с перезагрузкой при сохранении.

• Grebedoc для хостинга статических файлов.

В итоге factoqual.grebedoc.dev теперь предоставляет интерактивный GUI для планирования систем повышения качества. Его исходный код опубликован на codeberg.org/SimonSapin/factoqual.

Благодарности

В первую очередь меня вдохновили на этот проект посты Дэниела Монтейро о расчётах качества. Похожую работу проделали и другие авторы, в том числе Konage и контрибьюторы Factorio wiki. Но я считаю, что моё решение на основе уравнения равновесия представляет собой новый подход, в отличие от итеративной аппроксимации бесконечной суммы.