Prediksi pergerakan untuk non-penembak

35

Saya sedang mengerjakan game 2D isometrik dengan multiplayer skala sedang, sekitar 20-30 pemain terhubung sekaligus ke server persisten. Saya mengalami beberapa kesulitan untuk mendapatkan implementasi prediksi pergerakan yang baik.

Fisika / Gerakan

Gim ini tidak memiliki implementasi fisika sejati, tetapi menggunakan prinsip-prinsip dasar untuk mengimplementasikan gerakan. Alih-alih input polling yang terus-menerus, perubahan status (mis. Mouse / turun / atas / memindahkan peristiwa) digunakan untuk mengubah status entitas karakter yang dikontrol pemain. Arah pemain (yaitu / utara-timur) dikombinasikan dengan kecepatan konstan dan berubah menjadi vektor 3D sejati - kecepatan entitas.

Di loop permainan utama, "Pembaruan" disebut sebelum "Draw". Logika pembaruan memicu "tugas pembaruan fisika" yang melacak semua entitas dengan kecepatan non-nol menggunakan integrasi yang sangat mendasar untuk mengubah posisi entitas. Sebagai contoh: entitas.Posisi + = entitas.Velocity.Scale (ElapsedTime.Seconds) (di mana "Detik" adalah nilai titik mengambang, tetapi pendekatan yang sama akan bekerja untuk nilai integer milidetik).

Poin kuncinya adalah bahwa tidak ada interpolasi digunakan untuk gerakan - mesin fisika dasar tidak memiliki konsep "keadaan sebelumnya" atau "keadaan saat ini", hanya posisi dan kecepatan.

Sebutkan Perubahan dan Perbarui Paket

Ketika kecepatan entitas karakter pemain mengendalikan perubahan, paket "pindahkan avatar" dikirim ke server yang berisi jenis tindakan entitas (berdiri, berjalan, jalankan), arah (timur laut), dan posisi saat ini. Ini berbeda dari cara kerja game orang pertama 3D. Dalam game 3D, kecepatan (arah) dapat mengubah bingkai ke bingkai saat pemain bergerak. Mengirim setiap perubahan status akan secara efektif mengirimkan paket per frame, yang akan terlalu mahal. Sebagai gantinya, game 3D tampaknya mengabaikan perubahan status dan mengirim paket "pembaruan negara" pada interval tetap - misalnya, setiap 80-150 ms.

Karena pembaruan kecepatan dan arah terjadi lebih jarang di game saya, saya bisa lolos dengan mengirim setiap perubahan status. Meskipun semua simulasi fisika terjadi pada kecepatan yang sama dan bersifat deterministik, latensi masih menjadi masalah. Untuk alasan itu, saya mengirimkan paket pembaruan posisi rutin (mirip dengan game 3D) tetapi jauh lebih jarang - sekarang setiap 250ms, tetapi saya curiga dengan prediksi yang baik saya dapat dengan mudah meningkatkannya ke 500ms. Masalah terbesar adalah bahwa saya sekarang telah menyimpang dari norma - semua dokumentasi lain, panduan, dan sampel online mengirim pembaruan rutin dan interpolasi antara kedua negara. Tampaknya tidak kompatibel dengan arsitektur saya, dan saya perlu membuat algoritma prediksi pergerakan yang lebih baik yang lebih dekat dengan arsitektur "jaringan fisika" (sangat dasar).

Server kemudian menerima paket dan menentukan kecepatan pemain dari jenis gerakannya berdasarkan pada skrip (Apakah pemain dapat berlari? Dapatkan kecepatan lari pemain). Setelah memiliki kecepatan, ia menggabungkannya dengan arah untuk mendapatkan vektor - kecepatan entitas. Beberapa deteksi cheat dan validasi dasar terjadi, dan entitas di sisi server diperbarui dengan kecepatan, arah, dan posisi saat ini. Pelambatan dasar juga dilakukan untuk mencegah pemain membanjiri server dengan permintaan gerakan.

