¿Cómo son posibles los juegos deterministas frente al no determinismo de coma flotante?

52

Para hacer un juego como un RTS en red, he visto varias respuestas que sugieren que el juego sea completamente determinista; entonces solo tiene que transferir las acciones de los usuarios entre sí y retrasar un poco lo que se muestra para "bloquear" la entrada de todos antes de que se procese el siguiente marco. Entonces, cosas como las posiciones de la unidad, la salud, etc., no necesitan actualizarse constantemente a través de la red, porque la simulación de cada jugador será exactamente la misma. También he escuchado lo mismo sugerido para hacer repeticiones.

Sin embargo, dado que los cálculos de punto flotante no son deterministas entre máquinas, o incluso entre diferentes compilaciones del mismo programa en la misma máquina, ¿es realmente posible hacerlo? ¿Cómo evitamos que ese hecho cause pequeñas diferencias entre los jugadores (o las repeticiones) que se extienden a lo largo del juego ?

Escuché que algunas personas sugieren evitar por completo los números de coma flotante y usar intpara representar el cociente de una fracción, pero eso no me parece práctico: ¿qué sucede si necesito, por ejemplo, tomar el coseno de un ángulo? ¿Realmente necesito reescribir una biblioteca matemática completa?

Tenga en cuenta que estoy principalmente interesado en C #, que, por lo que puedo decir, tiene exactamente los mismos problemas que C ++ a este respecto.

BlueRaja - Danny Pflughoeft
fuente
55
Esta no es una respuesta a su pregunta, pero para abordar el problema de la red RTS, recomendaría ocasionalmente sincronizar las posiciones y el estado de la unidad para corregir cualquier deriva. Exactamente qué información necesita ser sincronizada dependerá del juego; puede optimizar el uso del ancho de banda al no molestarse en sincronizar cosas como los efectos de estado.
jhocking
@jhocking Sin embargo, es probablemente la mejor respuesta.
Jonathan Connell
Infacti de StarCraft II se sincroniza exactamente solo de vez en cuando, miré la reproducción del juego con mis amigos en cada computadora una al lado de la otra y allí donde las diferencias (también significativas), especialmente con un alto retraso (1 segundo). Tenía algunas unidades que tenían un mapa de 6/7 cuadrados muy lejos en mi pantalla con respecto al suyo
GameDeveloper

Respuestas:

15

¿Los puntos flotantes son deterministas?

Leí mucho sobre este tema hace unos años cuando quería escribir un RTS usando la misma arquitectura de bloqueo que usted.

Mis conclusiones sobre los puntos flotantes de hardware fueron:

  • El mismo código de ensamblaje nativo es probablemente determinista, siempre que tenga cuidado con las marcas de coma flotante y la configuración del compilador.
  • Hubo un proyecto RTS de código abierto que afirmó que obtuvieron compilaciones deterministas de C / C ++ en diferentes compiladores utilizando una biblioteca de envoltura. No verifiqué ese reclamo. (Si no recuerdo mal, se trataba de la STREFLOPbiblioteca)
  • El .net JIT tiene bastante margen de maniobra. En particular, se permite utilizar una precisión mayor de la requerida. También usa diferentes conjuntos de instrucciones en x86 y AMD64 (creo que en x86 usa x87, AMD64 usa algunas instrucciones SSE cuyo comportamiento difiere para denorms).
  • Las instrucciones complejas (incluida la función trigonométrica, exponenciales, logaritmos) son especialmente problemáticas.

Llegué a la conclusión de que es imposible usar los tipos de punto flotante integrados en .net de manera determinista.

Posibles soluciones

