Comment la compression delta réduit-elle la quantité de données envoyées sur le réseau?

De nombreux jeux utilisent la technique de la compression delta afin de réduire la charge de données envoyée. Je n'arrive pas à comprendre comment cette technique réduit réellement la charge de données?

Par exemple, disons que je veux envoyer un poste. Sans compression delta, j'envoie un vector3avec la position exacte de l'entité, par exemple (30, 2, 19). Avec la compression delta, j'envoie un vector3avec des nombres plus petits (0.2, 0.1, 0.04).

Je ne comprends pas comment cela réduit la charge de données si les deux messages sont vector3- 32 bits pour chaque flotteur - 32 * 3 = 96 bits!

Je sais que vous pouvez convertir chaque flotteur en octet, puis le reconvertir d'un octet en flottant, mais cela provoque des erreurs de précision qui sont visibles.

Il y a des moments où vous ne pouvez pas éviter d'envoyer l'état complet du jeu - comme lors du chargement d'une partie multijoueur enregistrée ou lorsqu'une resynchronisation est nécessaire. Mais l'envoi de l'état complet est généralement évitable, et c'est là qu'intervient l'encodage delta . Généralement, c'est tout ce que la compression delta est sur le point; votre exemple ne décrit pas vraiment cette situation. La raison pour laquelle la compression delta est même mentionnée est que les implémentations naïves envoient souvent un état plutôt que des deltas car l'état est généralement ce que toute implémentation de jeu naïf stocke de toute façon. Les deltas sont alors une optimisation.

Avec les deltas, vous n'enverriez jamais du tout les positions des unités qui ne bougeaient pas . C'est ça l'esprit.

Imaginez que nous étions des correspondants pendant des années et j'ai perdu la mémoire (et j'avais jeté toutes vos lettres après les avoir lues). Au lieu de simplement continuer votre série de lettres comme d'habitude, vous devrez m'écrire toute l'histoire de votre vie en une seule lettre massive, encore une fois, pour que je me rattrape.

Dans votre cas donné, il peut (selon votre base de code) être possible d'utiliser un nombre inférieur de bits pour coder les deltas, par opposition aux grandes plages de bits nécessaires pour envoyer l'état complet. Supposons que le monde ait plusieurs kilomètres de diamètre, vous aurez peut-être besoin d'un flotteur de 32 bits pour encoder avec précision des positions jusqu'à un centimètre dans un axe donné. Cependant, étant donné la vitesse maximale applicable aux entités, qui ne peut être que de quelques mètres par tick, elle peut être réalisable en seulement 8 bits (2 ^ 8 = 256 donc suffisante pour stocker max de 200 cm). Bien sûr, cela suppose une utilisation fixe plutôt que virgule flottante ... ou une sorte de demi / quart flottant comme dans OpenGL, si vous ne voulez pas de tracas en virgule fixe.

Vous avez le mauvais delta. Vous regardez le delta des éléments individuels. Vous devez penser au delta de toute la scène.

Supposons que vous ayez 100 éléments dans votre scène, mais seulement 1 d'entre eux a bougé. Si vous envoyez 100 vecteurs d'éléments, 99 d'entre eux sont perdus. Vous n'avez vraiment besoin d'envoyer que 1.

Supposons maintenant que vous ayez un objet JSON qui stocke tous vos vecteurs d'éléments. Cet objet est synchronisé entre votre serveur et votre client. Au lieu de décider «a fait telle ou telle chose? vous pouvez simplement générer votre prochain tick de jeu dans un objet JSON, faire un diff tick100.json tick101.jsonet envoyer ce diff. Côté client, vous appliquez le diff au vecteur de votre tick actuel et vous êtes prêt.

En faisant cela, vous tirez parti des décennies d'expertise dans la détection des différences de texte (ou binaire!) Et vous n'avez pas à vous soucier de ne rien manquer vous-même. Maintenant, idéalement, vous utilisez également une bibliothèque qui le fait en arrière-plan pour que cela vous soit encore plus facile en tant que développeur.

