W jaki sposób kompresja delta zmniejsza ilość danych przesyłanych przez sieć?

Wiele gier korzysta z techniki kompresji delta w celu zmniejszenia wysyłanego obciążenia danych. Nie rozumiem, w jaki sposób ta technika faktycznie zmniejsza obciążenie danych?

Powiedzmy na przykład, że chcę wysłać pozycję. Bez kompresji delty wysyłam na vector3przykład dokładną pozycję bytu (30, 2, 19). Z kompresją delta wysyłam vector3mniejszy numer (0.2, 0.1, 0.04).

Nie rozumiem, w jaki sposób zmniejsza obciążenie danych, jeśli oba komunikaty są vector3- 32-bitowe dla każdej liczby zmiennoprzecinkowej - 32 * 3 = 96 bitów!

Wiem, że możesz przekonwertować każdy zmiennoprzecinkowy na bajt, a następnie przekonwertować go z bajtu na zmiennoprzecinkowy, ale powoduje to widoczne błędy precyzji.

Są chwile, kiedy nie można uniknąć wysłania pełnego stanu gry - na przykład po załadowaniu zapisanej gry wieloosobowej lub gdy wymagana jest ponowna synchronizacja. Ale wysyłanie pełny stan jest zazwyczaj uniknąć, i to, gdzie kodowanie delta przychodzi Zazwyczaj jest to. Wszystko to kompresja delta wynosi około; twój przykład tak naprawdę nie opisuje tej sytuacji. Powodem, dla którego wspomniano nawet o kompresji delta, jest to, że naiwne implementacje często wysyłają stan, a nie delty, ponieważ stan jest zwykle tym, co przechowuje każda naiwna implementacja gry. Delty są wtedy optymalizacją.

Z deltami nigdy nie wysłałbyś pozycji jednostek, które się nie poruszyły . Taki jest jego duch.

Wyobraź sobie, że jesteśmy długoletnimi osobami, a straciłem pamięć (i po przeczytaniu odrzuciłem wszystkie twoje listy). Zamiast po prostu kontynuować normalną serię listów, musiałbyś napisać mi całą historię swojego życia jednym ogromnym listem, aby wszystko nadrobić.

W danym przypadku może (w zależności od bazy kodu) być możliwe użycie mniejszej liczby bitów do zakodowania delt, w przeciwieństwie do dużych zakresów bitów potrzebnych do wysłania pełnego stanu. Załóżmy, że świat ma wiele kilometrów średnicy, może być potrzebny 32-bitowy element pływający, aby dokładnie zakodować pozycje w dół, powiedzmy centymetr w danej osi. Jednak biorąc pod uwagę maksymalną prędkość mającą zastosowanie do bytów, która może wynosić tylko kilka metrów na tik, może to być wykonalne tylko w 8 bitach (2 ^ 8 = 256, co wystarcza do przechowywania maksymalnie 200 cm). Oczywiście zakłada to raczej stałe niż zmiennoprzecinkowe użycie ... lub pewnego rodzaju zmiennoprzecinkowe o wartości połowy / ćwiartki, jak w OpenGL, jeśli nie chcesz problemów z punktami stałymi.

Masz niewłaściwą różnicę. Patrzysz na deltę poszczególnych elementów. Musisz pomyśleć o delcie całej sceny.

Załóżmy, że masz 100 elementów w scenie, ale tylko 1 z nich się poruszył. Jeśli wyślesz 100 wektorów elementów, 99 z nich zostanie zmarnowanych. Naprawdę wystarczy wysłać tylko 1.

Powiedzmy, że masz obiekt JSON, który przechowuje wszystkie wektory elementów. Ten obiekt jest synchronizowany między serwerem a klientem. Zamiast decydować: „czy to i tak się przeprowadziło?” możesz po prostu wygenerować następną grę w obiekcie JSON, zróbdiff tick100.json tick101.json i wysłać różnicę. Po stronie klienta zastosujesz różnicę do wektora bieżącego tiku i wszystko jest gotowe.

Robiąc to, wykorzystujesz dziesięciolecia doświadczenia w wykrywaniu różnic w tekście (lub plikach binarnych!) I nie musisz się martwić, że coś przegapisz. Teraz idealnie jest również użyć biblioteki, która robi to za kulisami, aby jeszcze łatwiej było ci jako programistom.

