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

Проблема с суши-конвейером

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

Что же происходит?

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


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



До



После

Если тайл перед предметом не пуст, мы пока не можем передвинуть предмет, но, возможно, его можно будет передвинуть на следующей итерации. Например, предмет «A» на рисунке ниже не может переместиться, пока не сдвинется предмет «B», и это может занять несколько итераций.


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

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



До



После

Вот псевдокод:

do
    set MADE_PROGRESS to false
    for each item, I
        if I has not already moved
            let B be the belt under I
            let B' be the belt B outputs to
            if B' has no item
                move I from B to B'
                mark I as moved
                set MADE_PROGRESS to true
while MADE_PROGRESS is true

А вот визуализация полного выполнения алгоритма:

Пограничный случай Factorio

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


Ой-ёй!

Устраняем проблему при помощи оптимизма

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

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

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



До



После

Аналогично, если предмет заблокирован другим недвижимым предметом, то он тоже не может двигаться. После того, как мы пометим предмет красным «X», предмет перед ним тоже должен быть помечен.



До



После

Этот новый алгоритм тоже выполняется, пока не достигнет фиксированной точки. Затем все предметы без красного «X» могут быть перемещены вперёд.

Если попробовать этот алгоритм на кольцевом конвейере, то вы заметите, что он завершается, не расставив ни единого «X»! Но это правильно: все предметы на конвейере будут перемещаться по нему, потому что ни один из них не оказался недвижимым.

Слияния

Прежде чем показывать псевдокод, нужно разобраться с ещё одним аспектом. Что произойдёт при объединении двух или трёх конвейерных лент, как показано на рисунке ниже?


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

Мы можем исправить второй алгоритм, задав каждому из объединяемых конвейеров приоритет. Тайл конвейера с меньшим приоритетом будет считаться недвижимым, если на конвейере с более высоким приоритетом есть предмет. Ниже показан конвейер «A» с высоким приоритетом и конвейер «B» с низким. «A» занят, поэтому «B» должен быть недвижимым.



До



После

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

Готовый псевдокод

Показанный ниже код состоит из трёх этапов.

1. Обработка соединений конвейеров
2. Разметка недвижимых конвейеров (красным «X»)
3. Перемещение всех предметов на конвейерах, не помеченных как недвижимые

for each belt intersection, S
    set BLOCKED to false
    for each input belt to S, B
        if BLOCKED is true
            mark B as immobile
        if B has an item
            set BLOCKED to true

do
    set MADE_PROGRESS to false
    for each item, I
        let B be the belt under I
        let B' be the belt B outputs to
        if B' doesn't exist or if B' is immobile
            mark B as immobile
            set MADE_PROGRESS to true
while MADE_PROGRESS is true

for each item, I
    let B be the belt under I
    let B' be the belt B outputs to
    if B is not immobile
        move I from B to B'

Плюсы и минусы

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

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

Интересная связь с исследованиями компиляторов

Я писал эту статью о Factorio, но используемый принцип можно обобщить. Переворот задачи и замена местами того, что нужно доказать — очень полезный навык!

Изначально я у знал об этой технике из статьи об исследованиях компиляторов: «Combining Analyses, Combining Optimizations» Клиффа Клика. Любопытно, что в статье эта техника используется тоже для работы с циклами, только в программировании. Разумеется, Клифф Клик не первым проделал нечто подобное. Математики уже давно практикуют это.

Вопросы и ответы

• Вы играли в Factorio?

  
  Да я дважды прошёл игру и даже пытался создать собственную игру-клон. Статья появилась в результате этой работы.

• Код неэффективный! Factorio гораздо более оптимизирована.

  
  Да, я знаю, и я глубоко изучал Factorio перед написанием статьи. Однако добавление оптимизаций в моё объяснение запутало и удлинило бы статью.

• То есть оптимизировать решение нельзя?

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

• Почему бы не сделать попроще? Если конвейеры впадают сами в себя, то пусть образуют петлю.

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

• Но в Factorio есть двухдорожечные конвейеры!

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

• В Factorio можно решить проблему при помощи разделителей.

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

• Такое поведение реализовано специально/вызвано каким-то другим поведением.

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