Bagaimana mungkin game deterministik dalam menghadapi floating-point non-determinisme?

52

Untuk membuat game seperti jaringan RTS, saya telah melihat sejumlah jawaban di sini menyarankan untuk membuat game sepenuhnya deterministik; maka Anda hanya perlu mentransfer tindakan pengguna satu sama lain, dan ketinggalan apa yang ditampilkan sedikit untuk "mengunci" input semua orang sebelum bingkai berikutnya diberikan. Maka hal-hal seperti posisi unit, kesehatan, dll. Tidak perlu terus diperbarui melalui jaringan, karena simulasi setiap pemain akan persis sama. Saya juga mendengar hal yang sama yang disarankan untuk membuat replay.

Namun, karena perhitungan floating-point adalah non-deterministik antar mesin, atau bahkan antara kompilasi berbeda dari program yang sama pada mesin yang sama, apakah ini benar-benar mungkin dilakukan? Bagaimana kita mencegah fakta itu menyebabkan perbedaan kecil antara pemain (atau tayangan ulang) yang bergejolak di sepanjang permainan ?

Saya pernah mendengar beberapa orang menyarankan menghindari angka floating-point sama sekali dan menggunakan intuntuk mewakili hasil bagi sebagian, tetapi itu tidak terdengar praktis bagi saya - bagaimana jika saya perlu, misalnya, mengambil kosinus sudut? Apakah saya serius perlu menulis ulang seluruh perpustakaan matematika?

Perhatikan bahwa saya terutama tertarik pada C #, yang sejauh yang saya tahu, memiliki masalah yang sama persis seperti C ++ dalam hal ini.

BlueRaja - Danny Pflughoeft
sumber
5
Ini bukan jawaban untuk pertanyaan Anda, tetapi untuk mengatasi masalah jaringan RTS saya akan merekomendasikan sesekali menyinkronkan posisi unit dan kesehatan untuk memperbaiki setiap penyimpangan. Informasi apa yang perlu disinkronkan akan tergantung pada game; Anda dapat mengoptimalkan penggunaan bandwidth dengan tidak repot menyinkronkan hal-hal seperti efek status.
jhocking
@jhocking Namun itu mungkin jawaban terbaik.
Jonathan Connell
infacti starcraft II persis disinkronkan hanya setiap kali, saya melihat permainan replay dengan teman-teman saya masing-masing komputer berdampingan dan ada perbedaan (juga signifikan) terutama dengan lag tinggi (1 detik). Saya memiliki beberapa unit yang mana 6/7 kotak kuadrat jauh di layar saya sehubungan dengan miliknya sendiri
GameDeveloper

Jawaban:

15

Apakah floating-point deterministik?

Saya melakukan banyak membaca tentang masalah ini beberapa tahun yang lalu ketika saya ingin menulis RTS menggunakan arsitektur berbaris yang sama yang Anda lakukan.

Kesimpulan saya tentang floating-point perangkat keras adalah:

  • Kode rakitan asli yang sama kemungkinan besar bersifat deterministik asalkan Anda berhati-hati dengan flag titik mengambang dan pengaturan penyusun.
  • Ada satu proyek RTS open source yang mengklaim mereka mendapatkan kompilasi C / C ++ deterministik di berbagai kompiler menggunakan perpustakaan wrapper. Saya tidak memverifikasi klaim itu. (Jika saya ingat benar itu tentang STREFLOPperpustakaan)
  • JIT bersih. Diijinkan sedikit kelonggaran. Khususnya diizinkan untuk menggunakan akurasi yang lebih tinggi daripada yang dibutuhkan. Juga menggunakan set instruksi yang berbeda pada x86 dan AMD64 (saya pikir pada x86 menggunakan x87, AMD64 menggunakan beberapa instruksi SSE yang perilakunya berbeda untuk denorm).
  • Instruksi kompleks (termasuk fungsi trigonometri, eksponensial, logaritma) sangat bermasalah.