Setelah memperbarui entitasnya sendiri, server menyiarkan paket "pembaruan posisi avatar" ke semua pemain lain dalam jangkauan. Paket pembaruan posisi digunakan untuk memperbarui simulasi fisika sisi klien (keadaan dunia) dari klien jarak jauh dan melakukan prediksi dan kompensasi lag.

Prediksi dan Kompensasi Lag

Seperti disebutkan di atas, klien berwibawa untuk posisi mereka sendiri. Kecuali dalam kasus kecurangan atau anomali, avatar klien tidak akan pernah diposisikan ulang oleh server. Tidak diperlukan ekstrapolasi ("bergerak sekarang dan perbaiki nanti") untuk avatar klien - apa yang dilihat pemain itu benar. Namun, semacam ekstrapolasi atau interpolasi diperlukan untuk semua entitas jarak jauh yang bergerak. Beberapa jenis prediksi dan / atau kompensasi-lambat jelas diperlukan dalam mesin simulasi / fisika lokal klien.

Masalah

Saya telah berjuang dengan berbagai algoritma, dan memiliki sejumlah pertanyaan dan masalah:

  1. Haruskah saya mengekstrapolasi, menginterpolasi, atau keduanya? "Perasaan" saya adalah bahwa saya harus menggunakan ekstrapolasi murni berdasarkan kecepatan. Perubahan status diterima oleh klien, klien menghitung kecepatan "prediksi" yang mengkompensasi kelambatan, dan sistem fisika reguler melakukan sisanya. Namun, rasanya bertentangan dengan semua kode sampel dan artikel lainnya - mereka semua tampaknya menyimpan sejumlah negara dan melakukan interpolasi tanpa mesin fisika.

  2. Ketika sebuah paket tiba, saya telah mencoba menginterpolasi posisi paket dengan kecepatan paket selama periode waktu yang tetap (katakanlah, 200 ms). Saya kemudian mengambil perbedaan antara posisi interpolasi dan posisi "kesalahan" saat ini untuk menghitung vektor baru dan menempatkannya pada entitas alih-alih kecepatan yang dikirim. Namun, asumsinya adalah bahwa paket lain akan tiba dalam interval waktu itu, dan itu sangat sulit untuk "menebak" ketika paket berikutnya akan tiba - terutama karena mereka tidak semuanya tiba pada interval tetap (yaitu / perubahan negara juga). Apakah konsepnya cacat secara mendasar, atau apakah itu benar tetapi perlu beberapa perbaikan / penyesuaian?

  3. Apa yang terjadi ketika pemain jarak jauh berhenti? Saya dapat segera menghentikan entitas, tetapi akan diposisikan di tempat yang "salah" hingga bergerak lagi. Jika saya memperkirakan vektor atau mencoba menginterpolasi, saya memiliki masalah karena saya tidak menyimpan keadaan sebelumnya - mesin fisika tidak memiliki cara untuk mengatakan "Anda harus berhenti setelah Anda mencapai posisi X". Itu hanya memahami kecepatan, tidak ada yang lebih kompleks. Saya enggan menambahkan informasi "paket gerakan negara" ke entitas atau mesin fisika, karena melanggar prinsip-prinsip desain dasar dan mengeluarkan kode jaringan di seluruh mesin permainan.

  4. Apa yang harus terjadi ketika entitas bertabrakan? Ada tiga skenario - pemain pengendali bertabrakan secara lokal, dua entitas bertabrakan di server selama pembaruan posisi, atau pembaruan entitas jarak jauh bertabrakan pada klien lokal. Dalam semua kasus, saya tidak yakin bagaimana menangani tabrakan - selain dari menyontek, kedua negara "benar" tetapi pada periode waktu yang berbeda. Dalam kasus entitas jauh tidak masuk akal untuk menggambarnya berjalan melalui dinding, jadi saya melakukan deteksi tabrakan pada klien lokal dan membuatnya "berhenti". Berdasarkan poin # 2 di atas, saya dapat menghitung "vektor yang dikoreksi" yang terus-menerus mencoba untuk memindahkan entitas "melalui dinding" yang tidak akan pernah berhasil - avatar jarak jauh macet di sana sampai kesalahannya terlalu tinggi dan "terkunci" ke dalam posisi. Bagaimana permainan mengatasi ini?

