Пятничные факты #331 – Патч 0.18.0 и изменения поиска пути

Поделиться

опубликовали Klonan, V453000, boskid

Патч 0.18.0 Klonan

В начале этой недели мы нажали кнопку выпуска патча 0.18.0 (список изменений / patch notes). Это стало неожиданностью для многих игроков, так как чаще время между основными выпусками  больше. Однако это не так, как раньше, мы стараемся поддерживать размер патчей как можно меньше (FFF-314).

Это означает, что то, что в настоящее время находится в 0,18, – это лишь малая часть работы, которая должна быть выполнена в 0,18, и патчи в ближайшие месяцы продолжат завершать наш список задач 0,18.

Как только все в списке 0.18 будет завершено, и время наступит, мы превратим 0.18 в 1.0.

Что мы сделали в 0.18.0:

  • Интерфейс
    • Редизайн главного меню
  • Графика
    • Анимация воды
    • Анимация деревьев
    • Цветокоррекция (LUTs)
    • Новые взрывы и эффекты урона
  • Другое
    • Оптимизация
    • Новая система частиц
    • Первая работа над новым звуковым дизайном
    • Steam login

Что нам осталось сделать в 0.18:

  • Интерфейс
    • Интерфейс персонажа
    • Библиотека чертежей
    • Интерфейс статистики (производство, статистика электросети, и тп.)
    • Интерфейс обьектов (манипулятор, сборщики, сундуки, и тп.)
    • Интерфейс главного экрана (чат, миникарта, и тп.)
    • И намного больше
  • Графика
    • Редизайн насоса
    • Редизайн сборщика
    • Редизайн маяка
    • Иконки в высоком разрешении
    • Финальные настройки и полировка
  • Другое
    • Дальнейшие улучшения дизайна звука
    • Мини-туториалы
    • Замена NPE старым туториалом
    • Баланс и настройки поздней игры
    • Окончательная локализация и корректура

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

Интерфейс персонажа?

Изначально мы планировали, что GUI персонажа будет в первой версии 0.18. Однако задача оказалась довольно сложной в том виде, в каком она была написана, и когда пришла дата выпуска, она не была готова, поэтому мы задержали весь выпуск 0.18.0 (дважды). После тщательного  анализа мы решили отказаться от большей части работы и начать все заново с другим членом команды.

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

После этого решения Dominik, который работал над графическим интерфейсом персонажа, решил покинуть команду Factorio.

Кампания отменена V453000

В ФФФ-329 / FFF-329 мы упомянули два разных подхода к кампании. В этом FFF мы объявляем, что кампания была отменена, и я попытаюсь объяснить, почему.

После отмены Туториала/ NPE я понял несколько вещей, и это заставило меня переоценить то, что пытается сделать кампания, задав такие вопросы:

  • Является ли кампания «Способ» как играть в игру или просто «дополнительный контент»?
  • Кампания пытается имитировать Свободный режим?
  • Потеря прогресса и начало с нуля – это большая проблема?

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

Попытка быть похожей на Свободный режим и создать представление о том, как «Factorio» должна быть сыграна », была образцом мышления для кампании по расширению незавершенного производства. Основное преимущество по сравнению с Свободным режимом состоит в том, что контент сегментируется на более мелкие куски (что уже является своего рода случаем из-за развития производства / технологии научных пакетов – игрок не может собрать все с самого начала). Однако наличие краткосрочного квеста, нахождение в ограниченной области карты, взаимодействие с существующими заводскими руинами, которые мешают игроку перейти в следующую область, и т. Д., Вызывает много неожиданных проблем. Было просто не интересно играть в сравнении.

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

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

Мы сели на прошлой неделе, чтобы пересмотреть, что делать с кампанией из двух вариантов от ФФФ-329 / FFF-329. Расширение кампании было слишком рискованным из-за всех ее проблем, и мы не были достаточно уверены в этом. Отдельные уровни были бы более подходящим вариантом, но если они не являются основным способом игры, то они не так важны, как ядро игры для версии 1.0.

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

Изменения в поиске путей поездов boskid

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

  • рельс- единый объект, по которому могут ездить поезда. Основная единица строительства.
  • сегмент- серия рельсов, которые не разделены между собой перекрестками, сигналами или станциями. Базовый блок для поиска пути.
  • блок- группа отрезков, которые  соединяются без сигналов между ними. Базовая единица для бронирования поездов.