Saya menyimpulkan bahwa tidak mungkin untuk menggunakan tipe floating in built in .net secara deterministik.

Kemungkinan Solusi

Karena itu saya membutuhkan penyelesaian. Saya mempertimbangkan:

  1. Implementasikan FixedPoint32dalam C #. Meskipun ini tidak terlalu sulit (saya memiliki implementasi setengah jadi) rentang nilai yang sangat kecil membuatnya mengganggu untuk digunakan. Anda harus berhati-hati setiap saat sehingga Anda tidak meluap, atau kehilangan terlalu banyak presisi. Pada akhirnya saya menemukan ini tidak lebih mudah daripada menggunakan bilangan bulat secara langsung.
  2. Implementasikan FixedPoint64dalam C #. Saya menemukan ini agak sulit dilakukan. Untuk beberapa operasi, bilangan bulat menengah 128bit akan bermanfaat. Tapi .net tidak menawarkan tipe seperti itu.
  3. Gunakan kode asli untuk operasi matematika yang deterministik pada satu platform. Menghasilkan overhead panggilan delegasi pada setiap operasi matematika. Kehilangan kemampuan untuk menjalankan lintas platform.
  4. Gunakan Decimal. Tetapi lambat, membutuhkan banyak memori dan dengan mudah melempar pengecualian (pembagian 0, meluap). Ini sangat bagus untuk penggunaan finansial, tetapi tidak cocok untuk game.
  5. Terapkan floating-point 32 bit khusus. Kedengarannya agak sulit pada awalnya. Kurangnya intrinsik BitScanReverse menyebabkan beberapa gangguan ketika menerapkan ini.

SoftFloat saya

Terinspirasi oleh posting Anda di StackOverflow , saya baru saja mulai menerapkan tipe floating-point 32 bit dalam perangkat lunak dan hasilnya menjanjikan.

  • Representasi memori kompatibel dengan biner dengan IEEE floats, jadi saya dapat menafsirkan ulang cast ketika mengeluarkannya ke kode grafis.
  • Ini mendukung SubNorms, infinities dan NaNs.
  • Hasil pastinya tidak identik dengan hasil IEEE, tetapi itu biasanya tidak masalah untuk gim. Dalam kode semacam ini hanya penting bahwa hasilnya sama untuk semua pengguna, bukan akurat untuk angka terakhir.
  • Performanya layak. Tes sepele menunjukkan bahwa ia dapat melakukan sekitar 75MFLOPS dibandingkan 220-260MFLOPS dengan floatpenambahan / perkalian (Utas tunggal pada i66 2,66GHz ). Jika ada yang memiliki tolok ukur floating point yang baik untuk .net, silakan kirim ke saya, karena tes saya saat ini sangat sederhana.
  • Pembulatan dapat ditingkatkan. Saat ini memotong, yang kira-kira sama dengan pembulatan ke nol.
  • Itu masih sangat tidak lengkap. Saat ini pembagian, gips dan operasi matematika yang rumit tidak ada.

Jika ada yang ingin berkontribusi tes atau meningkatkan kode, cukup hubungi saya, atau mengeluarkan permintaan tarik di github. https://github.com/CodesInChaos/SoftFloat

Sumber ketidakpastian lainnya

Ada juga sumber ketidakpastian lainnya di .net.

  • iterasi di atas Dictionary<TKey,TValue>atau HashSet<T>mengembalikan elemen dalam urutan yang tidak ditentukan.
  • object.GetHashCode() berbeda dari menjalankan ke menjalankan.
  • Implementasi Randomkelas bawaan tidak ditentukan, gunakan milik Anda sendiri.
  • Multithreading dengan penguncian naif mengarah untuk menyusun ulang dan hasil yang berbeda. Berhati-hatilah untuk menggunakan utas dengan benar.
  • Ketika WeakReferencekehilangan target mereka tidak pasti karena GC dapat berjalan kapan saja.