ShadowChaser
sumber
1
Apa hubungannya game 3D atau 2D dengan server jenis apa yang Anda gunakan? dan mengapa server tidak athoritive bekerja untuk game Anda?
AttackingHobo
1
@Roy T. pengorbanan bandwidth. Bandwidth adalah sumber daya paling berharga dalam sistem komputer saat ini.
FxIII
1
Itu tidak benar, game online sebagian besar didominasi oleh waktu respons, misalnya pada garis 10Mbit (1,25MB / s) latensi antara server-klien adalah 20 ms, mengirimkan paket 1,25 kb akan memakan waktu 20 ms + 1 ms. Mengirim paket 12.5kb akan memakan waktu 30 ms. Pada jalur yang dua kali lebih cepat, paket 1.25kb masih akan membutuhkan 20ms + 0.5ms, dan 20ms + 5ms untuk paket 12.kb. Latensi adalah faktor pembatas, bukan bandwidth. Lagi pula, saya tidak tahu berapa banyak data yang ada, tetapi mengirim 50 vector3's (posisi 25x + rotasi 25x) hanya 600 byte, mengirimkan ini setiap 20ms akan dikenakan biaya 30kb / s. (+ paket overhead).
Roy T.
2
Mesin gempa memiliki prediksi sejak versi pertama. Prediksi gempa dijelaskan di sana dan di beberapa tempat lain. Saksikan berikut ini.
user712092
1
Apakah Anda melakukan posisi ini + = kecepatan * deltatime untuk setiap entitas secara paralel (imperatif: dalam kode Anda memiliki 2 array parameter fisik entitas, satu frame terpisah, Anda memperbarui yang lebih lama menjadi lebih baru dan menukar mereka)? Ada beberapa masalah dengan iterasi oleh Sean Barret, yang membuat basis mesin Thief 1 .
user712092

Jawaban:

3

Satu-satunya hal untuk dikatakan adalah 2D, isometrik, 3D, semuanya sama dalam masalah ini. Karena Anda melihat banyak contoh 3D dan Anda hanya menggunakan sistem input terbatas oktan 2D dengan kecepatan sesaat tidak berarti Anda dapat membuang prinsip-prinsip jaringan yang telah berkembang selama 20+ tahun terakhir.

Prinsip-prinsip desain akan terkutuk saat permainan dikompromikan!

Dengan membuang sebelumnya dan saat ini Anda membuang beberapa informasi yang dapat menyelesaikan masalah Anda. Untuk data tersebut saya akan menambahkan waktu-perangko dan menghitung lag sehingga ekstrapolasi dapat memprediksi dengan lebih baik di mana pemain akan berada dan interpolasi dapat lebih baik memuluskan perubahan kecepatan dari waktu ke waktu.

Di atas adalah alasan besar mengapa server tampaknya mengirimkan banyak informasi negara dan tidak mengontrol input. Alasan besar lainnya didasarkan pada protokol apa yang Anda gunakan. UDP dengan paket loss yang diterima dan pengiriman tidak sesuai pesanan? TCP dengan pengiriman yang terjamin dan coba lagi? Dengan protokol apa pun Anda akan mendapatkan paket pada waktu yang aneh, tertunda atau bertumpuk satu sama lain dalam kesibukan. Semua paket aneh itu perlu masuk ke dalam konteks sehingga klien dapat mengetahui apa yang terjadi.

