Как я могу выполнить детерминированное физическое моделирование?

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

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

Как я могу достичь этого детерминизма в моей игре? Я готов использовать различные фреймворки и языки, в том числе Javascript, C ++, Java, Python и C #.

Я соблазнил Box2D (C ++), а также его эквиваленты в других языках, поскольку он, кажется, отвечает моим потребностям, но в нем отсутствует детерминизм с плавающей запятой, особенно с тригонометрическими функциями.

Лучшим вариантом, который я видел до сих пор, был Java-эквивалент Box2D (JBox2D). Похоже, что он делает попытку детерминизма с плавающей запятой, используя, StrictMathа не Mathдля многих операций, но неясно, будет ли этот движок гарантировать все, что мне нужно, поскольку я еще не создал игру.

Можно ли использовать или модифицировать существующий двигатель в соответствии с моими потребностями? Или мне нужно будет создать двигатель самостоятельно?

РЕДАКТИРОВАТЬ: пропустите оставшуюся часть этого поста, если вам все равно, зачем кому-то нужна такая точность. Люди в комментариях и ответах, кажется, считают, что я ищу что-то, чего не должен, и поэтому я дополнительно объясню, как должна работать игра.

Игроку предоставляется головоломка или уровень, который содержит препятствия и цель. Изначально симуляция не запущена. Затем они могут использовать предоставленные им детали или инструменты для сборки машины. Как только они нажимают старт, начинается симуляция, и они больше не могут редактировать свою машину. Если машина решает карту, игрок побил уровень. В противном случае им придется нажать «Стоп», изменить свою машину и повторить попытку.

Причина, по которой все должно быть детерминированным, заключается в том, что я планирую создать код, который отобразит каждую машину (набор частей и инструментов, пытающихся решить уровень) в файл xml или json путем записи положения, размера и поворота каждой части. После этого игроки смогут обмениваться решениями (которые представлены этими файлами), чтобы они могли проверять решения, учиться друг у друга, проводить соревнования, сотрудничать и т. Д. Конечно, большинство решений, особенно простые или быстрые те, не будут затронуты отсутствием детерминизма. Но медленные или сложные проекты, которые решают действительно сложные уровни, могут, и это те, которые, вероятно, будут самыми интересными и заслуживающими внимания.

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

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

Существует множество литературы по числам с плавающей запятой:

• Что каждый ученый должен знать об арифметике с плавающей точкой
• НОВЫЙ СТАНДАРТ IEEE-754 ДЛЯ ПЛАВУЧЕЙ АРИФМЕТИКИ
• IEEE 754-2008 пересмотр

И как они проблемные:

• Согласованность результатов с плавающей запятой или почему мое приложение не всегда дает один и тот же ответ? ,
• Кроссплатформенные проблемы с арифметикой с плавающей точкой в ​​C ++ .
• Подводные камни проверки вычислений с плавающей точкой .
• Является ли математика с плавающей точкой детерминированной? ,
• Что может вызвать детерминированный процесс для генерации ошибок с плавающей запятой .
• Согласованность: как победить цель IEEE с плавающей запятой .

Для аннотации. По крайней мере, в одном потоке одинаковые операции с одинаковыми данными, происходящие в одном и том же порядке, должны быть детерминированными. Таким образом, мы можем начать с заботы о входах и переупорядочения.

Одним из таких факторов, вызывающих проблемы, является время.

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

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

Таким образом:

• Измерьте время: да
• Использовать время в симуляции: нет

Теперь порядок команд.

Компилятор может решить, что f * a + bэто то же самое b + f * a, что и другой результат. Он также может компилироваться в fmadd , или он может решить взять несколько строк, как это происходит вместе, и написать их с помощью SIMD , или какой-то другой оптимизации, о которой я не могу думать прямо сейчас. И помните, что мы хотим, чтобы одни и те же операции выполнялись в одном и том же порядке, возникает причина, по которой мы хотим контролировать, какие операции происходят.

И нет, использование двойного не спасет вас.

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

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

Таким образом:

• Эрн ... Хм ... Используйте компилятор, который позволит вам настроить их работу с числами с плавающей запятой . Например, см. / Fp (Укажите поведение с плавающей точкой) .

Случай для чисел с фиксированной точкой

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

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

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

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

Таким образом:

• Держите ценности маленькими: Да
• Тщательное округление: да
• Фиксированные номера точек, когда это возможно: Да

Подожди, зачем тебе с плавающей точкой? Не могли бы вы работать не только с целочисленным типом? О верно. Тригонометрия и радиация. Вы можете вычислить таблицы для тригонометрии и радиации и запекать их в своем источнике. Или вы можете реализовать алгоритмы, используемые для их вычисления с использованием числа с плавающей запятой, за исключением использования чисел с фиксированной запятой. Да, вам необходимо сбалансировать память, производительность и точность. Тем не менее, вы можете остаться вне чисел с плавающей запятой и оставаться детерминированным.

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