CodesInChaos
sumber
23

Jawaban untuk pertanyaan ini berasal dari tautan yang Anda poskan. Khususnya Anda harus membaca kutipan dari Game Bertenaga Gas:

Saya bekerja di Game Bertenaga Gas dan saya dapat memberi tahu Anda secara langsung bahwa matematika floating point bersifat deterministik. Anda hanya perlu set instruksi dan kompiler yang sama dan tentu saja prosesor pengguna mematuhi standar IEEE754, yang mencakup semua PC dan 360 pelanggan kami. Mesin yang menjalankan DemiGod, Supreme Commander 1 dan 2 mengandalkan standar IEEE754. Belum lagi mungkin semua game RTS peer to peer lainnya di pasar.

Dan kemudian di bawah yang itu adalah ini:

Jika Anda menyimpan replay sebagai input pengontrol, mereka tidak dapat diputar pada mesin dengan arsitektur CPU, kompiler, atau pengaturan optimisasi yang berbeda. Di MotoGP, ini berarti kami tidak dapat membagikan replay yang disimpan antara Xbox dan PC.

Permainan deterministik hanya akan bersifat deterministik saat menggunakan file yang dikompilasi secara identik dan berjalan pada sistem yang mematuhi standar IEEE. Simulasi atau replay jaringan yang disinkronkan lintas platform tidak akan mungkin.

SerangHobo
sumber
2
Seperti yang saya sebutkan, saya terutama tertarik pada C #; karena JIT melakukan kompilasi yang sebenarnya, saya tidak dapat menjamin bahwa itu "dikompilasi dengan pengaturan optimasi yang sama" bahkan ketika menjalankan executable yang sama pada mesin yang sama!
BlueRaja - Danny Pflughoeft
2
Kadang-kadang mode pembulatan diatur secara berbeda di fpu, pada beberapa arsitektur fpu memiliki register internal yang lebih besar daripada presisi untuk perhitungan ... sementara IEEE754 tidak memberikan kelonggaran berkaitan dengan cara operasi FP harus bekerja, itu tidak t menentukan bagaimana fungsi matematika tertentu harus diimplementasikan, yang dapat mengekspos perbedaan arsitektur.
Stephen
4
@ 3nixios Dengan pengaturan seperti itu, permainan tidak deterministik. Hanya game dengan catatan waktu tetap yang dapat menentukan. Anda berpendapat sesuatu sudah tidak deterministik saat menjalankan kembali simulasi pada satu mesin.
AttackingHobo
4
@ 3nixios, "Saya menyatakan bahwa bahkan dengan stempel waktu tetap, tidak ada yang memastikan stempel waktu akan selalu diperbaiki." Anda sepenuhnya salah. Inti dari cap waktu tetap adalah untuk selalu memiliki waktu delta yang sama untuk setiap centang dalam memperbarui
AttackingHobo
3
@ 3nixios Menggunakan stempel waktu tetap memastikan stempel waktu akan diperbaiki karena kami pengembang tidak mengizinkan sebaliknya. Anda salah mengartikan bagaimana lag harus dikompensasi ketika menggunakan langkah waktu yang tetap. Setiap pembaruan game harus menggunakan waktu pembaruan yang sama; oleh karena itu, ketika koneksi rekan tertinggal, ia masih harus menghitung setiap pembaruan individu yang terlewat.
Keeblebrox
3