в 0.17 и ранее, поиск пути использовал классический Dijkstra найти путь с наименьшим штрафом. Узлы связаны с сегментами с дополнительной информацией о направлении движения. Края относятся к сегментным соединениям (переходам).

Проблема 1: расстояние последнего сегмента не засчитывается в штраф

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

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

0.17 – поиск пути выбирает нижний путь, который длиннее

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

0.18 – Исправленный поиск пути выбирает верхний путь, который короче

Проблема 2:противоположная станция в последнем сегменте не засчитывается в штраф

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

0.17 – поиск пути выбирает нижний путь, потому что он не содержит штраф противоположной станции

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

0.18 – Исправленный поиск пути выбирает верхний путь, который короче. Оба пути имеют штраф в 1 станцию.

Проблема 3: расстояние первого сегмента не учитывает положение поезда

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

0.17 – поиск пути выбирает идти налево. Путь вправо стоит дороже на 2.

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

0.18 – Исправленный поиск пути выбирает идти направо. Положение поезда считается.

Проблема 4:  путь из одного сегмента имел приоритет над многосегментными путями

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


0.17 – поиск пути выбирает путь из одного сегмента.

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

0.18 – Исправленный поиск пути выбирает многосегментный путь, потому что он имеет более низкую стоимость.

Проблема 5: противоположная станция в первом сегменте была добавлена в штраф

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

0.17 – поиск пути выбирает левый путь, так как правый путь имеет штраф остановки поезда

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


0.18 – Исправленный поиск пути выбирает правильный путь. Остановка поезда под поездом не засчитывается.

Проблема 6: расстояние до блока от начала не было обновлено должным образом

Это довольно тонкий вопрос. Это связано с этим правилом штрафа:

“Когда жд блок занят поездом -> Добавьте штраф 2 * длины блока, деленной на расстояние блока от начала, чтобы удаленные пути не имели большого значения “.

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

0.17 – поиск пути выбирает нижний путь, потому что blockDistanceFromStart не обновляется должным образом в верхнем примере.

В этом примере проблема происходит в верхней части. Сегмент под верхним средним локомотивом расширяется первым при переходе от прямого сегмента слева – он был дешевле. Теперь этот сегмент имеет стоимость прямой траектории и расстояние до блока от начала 1, поскольку был только 1 переход к другому блоку. Был также штраф блока, занятого другим поездом.

Когда расширение проходит через верхний боковой рельс, оно попадает в 4 сигнала рельса, и поэтому расстояние между блоками от старта увеличивается до 4. Этот путь стоит дороже, пока сигнал левого рельса около верхнего среднего локомотива не увеличивается. Здесь, однако, стоимость блока, занятого другим поездом, ниже, так как мы входим в 5-й блок от старта при прохождении верхнего пути. Боковой путь выбран для обновления стоимости узла, относящейся к сегменту с верхним средним локомотивом, но расстояние блока от начала не было обновлено. Из-за этого, штраф за следующий сигнал рельса, который идет к другому занятому блоку, был равен расстоянию последнего сегмента, разделенному на 2 вместо 6. Это различие сделало бы путь через нижнее устройство более низкой стоимостью, так как прямой путь здесь обрезается, и узел для сегмента под средним локомотивом создается с подходящим расстоянием между блоками от начала.

Исправление было простым: при изменении стоимости от начала на существующем узле также измените расстояние блока от начала.


0.18 – Исправленный поиск пути выбирает верхний путь

Проблема 7: смена пути очистит счетчик тиков, ожидающих сигнала.

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

“Если путь включает в себя поезд, который в данный момент ожидает сигнала рельса -> Добавьте штраф в размере 100 + 0,1 за каждый тик, который поезд уже ждал ».

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

Универсальное исправление здесь: сбрасывать этот счетчик, только если поезд меняет состояние на что-либо, кроме ожидания по сигналу.

0.18 – Исправленные тики, ожидающие по сигнальной логике, после 3 смен пути штраф левого поезда увеличивается до точки, где правый поезд выбирает длинный путь.

Оптимизация Поиска пути – приоритетная очередь

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

Оптимизация Поиска пути -эвристический (преобразование из Dijkstra в A*)

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

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

Как всегда, дайте нам знать, что вы думаете на нашем форуме.


Поделиться

Комментарии: