Cara menangani sejumlah besar pickup dalam game MMO

26

Bagaimana gim seperti Minecraft, atau gim MMO mana pun yang memiliki pickup, menanganinya?

Katakanlah medan memunculkan 3 tetes pickup "kotoran" setiap kali Anda menggali medan tersebut. Katakanlah setiap item memiliki animasi rotasi yang menghitung setiap frame. Jika jumlah pickup di dunia menjadi sangat tinggi, itu akan menjadi biaya overhead besar yang tidak berguna dalam perhitungan frame untuk klien di server tertentu, karena kemungkinan banyak dari item pickup itu berjarak beberapa tahun dari Anda.

Jadi yang saya pikirkan adalah Anda harus "melakukan hal-hal" hanya dengan pickup dekat dengan pemain lokal, tetapi tetap saja ini menyiratkan bahwa setiap frame saya harus memeriksa apakah ada item pickup lain yang cukup dekat sehingga harus mulai dianimasikan.

Pertanyaan saya yang sebenarnya adalah: bagaimana MMO lain memecahkan masalah ini?

Alakanu
sumber
9
Selain itu, dalam konteks Minecraft, setelah sejumlah item cukup dekat satu sama lain (3+ item yang sama di blockspace yang sama), server mengganti 3 instance dengan instance yang dikelompokkan yang berisi tipe blok ( minecraft:dirt) dan hitungan (30), sehingga ketika pemain cukup dekat untuk mengambilnya, itu hanya menambahkan sebanyak mungkin hitungan ke inventaris pemain. Jika pemain hanya memiliki ruang untuk 6 item dan setumpuk 30 berada di tanah, pemain akan mengambil 6, dan tumpukan pada hitungan tanah dikurangi menjadi 24.
Zymus
6
@Zymus Perlu dicatat bahwa sebenarnya menurunkan kinerja kutu untuk jumlah item terjatuh yang moderat karena mereka semua terus mencari yang terdekat.
pengguna253751
Baca melalui en.wikipedia.org/wiki/Occlusion_culling
RJFalconer

Jawaban:

48

Dengan hanya memuat bagian-bagian dunia ke dalam memori yang dekat dengan pemain. Ada lagi yang diskors ke hard drive. Ketika ada benda mungil tergeletak sekitar dua kilometer jauhnya, maka pemain tidak bisa melihatnya dan tidak bisa berinteraksi dengannya. Jadi tidak ada alasan untuk memperbaruinya atau mengirimkannya ke GPU untuk dirender. Semakin kecil objek dan rentang interaksinya, semakin rendah kisaran di sekitar pemain tempat Anda perlu memuatnya.

Mengenai mencari tahu apa yang dekat dengan pemain: Itu sebagian besar bermuara untuk menyimpan dunia dalam struktur data yang dioptimalkan untuk pencarian spasial. Calon yang baik untuk itu adalah hashing spasial dan pohon multi-dimensi .

Philipp
sumber
Terima kasih atas jawaban cepatnya. Saya sedang berpikir tentang menggunakan Unity karena saya menebak itu menggunakan semacam partisi spasial untuk memeriksa memicu colliders, jadi saya akan membuat satu collider lingkaran besar di sekitar karakter saya dan setiap item di dalamnya akan "animasi". Apakah ini cara menerapkan jawaban Anda? Koreksi saya jika saya salah, tepuk tangan!
Alakanu
2
@Alakanu Dapat digunakan jika Anda ingin objek terlihat pada jarak jauh tetapi hanya melakukan perilaku intens-komputasi tertentu ketika dekat dengan pemain (dan hanya memutar sesuatu di sekitar sumbu y seharusnya tidak terlalu mahal). Tetapi tantangan yang sebenarnya ketika menerapkan permainan dunia terbuka di Unity adalah dengan cerdas membuat dan menghancurkan objek-objek game sementara pemain bergerak melalui dunia (atau bahkan lebih baik: menggunakan pengumpulan objek alih-alih membuat dan menghancurkan).
Philipp
Ya, pengumpulan objek adalah wajib dalam situasi ini :) Ok terima kasih banyak!
Alakanu
3
@Alakanu Anda dapat memeriksa konsep "Loaded Chunks" Minecraft untuk informasi lebih lanjut tentang bagaimana jawaban ini berlaku untuk permainan itu.
T. Sar - Reinstate Monica
1
Ini tidak hanya berlaku untuk pickup. Obyek APA SAJA yang terlalu jauh dari pemain dapat diperlakukan seperti itu. Terkadang bahkan benda yang dekat dengan pemain. Bayangkan sebuah rumah dengan interior penuh tetapi tidak perlu membuat sampai Anda benar-benar memasuki rumah.
Zibelas
22

