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

26

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.

user101051
la source
Chaque fois que vous faites du réseautage avec un jeu qui utilise n'importe quelle forme de compression delta, vous devez être parfaitement déterministe (échouer et vous obtenez des désynchronisations). Que la "conversion d'octet en flottant" (ou autre) provoque des erreurs de précision n'est pas important - la condition nécessaire est d'avoir tout exactement la même chose dans toutes les machines / jeux synchronisés. S'il y a des "erreurs de précision" (inévitables, même si vous avez utilisé des flottants complets - votre CPU n'utilise pas les mêmes flotteurs que mon CPU), ils doivent être les mêmes sur toutes les machines - et ne sont donc pas visibles. Vous avez choisi les types pour éviter les effets visibles.
Luaan
2
@Luaan ou vous pouvez ajouter un état absolu partiel de temps en temps, par exemple, vous pouvez de temps en temps sélectionner quelques entités et passer la position absolue, préférez sélectionner des entités proches du joueur.
monstre à cliquet
D'une manière ou d'une autre, je m'attendais à ce que cette question concerne un parent de rsync ...
SamB
Codage Huffman.
Ben Voigt
Il suffit d'utiliser l'homme du milieu
John Demetriou

Réponses:

41

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.

Ingénieur
la source
7
Votre réponse n'est pas claire pour moi. J'ai l'impression de ne pas envoyer les informations d'un objet qui ne bouge pas est juste un effet secondaire de l'encodage delta et non pas "l'esprit de celui-ci". La vraie raison d'utiliser l'encodage delta semble être mieux mise en évidence dans la réponse de Ratchet Freak.
Etsitpab Nioliv
14
@EtsitpabNioliv "L'Esprit" est simplement "n'envoyez pas ce que vous n'avez pas à". Cela peut être ramené au niveau binaire - "n'utilisez que la bande passante dont vous avez besoin pour obtenir le message requis sur le câble". Cette réponse semble évidemment assez claire pour tout le monde. Merci.
Ingénieur
4
@EtsitpabNioliv Avez-vous déjà appris comment SVN stocke les fichiers côté serveur? Il ne stocke pas le fichier entier à chaque validation. Il stocke les deltas , les changements que contient chaque commit. Le terme "delta" est souvent utilisé en mathématiques et en programmation pour désigner la différence entre deux valeurs. Je ne suis pas un programmeur de jeux, mais je serais surpris si l'utilisation est si différente dans les jeux. L'idée prend alors tout son sens: vous "compressez" la quantité de données que vous devez envoyer en envoyant uniquement les différences, au lieu de tout. (Si une partie me
déroute
1
En outre, les petits nombres ont un nombre plus élevé de bits zéro, et l'utilisation de l'algorithme de compression approprié pour coder / décoder les informations envoyées peut conduire à une charge utile encore plus petite à envoyer sur le réseau.
liggiorgio
22

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.

corsiKa
la source
2
Utiliser des diffsons comme un hack inefficace. Il n'est pas nécessaire de conserver la chaîne JSON sur l'extrémité de réception, de la corriger et de la désérialiser à chaque fois. Le calcul de la différence de deux dictionnaires de valeurs-clés n'est pas une tâche compliquée, en gros il suffit de parcourir toutes les clés et de vérifier si les valeurs sont égales. Sinon, vous les ajoutez au dict de valeur-clé résultant et enfin vous envoyez le dict sérialisé à JSON. Simple, aucune année d'expertise requise. Contrairement aux diffs, cette méthode: 1) n'inclura pas les anciennes données (remplacées); 2) joue mieux avec UDP; 3) ne compte pas sur les nouvelles lignes
gronostaj
8
@gronostaj C'était un exemple pour faire passer le message. Je ne préconise pas réellement l'utilisation de diff pour JSON - c'est pourquoi dites "suppose".
corsiKa
2
"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. plus facile pour vous en tant que développeur. " Cette partie donne définitivement l'impression que vous proposez d'utiliser un diff ou d'utiliser une bibliothèque qui utilise un diff alors que personne ne ferait raisonnablement une telle chose. Je n'appellerais pas la compression delta "différente", c'est juste une compression delta, les similitudes sont superficielles
Selali Adobor
Un diff optimal et une compression delta optimale sont les mêmes. Bien que l'utilitaire diff sur la ligne de commande soit destiné aux fichiers texte et ne vous fournisse probablement pas un résultat optimal, je vous recommande de rechercher des bibliothèques qui effectuent la compression delta pour vous. Le mot delta n'a rien d'extraordinaire - delta et diff, dans ce sens, signifient littéralement la même chose. Cela semble avoir été perdu au fil des ans.
corsiKa
9

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.

monstre à cliquet
la source
1
Un autre exemple: si vous avez 100 vaisseaux spatiaux chacun avec leur propre position mais voyageant au même vecteur de vitesse, vous n'avez besoin d'envoyer la vitesse qu'une seule fois (ou au moins de la compresser très bien); sinon, vous devrez envoyer 100 positions à la place. Laissez les autres faire l'ajout. Si vous considérez les simulations d'étapes de verrouillage à état partagé comme une forme agressive de compression delta, vous n'envoyez même pas les vitesses - uniquement les commandes provenant du lecteur. Encore une fois, laissez chacun faire sa propre addition.
Luaan
Je suis d'accord. La compression est pertinente dans la réponse.
Leopoldo Sanczyk
8

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.

Maximus Minimus
la source
8

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.

Peter Green
la source
6

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.

duveteux
la source
4

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
csiz
la source
Bel exemple. La compression joue ici un rôle.
Leopoldo Sanczyk
0

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.

the_lotus
la source
0

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.

MartinTeeVarga
la source