Saya punya banyak objek dengan ukuran dan kecepatan yang bervariasi yang saling tertarik satu sama lain. Pada setiap pembaruan, saya harus membahas setiap objek dan menambahkan kekuatan karena gravitasi dari setiap objek lainnya. Ini tidak skala dengan sangat baik, adalah salah satu dari dua hambatan besar yang saya temukan dalam permainan saya, dan saya tidak yakin apa yang harus dilakukan untuk meningkatkan kinerja.
Ini terasa seperti saya harus bisa meningkatkan kinerja. Pada waktu tertentu, mungkin 99% objek dalam sistem hanya akan memiliki pengaruh yang diabaikan pada objek. Saya tentu saja tidak dapat mengurutkan objek berdasarkan massa dan hanya mempertimbangkan 10 objek terbesar atau sesuatu, karena gaya bervariasi dengan jarak lebih dari dengan massa (persamaannya adalah di sepanjang garis force = mass1 * mass2 / distance^2). Saya pikir perkiraan yang baik adalah dengan mempertimbangkan benda - benda terbesar dan benda -benda terdekat, mengabaikan ratusan pecahan batu kecil di sisi lain dunia yang tidak mungkin mempengaruhi apa pun - tetapi untuk mengetahui benda mana yang paling dekat saya harus mengulangi semua objek, dan posisi mereka berubah terus-menerus, jadi bukan berarti saya bisa melakukannya sekali saja.
Saat ini saya sedang melakukan sesuatu seperti ini:
private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
for (int i = 0; i < bodies.Count; i++)
{
bodies[i].Update(i);
}
}
//...
public virtual void Update(int systemIndex)
{
for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
{
GravitatingObject body = system.MassiveBodies[i];
Vector2 force = Gravity.ForceUnderGravity(body, this);
ForceOfGravity += force;
body.ForceOfGravity += -force;
}
Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
ForceOfGravity = Vector2.Zero;
Velocity += Motion.Velocity(acceleration, elapsedTime);
Position += Motion.Position(Velocity, elapsedTime);
}
(perhatikan bahwa saya telah menghapus banyak kode - misalnya tes tabrakan, saya tidak mengulangi objek kedua kalinya untuk mendeteksi tabrakan).
Jadi saya tidak selalu mengulangi seluruh daftar - saya hanya melakukan itu untuk objek pertama, dan setiap kali objek menemukan kekuatan rasanya terhadap objek lain, objek lain merasakan kekuatan yang sama, jadi itu hanya memperbarui kedua mereka - dan kemudian objek pertama itu tidak harus dipertimbangkan lagi untuk sisa pembaruan.
Fungsi Gravity.ForceUnderGravity(...)dan Motion.Velocity(...), dll. Hanya menggunakan sedikit XNA yang dibangun dalam matematika vektor.
Ketika dua benda bertabrakan, mereka menciptakan puing tanpa massa. Itu disimpan dalam daftar terpisah dan benda-benda besar tidak iterate atas puing-puing sebagai bagian dari perhitungan kecepatan mereka, tetapi setiap potongan puing harus beralih pada partikel-partikel besar.
Ini tidak harus skala ke batas luar biasa. Dunia ini tidak terbatas, mengandung perbatasan yang menghancurkan benda-benda yang melintasinya - Saya ingin dapat menangani mungkin sekitar seribu benda, saat ini permainan mulai tersedak sekitar 200.
Adakah pemikiran tentang bagaimana saya dapat meningkatkan ini? Beberapa heuristik yang bisa saya gunakan untuk mencukur panjang loop dari ratusan ke hanya beberapa? Beberapa kode saya dapat mengeksekusi lebih jarang daripada setiap pembaruan? Haruskah saya hanya multithread sampai cukup cepat untuk memungkinkan dunia berukuran layak? Haruskah saya mencoba menurunkan perhitungan kecepatan ke GPU? Jika demikian, bagaimana saya merancang itu? Bisakah saya menyimpan data statis yang dibagikan di GPU? Dapatkah saya membuat fungsi HLSL pada GPU dan memanggilnya secara sewenang-wenang (menggunakan XNA) atau apakah mereka harus menjadi bagian dari proses pengundian?
sumber
G * m1 * m2 / r^2, di mana G hanya untuk mengubah perilaku. (walaupun saya tidak bisa membiarkan mereka mengikuti jalur, karena pengguna dapat mengganggu sistem)Jawaban:
Ini terdengar seperti pekerjaan untuk grid. Bagilah ruang permainan Anda ke dalam kisi dan untuk setiap sel kisi menyimpan daftar objek yang saat ini ada di dalamnya. Saat objek bergerak melintasi batas sel, perbarui daftar tempat mereka berada. Saat memperbarui objek dan mencari orang lain untuk berinteraksi, Anda dapat melihat hanya sel grid saat ini dan beberapa yang berdekatan. Anda dapat mengubah ukuran kisi untuk kinerja terbaik (menyeimbangkan biaya memperbarui sel kisi - yang lebih tinggi ketika sel kisi terlalu kecil - dengan biaya melakukan pencarian, yang lebih tinggi ketika sel kisi terlalu besar).
Ini tentu saja akan menyebabkan objek yang lebih jauh daripada beberapa sel kisi untuk tidak berinteraksi sama sekali, yang mungkin merupakan masalah karena akumulasi massa yang besar (baik objek besar, atau sekelompok banyak objek kecil) harus , seperti yang Anda sebutkan, memiliki wilayah pengaruh yang lebih besar.
Satu hal yang bisa Anda lakukan adalah melacak massa total dalam setiap sel kisi, dan memperlakukan seluruh sel sebagai objek tunggal untuk keperluan interaksi yang lebih jauh. Yaitu: ketika Anda menghitung gaya pada objek, menghitung akselerasi objek-ke-objek langsung untuk objek dalam beberapa sel grid di sekitarnya, lalu menambahkan akselerasi sel-ke-sel untuk setiap sel grid yang lebih jauh (atau mungkin hanya orang-orang dengan jumlah massa yang tidak dapat diabaikan di dalamnya). Dengan akselerasi sel ke sel, maksud saya vektor dihitung menggunakan massa total dua sel dan jarak antara pusat-pusatnya. Itu harus memberikan perkiraan yang masuk akal dari gravitasi yang dijumlahkan dari semua objek dalam sel grid, tetapi jauh lebih murah.
Jika dunia gim sangat besar, Anda bahkan bisa menggunakan kisi hierarkis , seperti quadtree (2D) atau octree (3D), dan menerapkan prinsip serupa. Interaksi jarak jauh akan sesuai dengan tingkat hierarki yang lebih tinggi.
sumber
Algoritma Barnes-Hut adalah cara untuk melakukannya. Ini telah digunakan dalam simulasi superkomputer untuk menyelesaikan masalah Anda. Tidak terlalu sulit untuk dikodekan, dan sangat efisien. Saya sebenarnya menulis applet Java belum lama ini untuk menyelesaikan masalah ini.
Kunjungi http://mathandcode.com/programs/javagrav/ dan tekan "mulai" dan "tampilkan quadtree".
Di tab opsi, Anda dapat melihat bahwa jumlah partikel dapat mencapai 200.000. Di komputer saya, perhitungan selesai dalam waktu sekitar 2 detik (menggambar 200.000 titik membutuhkan waktu sekitar 1 detik, tetapi perhitungan berjalan pada utas terpisah).
Inilah cara kerja applet saya:
Game Anda seharusnya dapat dengan mudah menangani ribuan objek yang saling menarik. Jika setiap objek "bodoh" (seperti partikel tulang-telanjang di applet saya), Anda seharusnya bisa mendapatkan 8000 hingga 9000 partikel, mungkin lebih. Dan ini mengasumsikan single-threading. Dengan aplikasi komputasi multi-threaded atau paralel, Anda bisa mendapatkan lebih banyak partikel daripada memperbarui secara real time.
Lihat juga: http://www.youtube.com/watch?v=XAlzniN6L94 untuk perenderan besar ini
sumber
Nathan Reed memiliki jawaban yang sangat bagus. Versi singkatnya adalah menggunakan teknik broadphase yang sesuai dengan topologi simulasi Anda, dan hanya menjalankan perhitungan gravitasi pada pasangan objek yang akan memiliki efek nyata pada satu sama lain. Ini benar-benar tidak berbeda dari apa yang akan Anda lakukan untuk broadphase deteksi tabrakan biasa.
Melanjutkan dari itu, meskipun, kemungkinan lain adalah hanya memperbarui objek sebentar-sebentar. Pada dasarnya, setiap langkah waktu (bingkai) hanya memperbarui sebagian kecil dari semua objek, dan meninggalkan kecepatan (atau akselerasi, tergantung pada preferensi Anda) sama untuk objek lain. Pengguna tidak akan melihat adanya keterlambatan pembaruan dari ini selama intervalnya tidak terlalu lama. Ini akan memberi Anda kecepatan linier dari algoritme, jadi pasti lihat teknik broadphase seperti yang disarankan Nathan juga, yang dapat memberikan peningkatan kecepatan yang jauh lebih signifikan jika Anda memiliki banyak objek. Meskipun sama sekali tidak memodelkan hal yang sama, ini seperti memiliki "gelombang gravitasi". :)
Juga, Anda bisa menghasilkan medan gravitasi dalam satu lintasan, lalu memperbarui objek dalam lintasan kedua. Lulus pertama Anda pada dasarnya mengisi kisi (atau struktur data spasial yang lebih kompleks) dengan pengaruh gravitasi dari setiap objek. Hasilnya sekarang adalah bidang gravitasi yang Anda bahkan dapat render (terlihat cukup keren) untuk melihat akselerasi apa yang akan diterapkan pada objek di lokasi tertentu. Kemudian Anda beralih ke objek dan hanya menerapkan efek medan gravitasi untuk objek itu. Bahkan lebih keren, Anda dapat melakukan ini pada GPU dengan merender objek sebagai lingkaran / bulatan menjadi tekstur, kemudian membaca tekstur (atau menggunakan umpan transform-umpan balik lain pada GPU) untuk memodifikasi kecepatan objek.
sumber
Saya akan merekomendasikan menggunakan Quad Tree. Mereka memungkinkan Anda dengan cepat dan efisien mencari semua objek di area persegi panjang yang sewenang-wenang. Inilah artikel wiki tentang mereka: http://en.wikipedia.org/wiki/Quadtree
Dan tautan tak tahu malu ke proyek XNA Quad Tree saya sendiri di SourceForge: http://sourceforge.net/projects/quadtree/
Saya juga akan memelihara daftar semua benda besar sehingga mereka dapat berinteraksi dengan semua tanpa memandang jarak.
sumber
Hanya sedikit input (mungkin naif). Saya tidak melakukan pemrograman game, tetapi yang saya rasakan adalah bahwa hambatan mendasar Anda adalah perhitungan gravitasi karena gravitasi. Alih-alih mengulangi setiap objek X dan kemudian menemukan efek gravitasi dari setiap objek Y dan menambahkannya, Anda dapat mengambil masing-masing pasangan X, Y dan menemukan kekuatan di antara mereka. Itu harus memotong jumlah perhitungan gravitasi dari O (n ^ 2). Maka Anda akan melakukan banyak penambahan (O (n ^ 2)), tetapi ini biasanya lebih murah.
Juga pada titik ini Anda dapat menerapkan aturan seperti "jika gaya gravitasi akan kurang dari \ epsilon karena benda-benda ini terlalu kecil, atur gaya ke nol". Mungkin bermanfaat untuk memiliki struktur ini untuk keperluan lain juga (termasuk deteksi tabrakan).
sumber
ForceOfGravityvektor adalah jumlah dari semua gaya, dan itu kemudian dikonversi menjadi kecepatan dan posisi baru. Saya tidak yakin bahwa perhitungan gravitasi sangat mahal, dan memeriksa apakah melebihi ambang batas terlebih dahulu tidak akan menghemat waktu, saya tidak berpikirDalam memperluas jawaban seanmiddleditch, saya pikir saya mungkin memberi sedikit cahaya (ironi?) Pada gagasan medan gravitasi.
Pertama, jangan menganggapnya sebagai tekstur, tetapi bidang nilai terpisah yang dapat dimodifikasi (seolah-olah array dua dimensi); dan akurasi simulasi selanjutnya bisa menjadi resolusi bidang itu.
Saat Anda memasukkan objek ke dalam bidang, potensi gravitasinya dapat dihitung untuk semua nilai di sekitarnya; dengan demikian menciptakan wastafel gravitasi di lapangan.
Tetapi berapa banyak poin ini yang harus Anda hitung sebelum menjadi lebih atau tidak efektif seperti sebelumnya? Mungkin tidak banyak, bahkan 32x32 adalah bidang yang penting untuk beralih ke setiap objek. Oleh karena itu pilah seluruh proses menjadi beberapa lintasan; masing-masing dengan berbagai resolusi (atau akurasi).
Yaitu, lintasan pertama dapat menghitung gravitasi objek yang direpresentasikan dalam kisi 4x4, dengan setiap nilai sel mewakili koordinat 2D dalam ruang. Memberikan kompleksitas sub-total O (n * 4 * 4).
Lulus kedua mungkin lebih akurat, dengan bidang gravitasi resolusi 64x64, dengan setiap nilai sel mewakili koordinat 2D di ruang angkasa. Namun, karena kerumitannya sangat tinggi, Anda dapat membatasi radius sel di sekitarnya yang terpengaruh (mungkin, hanya sel 5x5 di sekitarnya yang diperbarui).
Lulus ketiga tambahan dapat digunakan untuk perhitungan akurasi tinggi, dengan mungkin resolusi 1024x1024. Ingat kapan Anda benar-benar melakukan perhitungan terpisah 1024x1024, tetapi hanya beroperasi pada bagian-bagian dari bidang ini (mungkin sub-bagian 6x6).
Dengan demikian, keseluruhan kerumitan Anda untuk pembaruan adalah O (n * (4 * 4 + 5 * 5 + 6 * 6)).
Untuk kemudian menghitung perubahan kecepatan untuk setiap objek Anda, untuk setiap bidang gravitasi (4x4, 64x64, 1024x1024) Anda cukup memetakan posisi massa titik ke sel grid, menerapkan sel grid keseluruhan vektor potensi gravitasi ke vektor baru; ulangi untuk setiap "layer" atau "pass"; lalu tambahkan bersama. Ini akan memberi Anda vektor gaya gravitasi yang baik.
Oleh karena itu, kompleksitas keseluruhan adalah: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). Yang benar-benar diperhitungkan (untuk kompleksitas) adalah berapa banyak sel di sekitarnya yang Anda perbarui saat menghitung potensi gravitasi dalam lintasan, bukan resolusi keseluruhan dari medan gravitasi.
Alasan untuk bidang resolusi rendah (first pass) adalah untuk secara jelas mencakup alam semesta secara keseluruhan, dan memastikan massa yang berada di luar tertarik ke daerah yang lebih padat meskipun jaraknya jauh. Kemudian gunakan bidang resolusi yang lebih tinggi sebagai lapisan terpisah untuk meningkatkan akurasi bagi planet tetangga.
Saya harap ini masuk akal.
sumber
Bagaimana dengan pendekatan lain:
Tetapkan area pengaruh pada objek berdasarkan massanya - mereka terlalu kecil untuk memiliki efek yang terukur di luar rentang itu.
Sekarang bagilah duniamu menjadi grid dan letakkan setiap objek di daftar semua sel yang memiliki pengaruh.
Lakukan perhitungan gravitasi Anda hanya pada objek dalam daftar yang dilampirkan ke sel tempat objek berada.
Anda hanya perlu memperbarui daftar ketika suatu objek pindah ke sel grid baru.
Semakin kecil sel kisi, semakin sedikit perhitungan yang akan Anda lakukan per pembaruan, tetapi semakin banyak pekerjaan yang akan Anda lakukan memperbarui daftar.
sumber