Bagaimana kompresi delta mengurangi jumlah data yang dikirim melalui jaringan?

Banyak game menggunakan teknik kompresi delta untuk menurunkan beban data yang dikirim. Saya gagal memahami bagaimana teknik ini sebenarnya menurunkan beban data?

Misalnya, katakanlah saya ingin mengirim posisi. Tanpa kompresi delta, saya mengirim a vector3dengan posisi persis entitas, misalnya (30, 2, 19). Dengan kompresi delta, saya mengirim vector3angka yang lebih kecil (0.2, 0.1, 0.04).

Saya tidak mengerti bagaimana menurunkan beban data jika kedua pesannya vector3- 32 bit untuk setiap float - 32 * 3 = 96 bit!

Saya tahu Anda dapat mengkonversi setiap float ke byte dan kemudian mengubahnya kembali dari byte ke float tetapi menyebabkan kesalahan presisi yang terlihat.

Ada saat-saat ketika Anda tidak dapat menghindari pengiriman status permainan penuh - seperti saat memuat game multi-pemain yang disimpan, atau saat diperlukan sinkronisasi ulang. Tetapi mengirimkan negara penuh biasanya dihindari, dan di sanalah delta encoding datang Umumnya, ini. Semua yang kompresi delta adalah tentang; teladan Anda tidak benar-benar menggambarkan situasi itu. Alasan kompresi delta bahkan disebutkan adalah karena implementasi naif sering akan mengirim status daripada delta karena keadaan biasanya adalah apa yang disimpan oleh toko implementasi game naif. Delta kemudian merupakan optimasi.

Dengan delta, Anda tidak akan pernah mengirim posisi unit yang tidak bergerak sama sekali. Itulah semangatnya.

Bayangkan kami adalah sahabat selama bertahun-tahun, dan saya kehilangan ingatan (dan telah membuang semua surat Anda setelah membacanya). Alih-alih hanya melanjutkan dengan rangkaian surat Anda seperti biasa, Anda harus menulis kepada saya seluruh sejarah hidup Anda dalam satu surat besar, sekali lagi, agar saya bisa mengejarnya.

Dalam kasus Anda, mungkin (tergantung pada basis kode Anda) dimungkinkan menggunakan jumlah bit yang lebih rendah untuk menyandikan delta, sebagai lawan dari rentang bit besar yang diperlukan untuk mengirim keadaan penuh. Katakanlah dunia berjarak beberapa kilometer, Anda mungkin perlu pelampung 32-bit untuk secara akurat menyandikan posisi ke bawah untuk mengatakan, satu sentimeter dalam sumbu yang diberikan. Namun, mengingat kecepatan maksimum yang berlaku untuk entitas, yang mungkin hanya beberapa meter per tick, itu mungkin dapat dilakukan hanya dalam 8 bit (2 ^ 8 = 256 sehingga cukup untuk menyimpan maks 200cm). Tentu saja, ini mengasumsikan tetap daripada penggunaan floating point ... atau semacam float setengah / seperempat seperti di OpenGL, jika Anda tidak ingin kerepotan titik tetap.

Anda memiliki delta yang salah. Anda sedang melihat delta elemen individu. Anda perlu memikirkan delta dari seluruh adegan.

Misalkan Anda memiliki 100 elemen dalam adegan Anda, tetapi hanya 1 yang bergerak. Jika Anda mengirim 100 vektor elemen, 99 di antaranya terbuang sia-sia. Anda benar-benar hanya perlu mengirim 1.

Sekarang, katakanlah Anda memiliki objek JSON yang menyimpan semua vektor elemen Anda. Objek ini disinkronkan antara server Anda dan klien Anda. Alih-alih memutuskan "apakah ini dan itu bergerak?" Anda bisa menghasilkan centang game berikutnya di objek JSON, buat diff tick100.json tick101.jsondan kirim diff itu. Di sisi klien, Anda menerapkan diff ke vektor kutu Anda saat ini dan Anda siap.

Melakukan ini, Anda memanfaatkan keahlian puluhan tahun dalam mendeteksi perbedaan dalam teks (atau biner!) Dan tidak perlu khawatir kehilangan apa pun. Sekarang idealnya Anda juga menggunakan perpustakaan yang melakukan ini di belakang layar agar Anda lebih mudah sebagai pengembang.

