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

52

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

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

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

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

BlueRaja - Дэнни Пфлугхофт
источник
5
Это не ответ на ваш вопрос, но для решения проблемы сети RTS я бы порекомендовал время от времени синхронизировать позиции и состояние устройства, чтобы исправить любые отклонения. Какая именно информация должна быть синхронизирована, зависит от игры; Вы можете оптимизировать использование полосы пропускания, не потрудившись синхронизировать такие вещи, как эффекты состояния.
Джокинг
@jhocking Тем не менее, это, вероятно, лучший ответ.
Джонатан Коннелл
Starcraft II Infacti точно синхронизируются только каждый раз, я смотрел на воспроизведение игры с моими друзьями рядом друг с другом и там, где различия (также значимые), особенно с высокой задержкой (1 сек). У меня было несколько юнитов, где 6/7 отображают квадраты далеко на моем экране относительно его собственного
GameDeveloper

Ответы:

15

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

Несколько лет назад я много читал по этому вопросу, когда хотел написать 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 может работать в любое время.
CodesInChaos
источник
23

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

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

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

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

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

AttackingHobo
источник
2
Как я уже говорил, меня интересует прежде всего C #; Так как JIT выполняет фактическую компиляцию, я не могу гарантировать, что он «скомпилирован с теми же настройками оптимизации», даже когда выполняется один и тот же исполняемый файл на той же машине!
BlueRaja - Дэнни Пфлугхофт
2
Иногда режим округления задается по-другому в fpu, на некоторых архитектурах fpu имеет внутренний регистр для вычислений с большей точностью, чем в то время, как IEEE754 не дает свободы в отношении того, как должны работать операции FP, он не ' t определить, как должна быть реализована какая-либо конкретная математическая функция, которая может выявить архитектурные различия.
Стивен
4
@ 3nixios При такой настройке игра не является детерминированной. Только игры с фиксированным временным шагом могут быть детерминированными. Вы утверждаете, что что-то уже не является детерминированным при запуске моделирования на одной машине.
AttackingHobo
4
@ 3nixios, «Я заявлял, что даже с фиксированным временным шагом ничто не гарантирует, что временной шаг всегда останется фиксированным». Вы совершенно не правы. Суть фиксированного временного шага состоит в том, чтобы всегда иметь одинаковое время дельты для каждого тика в обновлении
AttackingHobo
3
@ 3nixios Использование фиксированного временного шага гарантирует, что временной шаг будет фиксированным, потому что мы, разработчики, не разрешаем иначе. Вы неправильно понимаете, как следует компенсировать задержку при использовании фиксированного временного шага. Каждое обновление игры должно использовать одинаковое время обновления; поэтому, когда соединение однорангового узла запаздывает, оно все равно должно рассчитывать каждое отдельное обновление, которое оно пропустило.
Киблброкс
3

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

Неважно
источник
Да, я мог бы сделать его клиент-сервер и справиться с головной болью предсказания и экстраполяции на стороне клиента. Этот вопрос касается одноранговой архитектуры, которая должна быть проще ...
BlueRaja - Дэнни Пфлугхофт
Что ж, вам не нужно делать прогноз в сценарии «все клиенты запускают один и тот же код». Роль сервера - быть полномочным только для синхронизации.
Неважно,
Сервер / клиент - это только один метод создания сетевой игры. Другой популярный метод (особенно для игр , например. РТС, как C & C или Starcraft) является равный-равному, в котором нет нет авторитетного сервера. Чтобы это было возможно, все расчеты должны быть полностью детерминированными и согласованными для всех клиентов - отсюда мой вопрос.
BlueRaja - Дэнни Пфлюгофт
Ну, вы не должны делать игру строго p2p без серверов / клиентов с повышенными правами. Если вам абсолютно необходимо - используйте фиксированную точку.
Неважно,
3

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

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

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

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

LukeN
источник
decimalдля этого тоже подойдет; но, это все еще имеет те же проблемы, что и при использовании int- как мне сделать триггер с ним?
BlueRaja - Дэнни Пфлюгофт
1
Самый простой способ - создать таблицу соответствия и отправить ее вместе с приложением. Вы можете интерполировать между значениями, если точность является проблемой.
ЛукиN
В качестве альтернативы вы можете заменить триггерные вызовы мнимыми числами или кватернионами (если 3D). Это отличное объяснение
ЛукиN
Это также может помочь.
ЛукиN
В компании, в которой я работал, мы создали ультразвуковой аппарат с использованием математики с фиксированной запятой, так что он точно подойдет вам.
ЛукиN
3

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

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

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

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

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

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

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

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

Лайза
источник
1

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

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

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

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

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

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

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

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

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

Николь Болас
источник
Помимо математики, что еще может отличаться? Предположительно, «входные» действия отправляются как логические действия в rts. Например, переместите блок «a» в положение «b». Я вижу проблему с генерацией случайных чисел, но она, очевидно, должна быть отправлена ​​как вход для симуляции.
ЛукиN
@LukeN: Проблема в том, что позиция Шона настоятельно предполагает, что различия компиляторов могут иметь реальное влияние на математику с плавающей точкой. Он знал бы больше, чем я; Я просто экстраполирую его предупреждение в область компиляции / интерпретации JIT и C #.
Никол Болас
C # имеет перегрузку операторов , а также имеет встроенный тип для математики с фиксированной запятой. Тем не менее, это имеет те же проблемы, что и при использовании int- как мне сделать триггер с ним?
BlueRaja - Дэнни Пфлюгофт
1
> Как вы думаете, что произойдет, если интерпретатор запустит ваш код> интерпретированный один раз, но затем JIT'd его во второй раз? Или, может быть, он> интерпретирует это дважды на чужой машине, но JIT это после> этого? 1. Код CLR всегда перед передачей 2. .net использует IEEE 754 для плавания, конечно. > JIT не является детерминированным, потому что вы очень мало контролируете его. Ваш вывод является довольно слабой причиной ложных ложных утверждений. > И Бог поможет вам, если один человек использует .NET 4.0 для запуска вашей игры,> а кто-то другой использует Mono CLR (конечно, с использованием библиотек .NET>). Even .NET
Романенков Андрей
@Romanenkov: «Ваш вывод является довольно слабой причиной ложных ложных утверждений». Пожалуйста, скажите мне, какие утверждения являются ложными и почему, чтобы их можно было исправить.
Никол Болас
1

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

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

кувырок
источник
0

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

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

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

jheriko
источник
-2

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

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

Дуга-W
источник
1
Это то, что ОП хочет знать, как делать с плавающей запятой.
Коммунистическая утка