Bagaimana kompresi delta mengurangi jumlah data yang dikirim melalui jaringan?

26

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.

pengguna101051
sumber
Setiap kali Anda melakukan jaringan dengan permainan yang menggunakan segala bentuk kompresi delta, Anda harus benar-benar deterministik (gagal, dan Anda mendapatkan desyncs). Apakah "mengubah dari byte ke float" (atau apa pun) menyebabkan kesalahan presisi tidak penting - syarat yang diperlukan adalah memiliki segalanya persis sama di semua mesin / game yang disinkronkan. Jika ada "kesalahan presisi" (tidak dapat dihindari, bahkan jika Anda menggunakan pelampung penuh - CPU Anda tidak menggunakan pelampung yang sama dengan CPU saya), mereka harus sama pada semua mesin - dan karenanya tidak terlihat. Anda memilih jenis untuk menghindari efek yang terlihat.
Luaan
2
@Luaan atau Anda dapat menambahkan status absolut parsial sesering mungkin, misalnya Anda dapat sesekali memilih beberapa entitas dan melewati posisi absolut, lebih suka memilih entitas yang dekat dengan pemain.
ratchet freak
Entah bagaimana, saya mengharapkan pertanyaan ini tentang kerabat rsync ...
SamB
Pengodean Huffman.
Ben Voigt
Cukup gunakan orang tengah
John Demetriou

Jawaban:

41

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.

Insinyur
sumber
7
Jawaban Anda tidak jelas bagi saya. Saya merasa seperti tidak mengirim informasi objek yang tidak bergerak hanyalah efek samping dari pengkodean delta dan bukan "Semangatnya". Alasan sebenarnya untuk menggunakan delta encoding sepertinya lebih disorot dalam jawaban ratchet freak.
Etsitpab Nioliv
14
@EtsitpabNioliv "The Spirit" hanyalah "jangan mengirim apa yang tidak perlu Anda". Ini dapat diturunkan ke tingkat bit - "gunakan hanya bandwidth sebanyak yang Anda butuhkan untuk mendapatkan pesan yang diperlukan melalui kabel". Jawaban ini tampaknya cukup jelas bagi semua orang. Terima kasih.
Insinyur
4
@EtsitpabNioliv Pernah belajar tentang bagaimana SVN menyimpan sisi server file? Itu tidak menyimpan seluruh file masing-masing komit. Ini menyimpan delta , perubahan yang dilakukan setiap komit. Istilah "delta" sering digunakan dalam matematika dan pemrograman untuk merujuk pada perbedaan antara dua nilai. Saya bukan programmer game, tetapi saya akan terkejut jika penggunaannya jauh berbeda dalam bermain game. Idenya kemudian masuk akal: Anda "memampatkan" jumlah data yang harus Anda kirim dengan hanya mengirim perbedaan, bukan segalanya. (Jika ada bagian yang membingungkan bagi saya, itu adalah kata "kompres.")
jpmc26
1
Juga, angka kecil memiliki jumlah nol bit yang lebih tinggi, dan menggunakan algoritma kompresi yang tepat untuk menyandikan / mendekode informasi yang dikirim dapat menyebabkan muatan yang lebih kecil untuk dikirim melalui jaringan.
liggiorgio
22

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.

corsiKa
sumber
2
Menggunakan diffsuara seperti peretasan yang tidak efisien. Menjaga string JSON di sisi penerima, menambal dan deserialisasi setiap kali tidak perlu. Menghitung perbedaan dari dua kamus nilai-kunci bukanlah tugas yang rumit, pada dasarnya Anda hanya mengulang semua kunci dan memeriksa apakah nilainya sama. Jika tidak, Anda menambahkan mereka ke dict nilai kunci yang dihasilkan dan akhirnya Anda mengirim dict serial ke JSON. Sederhana, tidak perlu keahlian bertahun-tahun. Tidak seperti diff, metode ini: 1) tidak akan menyertakan data lama (diganti); 2) bermain lebih baik dengan UDP; 3) tidak bergantung pada baris baru
gronostaj
8
@gronostaj Ini adalah contoh untuk menjelaskan maksudnya. Saya sebenarnya tidak menganjurkan menggunakan diff untuk JSON - itu sebabnya katakan "kira."
corsiKa
2
"Melakukan ini, Anda memanfaatkan keahlian puluhan tahun dalam mendeteksi perbedaan dalam teks (atau biner!) Dan tidak perlu khawatir kehilangan apa pun sendiri. Sekarang idealnya Anda juga menggunakan perpustakaan yang melakukan ini di belakang layar agar Anda membuatnya lebih rata lebih mudah bagimu sebagai pengembang. " Bagian itu pasti membuatnya terdengar seperti Anda menyarankan menggunakan diff atau menggunakan perpustakaan yang menggunakan diff ketika tidak ada yang akan melakukan hal seperti itu. Saya tidak akan menyebut kompresi delta "berbeda", itu hanya kompresi delta, persamaannya dangkal
Selali Adobor
Diff optimal dan kompresi delta optimal adalah sama. Sementara utilitas diff pada baris perintah diarahkan untuk file teks dan kemungkinan tidak akan memberikan Anda hasil yang optimal, saya akan merekomendasikan meneliti perpustakaan yang melakukan kompresi delta untuk Anda. Tidak ada yang mewah tentang kata delta - delta dan diff, dalam arti ini, secara harfiah berarti hal yang sama. Itu tampaknya telah hilang selama bertahun-tahun.
corsiKa
9

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.

ratchet freak
sumber
1
Contoh lain: jika Anda masing-masing memiliki 100 pesawat ruang angkasa dengan posisi masing-masing tetapi melakukan perjalanan pada vektor kecepatan yang sama, Anda hanya perlu mengirim kecepatan sekali (atau setidaknya kompres dengan sangat baik); jika tidak, Anda harus mengirim 100 posisi sebagai gantinya. Biarkan orang lain melakukan penambahan. Jika Anda menganggap simulasi langkah-keadaan bersama merupakan bentuk agresif kompresi-delta, Anda bahkan tidak mengirim kecepatan - hanya perintah yang datang dari pemain. Sekali lagi, biarkan semua orang menambahkan sendiri.
Luaan
Saya setuju. Kompresi relevan dalam jawabannya.
Leopoldo Sanczyk
8

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.

Maximus Minimus
sumber
8

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.

Peter Green
sumber
6

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.

halus
sumber
4

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
csiz
sumber
Contoh yang bagus. Kompresi berperan di sini.
Leopoldo Sanczyk
0

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.

the_lotus
sumber
0

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.

MartinTeeVarga
sumber