Bagaimana gim dapat menangani semua karakter sekaligus?

31

Pertanyaan ini hanya untuk mendapatkan pengetahuan tentang bagaimana permainan dapat menangani begitu banyak karakter sekaligus. Saya baru bermain game, jadi saya mohon maaf sebelumnya.

Contoh

Saya membuat permainan menara pertahanan di mana ada 15 slot menara di mana menara dibangun dan setiap menara mengeluarkan proyektil pada tingkat tertentu; katakanlah bahwa setiap detik, 2 proyektil dibuat oleh masing-masing menara dan ada musuh yang berbaris di medan perang, katakanlah 70 (masing-masing dengan 10 jenis atribut seperti HP, mana, dll., yang akan berubah ketika mereka bergerak di sekitar medan perang).

Ringkasan

Tower Count = 15
Proyektil Dibuat Oleh Setiap Tower Per Detik = 2
Jumlah Total Proyektil yang Dibuat Per Detik = 30
Unit di Battlefield Count = 70

Sekarang, apakah permainan menangani 30 proyektil dan 70 unit dengan menangani mereka pada 100 utas berbeda (yang terlalu banyak untuk PC) atau 1 utas yang menggerakkan semuanya, mengurangi nilainya, dll. (Yang akan agak lambat) , Kupikir)?

Saya tidak memiliki petunjuk tentang ini, jadi adakah yang bisa membimbing saya tentang bagaimana ini akan berhasil

Bangsa Pengembang
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
MichaelHouse
Menambahkan ke jawaban lain ... contoh dari beberapa permainan besar. Skyrim memiliki sebagian besar pembaruan logika game pada satu utas. Cara mengelola ini dengan sangat baik adalah bahwa NPC jauh (NPC yang jauh) diperkirakan sesuai dengan jadwal mereka. Kebanyakan MMO memperbarui logika game pada utas tunggal, TETAPI setiap bagian peta ada pada utas atau rak server yang berbeda.
moonshineTheleocat

Jawaban:

77

Sekarang bagaimana permainan menangani 30 Proyektil dan 70 unit dengan menangani mereka pada 100 utas yang berbeda

Tidak, jangan pernah lakukan itu. Jangan pernah membuat utas baru per sumber daya, ini tidak skala dalam jaringan, juga tidak dalam memperbarui entitas. (Adakah yang ingat saat-saat ketika Anda memiliki satu utas untuk membaca per soket di java?)

1 utas yang memindahkan semuanya mengurangi nilainya dll?

Ya, sebagai permulaan, ini adalah cara untuk pergi. "Mesin besar" membagi beberapa pekerjaan di antara utas, tetapi ini tidak diperlukan untuk memulai gim sederhana seperti gim pertahanan menara. Mungkin ada lebih banyak pekerjaan yang harus dilakukan setiap kutu yang juga akan Anda lakukan di utas ini. Oh ya, dan terjemahannya tentu saja.

(yang akan agak lambat saya pikir)

Baiklah ... Apa definisi Anda tentang lambat ? Untuk 100 entitas, seharusnya tidak perlu lebih dari setengah milidetik, mungkin bahkan kurang, tergantung pada kualitas kode Anda dan bahasa yang Anda gunakan. Dan bahkan jika itu membutuhkan dua milidetik penuh, itu masih cukup baik untuk mencapai 60 tps (kutu per detik, tidak berbicara tentang bingkai dalam kasus ini).

tkausl
sumber
34
Lebih seperti setengah mikrodetik, kecuali Anda melakukan sesuatu yang aneh. Tetapi yang paling penting, membagi pekerjaan melalui beberapa utas akan membuat segalanya lebih buruk , bukan lebih baik. Belum lagi multithreading sangat sulit.
Luaan
13
+1 Sebagian besar mesin game modern menghasilkan ribuan atau bahkan puluhan ribu poligon secara real time, yang jauh lebih intensif daripada melacak pergerakan 100 objek dalam memori.
phyrfox
1
"Game sederhana seperti game menara pertahanan." Hmm ... apakah Anda pernah memainkan Defense Grid: The Awakening , atau sekuelnya?
Mason Wheeler
4
"Jangan pernah membuat utas baru per sumber daya, ini tidak skala dalam jaringan ..." ahem beberapa arsitektur yang sangat scalable melakukan ini!
NPSF3000
2
@BarafuAlbino: Itu hal yang aneh untuk dikatakan. Ada banyak alasan valid untuk membuat lebih banyak utas daripada inti yang tersedia. Ini adalah kompleksitas / kinerja / etc trade-off seperti keputusan desain lainnya.
Dietrich Epp
39