Akhirnya, meskipun input Anda sangat terbatas pada 8 arah, perubahan yang sebenarnya dapat terjadi kapan saja - menerapkan siklus 250ms hanya akan membuat pemain frustrasi. 30 pemain bukan masalah besar untuk ditangani server mana pun. Jika Anda berbicara tentang ribuan ... bahkan grup-grup itu terbagi menjadi beberapa boxen sehingga masing-masing server hanya membawa beban yang masuk akal.

Apakah Anda pernah membuat profil mesin fisika seperti Havok atau Bullet berjalan? Mereka sangat dioptimalkan dan sangat, sangat cepat. Anda mungkin jatuh ke dalam perangkap dengan asumsi operasi ABC akan lambat dan mengoptimalkan sesuatu yang tidak membutuhkannya.

Patrick Hughes
sumber
Nasihat bijak-pasti di sini! Sangat mudah untuk melupakan gambaran besarnya. Saya menggunakan TCP dalam hal ini. Masalah "8-direction" tidak sebanyak masalah dalam hal input - itu lebih merupakan masalah dengan interpolasi dan ekstrapolasi. Grafiknya terbatas pada sudut-sudut itu dan menggunakan sprite animasi - gameplay "terlihat aneh" jika pemain bergerak dalam sudut atau kecepatan yang berbeda yang terlalu jauh dari biasanya.
ShadowChaser
1

Jadi server Anda pada dasarnya adalah "wasit"? Dalam hal ini, saya percaya bahwa segala sesuatu di klien Anda harus bersifat deterministik; Anda perlu memastikan bahwa semua yang ada di setiap klien akan selalu memberikan hasil yang sama.

Untuk pertanyaan pertama Anda, setelah pemain lokal menerima arah pemain lain, selain tidak mampu melemahkan pergerakannya dari waktu ke waktu dan menerapkan tabrakan, saya tidak melihat bagaimana Anda bisa memprediksi ke arah mana pemain akan beralih berikutnya, terutama dalam suatu 8 arah lingkungan.

Ketika Anda menerima pembaruan "posisi asli" dari masing-masing pemain (yang mungkin Anda bisa mencoba mengejutkannya di server) ya Anda perlu menginterpolasi posisi dan arah pemain. Jika posisi "tebak" sangat salah (yaitu pemain benar-benar mengubah arah tepat setelah paket arah terakhir dikirim) Anda akan memiliki celah besar. Ini berarti bahwa pemain melompat posisi, atau Anda dapat menginterpolasi ke posisi menebak berikutnya . Ini akan memberikan interpolasi yang lebih lancar dari waktu ke waktu.

Ketika entitas bertabrakan, jika Anda dapat membuat sistem determinis, setiap pemain dapat mensimulasikan tabrakan secara lokal, dan hasilnya tidak boleh terlalu jauh dari kenyataan. Setiap mesin lokal harus mensimulasikan tabrakan untuk kedua pemain, dalam hal ini memastikan bahwa keadaan akhir akan non-blocking dan dapat diterima.

Untuk sisi server, server wasit masih dapat melakukan perhitungan sederhana untuk memeriksa misalnya kecepatan pemain dalam waktu singkat untuk digunakan sebagai mekanisme anti-cheat sederhana. Jika Anda mengulang pemantauan setiap pemain lebih dari 1 pada satu waktu, deteksi cheat Anda akan scalable, hanya saja akan lebih lama untuk menemukan curang.