Por lo tanto, necesitaba soluciones alternativas. Yo considere:

  1. Implementar FixedPoint32en C #. Si bien esto no es demasiado difícil (tengo una implementación a medio terminar), el rango muy pequeño de valores hace que sea molesto de usar. Debe tener cuidado en todo momento para que no se desborde ni pierda demasiada precisión. Al final encontré esto no más fácil que usar enteros directamente.
  2. Implementar FixedPoint64en C #. Encontré esto bastante difícil de hacer. Para algunas operaciones, los enteros intermedios de 128 bits serían útiles. Pero .net no ofrece ese tipo.
  3. Use código nativo para las operaciones matemáticas que es determinista en una plataforma. Incurre en los gastos generales de una llamada de delegado en cada operación matemática. Pierde la capacidad de correr multiplataforma.
  4. Uso Decimal. Pero es lento, requiere mucha memoria y fácilmente genera excepciones (división por 0, desbordamientos). Es muy bueno para uso financiero, pero no es adecuado para juegos.
  5. Implemente un punto flotante personalizado de 32 bits. Sonaba bastante difícil al principio. La falta de un intrínseco BitScanReverse causa algunas molestias al implementar esto.

My SoftFloat

Inspirado por su publicación en StackOverflow , acabo de comenzar a implementar un tipo de software de punto flotante de 32 bits y los resultados son prometedores.

  • La representación de la memoria es binariamente compatible con los flotantes IEEE, por lo que puedo reinterpretar la conversión al enviarlos al código de gráficos.
  • Es compatible con SubNorms, infinitos y NaNs.
  • Los resultados exactos no son idénticos a los resultados de IEEE, pero eso generalmente no importa para los juegos. En este tipo de código solo importa que el resultado sea el mismo para todos los usuarios, no que sea exacto hasta el último dígito.
  • El rendimiento es decente. Una prueba trivial mostró que puede hacer alrededor de 75MFLOPS en comparación con 220-260MFLOPS con floatadición / multiplicación (hilo único en un i3 de 2.66GHz). Si alguien tiene buenos puntos de referencia de punto flotante para .net, envíelos, ya que mi prueba actual es muy rudimentaria.
  • El redondeo se puede mejorar. Actualmente se trunca, lo que corresponde aproximadamente al redondeo hacia cero.
  • Todavía está muy incompleto. Actualmente faltan divisiones, yesos y operaciones matemáticas complejas.

Si alguien quiere contribuir con pruebas o mejorar el código, solo contácteme o emita una solicitud de extracción en github. https://github.com/CodesInChaos/SoftFloat

Otras fuentes de indeterminismo.

También hay otras fuentes de indeterminismo en .net.

  • iterar sobre Dictionary<TKey,TValue>o HashSet<T>devuelve los elementos en un orden indefinido.
  • object.GetHashCode() difiere de una carrera a otra.
  • La implementación de la Randomclase integrada no está especificada, use la suya propia.
  • El subprocesamiento múltiple con bloqueo ingenuo conduce a una reordenación y resultados diferentes. Tenga mucho cuidado de usar hilos correctamente.
  • Cuando WeakReferences pierden su objetivo es indeterminista porque el GC puede ejecutarse en cualquier momento.
CodesInChaos
fuente
23

La respuesta a esta pregunta es del enlace que publicó. Específicamente deberías leer la cita de Gas Powered Games:

Trabajo en Gas Powered Games y puedo decirte de primera mano que las matemáticas de coma flotante son deterministas. Solo necesita el mismo conjunto de instrucciones y compilador y, por supuesto, el procesador del usuario se adhiere al estándar IEEE754, que incluye a todos nuestros clientes de PC y 360. El motor que ejecuta DemiGod, Supreme Commander 1 y 2 se basa en el estándar IEEE754. Sin mencionar probablemente todos los demás juegos de RTS peer to peer en el mercado.

Y luego debajo de eso está esto:

Si almacena las repeticiones como entradas de controlador, no se pueden reproducir en máquinas con diferentes arquitecturas de CPU, compiladores o configuraciones de optimización. En MotoGP, esto significaba que no podíamos compartir repeticiones guardadas entre Xbox y PC.

Un juego determinista solo será determinista cuando se utilicen los archivos compilados de manera idéntica y se ejecuten en sistemas que cumplan con los estándares IEEE. Las simulaciones o repeticiones de red sincronizadas multiplataforma no serán posibles.