Aturan nomor satu dari multithreading adalah: Jangan menggunakannya kecuali Anda perlu memparalelkan pada beberapa core CPU untuk kinerja atau responsif. Persyaratan "x dan y harus terjadi secara bersamaan dari sudut pandang pengguna" belum merupakan alasan yang cukup untuk menggunakan multithreading.

Mengapa?

Multithreading sulit. Anda tidak memiliki kendali atas ketika setiap utas dieksekusi yang dapat mengakibatkan semua jenis masalah yang tidak mungkin terjadi ("kondisi balapan"). Ada metode untuk menghindari ini (kunci sinkronisasi, bagian penting), tetapi ini datang dengan serangkaian masalah mereka sendiri ("deadlock").

Biasanya gim yang berurusan dengan jumlah objek yang rendah seperti hanya beberapa ratus (ya, ini tidak terlalu banyak dalam pengembangan gim) biasanya memprosesnya secara serial, masing-masing logika-centang menggunakan forloop umum .

Bahkan CPU smartphone yang relatif lebih lemah dapat melakukan miliaran instruksi per detik. Itu berarti bahkan ketika logika pembaruan objek Anda kompleks dan membutuhkan sekitar 1000 instruksi per objek dan centang, dan Anda bertujuan untuk 100 ticks per detik yang murah hati, Anda memiliki kapasitas CPU yang cukup untuk puluhan ribu objek. Ya, ini adalah perhitungan back-of-the-envelope yang terlalu disederhanakan, tetapi memberi Anda ide.

Juga, kebijaksanaan umum dalam pengembangan game adalah bahwa logika game sangat jarang menjadi hambatan dalam sebuah game. Bagian yang kritis terhadap kinerja hampir selalu berupa grafik. Ya, bahkan untuk game 2d.

Philipp
sumber
1
"Aturan nomor satu dari multithreading adalah: Jangan menggunakannya kecuali Anda perlu memparalelkan pada beberapa core CPU untuk kinerja atau responsif." Mungkin benar untuk pengembangan game (tapi saya bahkan meragukannya). Ketika bekerja dengan sistem waktu nyata alasan utama untuk menambahkan utas adalah untuk memenuhi tenggat waktu, dan untuk kesederhanaan yang logis.
Sam
6
@Sam. Tenggat waktu rapat dalam sistem waktu-nyata adalah kasus di mana Anda perlu multithreading untuk responsif. Tetapi bahkan di sana kesederhanaan logis yang tampaknya Anda capai melalui threading sering kali berbahaya, karena itu menciptakan kompleksitas tersembunyi dalam bentuk deadlock, kondisi ras, dan kelaparan sumber daya.
Philipp
Sayangnya, sering kali saya melihat logika permainan merusak seluruh permainan jika ada masalah merintis jalan.
Loren Pechtel
1
@ LorenPechtel Saya sudah melihat ini juga. Tapi biasanya itu bisa diselesaikan dengan tidak melakukan perhitungan jalur yang tidak perlu (seperti menghitung ulang setiap jalur tunggal pada setiap centang tunggal), caching jalur yang sering diminta, menggunakan pencarian jalur bertingkat dan menggunakan algoritma pencarian jalur yang lebih tepat. Ini adalah sesuatu di mana programmer yang terampil biasanya dapat menemukan banyak potensi optimasi.
Philipp
1
@LorenPechtel Misalnya dalam permainan menara pertahanan, Anda bisa menggunakan fakta bahwa biasanya hanya ada beberapa titik tujuan. Jadi Anda bisa menjalankan algoritma Dijkstra untuk setiap tujuan untuk menghitung peta arah yang memandu semua unit. Bahkan dalam lingkungan yang dinamis di mana Anda harus menghitung ulang peta-peta ini setiap frame, ini harus tetap terjangkau.
CodesInChaos
26