Sangat sering mekanisme kompresi lain akan dikombinasikan dengan pengkodean delta seperti misalnya kompresi aritmatika.

Skema kompresi tersebut bekerja jauh lebih baik ketika nilai yang mungkin dikelompokkan bersama secara terprediksi. Pengkodean Delta akan mengelompokkan nilai-nilai di sekitar 0.

Anda secara luas benar, tetapi kehilangan satu poin penting.

Entitas dalam game dijelaskan oleh banyak atribut, yang posisinya hanya satu .

Atribut seperti apa? Tanpa harus berpikir terlalu keras, dalam game jaringan ini termasuk:

• Posisi.
• Orientasi.
• Nomor bingkai saat ini.
• Informasi warna / pencahayaan.
• Transparansi.
• Model untuk digunakan.
• Tekstur untuk digunakan.
• Efek khusus.
• Dll

Jika Anda memilih masing-masing secara terpisah, Anda tentu dapat menyatakan bahwa jika dalam kerangka tertentu perlu diubah, maka harus ditransmisikan ulang sepenuhnya.

Namun, tidak semua atribut ini berubah pada kecepatan yang sama .

Model tidak berubah? Tanpa kompresi delta, bagaimanapun juga harus dikirimkan kembali. Dengan delta Compresion tidak perlu begitu.

Posisi dan orientasi adalah dua kasus yang lebih menarik, umumnya terdiri dari 3 pelampung masing-masing. Di antara dua frame yang diberikan, ada kemungkinan bahwa hanya 1 atau 2 dari setiap set 3 float yang dapat berubah. Bergerak dalam garis lurus? Tidak berputar? Tidak melompat? Ini semua adalah kasus di mana tanpa kompresi delta Anda harus mentransmisikan ulang secara penuh, tetapi dengan kompresi delta Anda hanya perlu mentransmisikan kembali yang berubah.

Anda benar bahwa perhitungan delta naif sendiri, dengan hasil disimpan dalam struktur data ukuran yang sama dengan operan dan ditransmisikan tanpa proses lebih lanjut tidak akan menghemat lalu lintas.

Namun, ada dua cara sistem yang dirancang dengan baik berdasarkan delta dapat menghemat lalu lintas.

Pertama-tama dalam banyak kasus delta akan menjadi nol. Anda dapat mendesain protokol Anda sehingga jika delta nol Anda tidak mengirimnya sama sekali. Jelas, ada beberapa overhead untuk ini karena Anda harus menunjukkan apa yang Anda kirim atau tidak, tetapi secara keseluruhan kemungkinan akan menjadi kemenangan besar.

Kedua, delta biasanya memiliki kisaran nilai yang jauh lebih kecil daripada angka aslinya. dan rentang itu akan berpusat pada nol. Ini dapat dieksploitasi baik dengan menggunakan tipe data yang lebih kecil untuk sebagian besar delta atau dengan melewatkan aliran data lengkap melalui algoritma kompresi tujuan umum.

Sementara sebagian besar jawaban berbicara tentang bagaimana pengkodean delta adalah hanya mengirim perubahan ke keadaan secara keseluruhan, ada hal lain yang disebut "pengkodean delta" yang dapat digunakan sebagai filter untuk mengurangi jumlah data yang Anda perlu kompres dalam keadaan penuh memperbarui juga, yang mungkin dari mana kebingungan berasal dari pertanyaan yang ditanyakan.

Saat menyandikan vektor angka, Anda dapat dalam beberapa kasus (misalnya bilangan bulat, enum, dll.) Menggunakan pengkodean byte-variabel untuk elemen individual, dan dalam beberapa kasus ini Anda dapat mengurangi jumlah data yang dibutuhkan setiap elemen jika Anda menyimpannya sebagai jumlah berjalan, atau sebagai nilai minimum dan perbedaan antara setiap nilai dan minimum itu.

Sebagai contoh, jika Anda ingin menyandikan vektor {68923, 69012, 69013, 69015}maka Anda bisa delta-encode sebagai {68923, 89, 1, 2}. Menggunakan pengkodean byte-variabel sepele di mana Anda menyimpan 7 bit data per byte dan menggunakan satu bit untuk menunjukkan bahwa ada byte lain yang datang, masing-masing elemen individu dalam array akan membutuhkan 3 byte untuk mengirimkannya, tetapi versi delta-encoded hanya membutuhkan 3 byte untuk elemen pertama dan 1 byte untuk elemen lainnya; tergantung pada jenis data yang Anda serialkan, ini dapat menyebabkan penghematan yang cukup mengesankan.

