Muchos juegos usan la técnica de compresión delta para reducir la carga de datos enviada. ¿No entiendo cómo esta técnica realmente reduce la carga de datos?
Por ejemplo, digamos que quiero enviar una posición. Sin compresión delta, envío un vector3
con la posición exacta de la entidad, por ejemplo (30, 2, 19)
. Con la compresión delta envío un vector3
número más pequeño (0.2, 0.1, 0.04)
.
¡No entiendo cómo disminuye la carga de datos si ambos mensajes son vector3
- 32 bits para cada flotante - 32 * 3 = 96 bits!
Sé que puede convertir cada flotante a un byte y luego convertirlo de nuevo a un flotante, pero causa errores de precisión que son visibles.
networking
compression
usuario101051
fuente
fuente
Respuestas:
Hay momentos en los que no puedes evitar enviar el estado completo del juego, como al cargar un juego multijugador guardado, o cuando se necesita una resincronización. Pero el envío de estado completo es generalmente evitable, y ahí es donde codificación delta viene en general, esto es. Todo lo que la compresión delta se trata; su ejemplo realmente no describe esa situación. La razón por la que incluso se menciona la compresión delta es porque las implementaciones ingenuas a menudo envían estados en lugar de deltas porque el estado es lo que generalmente almacena cualquier implementación ingenua de juegos. Los deltas son entonces una optimización.
Con deltas, nunca enviarías las posiciones de las unidades que no se movieron , en absoluto. Ese es el espíritu de eso.
Imagina que fuimos amigos por años y perdí la memoria (y descarté todas tus cartas después de leerlas). En lugar de simplemente continuar con su serie de cartas como siempre, tendría que escribirme toda la historia de su vida en una sola carta masiva, una vez más, para que me ponga al día.
En su caso dado, puede (dependiendo de su base de código) ser posible usar un número menor de bits para codificar los deltas, a diferencia de los grandes rangos de bits necesarios para enviar el estado completo. Digamos que el mundo tiene muchos kilómetros de diámetro, es posible que necesite un flotador de 32 bits para codificar con precisión las posiciones hacia abajo, por ejemplo, un centímetro en un eje dado. Sin embargo, dada la velocidad máxima aplicable a las entidades, que puede ser solo un par de metros por marca, puede ser factible en solo 8 bits (2 ^ 8 = 256, suficiente para almacenar un máximo de 200 cm). Por supuesto, esto supone un uso de punto fijo en lugar de flotante ... o algún tipo de medio / cuarto flotante como en OpenGL, si no desea problemas de punto fijo.
fuente
Tienes el delta equivocado. Estás mirando el delta de los elementos individuales. Debes pensar en el delta de toda la escena.
Supongamos que tiene 100 elementos en su escena, pero solo 1 de ellos se movió. Si envía 100 vectores de elementos, 99 de ellos se desperdician. Realmente solo necesitas enviar 1.
Ahora, supongamos que tiene un objeto JSON que almacena todos sus vectores de elementos. Este objeto se sincroniza entre su servidor y su cliente. En lugar de decidir "¿se movió tanto?" solo puede generar su próximo tic del juego en un objeto JSON, hacer un
diff tick100.json tick101.json
y enviar esa diferencia. En el lado del cliente, aplica el diff al vector de su marca actual y ya está todo listo.Al hacer esto, aprovecha las décadas de experiencia en la detección de diferencias en el texto (¡o binario!) Y no tiene que preocuparse por perderse nada usted mismo. Ahora, idealmente, también usa una biblioteca que hace esto detrás de escena para que sea aún más fácil para usted como desarrollador.
fuente
diff
sonidos como un truco ineficiente. Mantener la cadena JSON en el extremo receptor, parchearlo y deserializarlo cada vez es innecesario. Calcular la diferencia de dos diccionarios de valores clave no es una tarea complicada, básicamente solo recorre todas las claves y verifica si los valores son iguales. Si no, los agrega al dict resultante de clave-valor y finalmente envía el dict serializado a JSON. Simple, no se necesitan años de experiencia. A diferencia de las diferencias, este método: 1) no incluirá datos antiguos (reemplazados); 2) juega mejor con UDP; 3) no confía en las nuevas líneasMuy a menudo, otro mecanismo de compresión se combinará con la codificación delta como, por ejemplo, la compresión aritmética.
Esos esquemas de compresión funcionan mucho mejor cuando los posibles valores se agrupan de manera predecible. La codificación Delta agrupará los valores alrededor de 0.
fuente
En general, tienes razón, pero te falta un punto importante.
Las entidades en un juego se describen por muchos atributos, de los cuales la posición es solo una .
¿Qué tipo de atributos? Sin tener que pensar demasiado, en un juego en red, estos podrían incluir:
Si elige cada uno de estos de forma aislada, sin duda puede argumentar que si en cualquier marco dado necesita cambiar, entonces debe retransmitirse por completo.
Sin embargo, no todos estos atributos cambian a la misma velocidad .
¿El modelo no cambia? Sin compresión delta, debe retransmitirse de todos modos. Con la compresión delta no es necesario.
La posición y la orientación son dos casos que son más interesantes, comúnmente compuestos de 3 flotadores cada uno. Entre cualquiera de los dos cuadros, existe la posibilidad de que solo 1 o 2 de cada conjunto de 3 flotadores puedan cambiar. ¿Moviéndose en línea recta? ¿No gira? ¿No saltar? En todos estos casos, sin compresión delta, debe retransmitir por completo, pero con la compresión delta solo necesita retransmitir lo que cambia.
fuente
Tiene razón en que un cálculo delta ingenuo por sí solo, con el resultado almacenado en la misma estructura de datos de tamaño que los operandos y transmitido sin ningún procesamiento posterior, no ahorraría tráfico.
Sin embargo, hay dos formas en que un sistema bien diseñado basado en deltas puede ahorrar tráfico.
Primero, en muchos casos, el delta será cero. Puede diseñar su protocolo de modo que si el delta sea cero, no lo envíe en absoluto. Obviamente, hay algunos gastos generales para esto, ya que tienes que indicar lo que estás enviando o no, pero en general es probable que sea una gran victoria.
En segundo lugar, los deltas generalmente tendrán un rango de valores mucho más pequeño que los números originales. y ese rango se centrará en cero. Esto puede explotarse utilizando un tipo de datos más pequeño para la mayoría de los deltas o pasando el flujo de datos completo a través de un algoritmo de compresión de propósito general.
fuente
Si bien la mayoría de las respuestas hablan sobre cómo la codificación delta se trata solo de enviar los cambios al estado como un todo, hay otra cosa llamada "codificación delta" que se puede usar como un filtro para reducir la cantidad de datos que necesita comprimir en el estado completo actualizar también, que puede ser el origen de la confusión en la pregunta que se le hizo.
Al codificar un vector de números, en algunos casos (por ejemplo, enteros, enumeraciones, etc.) puede usar una codificación de bytes variables para los elementos individuales, y en algunos de estos casos puede reducir aún más la cantidad de datos que necesita cada elemento si lo almacena como sumas corrientes o como el valor mínimo y la diferencia entre cada valor y ese mínimo.
Por ejemplo, si desea codificar el vector
{68923, 69012, 69013, 69015}
, puede codificarlo delta como{68923, 89, 1, 2}
. Usando una codificación trivial de bytes variables donde almacena 7 bits de datos por byte y usa un bit para indicar que viene otro byte, cada uno de los elementos individuales en la matriz requeriría 3 bytes para transmitirlo, pero la versión codificada en delta solo requeriría 3 bytes para el primer elemento y 1 byte para los elementos restantes; dependiendo del tipo de datos que esté serializando, esto puede generar ahorros bastante impresionantes.Sin embargo, esto es más una optimización de serialización y no es lo que generalmente se quiere decir cuando hablamos de "codificación delta" cuando se trata de transmitir datos arbitrarios como parte del estado del juego (o video o similar); otras respuestas ya hacen un trabajo adecuado al explicar eso.
fuente
También vale la pena señalar que los algoritmos de compresión hacen su trabajo mejor en la diferencia. Como otras respuestas mencionan, o bien la mayoría de sus elementos permanecen iguales entre 2 estados, o los valores cambian en una pequeña fracción. En ambos casos, la aplicación de un algoritmo de compresión a la diferencia de su vector de números le brinda ahorros significativos. Incluso si no aplica ninguna lógica adicional a su vector, como eliminar los elementos 0.
Aquí hay un ejemplo en Python:
Lo que me da:
fuente
Si su posición está almacenada en vector3 pero la entidad real solo puede mover unos pocos enteros a la vez. Luego enviar su delta en bytes sería mejor que enviarlo en entero.
En lugar de enviar la posición exacta cada vez, enviamos el delta.
fuente
La compresión delta es una compresión de valores codificados delta. La codificación Delta es una transformación que produce una distribución estadística diferente de números. Si la distribución es favorable al algoritmo de compresión elegido, disminuye la cantidad de datos. Funciona muy bien en un sistema como un juego donde las entidades se mueven solo ligeramente entre dos actualizaciones.
Digamos que tienes 100 entidades en 2D. En una cuadrícula grande, 512 x 512. Considerando solo los enteros por el bien de ejemplo. Eso es dos números enteros por entidad o 200 números.
Entre dos actualizaciones, todas nuestras posiciones cambian en 0, 1, -1, 2 o -2. Ha habido 100 instancias de 0, 33 instancias de 1 y -1 y solo 17 instancias de 2 y -2. Esto es bastante común. Elegimos la codificación Huffman para la compresión.
El árbol de Huffman para esto será:
Todos sus 0 se codificarán como un solo bit. Eso es solo 100 bits. 66 valores se codificarán como 3 bits y solo 34 valores como 4 bits. Eso es 434 bits o 55 bytes. Además, algunos gastos generales pequeños para guardar nuestro árbol de mapeo, ya que el árbol es pequeño. Tenga en cuenta que para codificar 5 números, necesita 3 bits. Hemos intercambiado aquí la capacidad de usar 1 bit para '0' por la necesidad de usar 4 bits para '-2'.
Ahora compare esto con enviar 200 números arbitrarios. Si sus entidades no pueden estar en el mismo mosaico, está casi garantizado que obtendrá una mala distribución estadística. El mejor caso sería 100 números únicos (todos en la misma X con diferente Y). Eso es al menos 7 bits por número (175 bytes) y muy difícil para cualquier algoritmo de compresión.
La compresión delta funciona en el caso especial cuando sus entidades cambian solo un poco. Si tiene muchos cambios únicos, la codificación delta no ayudará.
Tenga en cuenta que la codificación y la compresión delta también se utilizan en otras situaciones con otras transformaciones.
MPEG divide la imagen en cuadrados pequeños y si parte de la imagen se mueve, solo se guardan el movimiento y un cambio es el brillo. En una película de 25 fps, muchos cambios entre fotogramas son muy pequeños. Nuevamente, codificación delta + compresión. Funciona mejor para escenas estáticas.
fuente