Anda memiliki dua hal yang sangat berbeda untuk dikelola:

  1. Server harus mengelola seluruh dunia, secara otoritatif. Untuk itu, komunikasi dengan klien N (di mana N "besar") diperlukan.

  2. Klien bisa , pada prinsipnya, tahu tentang seluruh dunia, tapi perlu tidak . Untuk klien, cukup mengetahui tentang apa yang ada di dekat pemain. Dengan asumsi misalnya partisi yang mirip grid yang agak kasar, perlu mengetahui hanya sel pemain dan 26 sel di sekitar pemain (atau 8 sel jika Anda memiliki grid 2D). Grid yang agak lebih baik lebih baik, tetapi Anda mendapatkan idenya.

Sekarang banyak pickup, apa itu "banyak"? Anda menggali mungkin 5 hal per detik, itu mungkin dua lusin angka yang perlu diperbarui di server, dan server mungkin harus mengirimkannya ke pemain lain yang bidang minatnya tumpang tindih sel Anda. Untuk komputer, ini adalah jumlah data yang cukup konyol, dan jumlah komputasi yang dapat diabaikan. Ini bisa menjadi tantangan ketika ada ratusan / ribu pemain di sel yang sama (maka paritioning Anda terlalu kasar).

Server tidak perlu tahu, atau peduli tentang rotasi pickup atau detail semacam itu. Kenapa harus begitu?

Klien sebenarnya juga tidak peduli, karena ini hanya permen mata yang bisa diganti oleh klien dengan cepat.

Apa yang diperlukan dari sudut pandang server adalah mengetahui bahwa Anda sedang menggali (30, 40, 50) di simpul tempat Anda berada, dan memutuskan bahwa ini memunculkan misalnya tiga objek tipe 5, atau satu objek tipe 7 dengan hitungan 3. Hanya itu yang peduli, dan hanya itu yang memberitahu Anda. Ini juga akan mencakup informasi dalam data yang dikirimkan kepada seseorang yang memindahkan bidang minatnya ke sel jaringan nanti (dengan asumsi itu masih ada saat itu).

Klien diberitahu tiga objek yang muncul di sana, bla bla. Sekarang, apakah klien menampilkan peta ASCII-art di mana sekarang ada 'D' atau apakah itu menunjukkan tumpukan tanah yang berputar, itu semua sama. Apakah tumpukan memiliki rotasi yang berbeda atau apakah hanya yang dekat dengan pemutar Anda juga tetap sama. Hanya saja hal-hal yang ditampilkan pada monitor Anda, tidak mempengaruhi orang lain.

Jadi, dalam kasus beton yang ingin Anda putar hanya tumpukan tanah di dekatnya, Anda bisa melakukan pemeriksaan jangkauan pada semua objek yang Anda ketahui. Karena kumpulan data tidak besar, bahkan kekuatan kasar pada semuanya akan bekerja.

Anda dapat (dan harus) bergantung pada ukuran partisi Anda, memangkas sel-sel grid yang terlalu jauh.

Anda dapat, tentu saja, lebih jauh membuat sub-partisi sel Anda dan menggunakan sesuatu yang super pintar. Gunakan kd-Tree jika Anda mau, tetapi jangan berharap keuntungan besar. Anda dapat memangkas barang dengan Manhattan distace, atau Anda dapat mengurutkan barang-barang Anda di kotak kecil Anda sendiri ... tetapi mengapa?

Pemeriksaan jarak (benar-benar jarak kuadrat, tetapi sama dengan Anda) adalah hanya dua perkalian dan tambahan (dioptimalkan untuk MUL, MADD, jadi benar-benar hanya dua operasi), diikuti oleh cabang atau gerakan kondisional. Itu hampir sama cepatnya dengan operasi lain yang tidak memangkas seluruh sel kotak sekaligus. Bahkan, ini adalah sesuatu yang bahkan dapat Anda lakukan pada GPU ...

Melihat bagaimana Anda akan memiliki beberapa ratus, atau paling banyak beberapa ribu pemeriksaan jarak terhadap posisi yang sama (jarak kuadrat berfungsi dengan baik), Anda benar-benar tidak mengalami banyak kesulitan hanya melakukan perhitungan itu, bahkan lebih karena itu agak cache- iterasi ramah atas memori yang berdekatan, dan dengan gerakan bersyarat, itu murah. Sesuatu seperti (kodesemu)rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i]; . Itu satu iterasi pada array beberapa ratus nilai per frame. Komputer tidak peduli tentang melakukan itu, itu adalah banyak dan toko yang berdekatan, ALU sederhana, tidak ada cabang, dan hanya beberapa ribu iterasi.

Ini (banyak-ke-satu) bukan kelas masalah yang sama (banyak-ke-banyak) seperti pada server. Sungguh, klien bukanlah masalahnya.