Namun, ini lebih merupakan optimasi serialisasi dan bukan apa yang umumnya dimaksudkan ketika kita berbicara tentang "delta encoding" ketika datang untuk streaming data sewenang-wenang sebagai bagian dari kondisi permainan (atau video atau sejenisnya); jawaban lain sudah cukup menjelaskan hal itu.

Perlu juga dicatat bahwa algoritma kompresi melakukan tugasnya dengan lebih baik pada diff. Seperti jawaban lain menyebutkan sebagian besar elemen Anda tetap sama di antara 2 status, atau nilainya berubah sedikit. Dalam kedua kasus ini menerapkan algoritma kompresi pada perbedaan vektor angka Anda memberi Anda penghematan yang signifikan. Bahkan jika Anda tidak menerapkan logika tambahan apa pun pada vektor Anda seperti menghapus 0 elemen.

Berikut ini contoh dalam 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)))

Yang memberi saya:

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

Jika posisi Anda disimpan dalam vector3 tetapi entitas yang sebenarnya hanya dapat memindahkan beberapa bilangan bulat sekaligus. Kemudian mengirimkan delta dalam byte akan lebih baik daripada mengirimkannya dalam bentuk integer.

Posisi saat ini: 23009.0, 1.0, 2342.0 (3 float)
Posisi baru: 23010.0, 1.0, 2341.0 (3 float)
Delta: 1, 0, -1 (3 byte)

Alih-alih mengirim posisi yang tepat setiap kali, kami mengirim delta.

Kompresi delta adalah kompresi nilai-nilai yang dikodekan delta. Pengkodean Delta adalah transformasi yang menghasilkan distribusi angka statistik yang berbeda. Jika distribusi menguntungkan untuk algoritma kompresi yang dipilih, itu menurunkan jumlah data. Ini bekerja sangat baik dalam sistem seperti game di mana entitas hanya bergerak sedikit antara dua pembaruan.

Katakanlah Anda memiliki 100 entitas dalam 2D. Pada kisi besar, 512 x 512. Mempertimbangkan hanya bilangan bulat demi contoh. Itu dua angka integer per entitas atau 200 angka.

Di antara dua pembaruan, semua posisi kami berubah dengan 0, 1, -1, 2 atau -2. Ada 100 contoh 0, 33 contoh 1 dan -1 dan hanya 17 contoh 2 dan -2. Ini sangat umum. Kami memilih pengkodean Huffman untuk kompresi.

Pohon Huffman untuk ini adalah:

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

Semua 0 Anda akan dikodekan sebagai bit tunggal. Itu hanya 100 bit. Nilai 66 akan dikodekan sebagai 3 bit dan hanya 34 nilai sebagai 4 bit. Itu 434 bit atau 55 byte. Ditambah beberapa overhead kecil untuk menyelamatkan pohon pemetaan kami, karena pohon itu kecil. Perhatikan bahwa untuk menyandikan 5 angka, Anda membutuhkan 3 bit. Kami telah diperdagangkan di sini kemampuan untuk menggunakan 1 bit untuk '0' untuk kebutuhan menggunakan 4 bit untuk '-2'.

Sekarang bandingkan ini dengan mengirim 200 nomor acak. Jika entitas Anda tidak dapat berada di ubin yang sama, Anda hampir dijamin bahwa Anda mendapatkan distribusi statistik yang buruk. Kasing terbaik adalah 100 nomor unik (semua pada X yang sama dengan Y yang berbeda). Itu setidaknya 7 bit per angka (175 byte) dan sangat sulit untuk semua algoritma kompresi.

Kompresi delta bekerja dalam kasus khusus ketika entitas Anda hanya berubah sedikit. Jika Anda memiliki banyak perubahan unik, pengkodean delta tidak akan membantu.

Perhatikan bahwa pengkodean dan kompresi delta digunakan dalam situasi lain dengan transformasi lain juga.

MPEG membagi gambar dalam kotak kecil dan jika bagian gambar bergerak, hanya gerakan dan perubahan kecerahan yang disimpan. Dalam film 25fps, banyak perubahan di antara frame sangat kecil. Sekali lagi, delta encoding + kompresi. Berfungsi paling baik untuk adegan statis.