Jonathan Connell
sumber
Terima kasih - kedengarannya cukup dekat dengan apa yang saya butuhkan, terutama di sisi server. Satu hal yang menarik adalah bahwa meskipun pemain terkunci dalam 8 arah, gerakan internal adalah vektor 3D. Saya memikirkan hal ini sedikit lebih pada hari yang lalu, dan saya pikir saya sedang berjuang dengan kenyataan bahwa saya tidak menerapkan interpolasi sama sekali - saya hanya menggunakan integrasi yang sangat mendasar, mengatur kecepatan dan memperbarui posisi berdasarkan pada vektor setiap pembaruan.
ShadowChaser
Saya tidak yakin bagaimana menggabungkannya dengan interpolasi atau prediksi. Saya mencoba mengambil posisi terbaru yang dikirim dalam paket, mengintegrasikannya selama periode waktu yang tetap (katakanlah, 200 ms) dan kemudian menentukan vektor (kecepatan) yang diperlukan untuk mencapai titik itu dalam 200 ms. Dengan kata lain, terlepas dari posisi salah pemain saat ini di sisi klien, mereka masih harus mencapai "perkiraan posisi yang benar" yang sama dalam 200 ms. Akhirnya mengirim karakter saya ke arah yang gila - saya berasumsi karena 200ms benar-benar harus menjadi waktu untuk paket berikutnya, yang saya tidak bisa perkirakan.
ShadowChaser
Apakah Anda memastikan untuk pertama mengintegrasikan posisi yang tepat di t ke t + 1 sebelum mengintegrasikan posisi yang salah ke posisi yang ditebak di t + 1?
Jonathan Connell
Ya - Saya memeriksa ulang apakah saya menggunakan posisi yang benar untuk integrasi asli. Awalnya itu adalah bug, tetapi memperbaikinya tampaknya tidak membuat peningkatan yang nyata. Kecurigaan saya adalah "+1" - itu harus sangat bergantung pada waktu antar paket. Ada dua masalah: kirim perubahan status selain pembaruan reguler (250 ms) dan saya tidak dapat memprediksi kapan itu akan terjadi. Juga, saya enggan untuk mengunci interval tertentu karena masuk akal bagi server untuk mengirim lebih sedikit pembaruan untuk entitas yang jauh dari pemain. Waktu antar paket bisa berubah.
ShadowChaser
1
Ya termasuk jenis timestep tetap mungkin bukan ide yang baik. Namun saya khawatir bahwa pergerakan 8 arah yang tidak menentu akan sangat sulit (jika bukan tidak mungkin?) Untuk diprediksi. Meski begitu, Anda mungkin dapat mencoba menggunakan latensi rata-rata klien untuk memprediksi t +1, dan memiliki ambang di atas di mana Anda selalu "memindahkan" pemain lain ke posisi baru mereka.
Jonathan Connell
0

Tidak bisakah Anda memasukkan kecepatan dalam keadaan Anda mengubah pesan dan menggunakannya untuk memprediksi gerakan? mis. anggap kecepatan tidak berubah sampai Anda mendapatkan pesan yang mengatakan itu berubah? Saya pikir Anda sudah mengirim posisi, jadi jika sesuatu "melampaui" karena ini Anda tetap memiliki posisi yang benar dari pembaruan berikutnya. Kemudian Anda dapat melangkah posisi selama pembaruan seperti yang Anda lakukan menggunakan kecepatan dari pesan terakhir, dan menimpa posisi setiap kali pesan diterima dengan posisi baru. Ini juga berarti bahwa jika posisi tidak berubah, tetapi kecepatan Anda perlu mengirim pesan (jika itu bahkan merupakan kasus yang valid dalam game Anda), tetapi itu tidak akan banyak mempengaruhi penggunaan bandwidth Anda, jika sama sekali.

Interpolasi seharusnya tidak menjadi masalah di sini, yaitu misalnya ketika Anda tahu di mana sesuatu akan terjadi di masa depan, apakah Anda memilikinya, metode apa yang Anda gunakan, dll. Apakah Anda bingung dengan ekstrapolasi mungkin? (yang saya jelaskan adalah satu, sederhana, pendekatan)

jheriko
sumber
-1

Pertanyaan pertama saya adalah: Apa yang salah dengan menggunakan model di mana server memiliki otoritas? Mengapa penting apakah lingkungannya 2D atau 3D? Itu akan membuat perlindungan cheat Anda jauh lebih mudah jika server Anda otoritatif.