AttackingHobo
fuente
2
Como mencioné, estoy interesado principalmente en C #; Como el JIT realiza la compilación real, no puedo garantizar que esté "compilado con la misma configuración de optimización" incluso cuando se ejecuta el mismo ejecutable en la misma máquina.
BlueRaja - Danny Pflughoeft
2
A veces, el modo de redondeo se configura de manera diferente en la fpu, en algunas arquitecturas la fpu tiene un registro interno más grande que la precisión para los cálculos ... mientras que IEEE754 no da margen de maniobra con respecto a la forma en que deberían funcionar las operaciones de FP, no funciona No especifique cómo debe implementarse una función matemática particular, lo que puede exponer las diferencias arquitectónicas.
Stephen
44
@ 3nixios Con ese tipo de configuración, el juego no es determinista. Solo los juegos con un paso de tiempo fijo pueden ser deterministas. Está argumentando que algo ya no es determinista al ejecutar una simulación en una sola máquina.
AttackingHobo
44
@ 3nixios: "Estaba afirmando que incluso con un paso de tiempo fijo, nada asegura que el paso de tiempo siempre se mantenga fijo". Estás completamente equivocado. El objetivo de un paso de tiempo fijo es tener siempre el mismo tiempo delta para cada tic en la actualización
AttackingHobo
3
@ 3nixios El uso de un paso de tiempo fijo garantiza que el paso de tiempo se arregle porque los desarrolladores no permitimos lo contrario. Está malinterpretando cómo se debe compensar el retraso cuando se utiliza un paso de tiempo fijo. Cada actualización del juego debe usar el mismo tiempo de actualización; por lo tanto, cuando se demora la conexión de un compañero, aún debe calcular cada actualización individual que perdió.
Keeblebrox
3

