Игры

Детерминированная многопоточность — это сложно

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

Воспроизвести рассинхронизацию мне не удалось, но плеер смог с легкостью. Сначала я подумал, что это проблема Windows и Linux (у нас было много таких), но потом плеер смог воспроизвести ее с Linux на обоих компьютерах. Затем я подумал, что это аппаратная проблема: мы видели немало неисправных компьютеров, которые просто не делают того, что должны. Убедить кого-то, что его оборудование сломано, сложно и в лучшем случае отнимает много времени.

После нескольких неудачных попыток воспроизвести проблему на моем одном компьютере Боскид, используя несколько своих компьютеров, смог это сделать. Я думаю, что возможность воспроизводить ошибки локально занимает около 90-95% времени, потраченного на исправление обнаруженных ошибок. Воспроизведя проблему по требованию, Боскид смог сузить ее до того факта, что компьютеры имели разное количество ядер ЦП. Благодаря этим новообретенным знаниям он смог провести тест, который можно было запустить на моем единственном компьютере, чтобы воспроизвести рассинхронизацию, искусственно притворившись, что у меня меньше ядер процессора, чем на самом деле.

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

1) Моду необходимо было прослушивать событие, генерируемое чанком, и менять тайлы на чанке, когда оно происходило.

2) Моду необходимо было запросить создание нескольких фрагментов.

3) Моду необходимо было принудительно сгенерировать все запрошенные фрагменты прямо сейчас .

4) Игру необходимо было запустить на двух компьютерах с разным количеством ядер процессора.

Логика генерации фрагментов «прямо сейчас» будет пытаться использовать все доступные ядра ЦП, но это было сделано таким образом, что количество ядер - в сочетании с другими движущимися частями - слегка меняло результаты генерации фрагментов.

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

Многопользовательская игра с автопаузой

У нас есть особенность выделенных серверов: когда последний игрок отключается, сервер автоматически приостанавливается. Это прекрасно работает и означает, что вы можете оставить выделенный сервер включенным, не беспокоясь о том, что кусаки съедят вашу базу, когда вы уйдете. За исключением некоторых крайних случаев, с которыми нам так и не удалось справиться (до сих пор).

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

Случай 2: Присоединяющимся игрокам необходимо не отставать от текущей игры. Это отлично работает для «обычных» игр и позволяет существующим игрокам продолжать игру, не дожидаясь присоединения игроков. Но игроки сталкиваются с проблемами, связанными с гораздо большими картами или медленным подключением к Интернету. Для присоединения кого-либо может потребоваться 1, 2 или несколько минут, чтобы загрузиться и полностью подключиться к серверу. В версии 2.0 мы добавили опцию «автоматическая пауза, когда игрок присоединяется», которая работает именно так, как указано.

Более быстрые задачи строительных роботов

Такое ощущение, что каждую неделю кто-то спрашивает: «Почему мои строительные роботы не работают?» и на скриншоте, который они предоставляют, есть небольшое предупреждение, показывающее «600 рабочих мест, не хватает материалов/роботов». Эта проблема существовала с самого начала появления роботов, и до сих пор у нас нет хорошего решения для нее.

Проблема в том, что, учитывая задачу, которую должны выполнить роботы-конструкторы, игре необходимо найти лучшего робота из логистической сети, который находится в пределах досягаемости, чтобы выполнить эту задачу. Проверка того, находится ли эта логистическая сеть в радиусе действия объекта, равна O(Roboport-Count). Мы не контролируем, насколько медленным это будет, потому что игрок может построить 1 Робопорт, или 100 000, или столько, сколько сможет вместить его компьютер. Поэтому нам нужно убедиться, что эта операция не приводит к остановке игры во время ее работы. Мы делаем это, обрабатывая всего несколько задач строительных роботов за каждый такт.

В версии 1.1 игра будет проверять строительные работы 3 раза за каждое обновление. Если ему не удастся найти робота, он остановится для текущего обновления. Оповещения о неудачных попытках длятся 10 секунд. Таким образом, при 60 обновлениях в секунду и 10 секундах на каждое оповещение это означает, что будет создано 600 оповещений до истечения срока действия первого. Вот откуда берется волшебное количество предупреждений «600 рабочих мест, не хватает материалов/роботов».

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

Ранее в этом году кто-то ( сообщение на форуме ) снова столкнулся с этой проблемой, но решил «решить» ее самостоятельно, сделав то, что, как мы сказали, мы не можем сделать: «запустить проверенные задачи для каждого обновления», за исключением того, что они перешли с 1 на каждое обновление. до 374. Также построено 36 815 роботопортов. Как и предполагалось, это было медленно.

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

Это, в сочетании с сортировкой полученных прямоугольников, означало, что я мог выполнить простой двоичный поиск, чтобы проверить, находится ли данная задача в пределах сети. В конце концов проверка изменилась с O(N) на 36 815 роботопортах до O(N) на 900~ прямоугольных объединенных областях и до O(logN) на 900~ прямоугольных объединенных областях.

Время проверки «есть ли оно в этой сети» из дорогого превратилось в практически незаметное. Благодаря этому ускорению я смог увеличить скорость проверки задач для версии 2.0 и, надеюсь, решить эту проблему.