Sebagian besar sampel yang saya lihat erat prediksi pergerakan pasangan ke entitas itu sendiri. Misalnya, menyimpan kondisi sebelumnya bersama dengan kondisi saat ini. Saya ingin menghindari itu dan menjaga entitas dengan "kondisi saat ini" saja. Apakah ada cara yang lebih baik untuk menangani ini?

Saat melakukan prediksi, perlu untuk mempertahankan beberapa status (atau setidaknya delta) pada klien sehingga ketika status otoritatif / delta diterima dari server, dapat dibandingkan dengan yang dimiliki klien dan Anda dapat membuat yang diperlukan koreksi. Idenya adalah untuk menjaga sebanyak mungkin deterministik untuk meminimalkan jumlah koreksi yang diperlukan. Jika Anda tidak mempertahankan status sebelumnya, Anda tidak bisa tahu apakah sesuatu yang berbeda terjadi di server.

Apa yang harus terjadi ketika pemain berhenti? Saya tidak dapat menginterpolasi ke posisi yang benar, karena mereka mungkin perlu berjalan mundur atau arah aneh lain jika posisi mereka terlalu jauh di depan.

Mengapa Anda perlu interpolasi? Server otoritatif harus menimpa setiap gerakan yang salah.

Apa yang harus terjadi ketika entitas bertabrakan? Jika pemain saat ini bertabrakan dengan sesuatu, jawabannya sederhana - hentikan saja pemain agar tidak bergerak. Tetapi apa yang terjadi jika dua entitas mengambil ruang yang sama di server? Bagaimana jika prediksi lokal menyebabkan entitas jauh bertabrakan dengan pemain atau entitas lain - apakah saya juga menghentikannya? Jika prediksi tersebut memiliki kemalangan untuk menempelkannya di depan tembok yang telah dilewati pemain, prediksi tersebut tidak akan pernah bisa mengkompensasi dan begitu kesalahan bertambah tinggi, entitas akan beralih ke posisi baru.

Ini adalah situasi di mana akan ada konflik antara server dan klien dan itulah sebabnya Anda perlu mempertahankan status pada klien sehingga server dapat memperbaiki kesalahan.

Maaf untuk jawaban cepat, saya harus pergi. Baca artikel ini , ia menyebutkan penembak tetapi harus bekerja untuk game apa pun yang membutuhkan jaringan waktu nyata.

Gyan alias Gary Buyn
sumber
Beberapa jawaban: * Jika server memiliki otoritas, itu akan bertanggung jawab untuk melacak semua entitas yang bergerak dan memperbarui posisi mereka secara berkala. Dengan kata lain, perlu menjalankan mesin fisika - yang bisa mahal. Skalabilitas adalah tujuan desain utama saya. * Saya perlu melakukan interpolasi di sisi klien, jika tidak, setiap pembaruan server yang dikirim ke klien akan menyebabkan entitas melompat. Saat ini interpolasi saya dilakukan di mesin fisika - itu hanya mengatur kecepatan. Tidak ada status atau delta.
ShadowChaser
Saya sudah membaca semua artikel Glenn, tetapi dia menyatakan dalam komentar bahwa mereka hanya diarahkan untuk penembak (yaitu / frekuensi pembaruan tinggi). Beberapa artikelnya berbicara tentang klien yang berwibawa, yang merupakan implementasi yang saya perjuangkan. Saya tidak ingin melakukan interpolasi / fisika di server, tapi saya bersedia mengubah pikiran saya jika itu benar-benar satu-satunya cara :)
ShadowChaser
1
-1. Apa yang Anda tulis hanya menyentuh sedikit tentang topik itu; terasa ambigu. Jawaban terasa sub-par ketika mereka pada dasarnya "baca artikel panjang ini", sementara tidak mengandung informasi berguna dari artikel yang ada.
AttackingHobo
1
@AttackingHobo saya harus setuju dengan Anda. Saya mengatakan saya sedang terburu-buru tapi itu bukan alasan. Jika saya tidak punya waktu, akan lebih baik membiarkannya sendiri. Pelajaran yang dipetik.
Gyan alias Gary Buyn