Bardzo często inny mechanizm kompresji będzie w połączeniu z kodowaniem delta, jak na przykład kompresja arytmetyczna.

Te schematy kompresji działają znacznie lepiej, gdy możliwe wartości są pogrupowane w przewidywalny sposób. Kodowanie Delta zgrupuje wartości wokół 0.

Zasadniczo masz rację, ale brakuje ci jednego ważnego punktu.

Podmioty w grze są opisane wieloma atrybutami, z których pozycja jest tylko jedna .

Jakie atrybuty? Bez konieczności zbytniego myślenia, w grze sieciowej mogą to być:

• Pozycja.
• Orientacja.
• Aktualny numer klatki.
• Informacje o kolorze / oświetleniu.
• Przezroczystość.
• Model do użycia.
• Tekstura do użycia.
• Efekty specjalne.
• Itp.

Jeśli wybierzesz każdy z nich osobno, z pewnością możesz stwierdzić, że jeśli w dowolnej ramce musi się zmienić, to należy go ponownie przesłać w całości.

Jednak nie wszystkie z tych atrybutów zmieniają się w tym samym tempie .

Model się nie zmienia? Bez kompresji delta musi i tak zostać ponownie przesłany. Z kompresją delta nie musi tak być.

Pozycja i orientacja to dwa przypadki, które są bardziej interesujące, zwykle złożone z 3 pływaków każdy. Pomiędzy dowolnymi dwiema ramkami istnieje możliwość zmiany tylko 1 lub 2 każdego zestawu 3 pływaków. Poruszasz się po linii prostej? Nie obracasz się? Nie skakać? Są to wszystkie przypadki, w których bez kompresji delta musisz ponownie przesłać w całości, ale w przypadku kompresji delta wystarczy tylko retransmitować to, co się zmienia.

Masz rację, że samo naiwne obliczanie delty, z wynikiem zapisanym w strukturze danych o tym samym rozmiarze co operandy i przesyłanym bez dalszego przetwarzania, nie zaoszczędziłoby żadnego ruchu.

Istnieją jednak dwa sposoby, aby dobrze zaprojektowany system oparty na delcie mógł zaoszczędzić ruch.

Po pierwsze w wielu przypadkach delta będzie wynosić zero. Możesz zaprojektować swój protokół tak, aby jeśli delta wynosiła zero, wcale go nie wysyłałeś. Oczywiście wiąże się to z dodatkowymi kosztami, ponieważ musisz wskazać, co wysyłasz lub nie wysyłasz, ale ogólnie jest to duża wygrana.

Po drugie, delty będą zwykle miały znacznie mniejszy zakres wartości niż liczby pierwotne. i ten zakres będzie wyśrodkowany na zero. Można to wykorzystać albo przez użycie mniejszego typu danych dla większości delt, albo przez przekazanie pełnego strumienia danych przez algorytm kompresji ogólnego przeznaczenia.

Podczas gdy większość odpowiedzi mówi o tym, jak kodowanie delta polega tylko na wysyłaniu zmian do stanu jako całości, istnieje jeszcze jedna rzecz zwana „kodowaniem delta”, która może być używana jako filtr do zmniejszania ilości danych, które należy skompresować w pełnym stanie aktualizuj również, co może być źródłem nieporozumień w zadanym pytaniu.

Podczas kodowania wektora liczb można w niektórych przypadkach (np. Liczby całkowite, wyliczenia itp.) Użyć kodowania zmiennego bajtu dla poszczególnych elementów, aw niektórych przypadkach można dodatkowo zmniejszyć ilość danych potrzebnych każdemu elementowi jeśli przechowujesz je jako sumy bieżące lub jako wartość minimalną i różnicę między każdą wartością a tym minimum.

Na przykład, jeśli chcesz zakodować wektor, możesz go zakodować w formacie {68923, 69012, 69013, 69015}delta jako {68923, 89, 1, 2}. Używając trywialnego kodowania zmiennego bajtu, w którym przechowujesz 7 bitów danych na bajt i używasz jednego bitu, aby wskazać, że nadchodzi kolejny bajt, każdy z poszczególnych elementów w tablicy wymagałby 3 bajtów do przesłania, ale wersja w wersji delta wymagałoby tylko 3 bajtów dla pierwszego elementu i 1 bajtu dla pozostałych elementów; w zależności od tego, jakie dane szeregujesz, może to przynieść całkiem imponujące oszczędności.