Jawaban lain telah menangani threading dan kekuatan komputer modern. Untuk menjawab pertanyaan yang lebih besar, apa yang Anda coba lakukan di sini adalah menghindari situasi "n kuadrat".

Sebagai contoh jika Anda memiliki 1000 proyektil dan 1000 musuh solusi naif adalah dengan hanya memeriksa mereka satu sama lain.

Ini berarti Anda berakhir dengan p * e = 1.000 * 1.000 = 1.000.000 cek berbeda! Ini adalah O (n ^ 2).

Di sisi lain, jika Anda mengatur data dengan lebih baik, Anda dapat menghindari banyak hal.

Sebagai contoh jika Anda mendaftar pada setiap kotak dari musuh apa yang ada dalam kotak itu maka Anda dapat mengulangi 1000 proyektil Anda dan cukup memeriksa kotak pada kotak. Sekarang Anda hanya perlu memeriksa setiap proyektil terhadap alun-alun, ini O (n). Alih-alih satu juta cek setiap frame Anda hanya perlu seribu.

Berpikir untuk mengatur data Anda dan memprosesnya secara efisien karena organisasi itu adalah optimasi tunggal terbesar yang dapat Anda lakukan.

Tim B
sumber
1
Sebagai alternatif untuk menyimpan seluruh grid dalam memori hanya untuk melacak beberapa elemen, Anda juga dapat menggunakan b-tree, satu untuk setiap sumbu, untuk dengan cepat mencari kandidat yang mungkin untuk tabrakan, dll. Beberapa mesin bahkan melakukan ini untuk Anda "secara otomatis "; Anda menentukan daerah hit, dan meminta daftar tabrakan, dan perpustakaan memberikannya kepada Anda. Ini adalah salah satu dari banyak alasan mengapa pengembang harus menggunakan mesin alih-alih menulis dari awal (bila memungkinkan, tentu saja).
phyrfox
@ phyrfox Tentu saja, ada sejumlah cara berbeda untuk melakukannya - tergantung pada kasus penggunaan Anda yang lebih baik akan bervariasi secara substansial.
Tim B
17

Jangan membuat utas per sumber daya / objek tetapi per bagian dari logika program Anda. Sebagai contoh:

  1. Utas untuk memperbarui unit dan proyektil - utas logika
  2. Utas untuk menampilkan layar - utas GUI
  3. Utas untuk jaringan (mis. Multipemain) - Utas IO

Keuntungan dari ini adalah bahwa GUI Anda (mis. Tombol) tidak selalu macet jika logika Anda lambat. Pengguna masih dapat menjeda dan menyimpan game. Ini juga baik untuk mempersiapkan gim Anda untuk multipemain, sekarang Anda memisahkan grafik dari logika.

Tomáš Zato - Pasang kembali Monica
sumber
1
Untuk pemula, saya tidak akan merekomendasikan menggunakan utas grafik dan logika yang terpisah, karena kecuali jika Anda menyalin data yang diperlukan, merender kondisi permainan memerlukan akses baca ke kondisi permainan, jadi Anda tidak dapat mengubah kondisi permainan saat menggambarnya.
CodesInChaos
1
Tidak menggambar terlalu sering (mis. Lebih dari 50 kali per detik) agak penting dan pertanyaan ini adalah tentang kinerja. Program pembagian adalah hal paling sederhana untuk dilakukan demi keuntungan kinerja nyata. Memang benar ini membutuhkan beberapa pengetahuan tentang utas, tetapi memperoleh pengetahuan itu bermanfaat.
Tomáš Zato - Reinstate Monica
Membagi Program menjadi beberapa Thread adalah jenis hal tersulit yang harus dilakukan oleh seorang programmer. Bug paling menjengkelkan berasal dari multi-threading dan itu adalah jumlah besar kerumitan dan sebagian besar waktu tidak sepadan - Aturan pertama: Periksa apakah Anda memiliki masalah kinerja, MAKA optimalkan. Dan optimalkan tepat di mana kemacetan. Mungkin utas eksternal tunggal untuk algoritma kompleks tertentu. Tetapi meskipun demikian Anda harus berpikir bagaimana logika permainan Anda akan maju ketika algoritma ini membutuhkan 3 detik untuk menyelesaikan ...
Falco
@ Falco Anda mengawasi keuntungan jangka panjang dari model ini - baik untuk pengalaman proyek maupun programmer. Klaim Anda bahwa pemikiran tersulit tidak dapat benar-benar ditangani, itu hanya pendapat. Bagi saya desain GUI jauh lebih menakutkan. Semua bahasa yang dikembangkan (C ++, Java) memiliki model multithreading yang cukup jelas. Dan jika Anda benar-benar tidak yakin, Anda dapat menggunakan model aktor yang tidak menderita bug multithreading pemula. Anda tahu ada alasan mengapa sebagian besar aplikasi dirancang seperti yang saya usulkan, tetapi jangan ragu untuk memperdebatkannya lebih lanjut.
Tomáš Zato - Reinstate Monica
4

