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

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

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

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

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

48 голосов | спросил BlueRaja - Danny Pflughoeft 13 J000000Wednesday11 2011, 03:40:09

9 ответов


12

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

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

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

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

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

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

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

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

My SoftFloat

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

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

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

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

Существуют также другие источники индетерминизма в .net.

  • итерация по Dictionary<TKey,TValue> или HashSet<T> возвращает элементы в неопределенном порядке.
  • object.GetHashCode() отличается от run to run.
  • Реализация встроенного класса Random не указана, используйте свой собственный.
  • Многопоточность с наивной блокировкой приводит к переупорядочению и различным результатам. Будьте очень осторожны, чтобы правильно использовать потоки.
  • Когда WeakReference s теряют свою цель, индетерминирован, потому что GC может работать в любое время.
ответил CodesInChaos 16 J000000Saturday11 2011, 16:29:44
20

Ответ на этот вопрос - из ссылки, которую вы опубликовали. В частности, вы должны прочитать цитату из Gas Powered Games:

  

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

И затем ниже этого:

  

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

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

Невозможно выполнить симуляцию или повторную синхронизацию с помощью синхронной сети.
ответил AttackingHobo 13 J000000Wednesday11 2011, 05:40:27
3

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

ответил Nevermind 13 J000000Wednesday11 2011, 08:52:23
3

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

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

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

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

ответил LukeN 13 J000000Wednesday11 2011, 06:19:04
3

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

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

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

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

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

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

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

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

ответил lisa 14 52014vEurope/Moscow11bEurope/MoscowFri, 14 Nov 2014 12:55:11 +0300 2014, 12:55:11
1
  

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

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

Например, возьмите это утверждение от Shawn Hawgraves:

  

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

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

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

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

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

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

ответил Nicol Bolas 13 J000000Wednesday11 2011, 07:00:53
1

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

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

ответил Flip 13 J000000Wednesday11 2011, 18:44:20
0

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

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

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

ответил jheriko 16 J000000Saturday11 2011, 07:02:13
-2

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

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

ответил Doug-W 13 J000000Wednesday11 2011, 05:19:40

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132