Très souvent, un autre mécanisme de compression sera associé à un codage delta comme par exemple la compression arithmétique.

Ces schémas de compression fonctionnent beaucoup mieux lorsque les valeurs possibles sont regroupées de manière prévisible. L'encodage Delta regroupera les valeurs autour de 0.

Vous avez globalement raison, mais il manque un point important.

Les entités d'un jeu sont décrites par de nombreux attributs, dont la position n'est qu'un .

Quel genre d'attributs? Sans trop réfléchir, dans un jeu en réseau, cela peut inclure:

• Position.
• Orientation.
• Numéro de trame actuel.
• Informations sur la couleur / l'éclairage.
• Transparence.
• Modèle à utiliser.
• Texture à utiliser.
• Effets spéciaux.
• Etc.

Si vous choisissez chacun de ces éléments isolément, vous pouvez certainement faire valoir que si, dans un cadre donné, il doit changer, il doit être retransmis en totalité.

Cependant, tous ces attributs ne changent pas au même rythme .

Le modèle ne change pas? Sans compression delta, il doit quand même être retransmis. Avec la compression delta, ce n'est pas nécessaire.

La position et l'orientation sont deux cas plus intéressants, généralement composés de 3 flotteurs chacun. Entre deux images, il est possible que seulement 1 ou 2 de chaque ensemble de 3 flotteurs puissent changer. Vous vous déplacez en ligne droite? Ne tourne pas? Ne pas sauter? Ce sont tous des cas où, sans compression delta, vous devez retransmettre en totalité, mais avec la compression delta, vous devez uniquement retransmettre ce qui change.

Vous avez raison de dire qu'un calcul delta naïf à lui seul, avec le résultat stocké dans la même structure de données de taille que les opérandes et transmis sans autre traitement, ne sauverait aucun trafic.

Cependant, il existe deux façons dont un système bien conçu basé sur des deltas peut économiser du trafic.

Tout d'abord dans de nombreux cas, le delta sera nul. Vous pouvez concevoir votre protocole de telle sorte que si le delta est nul, vous ne l'envoyez pas du tout. De toute évidence, il y a des frais généraux à cela car vous devez indiquer ce que vous envoyez ou ce que vous n'envoyez pas, mais dans l'ensemble, ce sera probablement une grande victoire.

Deuxièmement, les deltas auront généralement une plage de valeurs beaucoup plus petite que les nombres d'origine. et cette plage sera centrée sur zéro. Cela peut être exploité soit en utilisant un type de données plus petit pour la plupart des deltas, soit en passant le flux de données complet via un algorithme de compression à usage général.

Alors que la plupart des réponses parlent de la façon dont l'encodage delta consiste uniquement à envoyer les modifications à l'état dans son ensemble, il existe une autre chose appelée «encodage delta» qui peut être utilisée comme filtre pour réduire la quantité de données dont vous avez besoin pour compresser dans l'état complet. mise à jour également, ce qui peut être la source de la confusion dans la question posée.

Lors du codage d'un vecteur de nombres, vous pouvez dans certains cas (par exemple des entiers, des énumérations, etc.) utiliser un codage à octets variables pour les éléments individuels, et dans certains de ces cas, vous pouvez réduire davantage la quantité de données dont chaque élément a besoin si vous le stockez en tant que sommes cumulées, ou en tant que valeur minimale et différence entre chaque valeur et ce minimum.

Par exemple, si vous souhaitez coder le vecteur, {68923, 69012, 69013, 69015}vous pouvez le coder en delta en tant que {68923, 89, 1, 2}. En utilisant un encodage variable à octets variables où vous stockez 7 bits de données par octet et utilisez un bit pour indiquer qu'un autre octet arrive, chacun des éléments individuels du tableau nécessiterait 3 octets pour le transmettre, mais la version codée en delta ne nécessiterait que 3 octets pour le premier élément et 1 octet pour les autres éléments; selon les types de données que vous sérialisez, cela peut entraîner des économies assez impressionnantes.