Bahkan Space Invaders mengatur lusinan objek yang berinteraksi. Sedangkan decoding satu frame video HD H264 melibatkan ratusan juta operasi aritmatika. Anda memiliki banyak daya pemrosesan yang tersedia.

Yang mengatakan, Anda masih bisa membuatnya lambat jika Anda menyia-nyiakannya. Masalahnya bukan jumlah objek seperti jumlah tes tabrakan yang dilakukan; pendekatan sederhana memeriksa setiap objek terhadap satu sama lain objek kuadrat jumlah perhitungan yang diperlukan. Menguji 1001 objek untuk tabrakan dengan cara ini akan membutuhkan satu juta perbandingan. Seringkali ini diatasi dengan misalnya tidak memeriksa proyektil untuk saling bertabrakan.

pjc50
sumber
2
Saya tidak yakin Space Invaders adalah perbandingan terbaik untuk dibuat. Alasan itu dimulai lambat dan mempercepat saat Anda membunuh musuh bukan karena itu dirancang seperti itu, tetapi karena perangkat keras tidak dapat menangani rendering yang banyak musuh sekaligus. en.wikipedia.org/wiki/Space_Invaders#Hardware
Mike Kellogg
Bagaimana dengan, masing-masing objek menyimpan daftar semua objek yang cukup dekat sehingga mungkin bertabrakan dengan mereka di detik berikutnya, diperbarui sekali dalam satu detik atau setiap kali mereka mengubah arah?
Random832
Tergantung pada apa yang Anda modelkan. Solusi partisi ruang adalah pendekatan umum lainnya: mempartisi dunia menjadi wilayah (mis. BSP yang mungkin harus Anda lakukan untuk tujuan rendering, atau quadtree), maka Anda hanya dapat bertabrakan dengan objek di wilayah yang sama.
pjc50
3

Saya akan tidak setuju dengan beberapa jawaban lain di sini. Utas logika terpisah bukan hanya ide yang bagus, tetapi juga sangat bermanfaat untuk kecepatan pemrosesan - jika logika Anda mudah dipisahkan .

Pertanyaan Anda adalah contoh logis yang mungkin dapat dipisahkan jika Anda dapat menambahkan beberapa logika tambahan di atasnya. Misalnya, Anda dapat menjalankan beberapa utas pendeteksian hit baik dengan mengunci utas ke wilayah ruang tertentu, atau memotong-motong objek yang terlibat.

