Как возможны детерминированные игры перед лицом недетерминированности с плавающей точкой?

Чтобы сделать игру похожей на сетевую RTS, я видел несколько ответов, предлагающих сделать игру полностью детерминированной; тогда вам нужно всего лишь передать действия пользователей друг другу и немного отстать от того, что отображается, чтобы «заблокировать» ввод всех пользователей до того, как будет визуализирован следующий кадр. Тогда такие вещи, как положение юнита, здоровье и т. Д. Не нужно постоянно обновлять по сети, потому что симуляция каждого игрока будет абсолютно одинаковой. Я также слышал то же самое, что предлагалось для повторов.

Однако, поскольку вычисления с плавающей точкой являются недетерминированными между машинами или даже между различными компиляциями одной и той же программы на одной машине, возможно ли это сделать? Как мы можем предотвратить возникновение небольших различий между игроками (или повторами), которые будут колебаться на протяжении всей игры ?

Я слышал, что некоторые люди предлагают вообще избегать чисел с плавающей запятой и использовать intдля представления частное дроби, но это не кажется мне практичным - что, если мне нужно, например, взять косинус угла? Мне серьезно нужно переписать целую математическую библиотеку?

Обратите внимание, что я в основном заинтересован в C #, который, насколько я могу судить, имеет точно такие же проблемы, что и C ++ в этом отношении.

Являются ли числа с плавающей точкой детерминированными?

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

Мои выводы об аппаратных плавающих точках были:

• Тот же самый собственный код ассемблера, скорее всего, является детерминированным, если вы будете осторожны с флагами с плавающей запятой и настройками компилятора.
• Был один проект RTS с открытым исходным кодом, в котором утверждалось, что они получают детерминированные компиляции C / C ++ для разных компиляторов с использованием библиотеки-оболочки. Я не проверял это утверждение. (Если я правильно помню, это было о STREFLOPбиблиотеке)
• .Net JIT допускается немного свободы. В частности, разрешено использовать более высокую точность, чем требуется. Также он использует разные наборы инструкций на x86 и AMD64 (я думаю, на x86 он использует x87, AMD64 использует некоторые инструкции SSE, поведение которых отличается для денормс).
• Сложные инструкции (включая тригонометрическую функцию, экспоненты, логарифмы) особенно проблематичны.

Я пришел к выводу, что невозможно использовать встроенные типы с плавающей точкой в ​​.net детерминистически.

Возможные обходные пути

Таким образом, мне нужны обходные пути. Я считал:

1. Реализовать FixedPoint32в C #. Хотя это не так сложно (у меня есть половина готовой реализации), очень маленький диапазон значений делает его раздражающим в использовании. Вы должны быть осторожны все время, чтобы не переполнить и не потерять слишком много точности. В конце концов я обнаружил, что это не проще, чем использовать целые числа напрямую.
2. Реализовать FixedPoint64в C #. Я нашел это довольно сложно сделать. Для некоторых операций были бы полезны промежуточные целые числа из 128 бит. Но .net не предлагает такой тип.
3. Используйте собственный код для математических операций, который является детерминированным на одной платформе. Вносит накладные расходы на вызов делегата при каждой математической операции. Теряет способность бегать кроссплатформенно.
4. Использование Decimal. Но это медленно, занимает много памяти и легко генерирует исключения (деление на 0, переполнение). Это очень хорошо для финансового использования, но не подходит для игр.
5. Реализуйте пользовательские 32-битные с плавающей точкой. Поначалу звучало довольно сложно. Отсутствие встроенного BitScanReverse вызывает некоторые неудобства при реализации этого.

Мой SoftFloat

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

• Представление в памяти двоично совместимо с плавающими IEEE, поэтому я могу переосмыслить приведение при выводе их в графический код.
• Он поддерживает SubNorms, бесконечности и NaN.
• Точные результаты не идентичны результатам IEEE, но это обычно не имеет значения для игр. В этом типе кода важно только то, что результат одинаков для всех пользователей, а не то, что он точен до последней цифры.
• Производительность приличная. Тривиальный тест показал, что он может сделать около 75MFLOPS по сравнению с 220-260MFLOPS floatдля сложения / умножения (одиночный поток на i66 с частотой 2,66 ГГц). Если у кого-то есть хорошие тесты с плавающей точкой для .net, пожалуйста, пришлите их мне, так как мой текущий тест очень элементарный.
• Округление может быть улучшено. В настоящее время он усекается, что примерно соответствует округлению до нуля.
• Это все еще очень неполно В настоящее время разделение, приведение и сложные математические операции отсутствуют.

Если кто-то хочет внести свой вклад в тестирование или улучшить код, просто свяжитесь со мной или выполните запрос на github. https://github.com/CodesInChaos/SoftFloat

Другие источники индетерминизма

Есть и другие источники неопределенности в .net.

• итерация по a Dictionary<TKey,TValue>или HashSet<T>возвращает элементы в неопределенном порядке.
• object.GetHashCode() отличается от бега к бегу.
• Реализация встроенного Randomкласса не указана, используйте свою.
• Многопоточность с наивной блокировкой приводит к переупорядочению и отличным результатам. Будьте очень осторожны, чтобы правильно использовать темы.
• Когда WeakReferences теряют свою цель, это неопределенно, потому что GC может работать в любое время.

Ответ на этот вопрос от ссылки, которую вы разместили. В частности, вы должны прочитать цитату из газовых игр:

Я работаю в Gas Powered Games и могу вам сказать, что математика с плавающей точкой является детерминированной. Вам просто нужен тот же набор инструкций и компилятор, и, конечно, процессор пользователя соответствует стандарту IEEE754, который включает в себя все наши ПК и 360 клиентов. Двигатель, который работает DemiGod, Supreme Commander 1 и 2, основан на стандарте IEEE754. Не говоря уже о, вероятно, всех других одноранговых RTS-играх на рынке.