Cependant, il s'agit davantage d'une optimisation de sérialisation et ce n'est pas ce que l'on entend généralement lorsque nous parlons de «codage delta» lorsqu'il s'agit de diffuser des données arbitraires dans le cadre de l'état du jeu (ou de la vidéo ou similaire); d'autres réponses expliquent déjà bien cela.

Il convient également de noter que les algorithmes de compression font mieux leur travail sur le diff. Comme d'autres réponses mentionnent soit la plupart de vos éléments restent les mêmes entre 2 états, soit les valeurs changent d'une petite fraction. Dans ces deux cas, l'application d'un algorithme de compression à la différence de votre vecteur de nombres vous permet de réaliser d'importantes économies. Même si vous n'appliquez aucune logique supplémentaire à votre vecteur comme la suppression des éléments 0.

Voici un exemple 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)))

Ce qui me donne:

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

Si votre position est stockée dans vector3 mais que l'entité réelle ne peut déplacer que quelques entiers à la fois. Ensuite, envoyer son delta en octets serait mieux que de l'envoyer en entier.

Position actuelle: 23009.0, 1.0, 2342.0 (3 flotteurs)
Nouvelle position: 23010.0, 1.0, 2341.0 (3 flottants)
Delta: 1, 0, -1 (3 octets)

Au lieu d'envoyer la position exacte à chaque fois, nous envoyons le delta.

La compression delta est une compression de valeurs codées delta. Le codage delta est une transformation qui produit une distribution statistique différente des nombres. Si la distribution est favorable à l'algorithme de compression choisi, elle diminue la quantité de données. Cela fonctionne très bien dans un système comme un jeu où les entités ne se déplacent que légèrement entre deux mises à jour.

Disons que vous avez 100 entités en 2D. Sur une grande grille, 512 x 512. En ne prenant en compte que des nombres entiers à titre d'exemple. C'est deux nombres entiers par entité ou 200 nombres.

Entre deux mises à jour, toutes nos positions changent de 0, 1, -1, 2 ou -2. Il y a eu 100 instances de 0, 33 instances de 1 et -1 et seulement 17 instances de 2 et -2. C'est assez courant. Nous choisissons le codage Huffman pour la compression.

L'arbre Huffman pour cela sera:

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

Tous vos 0 seront codés en un seul bit. Ce n'est que 100 bits. 66 valeurs seront codées en 3 bits et seulement 34 valeurs en 4 bits. C'est 434 bits ou 55 octets. Plus quelques petits frais généraux pour enregistrer notre arbre de cartographie, car l'arbre est minuscule. Notez que pour encoder 5 nombres, vous avez besoin de 3 bits. Nous avons échangé ici la possibilité d'utiliser 1 bit pour «0» pour la nécessité d'utiliser 4 bits pour «-2».

Comparez maintenant cela à l'envoi de 200 nombres arbitraires. Si vos entités ne peuvent pas être sur la même tuile, vous êtes presque assuré d'obtenir une mauvaise distribution statistique. Le meilleur cas serait de 100 numéros uniques (tous sur le même X avec des Y différents). C'est au moins 7 bits par nombre (175 octets) et très difficile pour tout algorithme de compression.

La compression delta fonctionne dans le cas spécial où vos entités ne changent que peu. Si vous avez beaucoup de changements uniques, l'encodage delta ne vous aidera pas.

Notez que l'encodage et la compression delta sont également utilisés dans d'autres situations avec d'autres transformations.

MPEG divise l'image en petits carrés et si une partie de l'image se déplace, seuls le mouvement et un changement de luminosité sont enregistrés. Dans un film à 25 images par seconde, de nombreux changements entre les images sont très faibles. Encore une fois, encodage delta + compression. Fonctionne mieux pour les scènes statiques.