Кстати, я не говорю, чтобы не использовать с плавающей запятой для графики. Просто для физики. Я имею в виду, конечно, позиции будут зависеть от физики. Однако, как вы знаете, коллайдер не обязательно должен соответствовать модели. Мы не хотим видеть результаты усечения моделей.

Таким образом: используйте фиксированные номера точек.

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

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

Смотрите также:

• 3D-графика на мобильных устройствах. Часть 2. Математика с фиксированной точкой
• Заброшенное искусство арифметики с фиксированной точкой
• Код имитации алгоритма CORDIC

Приложение : Я предлагаю сохранить размер мира маленьким. При этом оба OP и Jibb Smart поднимают вопрос о том, что удаление от исходных поплавков имеет меньшую точность. Это повлияет на физику, которая будет видна гораздо раньше, чем край света. Числа с фиксированной точкой, ну, имеют фиксированную точность, они будут одинаково хорошими (или плохими, если хотите) везде. Что хорошо, если мы хотим детерминизма. Я также хочу отметить, что то, как мы обычно занимаемся физикой, обладает свойством усиливать небольшие вариации. Посмотрите Эффект Бабочки - Детерминированная Физика в Невероятной Машине и Создателе Контрацепции .

Еще один способ заниматься физикой

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

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

Там есть аргумент для тестирования там. Если мы решим, как именно все должно работать, и сможем протестировать на целевом оборудовании, мы не должны выпускать сборки с другим поведением.

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

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

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

Да, это много работы одного шага моделирования. Это означает, что симуляция не начнется мгновенно ...

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

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

Я бы поспорил за интерполяцию. Однако, учитывая, что есть ускорения, мы не можем просто интерполировать все одинаково. Вместо этого нам нужно интерполировать с учетом ускорения каждого объекта. В этом отношении мы могли бы просто обновить позицию таким же образом, как мы делаем для большого временного шага (что также означает, что он менее подвержен ошибкам, потому что мы не будем использовать две разные реализации для одного и того же движения).

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

добавление

От ОП в комментарии :

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

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

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

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

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

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

Если вы собираетесь попробовать свои собственные вещи, несколько вещей, которые могут помочь:

• Поплавки IEE754 являются детерминированными, если вы не делаете ничего слишком фруктового (в Google "IEE754 детерминизм" для получения дополнительной информации о том, что есть или нет)
• Вы должны убедиться, что у каждого клиента одинаковый режим округления и точность (для этого используйте controlfp)
• Режим округления и точность могут быть изменены некоторыми математическими библиотеками, поэтому, если вы используете какие-либо закрытые библиотеки, вы можете проверить их после выполнения вызовов (снова с помощью controlfp для проверки)
• некоторые инструкции SIMD являются детерминированными, многие - нет, будьте осторожны
• как упоминалось выше, для обеспечения детерминизма вам также нужна та же платформа, та же точная версия того же компилятора, компилирующая ту же конфигурацию, с теми же настройками компилятора
• встроить некоторые инструменты для обнаружения рассинхронизированных состояний и помочь в их диагностике - например, CRC отображает состояние игры в каждом кадре, чтобы определить, когда происходит рассинхронизация, а затем включить режим подробного протоколирования, который можно включить, когда изменения в игровом состоянии трудоемко записываются в файл, затем возьмите 2 файла из симуляций, которые рассинхронизированы друг с другом, и сравните их в инструменте сравнения, чтобы увидеть, в чем дело.
• инициализировать все ваши переменные в состоянии игры, основной источник рассинхронизации
• чтобы избежать рассинхронизаций, симуляция всей игры должна происходить в одном и том же порядке, невероятно легко ошибиться, желательно структурировать симуляцию игры таким образом, чтобы минимизировать это. Я на самом деле не являюсь разработчиком шаблонов разработки программного обеспечения, но для этого случая это, вероятно, хорошая идея - вы могли бы рассмотреть какой-то шаблон, в котором игровое моделирование похоже на безопасный ящик, и единственный способ изменить состояние игры - вставить «сообщения» или «команды», причем только постоянный доступ предоставляется ко всему, что находится за пределами игрового состояния (например, рендеринг, работа в сети и т. д.). Таким образом, сетевая симуляция для многопользовательской игры - это случай отправки этих команд по сети, или воспроизведение той же симуляции - это случай записи потока команд в первый раз,

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

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

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

Уменьшить точность.

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

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

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

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

Создайте свой собственный класс для хранения чисел!

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

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

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

Вот видео реального устройства, поведение которого преднамеренно непредсказуемо, кроме как в статистическом смысле:

https://www.youtube.com/watch?v=EvHiee7gs9Y

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

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

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

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

Игрок должен открыть физику игры, играя в игру. Неважно, не является ли он «полностью реалистичным», если он самосогласован и достаточно похож на опыт здравого смысла, чтобы быть правдоподобным.

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

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

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

Используйте Шаблон Памяти .

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

Затем, когда вы воспроизводите симуляцию, следуйте произвольной физике, но обновляйте позиционные данные каждые n кадров.

Слишком упрощенный псевдокод:

function Update():
    if(firstRun) then (SaveData(frame, position));
    else if(reproducedRun) then (this.position = GetData(frame));