Anda mungkin TIDAK ingin satu utas untuk setiap kemungkinan tabrakan, hanya karena itu kemungkinan akan mengganggu penjadwal; ada juga biaya yang terkait dengan membuat dan menghancurkan utas. Lebih baik membuat beberapa utas di sekitar inti sistem (atau menggunakan metrik seperti yang lama #cores * 2 + 4), kemudian menggunakannya kembali ketika proses mereka selesai.

Tidak semua logika mudah dipisahkan. Terkadang operasi Anda dapat menjangkau seluruh data game sekaligus, yang akan membuat threading tidak berguna (pada kenyataannya, berbahaya, karena Anda perlu menambahkan cek untuk menghindari masalah threading). Lebih lanjut, jika beberapa tahapan logika sangat tergantung satu sama lain yang terjadi dalam pesanan tertentu, Anda harus mengontrol pelaksanaan utas sedemikian rupa untuk memastikan bahwa tidak memberikan hasil yang bergantung pada pesanan. Namun, masalah itu tidak dihilangkan dengan tidak menggunakan utas, utas hanya memperburuknya.

Sebagian besar gim tidak melakukan ini hanya karena lebih rumit dari yang biasanya diinginkan / dapat ditangani oleh pengembang gim untuk apa yang biasanya bukan hambatan. Sebagian besar permainan terbatas pada GPU, bukan terbatas pada CPU. Meskipun meningkatkan kecepatan CPU dapat membantu secara keseluruhan, biasanya ini bukan fokus.

Yang mengatakan, mesin fisika sering menggunakan beberapa utas, dan saya dapat menyebutkan beberapa permainan yang saya pikir akan mendapat manfaat dari beberapa utas logika (permainan Paradox RTS seperti HOI3 dan semacamnya, misalnya).

Saya setuju dengan posting lain bahwa Anda mungkin tidak perlu menggunakan utas dalam contoh khusus ini, bahkan jika itu bisa bermanfaat. Threading harus disediakan untuk kasus-kasus di mana Anda memiliki beban CPU yang berlebihan yang tidak dapat dioptimalkan melalui metode lain. Ini adalah tugas besar dan akan mempengaruhi struktur dasar sebuah mesin; itu bukan sesuatu yang bisa Anda tempel setelah fakta.


sumber
2

Saya pikir jawaban lain kehilangan bagian penting dari pertanyaan dengan terlalu fokus pada bagian threading dari pertanyaan.

Komputer tidak menangani semua objek dalam game sekaligus. Ini menangani mereka secara berurutan.

Sebuah game komputer berkembang dalam tahapan waktu yang berbeda. Tergantung pada gim dan kecepatan PC, langkah-langkah ini biasanya 30 atau 60 langkah per detik, atau sebanyak / beberapa langkah yang dapat dihitung oleh PC.

Dalam satu langkah seperti itu, komputer menghitung apa yang akan dilakukan oleh masing-masing objek permainan selama langkah itu dan memutakhirkannya, satu demi satu. Ia bahkan bisa melakukannya secara paralel, menggunakan utas untuk menjadi lebih cepat, tetapi karena kita akan segera melihat kecepatan bukanlah masalah sama sekali.

CPU rata-rata harus 2 GHz atau lebih cepat, itu berarti 10 9 clock cycle per detik. Jika kita menghitung 60 timesteps per detik, bahwa daun 10 9 siklus / 60 jam siklus = 16.666.666 jam per langkah waktu. Dengan 70 unit, kami masih memiliki sekitar 2.400.000 siklus clock per unit tersisa. Jika kami harus mengoptimalkan, kami mungkin dapat memperbarui setiap unit hanya dalam 240 siklus, tergantung pada kompleksitas logika permainan. Seperti yang Anda lihat, komputer kami sekitar 10.000 kali lebih cepat dari yang seharusnya untuk tugas ini.

Peter
sumber
0

Penafian: Jenis permainan favorit saya sepanjang masa adalah berbasis teks dan saya menulis ini sebagai programmer lama dari MUD lama.

Saya pikir pertanyaan penting yang perlu Anda tanyakan pada diri sendiri adalah ini: Apakah Anda bahkan perlu utas? Saya mengerti bahwa permainan grafis mungkin lebih banyak menggunakan MTs tetapi saya pikir itu juga tergantung pada mekanisme permainan. (Mungkin juga layak mempertimbangkan bahwa dengan GPU, CPU dan semua sumber daya lain yang kita miliki saat ini jauh lebih kuat yang membuat masalah sumber daya Anda menjadi masalah seperti yang terlihat bagi Anda; memang 100 objek hampir nol). Itu juga tergantung pada bagaimana Anda mendefinisikan 'semua karakter sekaligus'. Apakah maksud Anda pada saat yang bersamaan? Anda tidak akan memiliki itu seperti yang ditunjukkan oleh Peter dengan tepat sehingga secara bersamaan tidak relevan dalam arti harfiah; hanya muncul seperti ini.

Dengan asumsi Anda akan menggunakan utas: Anda pasti tidak harus mempertimbangkan 100 utas (dan saya bahkan tidak akan membahas apakah itu terlalu banyak untuk CPU Anda atau tidak; Saya hanya merujuk pada komplikasi dan kepraktisannya).

Tapi ingat ini: multi-threading tidak mudah (seperti yang ditunjukkan Philipp) dan memiliki banyak masalah. Yang lain memiliki lebih banyak pengalaman (dengan banyak) daripada yang saya lakukan dengan MT tetapi saya akan mengatakan mereka juga akan menyarankan hal yang sama (meskipun mereka akan lebih mampu daripada saya - terutama tanpa latihan di pihak saya).

Beberapa berpendapat bahwa mereka tidak setuju bahwa utas tidak menguntungkan dan beberapa berpendapat bahwa setiap objek harus memiliki utas. Tapi (dan sekali lagi ini semua teks tetapi bahkan jika Anda mempertimbangkan lebih dari satu utas Anda tidak perlu - dan tidak boleh - mempertimbangkannya untuk setiap objek) karena Philipp menunjukkan permainan cenderung beralih melalui daftar. Tapi itu bukan hanya (seperti yang dia sarankan meskipun saya sadar dia hanya menanggapi parameter Anda dari begitu sedikit objek) untuk beberapa objek. Dalam MUD saya seorang programmer karena kami memiliki yang berikut (dan ini tidak semua aktivitas yang terjadi secara real-time jadi ingatlah itu juga):

(Jumlah contoh tentu saja bervariasi - lebih tinggi dan lebih rendah)

Mobiles (NPC yaitu karakter bukan pemain): 2614; prototipe: 1360 Objek: 4457; prototipe: 2281 Kamar: 7983; prototipe: 7983. Setiap kamar biasanya memiliki contohnya sendiri tetapi kami juga memiliki kamar yang dinamis, yaitu kamar di dalam kamar; atau kamar di dalam ponsel misalnya perut naga; atau ruangan di objek misalnya Anda memasukkan objek magis). Perlu diingat bahwa ruang dinamis ini ada per objek / ruang / ponsel yang sebenarnya telah ditentukan. Ya ini sangat mirip dengan World of Warcraft (saya tidak memainkannya tetapi seorang teman meminta saya memainkannya ketika saya memiliki mesin Windows, untuk sementara waktu) gagasan contoh kecuali kami memilikinya jauh sebelum World of Warcraft bahkan ada.