И тогда ниже этого:

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

Детерминированная игра будет детерминированной только при использовании одинаково скомпилированных файлов и запускается в системах, которые соответствуют стандартам IEEE. Межплатформенное синхронизированное сетевое моделирование или повторы невозможны.

Используйте арифметику с фиксированной точкой. Или выберите авторитетный сервер и время от времени синхронизируйте состояние игры - это то, что делает MMORTS. (По крайней мере, Elements of War работает следующим образом. Он также написан на C #.) Таким образом, ошибки не имеют шансов накапливаться.

Изменить: ссылка на класс с фиксированной точкой (покупатель остерегается! - я не использовал его ...)

Вы всегда можете вернуться к арифметике с фиксированной точкой . Кто-то (делая rts, не меньше) уже выполнил работу по обработке стека .

Вы заплатите штраф за производительность, но это может быть, а может и не быть проблемой, так как .net здесь не будет особенно производительным, так как не будет использовать инструкции simd. Benchmark!

NB Похоже, что кто-то в Intel имеет решение, позволяющее вам использовать библиотеку примитивов производительности Intel из c #. Это может помочь векторизации кода с фиксированной запятой, чтобы компенсировать снижение производительности.

Я работал над несколькими большими названиями.

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

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

Эти различия в платформе связаны с кремнием, а не с программным обеспечением, поэтому на ваш вопрос также влияет C #. Такие инструкции, как слияние, умножение, сложение (FMA) против ADD + MUL, изменяют результат, потому что он округляется внутри только один раз, а не дважды. C дает вам больше контроля, чтобы заставить процессор делать то, что вы хотите, в основном, исключая такие операции, как FMA, чтобы сделать вещи «стандартными» - но за счет скорости. Внутренние свойства кажутся наиболее склонными к различиям. В одном проекте мне пришлось выкопать 150-летнюю книгу таблиц acos, чтобы получить значения для сравнения, чтобы определить, какой процессор был «правильным». Многие процессоры используют полиномиальные приближения для тригонометрических функций, но не всегда с одинаковыми коэффициентами.

Моя рекомендация:

Независимо от того, используете ли вы целочисленную блокировку или синхронизацию, обрабатывайте основную механику игры отдельно от презентации. Сделайте игру точной, но не беспокойтесь о точности на уровне представления. Также помните, что вам не нужно отправлять все данные сетевого мира с одинаковой частотой кадров. Вы можете расставить приоритеты ваших сообщений. Если ваша симуляция соответствует 99,999%, вам не нужно будет передавать так часто, чтобы оставаться в паре. (Обманка в сторону.)

Есть хорошая статья о движке Source, которая объясняет один из способов синхронизации: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

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

Обратите внимание, что я в основном заинтересован в C #, который, насколько я могу судить, имеет точно такие же проблемы, что и C ++ в этом отношении.

Да, C # имеет те же проблемы, что и C ++. Но это также имеет гораздо больше.

Например, возьмите это утверждение от Шона Хоугрейвса:

Если вы храните повторы как входы контроллера, они не могут быть воспроизведены на машинах с разными архитектурами ЦП, компиляторами или настройками оптимизации.

Это достаточно просто, чтобы гарантировать, что это происходит в C ++. Однако в C # с этим будет гораздо сложнее иметь дело. Это благодаря JIT.

Как вы думаете, что произойдет, если интерпретатор запустит интерпретируемый код один раз, но затем JIT сделает это во второй раз? Или, может быть, он интерпретирует это дважды на чужой машине, но JIT это после этого?

JIT не является детерминированным, потому что у вас очень мало контроля над ним. Это одна из вещей, которую вы отказываетесь от использования CLR.

И Бог поможет вам, если один человек использует .NET 4.0 для запуска вашей игры, а кто-то другой использует Mono CLR (конечно, с использованием библиотек .NET). Даже .NET 4.0 и .NET 5.0 могут отличаться. Вам просто нужно больше контроля над низкоуровневыми деталями платформы, чтобы гарантировать такие вещи.

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

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

Наряду с совместным использованием ввода, которое вы транслируете всем игрокам, может быть очень полезно создать и передать контрольную сумму важного игрового состояния, такого как позиции игрока, здоровье и т. Д. При обработке ввода утверждают, что контрольные суммы состояния игры для все удаленные плееры синхронизированы. Вы гарантированно исправите ошибки из-за несинхронизации (OOS), и это упростит задачу - вы будете раньше замечать, что что-то пошло не так (что поможет вам определить шаги воспроизведения), и вы сможете добавить больше регистрация состояния игры в подозрительном коде, чтобы вы могли заключить в скобки все, что вызывает OOS.

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

Сети с потерями, медленные, имеют задержку и могут даже загрязнять ваши данные. «Детерминизм с плавающей точкой» (который звучит достаточно громко, чтобы заставить меня скептически относиться) - это наименьшее из ваших беспокойств в реальности ... особенно если вы используете фиксированный временной шаг. с переменными временными шагами вам нужно будет интерполировать между фиксированными временными шагами, чтобы избежать проблем детерминизма. Я думаю, что это обычно то, что подразумевается под недетерминированным поведением «с плавающей запятой» - только то, что переменные временные шаги приводят к расхождению интеграций - не имеет ничего общего с математическими библиотеками или низкоуровневыми функциями.

Синхронизация является ключевым моментом.

Вы делаете их детерминированными. Прекрасный пример можно найти в презентации GDC компании Dungeon Siege о том, как они сделали сети в мире доступными.

Также помните, что детерминизм применим и к «случайным» событиям!