Gunakan aritmatika titik tetap. Atau pilih server yang otoritatif dan sesekali sinkronkan status permainan - itulah yang dilakukan MMORTS. (Setidaknya, Elements of War bekerja seperti ini. Itu ditulis dalam C # juga.) Dengan cara ini, kesalahan tidak memiliki kesempatan untuk menumpuk.

Lupakan
sumber
Ya, saya bisa menjadikannya server-klien dan berurusan dengan sakit kepala prediksi sisi klien dan ekstrapolasi. Pertanyaan ini adalah tentang arsitektur peer-to-peer, yang seharusnya lebih mudah ...
BlueRaja - Danny Pflughoeft
Nah, Anda tidak perlu melakukan prediksi dalam skenario "semua klien menjalankan kode yang sama". Peran server adalah menjadi otoritas pada sinkronisasi saja.
Nevermind
Server / klien hanyalah satu metode untuk membuat game berjaringan. Metode lain yang populer (terutama untuk game misalnya. RTS, seperti C & C atau Starcraft) adalah peer-to-peer, di mana ada adalah tidak ada server otoritatif. Agar hal itu dimungkinkan, semua perhitungan harus sepenuhnya deterministik dan konsisten di semua klien - maka pertanyaan saya.
BlueRaja - Danny Pflughoeft
Yah itu tidak seperti Anda benar-benar HARUS membuat gim p2p ketat tanpa server / klien yang ditinggikan. Namun jika Anda benar-benar harus - maka gunakan titik tetap.
Nevermind
3

Sunting: Tautan ke kelas titik tetap (Pembeli Waspadalah! - Saya belum menggunakannya ...)

Anda selalu bisa kembali ke aritmatika titik tetap . Seseorang (membuat rts, tidak kurang) telah melakukan pekerjaan kaki pada stackoverflow .

Anda akan membayar penalti kinerja, tetapi ini mungkin atau mungkin tidak menjadi masalah, karena .net tidak akan terutama tampil di sini karena tidak akan menggunakan instruksi simd. Tolok Ukur!

NB Rupanya seseorang di intel tampaknya memiliki solusi untuk memungkinkan Anda menggunakan pustaka primitif kinerja intel dari c #. Ini dapat membantu membuat vektor kode titik tetap untuk mengimbangi kinerja yang lebih lambat.

LukeN
sumber
decimalakan bekerja dengan baik untuk itu juga; tetapi, ini masih memiliki masalah yang sama dengan menggunakan int- bagaimana cara saya memicu dengannya?
BlueRaja - Danny Pflughoeft
1
Cara termudah adalah membangun tabel pencarian dan mengirimkannya di samping aplikasi. Anda dapat menginterpolasi antar nilai jika presisi merupakan masalah.
LukeN
Atau, Anda mungkin dapat mengganti panggilan trigonometri dengan angka atau angka imajiner (jika 3D). Ini adalah penjelasan yang bagus
LukeN
Ini juga dapat membantu.
LukeN
Di perusahaan tempat saya bekerja, kami membangun mesin ultrasound menggunakan matematika titik tetap, jadi pasti akan berhasil untuk Anda.
LukeN
3

Saya telah mengerjakan sejumlah judul besar.

Jawaban singkat: Mungkin saja jika Anda sangat keras, tetapi mungkin tidak sepadan. Kecuali jika Anda menggunakan arsitektur tetap (baca: konsol) itu rewel, rapuh dan dilengkapi dengan sejumlah masalah sekunder seperti terlambat bergabung.

Jika Anda membaca beberapa artikel yang disebutkan, Anda akan mencatat bahwa sementara Anda dapat mengatur mode CPU ada beberapa kasus aneh seperti ketika driver cetak mengganti mode CPU karena berada di ruang alamat yang sama. Saya punya kasus di mana aplikasi dikunci bingkai ke perangkat eksternal, tetapi komponen yang salah menyebabkan CPU melambat karena panas dan melaporkan secara berbeda di pagi dan sore hari, membuatnya berlaku mesin yang berbeda setelah makan siang.

Perbedaan platform ini ada pada silikon, bukan perangkat lunak, jadi untuk menjawab pertanyaan Anda C # juga terpengaruh. Instruksi seperti gabungan multiply-add (FMA) vs ADD + MUL mengubah hasilnya karena hanya dibulatkan secara internal satu kali, bukan dua kali. C memberi Anda lebih banyak kontrol untuk memaksa CPU melakukan apa yang Anda inginkan pada dasarnya dengan mengecualikan operasi seperti FMA untuk menjadikan hal-hal "standar" - tetapi dengan mengorbankan kecepatan. Secara intrinsik tampaknya paling cenderung berbeda. Pada satu proyek saya harus menggali buku acos tables berusia 150 tahun untuk mendapatkan nilai perbandingan untuk menentukan CPU mana yang "benar". Banyak CPU menggunakan perkiraan polinomial untuk fungsi trigonometri tetapi tidak selalu dengan koefisien yang sama.

Rekomendasi saya:

Terlepas dari apakah Anda melakukan langkah-kunci integer atau menyinkronkan, menangani mekanik game inti secara terpisah dari presentasi. Jadikan permainan ini akurat, tetapi jangan khawatir tentang akurasi di lapisan presentasi. Juga ingat Anda tidak perlu mengirim semua data dunia jaringan pada kecepatan bingkai yang sama. Anda dapat memprioritaskan pesan Anda. Jika simulasi Anda 99,999% cocok, Anda tidak perlu mengirim sesering untuk tetap berpasangan. (Mengesampingkan pencegahan.)

Ada artikel yang bagus tentang mesin Sumber yang menjelaskan satu cara untuk pergi tentang sinkronisasi: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Ingat, jika Anda tertarik untuk terlambat bergabung, Anda harus menggigit peluru dan tetap menyinkronkan.

lisa
sumber
1

Perhatikan bahwa saya terutama tertarik pada C #, yang sejauh yang saya tahu, memiliki masalah yang sama persis seperti C ++ dalam hal ini.

Ya, C # memiliki masalah yang sama dengan C ++. Tetapi juga memiliki lebih banyak.

Misalnya, ambil pernyataan ini dari Shawn Hawgraves:

Jika Anda menyimpan replay sebagai input pengontrol, mereka tidak dapat diputar pada mesin dengan arsitektur CPU, kompiler, atau pengaturan optimisasi yang berbeda.

"Cukup mudah" untuk memastikan bahwa ini terjadi di C ++. Namun dalam C # , itu akan menjadi jauh lebih sulit untuk dihadapi. Ini berkat JIT.

Menurut Anda apa yang akan terjadi jika penerjemah menjalankan kode Anda ditafsirkan sekali, tetapi kemudian JIT melakukannya untuk yang kedua kalinya? Atau mungkin itu menafsirkannya dua kali pada mesin orang lain, tetapi JIT setelah itu?

JIT tidak deterministik, karena Anda memiliki sedikit kendali atas itu. Ini adalah salah satu hal yang Anda menyerah untuk menggunakan CLR.

Dan Tuhan membantu Anda jika satu orang menggunakan .NET 4.0 untuk menjalankan permainan Anda, sementara orang lain menggunakan Mono CLR (menggunakan perpustakaan .NET tentu saja). Bahkan .NET 4.0 vs. .NET 5.0 dapat berbeda. Anda hanya perlu lebih banyak kontrol atas detail level rendah dari platform untuk menjamin hal semacam ini.

Anda harus bisa lolos dengan matematika fixed-point. Tapi itu saja.

Nicol Bolas
sumber
Selain dari matematika, apa lagi yang mungkin berbeda? Agaknya, tindakan "input" sedang dikirim sebagai tindakan logis dalam rts. Misalnya, Pindahkan unit "a" ke posisi "b". Saya bisa melihat masalah dengan pembuatan bilangan acak, tapi itu jelas perlu dikirim sebagai input simulasi juga.
LukeN
@ Lukas: Masalahnya adalah bahwa posisi Shawn sangat menyarankan bahwa perbedaan kompiler dapat memiliki efek nyata pada matematika titik-mengambang. Dia akan tahu lebih banyak daripada saya; Saya hanya mengekstrapolasi peringatannya ke ranah kompilasi / interpretasi JIT dan C #.
Nicol Bolas
C # memiliki kelebihan operator , dan juga memiliki tipe bawaan untuk matematika titik tetap. Namun, ini memiliki masalah yang sama dengan menggunakan int- bagaimana saya melakukan trigonometri dengan itu?
BlueRaja - Danny Pflughoeft
1
> Menurut Anda apa yang akan terjadi jika penerjemah menjalankan kode Anda> ditafsirkan sekali, tetapi kemudian JIT melakukannya untuk kedua kalinya? Atau mungkin itu menafsirkannya dua kali di komputer orang lain, tetapi JIT setelah itu? 1. Kode CLR selalu dipasangkan sebelum eksekusi. 2. .net menggunakan IEEE 754 untuk mengapung tentu saja. > JIT tidak deterministik, karena Anda memiliki sedikit kendali atas itu. Kesimpulan Anda cukup lemah karena pernyataan palsu yang salah. > Dan Tuhan membantu Anda jika satu orang menggunakan .NET 4.0 untuk menjalankan game Anda,> sementara orang lain menggunakan Mono CLR (menggunakan tentu saja .NET libraries). Even .NET
Romanenkov Andrey
@Romanenkov: "Kesimpulan Anda cukup lemah karena pernyataan palsu yang salah." Tolong, beri tahu saya pernyataan apa yang salah dan mengapa, sehingga bisa diperbaiki.
Nicol Bolas
1

Saya menyadari setelah menulis jawaban ini bahwa itu sebenarnya tidak menjawab pertanyaan, yang secara khusus tentang nondeterminisme floating-point. Tapi mungkin ini berguna baginya jika dia akan membuat game berjaringan dengan cara ini.

Bersamaan dengan berbagi input yang Anda siarkan kepada semua pemain, akan sangat berguna untuk membuat dan menyiarkan checksum dari status permainan penting, seperti posisi pemain, kesehatan, dll. Saat memproses input, nyatakan bahwa checksum status permainan untuk semua pemain jarak jauh dalam sinkronisasi. Anda dijamin tidak memiliki sinkronisasi (OOS) bug untuk diperbaiki dan ini akan membuatnya lebih mudah - Anda akan memiliki pemberitahuan sebelumnya bahwa ada yang tidak beres (yang akan membantu Anda mengetahui langkah-langkah reproduksi), dan Anda harus dapat menambahkan lebih banyak status permainan masuk dalam kode yang dicurigai untuk memungkinkan Anda untuk menandai apa pun yang menyebabkan OOS.

Balik
sumber
0

Saya pikir ide dari blog yang ditautkan masih memerlukan sinkronisasi berkala agar dapat hidup - saya telah melihat cukup banyak bug di game RTS jaringan yang tidak menggunakan pendekatan itu.

Jaringan bersifat lossy, lambat, latensi, dan bahkan mungkin mencemari data Anda. "Floating point determinism", (yang terdengar buzzwordy cukup membuat saya skeptis) adalah yang paling tidak Anda khawatirkan dalam kenyataan ... khususnya jika Anda menggunakan langkah waktu yang tetap. dengan langkah waktu variabel Anda perlu interpolasi antara langkah waktu tetap untuk menghindari masalah determinisme juga. Saya pikir ini biasanya apa yang dimaksud dengan perilaku "floating point" non-deterministik - hanya saja langkah-langkah waktu variabel menyebabkan integrasi berbeda - tidak ada hubungannya dengan perpustakaan matematika atau fungsi tingkat rendah.

Sinkronisasi adalah kuncinya.

jheriko
sumber
-2

Anda membuatnya deterministik. Untuk contoh yang bagus, lihat Dungeon Siege GDC Presentation tentang bagaimana mereka membuat lokasi di dunia menjadi jaringan.

Juga ingat bahwa determinisme juga berlaku untuk peristiwa 'acak'!

Doug-W
sumber
1
Inilah yang ingin diketahui OP bagaimana melakukannya, dengan floating point.
Bebek Komunis