Saya membuat permainan fisika yang melibatkan benda tegar di mana pemain memindahkan potongan dan bagian untuk memecahkan teka-teki / peta. Aspek yang sangat penting dari gim ini adalah ketika pemain memulai simulasi, gim ini berjalan di mana-mana , terlepas dari sistem operasi, prosesor, dll ...
Ada ruang untuk banyak kerumitan, dan simulasi dapat berjalan untuk waktu yang lama, jadi penting bahwa mesin fisika sepenuhnya deterministik sehubungan dengan operasi floating point-nya, jika tidak solusi mungkin tampak "menyelesaikan" pada mesin satu pemain dan "gagal" pada yang lain.
Bagaimana saya bisa mendapatkan determinisme ini di game saya? Saya bersedia menggunakan berbagai kerangka kerja dan bahasa, termasuk Javascript, C ++, Java, Python, dan C #.
Saya telah tergoda oleh Box2D (C ++) serta padanannya dalam bahasa lain, karena tampaknya memenuhi kebutuhan saya, tetapi tidak memiliki determinisme floating point, terutama dengan fungsi trigonometri.
Pilihan terbaik yang pernah saya lihat sejauh ini adalah Box2D's Java equivalen (JBox2D). Tampaknya melakukan upaya determinisme floating point dengan menggunakan StrictMath
daripada Math
untuk banyak operasi, tetapi tidak jelas apakah mesin ini akan menjamin semua yang saya butuhkan karena saya belum membangun permainan.
Apakah mungkin menggunakan atau memodifikasi mesin yang ada untuk memenuhi kebutuhan saya? Atau apakah saya perlu membuat mesin sendiri?
Sunting: Lewati sisa posting ini jika Anda tidak peduli mengapa seseorang membutuhkan ketelitian seperti itu. Individu dalam komentar dan jawaban tampaknya percaya bahwa saya mencari sesuatu yang seharusnya tidak saya miliki, dan karenanya, saya akan menjelaskan lebih lanjut bagaimana permainan seharusnya bekerja.
Pemain diberi puzzle atau level, yang berisi rintangan dan tujuan. Awalnya, simulasi tidak berjalan. Mereka kemudian dapat menggunakan potongan atau alat yang disediakan untuk membangun mesin. Begitu mereka menekan start, simulasi dimulai dan mereka tidak dapat lagi mengedit mesin mereka. Jika mesin memecahkan peta, pemain telah mengalahkan level. Jika tidak, mereka harus menekan berhenti, mengganti mesin mereka, dan coba lagi.
Alasan semuanya perlu deterministik adalah karena saya berencana untuk menghasilkan kode yang akan memetakan setiap mesin (satu set potongan dan alat yang mencoba untuk menyelesaikan level) ke file xml atau json dengan merekam posisi, ukuran, dan rotasi masing-masing bagian. Maka akan memungkinkan bagi pemain untuk membagikan solves (yang diwakili oleh file-file ini) sehingga mereka dapat memverifikasi solves, belajar dari satu sama lain, mengadakan kompetisi, berkolaborasi, dll ... Tentu saja, kebanyakan solve, terutama yang sederhana atau cepat yang, tidak akan terpengaruh oleh kurangnya determinisme. Tetapi desain lambat atau kompleks yang menyelesaikan level yang sangat sulit mungkin, dan itu adalah yang akan menjadi yang paling menarik dan layak untuk dibagikan.
sumber
Jawaban:
Pada penanganan angka floating point dengan cara deterministik
Floating point bersifat deterministik. Yah, seharusnya begitu. Itu rumit.
Ada banyak literatur tentang angka floating point:
Dan bagaimana mereka bermasalah:
Untuk abstrak. Setidaknya, pada utas tunggal, operasi yang sama, dengan data yang sama, yang terjadi dalam urutan yang sama, harus bersifat deterministik. Jadi, kita bisa mulai dengan mengkhawatirkan input, dan menyusun ulang.
Salah satu input yang menyebabkan masalah adalah waktu.
Pertama-tama, Anda harus selalu menghitung timestep yang sama. Saya tidak mengatakan untuk tidak mengukur waktu, saya mengatakan bahwa Anda tidak akan melewatkan waktu untuk simulasi fisika, karena variasi waktu adalah sumber kebisingan dalam simulasi.
Mengapa Anda mengukur waktu jika Anda tidak meneruskannya ke simulasi fisika? Anda ingin mengukur waktu yang telah berlalu untuk mengetahui kapan langkah simulasi harus dipanggil, dan - dengan asumsi Anda menggunakan tidur - berapa banyak waktu untuk tidur.
Jadi:
Sekarang, instruksi pemesanan ulang.
Kompilator dapat memutuskan bahwa
f * a + b
itu sama denganb + f * a
, namun itu mungkin memiliki hasil yang berbeda. Itu juga dapat dikompilasi ke fmadd , atau dapat memutuskan mengambil beberapa baris seperti itu yang terjadi bersama dan menulisnya dengan SIMD , atau beberapa pengoptimalan lain yang tidak dapat saya pikirkan saat ini. Dan ingat kami ingin operasi yang sama terjadi pada urutan yang sama, itu menjadi alasan bahwa kami ingin mengendalikan operasi apa yang terjadi.Dan tidak, menggunakan dobel tidak akan menyelamatkan Anda.
Anda perlu khawatir tentang kompiler dan konfigurasinya, khususnya untuk menyinkronkan angka floating point di seluruh jaringan. Anda perlu mendapatkan build untuk menyetujui untuk melakukan hal yang sama.
Bisa dibilang, menulis majelis akan ideal. Dengan begitu Anda memutuskan operasi apa yang harus dilakukan. Namun, itu bisa menjadi masalah untuk mendukung banyak platform.
Jadi:
Kasus untuk nomor titik tetap
Karena cara mengapung diwakili dalam memori, nilai-nilai besar akan kehilangan presisi. Ini menjadi alasan bahwa menjaga nilai-nilai Anda kecil (penjepit) mengurangi masalah. Dengan demikian, tidak ada kecepatan besar dan tidak ada kamar besar. Yang juga berarti Anda dapat menggunakan fisika diskrit karena risiko risikonya lebih kecil.
Di sisi lain, kesalahan kecil akan menumpuk. Jadi, terpotong. Maksud saya, skala dan dilemparkan ke tipe integer. Dengan begitu Anda tahu tidak ada yang menumpuk. Akan ada operasi yang dapat Anda lakukan dengan tetap menggunakan tipe integer. Ketika Anda perlu kembali ke floating point, Anda membuang dan membatalkan penskalaan.
Catatan saya katakan skala. Idenya adalah bahwa 1 unit sebenarnya akan direpresentasikan sebagai kekuatan dua (16384 misalnya). Apa pun itu, buatlah itu konstan dan gunakanlah. Anda pada dasarnya menggunakannya sebagai nomor titik tetap. Bahkan, jika Anda dapat menggunakan nomor titik tetap yang tepat dari beberapa pustaka yang dapat diandalkan, jauh lebih baik.
Saya katakan truncate. Tentang masalah pembulatan, itu berarti Anda tidak bisa mempercayai sedikit pun dari nilai apa pun yang Anda dapatkan setelah pemeran. Jadi, sebelum skala pemeran mendapatkan sedikit lebih banyak dari yang Anda butuhkan, dan potong setelahnya.
Jadi:
Tunggu, mengapa Anda membutuhkan floating point? Bisakah Anda tidak bekerja hanya dengan tipe integer? Oh benar Trigonometri dan radikalisasi. Anda dapat menghitung tabel untuk trigonometri dan radikasi dan membuatnya dipanggang di sumber Anda. Atau Anda dapat menerapkan algoritma yang digunakan untuk menghitungnya dengan angka titik mengambang, kecuali menggunakan nomor titik tetap. Ya, Anda perlu menyeimbangkan memori, kinerja, dan presisi. Namun, Anda bisa tetap keluar dari angka floating point, dan tetap deterministik.
Tahukah Anda bahwa mereka melakukan hal-hal seperti itu untuk PlayStation asli? Silakan Temui Anjing Saya, Tambalan .
By the way, saya tidak mengatakan untuk tidak menggunakan floating point untuk grafik. Hanya untuk fisika. Maksudku, tentu saja, posisi akan tergantung pada fisika. Namun, seperti yang Anda tahu collider tidak harus cocok dengan model. Kami tidak ingin melihat hasil pemotongan model.
Jadi: GUNAKAN ANGKA TETAP TETAP.
Agar jelas, jika Anda dapat menggunakan kompiler yang memungkinkan Anda menentukan cara floating point bekerja, dan itu sudah cukup untuk Anda, maka Anda bisa melakukannya. Itu tidak selalu menjadi pilihan. Selain itu, kami melakukan ini untuk determinisme. Nomor titik tetap tidak berarti tidak ada kesalahan, setelah semua mereka memiliki presisi terbatas.
Saya tidak berpikir bahwa "nomor titik tetap itu sulit" adalah alasan yang baik untuk tidak menggunakannya. Dan jika Anda ingin alasan yang baik untuk menggunakannya, itu adalah determinisme, khususnya determinisme lintas platform.
Lihat juga:
Tambahan : Saya menyarankan agar ukuran dunia kecil. Dengan mengatakan itu, Kedua OP ans Jibb Smart memunculkan titik bahwa bergerak menjauh dari pelampung asal memiliki presisi kurang. Itu akan memiliki efek pada fisika, yang akan terlihat jauh lebih awal daripada ujung dunia. Nomor titik tetap, baik, memiliki presisi tetap, mereka akan sama baik (atau buruk, jika Anda suka) di mana-mana. Mana yang baik jika kita menginginkan determinisme. Saya juga ingin menyebutkan bahwa cara kita biasanya melakukan fisika memiliki sifat memperkuat variasi kecil. Lihat Efek Kupu-Kupu - Fisika Deterministik dalam Mesin Luar Biasa dan Pembuat Alat .
Cara lain untuk melakukan fisika
Saya telah berpikir, alasan mengapa kesalahan kecil dalam presisi dalam angka floating point menguat adalah karena kita melakukan iterasi pada angka-angka itu. Setiap langkah simulasi, kami mengambil hasil dari langkah simulasi terakhir dan melakukan hal-hal pada mereka. Mengumpulkan kesalahan di atas kesalahan. Itu adalah efek kupu-kupu Anda.
Saya tidak berpikir kita akan melihat satu build menggunakan satu thread pada mesin yang sama menghasilkan output yang berbeda dengan input yang sama. Namun, pada mesin lain itu bisa, atau bangunan lain bisa.
Ada argumen untuk pengujian di sana. Jika kita memutuskan dengan tepat bagaimana hal-hal seharusnya bekerja, dan kita dapat menguji pada perangkat keras target, kita tidak boleh memadamkan build yang memiliki perilaku berbeda.
Namun, ada juga argumen untuk tidak bekerja jauh yang mengakumulasi begitu banyak kesalahan. Mungkin ini adalah kesempatan untuk melakukan fisika dengan cara yang berbeda.
Seperti yang mungkin Anda ketahui, ada fisika kontinu dan diskrit, keduanya bekerja pada seberapa banyak masing-masing objek akan maju pada catatan waktu. Namun, fisika kontinu memiliki cara untuk mencari tahu instan tabrakan, bukan menyelidiki berbagai kemungkinan yang mungkin untuk melihat apakah tabrakan terjadi.
Jadi, saya mengusulkan yang berikut: gunakan teknik fisika kontinu untuk mencari tahu kapan tabrakan berikutnya dari setiap objek akan terjadi, dengan timestep besar, jauh lebih besar dari yang ada pada satu langkah simulasi tunggal. Kemudian Anda mengambil instan tabrakan terdekat dan mencari tahu di mana semuanya akan berada pada saat itu.
Ya, itu banyak pekerjaan dari satu langkah simulasi. Itu berarti simulasi itu tidak akan mulai secara instan ...
... Namun, Anda dapat mensimulasikan beberapa langkah simulasi berikutnya tanpa memeriksa tabrakan setiap kali, karena Anda sudah tahu kapan tabrakan berikutnya akan terjadi (atau bahwa tidak ada tabrakan yang terjadi di timestep besar). Selain itu, kesalahan yang diakumulasikan dalam simulasi tersebut tidak relevan karena setelah simulasi mencapai timestep besar, kami hanya menempatkan posisi yang kami hitung sebelumnya.
Sekarang, kita dapat menggunakan anggaran waktu yang akan kita gunakan untuk memeriksa tabrakan setiap langkah simulasi untuk menghitung tabrakan berikutnya setelah yang kita temukan. Itu adalah kita dapat mensimulasikan ke depan dengan menggunakan timestep besar. Dengan asumsi dunia terbatas dalam ruang lingkup (ini tidak akan bekerja untuk permainan besar), harus ada antrian negara masa depan untuk simulasi, dan kemudian setiap frame Anda hanya interpolasi dari negara terakhir ke yang berikutnya.
Saya akan berdebat untuk interpolasi. Namun, mengingat ada percepatan, kita tidak bisa begitu saja menginterpolasi semuanya dengan cara yang sama. Sebagai gantinya kita perlu menginterpolasi dengan mempertimbangkan percepatan setiap objek. Dalam hal ini kita bisa memperbarui posisi dengan cara yang sama seperti yang kita lakukan untuk timestep besar (yang juga berarti lebih sedikit kesalahan karena kita tidak akan menggunakan dua implementasi berbeda untuk gerakan yang sama).
Catatan : Jika kita melakukan angka floating point ini, pendekatan ini tidak memecahkan masalah objek yang berperilaku berbeda semakin jauh dari asal mereka. Namun, meskipun benar bahwa ketepatan hilang semakin jauh Anda pergi dari asal, itu masih deterministik. Bahkan, itu sebabnya bahkan tidak memunculkannya pada awalnya.
Tambahan
Dari OP dalam komentar :
Jadi, tidak ada format biner, kan? Itu berarti kita juga perlu khawatir apa pun angka floating point yang ditemukan sesuai dengan aslinya. Lihat: Float Precision Revisited: Portabilitas Float Sembilan Digit
sumber
base64
elemen menggunakan XML & JSON . Ini bukan cara yang efisien untuk mewakili sejumlah besar data seperti itu, tetapi itu tidak benar untuk menyiratkan bahwa mereka mencegah penggunaan representasi biner.Saya bekerja untuk perusahaan yang membuat game strategi real-time tertentu yang terkenal, dan saya dapat memberitahu Anda bahwa determinisme floating point adalah mungkin.
Menggunakan kompiler yang berbeda, atau kompiler yang sama dengan pengaturan yang berbeda, atau bahkan versi yang berbeda dari kompiler yang sama, semuanya dapat mematahkan determinisme.
Jika Anda memerlukan crossplay antara platform atau versi game maka saya pikir Anda harus pergi ke titik tetap - satu-satunya crossplay yang mungkin saya sadari dengan floating point, adalah antara PC dan XBox1, tapi itu cukup gila.
Anda harus menemukan mesin fisika yang sepenuhnya deterministik, atau mengambil mesin open source dan membuatnya deterministik, atau memutar mesin Anda sendiri. Dari atas kepala saya, saya merasa bahwa Unity dari semua hal menambahkan mesin fisika deterministik, tetapi saya tidak yakin apakah itu hanya deterministik pada mesin yang sama atau deterministik di semua mesin.
Jika Anda akan mencoba untuk menggulung barang-barang Anda sendiri, beberapa hal yang dapat membantu:
sumber
rsqrtps
?Saya tidak yakin apakah ini adalah jenis jawaban yang Anda cari, tetapi alternatif mungkin adalah untuk menjalankan perhitungan pada server pusat. Mintalah klien mengirim konfigurasi ke server Anda, biarkan ia melakukan simulasi (atau mengambil yang di-cache) dan mengirim kembali hasilnya, yang kemudian ditafsirkan oleh klien dan diproses menjadi grafik.
Tentu saja, ini menutup semua rencana yang Anda mungkin harus menjalankan klien dalam mode offline, dan tergantung pada seberapa intensif komputasi simulasi Anda mungkin memerlukan server yang sangat kuat. Atau beberapa, tetapi setidaknya Anda memiliki pilihan untuk memastikan bahwa mereka memiliki konfigurasi perangkat keras dan perangkat lunak yang sama. Simulasi waktu nyata mungkin sulit tetapi bukan tidak mungkin (pikirkan streaming video langsung - mereka bekerja, tetapi dengan sedikit penundaan).
sumber
Saya akan memberikan saran kontra-intuitif bahwa, meskipun tidak 100% andal, harus berfungsi dengan baik sebagian besar waktu dan sangat mudah untuk diterapkan.
Kurangi presisi.
Gunakan ukuran langkah-waktu konstan yang telah ditentukan sebelumnya, lakukan fisika pada setiap langkah-waktu dalam pelampung presisi ganda standar, tetapi kemudian ukur resolusi semua variabel menjadi presisi-tunggal (atau sesuatu yang lebih buruk) setelah setiap langkah. Maka sebagian besar kemungkinan penyimpangan yang dapat disusun ulang dengan floating-point (dibandingkan dengan menjalankan referensi dari program yang sama) akan dihapus karena penyimpangan tersebut terjadi dalam digit yang bahkan tidak ada dalam presisi berkurang. Dengan demikian penyimpangan tidak mendapatkan kesempatan penumpukan Lyapunov (Butterfly Effect) yang akhirnya akan menjadi terkenal.
Tentu saja, simulasi akan sedikit kurang akurat daripada yang seharusnya (dibandingkan dengan fisika nyata), tetapi itu tidak terlalu penting selama semua program Anda berjalan tidak akurat dengan cara yang sama .
Sekarang, secara teknis tentu saja mungkin bahwa penataan ulang akan menyebabkan penyimpangan yang mencapai angka signifikansi yang lebih tinggi, tetapi jika penyimpangan benar-benar hanya disebabkan oleh float dan nilai-nilai Anda mewakili jumlah fisik kontinu, ini sangat tidak mungkin. Perhatikan bahwa ada setengah miliar
double
nilai di antara duasingle
yang mana saja, sehingga sebagian besar waktu-langkah dalam sebagian besar simulasi dapat diharapkan persis sama di antara simulasi berjalan. Beberapa kasus di mana penyimpangan berhasil melewati quantisation diharapkan dalam simulasi yang tidak berjalan begitu lama (setidaknya tidak dengan dinamika kacau).Saya juga akan merekomendasikan Anda mempertimbangkan pendekatan yang sepenuhnya berlawanan dengan apa yang Anda tanyakan: merangkul ketidakpastian ! Jika perilakunya sedikit tidak deterministik, maka ini sebenarnya lebih dekat dengan eksperimen fisika aktual. Jadi, mengapa tidak sengaja mengacak parameter awal untuk setiap simulasi, dan membuatnya menjadi syarat bahwa simulasi berhasil secara konsisten selama beberapa percobaan? Itu akan mengajarkan lebih banyak tentang fisika, dan tentang bagaimana merekayasa mesin agar cukup kuat / linier, daripada yang sangat rapuh yang hanya realistis dalam simulasi.
sumber
Buat kelas Anda sendiri untuk menyimpan angka!
Anda dapat memaksakan perilaku deterministik jika Anda tahu persis bagaimana perhitungan akan dilakukan. Misalnya, jika satu-satunya operasi yang Anda tangani adalah perkalian, pembagian, penjumlahan, dan pengurangan, maka cukup untuk mewakili semua angka hanya sebagai angka rasional. Untuk melakukan ini, kelas Rasional sederhana akan baik-baik saja.
Tetapi jika Anda ingin berurusan dengan perhitungan yang lebih rumit (mungkin fungsi trigonometri misalnya), maka Anda harus menulis sendiri fungsi tersebut. Jika Anda ingin dapat mengambil sinus angka, Anda harus dapat menulis fungsi yang mendekati sinus angka sementara hanya menggunakan operasi yang disebutkan di atas. Ini semua bisa dilakukan, dan menurut saya mengelak dari banyak detail berbulu di jawaban lain. Imbalannya adalah Anda malah harus berhadapan dengan matematika.
sumber
*
/
+
-
maka penyebut akan semakin besar dan lebih besar dari waktu ke waktu.Ada beberapa kebingungan istilah di sini. Sebuah sistem fisik dapat sepenuhnya deterministik, tetapi tidak mungkin untuk memodelkan periode waktu yang berguna karena perilakunya sangat sensitif terhadap kondisi awal, dan perubahan yang sangat kecil dalam kondisi awal akan menghasilkan perilaku yang sama sekali berbeda.
Berikut adalah video perangkat nyata yang perilakunya sengaja tidak dapat diprediksi, kecuali dalam arti statistik:
https://www.youtube.com/watch?v=EvHiee7gs9Y
Sangat mudah untuk membangun sistem matematika sederhana (hanya menggunakan penjumlahan dan perkalian) di mana hasil setelah langkah N tergantung pada tempat desimal N'th dari kondisi awal. Menulis perangkat lunak untuk memodelkan sistem seperti itu secara konsisten, pada setiap perangkat keras dan perangkat lunak komputer yang mungkin dimiliki pengguna, hampir tidak mungkin - bahkan jika Anda memiliki anggaran yang cukup besar, uji aplikasi pada setiap kemungkinan kombinasi perangkat keras dan perangkat lunak.
Cara terbaik untuk memperbaikinya adalah dengan menyerang masalah pada sumbernya: jadikan fisika permainan Anda deterministik seperti yang diperlukan untuk mendapatkan hasil yang dapat direproduksi.
Alternatifnya adalah mencoba membuatnya deterministik dengan mengutak-atik perangkat lunak komputer untuk memodelkan sesuatu yang tidak ditentukan oleh fisika. Masalahnya adalah Anda telah memasukkan beberapa lapisan kompleksitas ke dalam sistem, dibandingkan dengan mengubah fisika secara eksplisit.
Sebagai contoh spesifik, anggaplah gim Anda melibatkan benturan tubuh yang kaku. Bahkan jika Anda mengabaikan gesekan, pemodelan tabrakan yang tepat antara objek berbentuk sewenang-wenang yang mungkin berputar saat bergerak dalam praktiknya mustahil. Tetapi jika Anda mengubah situasi sehingga satu-satunya benda adalah batu bata persegi empat yang tidak berputar, hidup menjadi jauh lebih sederhana. Jika objek dalam game Anda tidak terlihat seperti batu bata, maka sembunyikan fakta itu dengan beberapa grafik "non-fisik" - misalnya benar-benar menyembunyikan instan tabrakan di balik asap atau api, atau gelembung teks kartun "Aduh" atau terserah.
Pemain harus menemukan permainan fisika dengan memainkan permainan. Tidak masalah jika itu tidak "sepenuhnya realistis" asalkan konsisten dengan diri sendiri, dan cukup mirip dengan pengalaman yang masuk akal untuk masuk akal.
Jika Anda membuat fisika itu sendiri berperilaku stabil, model komputer itu juga dapat menghasilkan hasil yang stabil, setidaknya dalam arti bahwa kesalahan pembulatan tidak akan relevan.
sumber
Gunakan presisi floating point ganda , alih-alih presisi floating point tunggal . Meskipun tidak sempurna, itu cukup akurat untuk dianggap deterministik dalam fisika Anda. Anda dapat mengirim roket ke bulan dengan presisi titik mengambang ganda, tetapi tidak presisi titik mengambang tunggal.
Jika Anda benar-benar membutuhkan determinisme sempurna, gunakan matematika titik tetap . Ini akan memberi Anda lebih sedikit presisi (dengan asumsi Anda menggunakan jumlah bit yang sama), tetapi hasilnya deterministik. Saya tidak mengetahui adanya mesin fisika yang menggunakan matematika titik tetap, jadi Anda mungkin perlu menulis sendiri jika Anda ingin menempuh rute ini. (Sesuatu yang saya sarankan menentang.)
sumber
Gunakan Pola Memento .
Dalam menjalankan awal Anda, simpan data posisi setiap frame, atau tolok ukur apa pun yang Anda butuhkan. Jika itu terlalu kinerja, hanya lakukan itu setiap n frame.
Kemudian ketika Anda mereproduksi simulasi, ikuti fisika arbitrer, tetapi perbarui data posisi setiap n bingkai.
Kode pseudo yang terlalu disederhanakan:
sumber