Use aritmética de punto fijo. O elija un servidor autorizado y haga que sincronice el estado del juego de vez en cuando, eso es lo que hace MMORTS. (Al menos, Elements of War funciona así. También está escrito en C #). De esta forma, los errores no tienen la posibilidad de acumularse.

No importa
fuente
Sí, podría convertirlo en un servidor cliente y lidiar con los dolores de cabeza de la predicción y extrapolación del lado del cliente. Esta pregunta es sobre arquitecturas entre pares, que se supone que son más fáciles ...
BlueRaja - Danny Pflughoeft
Bueno, no necesita hacer predicciones en un escenario de "todos los clientes ejecutan el mismo código". El rol del servidor es ser la autoridad en la sincronización solamente.
importa
Servidor / cliente es solo un método para hacer un juego en red. Otro método popular (especialmente para juegos, por ejemplo. RTS, como C & C o Starcraft) es peer-to-peer, en el que no es ningún servidor autorizado. Para que eso sea posible, todos los cálculos deben ser completamente deterministas y consistentes en todos los clientes, de ahí mi pregunta.
BlueRaja - Danny Pflughoeft
Bueno, no es que TENGA que hacer el juego estrictamente p2p sin servidores / clientes elevados. Sin embargo, si es absolutamente necesario, entonces use un punto fijo.
importa
3

Editar: Un enlace a una clase de punto fijo (¡Cuidado con el comprador! No lo he usado ...)

Siempre puede recurrir a la aritmética de punto fijo. Alguien (haciendo un rts, nada menos) ya ha hecho el trabajo de pierna en stackoverflow .

Pagará una penalización de rendimiento, pero esto puede o no ser un problema, ya que .net no tendrá un rendimiento especial aquí ya que no usará instrucciones SIMD. ¡Punto de referencia!

NB Aparentemente, alguien en Intel parece tener una solución que le permite utilizar la biblioteca de primitivas de rendimiento de Intel desde c #. Esto puede ayudar a vectorizar el código de punto fijo para compensar el rendimiento más lento.

LukeN
fuente
decimalfuncionaría bien para eso también; pero, esto todavía tiene los mismos problemas que usar int: ¿cómo hago trigonometría con él?
BlueRaja - Danny Pflughoeft
1
La forma más fácil sería crear una tabla de búsqueda y enviarla junto con la aplicación. Puede interpolar entre valores si la precisión es un problema.
LukeN
Alternativamente, puede reemplazar las llamadas trigonométricas con números imaginarios o cuaterniones (si es 3D). Esta es una excelente explicación
LukeN
Esto también puede ayudar.
LukeN
En la compañía para la que solía trabajar, construimos una máquina de ultrasonido usando matemáticas de punto fijo, por lo que definitivamente funcionará para usted.
LukeN
3

He trabajado en varios títulos grandes.

Respuesta corta: es posible si eres increíblemente riguroso, pero probablemente no valga la pena. A menos que esté en una arquitectura fija (léase: consola), es delicada, frágil y viene con una serie de problemas secundarios, como la unión tardía.

Si lees algunos de los artículos mencionados, notarás que si bien puedes configurar el modo CPU, hay casos extraños, como cuando un controlador de impresión cambia el modo CPU porque estaba en el mismo espacio de direcciones. Tuve un caso en el que una aplicación estaba bloqueada por trama en un dispositivo externo, pero un componente defectuoso estaba causando que la CPU se acelere debido al calor e informe de manera diferente en la mañana y la tarde, lo que la convirtió en una máquina diferente después del almuerzo.

Estas diferencias de plataforma están en el silicio, no en el software, por lo que para responder a su pregunta, C # también se ve afectado. Instrucciones como Fusionar-agregar (FMA) vs ADD + MUL cambian el resultado porque se redondea internamente solo una vez en lugar de dos veces. C le da más control para obligar a la CPU a hacer lo que quiere básicamente al excluir operaciones como FMA para hacer las cosas "estándar", pero a costa de la velocidad. Los intrínsecos parecen ser los más propensos a diferir. En un proyecto tuve que desenterrar un libro de 150 años de tablas acos para obtener valores de comparación y determinar qué CPU era "correcta". Muchas CPU usan aproximaciones polinómicas para funciones trigonométricas, pero no siempre con los mismos coeficientes.

Mi recomendación:

Independientemente de si va a sincronizar o sincronizar, maneje la mecánica del juego por separado de la presentación. Haga que el juego sea preciso, pero no se preocupe por la precisión en la capa de presentación. También recuerde que no necesita enviar todos los datos mundiales en red a la misma velocidad de fotogramas. Puedes priorizar tus mensajes. Si su simulación es 99.999% coincidente, no necesitará transmitir con tanta frecuencia para mantenerse emparejado. (Dejando de lado la prevención de trampas).

Hay un buen artículo sobre el motor Source que explica una forma de sincronizar: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Recuerde, si está interesado en unirse tarde, tendrá que morder la bala y sincronizar de todos modos.

lisa
fuente
1

Tenga en cuenta que estoy principalmente interesado en C #, que, por lo que puedo decir, tiene exactamente los mismos problemas que C ++ a este respecto.

Sí, C # tiene los mismos problemas que C ++. Pero también tiene mucho más.

Por ejemplo, tome esta declaración de Shawn Hawgraves:

Si almacena las repeticiones como entradas de controlador, no se pueden reproducir en máquinas con diferentes arquitecturas de CPU, compiladores o configuraciones de optimización.

Es "bastante fácil" asegurar que esto suceda en C ++. En C # , sin embargo, será mucho más difícil lidiar con eso. Esto es gracias a JIT.

¿Qué supone que sucedería si el intérprete ejecutara su código interpretado una vez, pero luego lo JITED la segunda vez? ¿O tal vez lo interpreta dos veces en la máquina de otra persona, pero JIT lo es después de eso?

JIT no es determinista, porque tiene muy poco control sobre él. Esta es una de las cosas que renuncias para usar el CLR.

Y que Dios lo ayude si una persona está usando .NET 4.0 para ejecutar su juego, mientras que otra persona está usando Mono CLR (por supuesto, usando las bibliotecas .NET). Incluso .NET 4.0 vs. .NET 5.0 podría ser diferente. Simplemente necesita más control sobre los detalles de bajo nivel de una plataforma para garantizar este tipo de cosas.

Deberías poder salirte con las matemáticas de punto fijo. Pero eso es todo.

Nicol Bolas
fuente
Aparte de las matemáticas, ¿qué más puede ser diferente? Presumiblemente, las acciones de "entrada" se envían como acciones lógicas en un rts. Por ejemplo, mueva la unidad "a" a la posición "b". Puedo ver un problema con la generación de números aleatorios, pero eso obviamente también debe enviarse como una entrada de simulación.
LukeN
@LukeN: El problema es que la posición de Shawn sugiere fuertemente que las diferencias del compilador pueden tener efectos reales en las matemáticas de punto flotante. Él sabría más que yo; Simplemente estoy extrapolando su advertencia al ámbito de la compilación / interpretación de JIT y C #.
Nicol Bolas
C # tiene sobrecarga del operador y también tiene un tipo incorporado para matemática de punto fijo. Sin embargo, esto tiene los mismos problemas que usar un int- ¿cómo hago trigonometría con él?
BlueRaja - Danny Pflughoeft
1
> ¿Qué crees que pasaría si el intérprete ejecutara tu código> interpretado una vez, pero luego lo JITED la segunda vez? ¿O tal vez> lo interpreta dos veces en la máquina de otra persona, pero JIT es después de eso? 1. El código CLR siempre se modifica antes de la ejecución. 2. .net utiliza IEEE 754 para flotadores, por supuesto. > JIT no es determinista, porque tienes muy poco control sobre él. Su conclusión es una causa bastante débil de falsas declaraciones falsas. > Y que Dios te ayude si una persona está usando .NET 4.0 para ejecutar tu juego,> mientras que otra persona está usando Mono CLR (usando las bibliotecas .NET por supuesto). Incluso .NET
Romanenkov Andrey
@Romanenkov: "Su conclusión es una causa bastante débil de declaraciones falsas falsas". Por favor, dígame qué declaraciones son falsas y por qué, para que puedan corregirse.
Nicol Bolas
1

Después de escribir esta respuesta, me di cuenta de que en realidad no responde la pregunta, que era específicamente sobre el no determinismo de punto flotante. Pero tal vez esto sea útil para él de todos modos si va a hacer un juego en red de esta manera.

Junto con el intercambio de entradas que está transmitiendo a todos los jugadores, puede ser muy útil crear y transmitir una suma de verificación del estado importante del juego, como las posiciones del jugador, la salud, etc. Al procesar la entrada, afirme que el estado del juego suma Todos los reproductores remotos están sincronizados. Se garantiza que tendrá errores de sincronización (OOS) para corregir y esto lo hará más fácil: recibirá una notificación anterior de que algo salió mal (lo que lo ayudará a descubrir los pasos de reproducción), y debería poder agregar más inicio de sesión del estado del juego en código sospechoso para permitirle poner entre paréntesis lo que está causando el OOS.

Dar la vuelta
fuente
0

Creo que la idea del blog vinculado aún necesita sincronización periódica para ser viable: he visto suficientes errores en los juegos RTS en red que no toman ese enfoque.

Las redes son con pérdida, lentas, tienen latencia e incluso pueden contaminar sus datos. El "determinismo de punto flotante" (que suena lo suficientemente popular como para hacerme escéptico) es la menor de sus preocupaciones en realidad ... especialmente si usa un paso de tiempo fijo. con pasos de tiempo variable, deberá interpolar entre pasos de tiempo fijos para evitar problemas de determinismo también. Creo que esto es generalmente lo que se entiende por comportamiento no determinista de "punto flotante", solo que los pasos de tiempo variable causan divergencias en las integraciones, no tiene nada que ver con bibliotecas matemáticas o funciones de bajo nivel.

Sin embargo, la sincronización es clave.

jheriko
fuente
-2

Los haces deterministas. Para un gran ejemplo, vea la presentación de Dungeon Siege GDC sobre cómo hicieron que las ubicaciones en el mundo pudieran conectarse en red.

¡Recuerde también que el determinismo se aplica también a eventos 'aleatorios'!

Doug-W
fuente
1
Esto es lo que el OP quiere saber cómo hacer, con coma flotante.
El pato comunista