Jest to jednak bardziej optymalizacja serializacji i nie ma to na ogół znaczenia, gdy mówimy o „kodowaniu delta”, jeśli chodzi o przesyłanie dowolnych danych w ramach stanu gry (lub wideo lub podobnego); inne odpowiedzi już dobrze tłumaczą.

Warto również zauważyć, że algorytmy kompresji wykonują swoją pracę lepiej na diff. Jak wspominają inne odpowiedzi, albo większość twoich elementów pozostaje niezmienna między 2 stanami, albo wartości zmieniają się o niewielki ułamek. W obu przypadkach zastosowanie algorytmu kompresji do różnicy wektora liczb daje znaczne oszczędności. Nawet jeśli nie zastosujesz żadnej dodatkowej logiki do swojego wektora, takiej jak usunięcie 0 elementów.

Oto przykład w Pythonie:

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)))

Co daje mi:

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

Jeśli twoja pozycja jest zapisana w wektorze3, ale rzeczywisty byt może przesunąć tylko kilka liczb całkowitych naraz. Wtedy przesłanie jego delty w bajtach byłoby lepsze niż wysłanie jej w liczbach całkowitych.

Aktualna pozycja: 23009,0, 1.0, 2342.0 (3 zmiennoprzecinkowe)
Nowa pozycja: 23010.0, 1.0, 2341.0 (3 zmiennoprzecinkowe)
Delta: 1, 0, -1 (3 bajty)

Zamiast wysyłania dokładnej pozycji za każdym razem, wysyłamy deltę.

Kompresja delta to kompresja wartości zakodowanych w delcie. Kodowanie delta to transformacja, która powoduje różny statystyczny rozkład liczb. Jeśli rozkład jest korzystny dla wybranego algorytmu kompresji, zmniejsza ilość danych. Działa bardzo dobrze w systemie takim jak gra, w której jednostki poruszają się tylko nieznacznie między dwiema aktualizacjami.

Załóżmy, że masz 100 elementów w 2D. Na dużej siatce 512 x 512. Biorąc pod uwagę tylko liczby całkowite. To dwie liczby całkowite na jednostkę lub 200 liczb.

Pomiędzy dwiema aktualizacjami wszystkie nasze pozycje zmieniają się o 0, 1, -1, 2 lub -2. Było 100 wystąpień 0, 33 wystąpień 1 i -1 i tylko 17 wystąpień 2 i -2. To jest dość powszechne. Do kompresji wybieramy kodowanie Huffmana.

Drzewo Huffmana do tego będzie:

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

Wszystkie twoje 0 zostaną zakodowane jako pojedynczy bit. To tylko 100 bitów. 66 wartości zostanie zakodowanych jako 3 bity, a tylko 34 wartości jako 4 bity. To 434 bity lub 55 bajtów. Plus trochę narzutów, aby uratować nasze drzewo mapowania, ponieważ drzewo jest małe. Pamiętaj, że do zakodowania 5 liczb potrzebujesz 3 bitów. Wymieniliśmy tutaj możliwość użycia 1 bitu dla „0” dla potrzeby użycia 4 bitów dla „-2”.

Porównaj to teraz z wysyłaniem 200 dowolnych numerów. Jeśli twoje byty nie mogą znajdować się na tym samym kafelku, masz prawie gwarancję, że otrzymasz zły rozkład statystyczny. Najlepszym przypadkiem byłoby 100 niepowtarzalnych liczb (wszystkie na tym samym X z innym Y). To co najmniej 7 bitów na liczbę (175 bajtów) i jest bardzo trudne dla dowolnego algorytmu kompresji.

Kompresja delta działa w szczególnym przypadku, gdy twoje byty zmieniają się tylko nieznacznie. Jeśli masz wiele unikalnych zmian, kodowanie delta nie pomoże.

Zauważ, że kodowanie i kompresja delta jest stosowane również w innych sytuacjach z innymi transformacjami.

MPEG dzieli obraz na małe kwadraty, a jeśli część obrazu się porusza, zapisywany jest tylko ruch i zmiana jasności. W filmie o prędkości 25 klatek na sekundę wiele zmian między klatkami jest bardzo niewielkich. Ponownie kodowanie delta + kompresja. Działa najlepiej w przypadku scen statycznych.