¿Cómo reduce la compresión delta la cantidad de datos enviados a través de la red?

26

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 vector3con la posición exacta de la entidad, por ejemplo (30, 2, 19). Con la compresión delta envío un vector3nú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.

usuario101051
fuente
Cada vez que trabajes en red con un juego que use cualquier forma de compresión delta, debes ser perfectamente determinista (falla y obtienes desincronizaciones). Si "convertir de byte a flotante" (o lo que sea) causa errores de precisión no es importante: la condición necesaria es tener todo exactamente igual en todas las máquinas / juegos sincronizados. Si hay "errores de precisión" (inevitables, incluso si usó flotantes completos (su CPU no usa los mismos flotantes que mi CPU), deben ser los mismos en todas las máquinas y, por lo tanto , no son visibles. Elegiste los tipos para evitar los efectos visibles.
Luaan
2
@Luaan o puede agregar un estado absoluto parcial de vez en cuando, por ejemplo, puede seleccionar de vez en cuando algunas entidades y pasar la posición absoluta, prefiera seleccionar entidades cercanas al jugador.
monstruo de trinquete
De alguna manera, esperaba que esta pregunta fuera sobre algún pariente de rsync ...
SamB
Codificación Huffman.
Ben Voigt
Solo usa un hombre medio
John Demetriou

Respuestas:

41

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.

Ingeniero
fuente
77
Tu respuesta no está clara para mí. Siento que no enviar la información de un objeto que no se mueve es solo un efecto secundario de la codificación delta y no "El espíritu del mismo". La verdadera razón para usar la codificación delta parece resaltarse mejor en la respuesta de Ratchet Freak.
Etsitpab Nioliv
14
@EtsitpabNioliv "El Espíritu" es simplemente "no envíes lo que no tienes que enviar". Esto puede reducirse al nivel de bits: "use solo el ancho de banda que necesite para obtener el mensaje requerido por cable". Esta respuesta evidentemente parece lo suficientemente clara para todos los demás. Gracias.
Ingeniero
44
@EtsitpabNioliv ¿Alguna vez aprendiste sobre cómo SVN almacena archivos en el lado del servidor? No almacena el archivo completo en cada confirmación. Almacena deltas , los cambios que contiene cada confirmación. El término "delta" se usa a menudo en matemáticas y programación para referirse a la diferencia entre dos valores. No soy un programador de juegos, pero me sorprendería si el uso es muy diferente en los juegos. La idea tiene sentido: "comprime" la cantidad de datos que debe enviar enviando solo las diferencias, en lugar de todo. (Si alguna parte es confusa para mí, es la palabra "comprimir")
Jpmc26
1
Además, los números pequeños tienen un mayor número de bits cero, y el uso del algoritmo de compresión adecuado para codificar / decodificar la información enviada puede llevar a una carga útil aún menor a través de la red.
liggiorgio
22

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.jsony 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.

corsiKa
fuente
2
Usar diffsonidos 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íneas
gronostaj
8
@gronostaj Este fue un ejemplo para transmitir el punto. En realidad, no abogo por usar diff para JSON, por eso digo "supongamos".
corsiKa
2
"Al hacer esto, aprovechas las décadas de experiencia en detectar diferencias en el texto (¡o binario!) Y no tienes que preocuparte por perderte nada tú mismo. Ahora, idealmente, también usas una biblioteca que hace esto detrás de escena para que puedas hacerlo incluso más fácil para usted como desarrollador ". Esa parte definitivamente hace que parezca que estás sugiriendo usar un diff o una biblioteca que usa un diff cuando nadie razonablemente haría tal cosa. No llamaría "diferencia" a la compresión delta, es solo compresión delta, las similitudes son superficiales
Selali Adobor
Un diferencial óptimo y una compresión óptima delta son lo mismo. Si bien la utilidad diff en la línea de comandos está diseñada para archivos de texto y probablemente no le brinde un resultado óptimo, recomendaría investigar bibliotecas que hagan la compresión delta por usted. No hay nada de lujos en la palabra delta: delta y diff, en este sentido, significan literalmente lo mismo. Eso parece haberse perdido con los años.
corsiKa
9

Muy 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.

monstruo de trinquete
fuente
1
Otro ejemplo: si tiene 100 naves espaciales cada una con su propia posición pero viajando al mismo vector de velocidad, solo necesita enviar la velocidad una vez (o al menos hacer que se comprima realmente bien); de lo contrario, deberías enviar 100 puestos en su lugar. Deje que otros hagan la suma. Si considera que las simulaciones de pasos de bloqueo de estado compartido son una forma agresiva de compresión delta, ni siquiera envía las velocidades, solo los comandos que provienen del reproductor. Nuevamente, deje que todos hagan su propia suma.
Luaan
Estoy de acuerdo. La compresión es relevante en la respuesta.
Leopoldo Sanczyk
8

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:

  • Posición.
  • Orientación.
  • Número de cuadro actual.
  • Información de color / iluminación.
  • Transparencia.
  • Modelo a utilizar.
  • Textura a utilizar.
  • Efectos especiales.
  • Etc.

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.

Maximus Minimus
fuente
8

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.

Peter Green
fuente
6

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.

mullido
fuente
4

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:

import numpy as np
import zlib
import json
import array


state1 = np.random.random(int(1e6))

diff12 = np.r_[np.random.random(int(0.1e6)), np.zeros(int(0.9e6))]
np.random.shuffle(diff12) # shuffle so we don't cheat by having all 0s one after another
state2 = state1 + diff12

state3 = state2 + np.random.random(int(1e6)) * 1e-6
diff23 = state3 - state2

def compressed_size(nrs):
    serialized = zlib.compress(array.array("d", nrs).tostring())
    return len(serialized)/(1024**2)


print("Only 10% of elements change for state2")
print("Compressed size of diff12: {:.2f}MB".format(compressed_size(diff12)))
print("Compressed size of state2: {:.2f}MB".format(compressed_size(state2)))

print("All elements change by a small value for state3")
print("Compressed size of diff23: {:.2f}MB".format(compressed_size(diff23)))
print("Compressed size of state3: {:.2f}MB".format(compressed_size(state3)))

Lo que me da:

Only 10% of elements change for state2
Compressed size of diff12: 0.90MB
Compressed size of state2: 7.20MB
All elements change by a small value for state3
Compressed size of diff23: 5.28MB
Compressed size of state3: 7.20MB
csiz
fuente
Buen ejemplo La compresión juega un papel aquí.
Leopoldo Sanczyk
0

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.

Posición actual: 23009.0, 1.0, 2342.0 (3 flotadores)
Nueva posición: 23010.0, 1.0, 2341.0 (3 flotadores)
Delta: 1, 0, -1 (3 bytes)

En lugar de enviar la posición exacta cada vez, enviamos el delta.

the_lotus
fuente
0

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á:

 0  0
-1  100
 1  101
 2  110
-2  1110

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.

MartinTeeVarga
fuente