Script: 868 (saat ini) (anehnya perintah statistik kami tidak menunjukkan berapa banyak prototipe yang kami miliki sehingga saya akan menambahkannya). Semua ini diadakan di daerah / zona dan kami memiliki 103 di antaranya. Kami juga memiliki prosedur khusus yang diadakan pada waktu yang berbeda. Kami juga memiliki acara lainnya. Kemudian kami juga memiliki soket yang terhubung. Ponsel bergerak, melakukan aktivitas yang berbeda (selain pertempuran), berinteraksi dengan pemain, dan sebagainya. (Begitu juga jenis entitas lainnya).

Bagaimana kita menangani semua ini tanpa penundaan?

  • soket: pilih (), antrian (input, output, peristiwa, hal-hal lain), buffer (input, output, hal-hal lain), dll. Ini disurvei 10 kali per detik.

  • karakter, objek, ruang, pertempuran, semuanya: semua dalam satu lingkaran pusat pada pulsa yang berbeda.

Kami juga (implementasi saya berdasarkan diskusi antara pendiri / programmer lain dan saya sendiri) memiliki pelacakan daftar yang luas dan pengujian validitas pointer dan kami memiliki lebih dari cukup sumber daya gratis seandainya kami benar-benar membutuhkannya. Semua ini (kecuali kita telah memperluas dunia) ada bertahun-tahun yang lalu ketika ada lebih sedikit RAM, daya CPU, ruang hard disk, dll. Dan bahkan kemudian kita tidak punya masalah. Dalam loop yang dijelaskan (skrip menyebabkan ini seperti melakukan reset area / repopulasi seperti halnya hal-hal lain) monster, objek (item), dan hal-hal lain sedang dibuat, dibebaskan, dan sebagainya. Koneksi juga diterima, disurvei, dan segala sesuatu yang Anda harapkan.


sumber