Damon
sumber
Maaf, saya pikir sudah jelas bahwa saya berbicara tentang klien ketika saya mulai berbicara tentang framerate.
Alakanu
1
Tetapi klien tidak pernah menjadi masalah. Klien sangat non-masif, dan sangat lokal, perlu tahu jauh lebih sedikit daripada server. Idealnya, klien tahu node partisi spasial (apa pun itu, katakanlah, kotak) pemain berada di, dan yang segera mengelilingi, dan hanya itu. Pembaruan sangat sederhana kecuali jika seribu pemain berdiri di samping satu sama lain. Biasanya, Anda hanya perlu delta untuk satu atau dua objek, dan konten simpul kotak baru setelah bergerak ke arah satu arah untuk lebih dari setengah lebar simpul. Yang lainnya: Bukan masalah Anda.
Damon
1
Intinya adalah bahwa terlalu pintar bisa menjadi ide yang sangat bodoh. Dunia Anda sudah terbagi secara spasial, dengan sejumlah objek yang dapat dikelola di setiap node. CPU modern (dan GPU lebih dari itu) bagus dalam memproses bulks data SoA secara berurutan. Mereka tidak suka percabangan tidak koheren, dan mereka seperti akses memori tidak koheren bahkan kurang - yang namun persis apa yang "hanya memproses terdekat" tidak. Untuk angka yang dapat dikelola (beberapa ratus, beberapa ribu), "proses semua" dalam satu sel sangat memadai, dan kemungkinan hal terbaik yang dapat Anda lakukan.
Damon
1
@Alakanu Ini sepertinya jawaban yang terperinci dan lengkap untuk pertanyaan Anda, bagi saya. Jika Anda pikir itu bukan jawaban, apakah Anda salah paham atau pertanyaan Anda tidak jelas sehingga disalahpahami oleh Damon, saya dan semua orang yang telah memilih jawaban ini secara terbalik.
David Richerby
2
@Alakanu Anda benar-benar menghabiskan banyak waktu untuk mengeluh pada orang yang mencoba membantu Anda. Semoga beruntung dengan itu.
David Richerby
2

@ T.Sar menulis dalam komentar bahwa Anda harus melihat konsep Minecrafts "loaded chunk" untuk informasi lebih lanjut. Jika ya, ketahuilah bahwa ini agak rumit di Minecraft karena orang membuat mesin di dalam gim.

Versi yang sangat sederhana berikut:

Dunia terbagi menjadi wilayah kuadrat (bongkahan). Di Minecraft juga ada pembagian ketinggian, tetapi sebagian besar mmos tidak membutuhkannya.

Klien game hanya peduli dengan wilayah yang dekat dengan pemain. Ini jauh lebih sederhana daripada menggambar lingkaran di sekitar pemain, tetapi cukup bagus.

Di Minecraft, wilayahnya 16x16 blok, dan klien tahu tentang wilayah 9x9, 4 wilayah di setiap arah. (4 wilayah pemain + wilayah timur di + 4 wilayah barat = total 9 wilayah. Utara / selatan yang sama)

Tidak ada yang ajaib tentang angka-angka ini, gunakan apa pun yang masuk akal dalam gim Anda.

Klien hanya menjiwai hal-hal di dalam area ini. Server hanya menghitung hal-hal seperti monster yang berkeliaran di daerah yang dekat dengan beberapa pemain.

Ketika seorang pemain berjalan di dalam suatu wilayah, tidak ada yang istimewa terjadi, ketika mereka melintasi perbatasan wilayah, "ujung animasi" didorong satu daerah. Klien kemudian perlu bertanya kepada server tentang daerah yang sekarang dilihatnya.

Tidak ada yang salah dengan memiliki beberapa batas animasi bersarang. Misalnya item beranimasi jatuh di area 3x3, mengembara monster di area 5x5 dan hanya menunjukkan lanskap di area 9x9.

Server menyimpan "versi beku" dari wilayah yang tidak terlihat oleh pemain. Jika ini membutuhkan banyak memori, Anda mungkin ingin menurunkannya setelah beberapa saat. Ketika seorang pemain berikutnya tiba, wilayah tersebut dimuat kembali tanpa item jatuh. Anda harus lebih cepat lain kali, Pemain 1.

Stig Hemmer
sumber
Draw draw dapat disesuaikan tetapi dalam kasus ini 8 chunks adalah 9x9 dan merupakan keputusan sisi klien, ia dapat menginformasikan server untuk mempercepatnya (sehingga server tidak mengirim data yang tidak akan di-render oleh klien). Juga ... bukankah Doom and Quake menyelesaikan masalah tentang rendering hanya apa yang masuk akal?
SparK
Tentang melecehkan item yang dijatuhkan ... di minecraft, item itu hanya "menua" ketika ada pemain di dekatnya. Jadi, Anda dapat "menyimpan" barang yang jatuh ke dalam bongkahan yang tidak dimuat dan mendapatkannya nanti.
SparK