Mengoptimalkan perhitungan gravitasi

23

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?

Carson Myers
sumber
1
Sekadar catatan, Anda berkata, "Benda-benda masif itu tidak berulang di atas puing-puing sebagai bagian dari perhitungan kecepatannya, tetapi setiap potongan puing harus bergerak di atas partikel-partikel masif." Saya mendapat kesan dari itu, bahwa Anda menganggap itu lebih efisien. Namun, iterasi 100 objek puing masing-masing 10 kali, masih sama dengan iterasi 10 objek besar 100 kali. Mungkin, itu ide yang baik untuk mengulangi setiap objek puing di loop objek besar sehingga Anda tidak melakukannya untuk kedua kalinya.
Richard Marskell - Drackir 4/11
Seberapa akurat simulasi yang Anda butuhkan? Apakah Anda benar-benar membutuhkan segalanya untuk saling mempercepat? Dan apakah Anda benar-benar perlu menggunakan perhitungan gravitasi yang benar? Atau bisakah Anda berangkat dari kebaktian itu untuk apa yang ingin Anda capai?
chaosTechnician
@Drackir saya pikir kamu benar. Sebagian alasan mereka terpisah adalah karena matematika berbeda untuk benda tak bermassa, dan sebagian adalah karena mereka awalnya tidak mematuhi gravitasi sama sekali, jadi lebih efisien untuk tidak memasukkannya. Jadi ini asli
Carson Myers
@chaosTechnician itu tidak harus sangat akurat - bahkan jika itu hanya memperhitungkan beberapa kekuatan paling dominan maka sistem akan lebih stabil, yang ideal. Tapi itu mencari tahu kekuatan mana yang paling dominan dengan cara efisien yang membuat saya kesulitan. Juga perhitungan gravitasi sudah diperkirakan, hanya saja 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)
Carson Myers
Mengapa masing-masing potongan puing harus beralih ke partikel masif jika tidak bermassa? Tabrakan?
sam hocevar

Jawaban:

26

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.

Nathan Reed
sumber
1
+1 untuk gagasan kisi. Saya sarankan juga melacak pusat massa untuk grid juga untuk menjaga perhitungan sedikit lebih murni (jika perlu).
chaosTechnician
Saya sangat menyukai ide ini. Saya telah mempertimbangkan untuk memuat objek dalam sel, tetapi mengabaikannya ketika mempertimbangkan dua objek terdekat yang secara teknis berada di sel yang berbeda - tetapi saya tidak membuat lompatan mental untuk mempertimbangkan beberapa sel yang berdekatan, serta mempertimbangkan massa gabungan dari objek lain. sel. Saya pikir ini harus bekerja dengan sangat baik jika saya melakukannya dengan benar.
Carson Myers
8
Ini pada dasarnya adalah algoritma Barnes-Hut: en.wikipedia.org/wiki/Barnes –Hut_simulation
Russell Borogove
Bahkan terdengar mirip dengan bagaimana gravitasi seharusnya bekerja dalam fisika - pembengkokan ruang-waktu.
Zan Lynx
Saya suka ide itu - tetapi saya benar-benar berpikir itu perlu sedikit lebih banyak penyempurnaan - apa yang terjadi jika dua objek sangat dekat satu sama lain tetapi dalam sel terpisah? Saya bisa melihat bagaimana paragraf ketiga Anda dapat membantu - tetapi mengapa tidak melakukan cull melingkar pada objek yang berinteraksi?
Jonathan Dickinson
16

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:

  1. Buat daftar partikel acak, dengan massa acak, posisi, dan kecepatan mulai.
  2. Bangun quadtree dari partikel-partikel ini. Setiap node quadtree berisi pusat massa masing-masing subnode. Pada dasarnya, untuk setiap node Anda memiliki tiga nilai: massx, massy, ​​dan massa. Setiap kali Anda menambahkan partikel ke node yang diberikan, Anda meningkatkan massax dan massa dengan partikel.x * partikel.mass dan partikel.y * partikel.ass masing-masing. Posisi (massx / mass, massy / mass) akan berakhir sebagai pusat massa node.
  3. Untuk setiap partikel, hitung gaya (dijelaskan sepenuhnya di sini ). Ini dilakukan dengan mulai dari node atas dan berulang melalui setiap subnode dari quadtree sampai subnode yang diberikan cukup kecil. Setelah berhenti berulang, Anda bisa menghitung jarak dari partikel ke pusat massa node, dan kemudian Anda bisa menghitung gaya menggunakan massa node dan massa partikel.

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
Tautan pertama sudah mati. Apakah applet di-host di tempat lain?
Anko
1
Tetap! maaf, lupa membayar sewa pada domain itu, dan seseorang membelinya secara otomatis: \ Selain itu, 3 menit adalah waktu respons yang cukup baik pada pos berusia 8 tahun 8D
Dan saya harus menambahkan: Saya tidak memiliki kode sumber. Jika Anda mencari beberapa kode sumber, periksa part-nd (ditulis dalam c). Saya yakin ada orang lain di luar sana juga.
3

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.

Sean Middleditch
sumber
Memisahkan proses menjadi operan adalah ide yang bagus, karena interval pembaruan (sejauh yang saya tahu) adalah sepersekian detik yang sangat kecil. Tekstur medan gravitasi mengagumkan, tetapi mungkin sedikit di luar jangkauan saya sekarang.
Carson Myers
1
Jangan lupa untuk melipatgandakan kekuatan yang diterapkan dengan berapa banyak irisan waktu telah dilewati sejak pembaruan terakhir.
Zan Lynx
@ seanmiddlemitch: Bisakah Anda menguraikan tekstur medan gravitasi sedikit lebih banyak? Maaf, saya bukan programmer grafis, tetapi ini terdengar sangat menarik; Aku hanya tidak mengerti bagaimana itu seharusnya bekerja. Dan / atau mungkin Anda memiliki tautan ke deskripsi teknik?
Felix Dombek
@FelixDombek: Jadikan objek Anda sebagai lingkaran yang mewakili area pengaruh. Fragmen shader menulis vektor yang menunjuk pada pusat objek dan dengan besaran yang sesuai (berdasarkan jarak dari pusat dan massa objek). Pencampuran perangkat keras dapat menangani penjumlahan vektor-vektor ini dalam mode aditif. Hasilnya tidak akan menjadi bidang gravitasi yang akurat, tetapi hampir pasti akan cukup baik untuk kebutuhan gim. Sebagai pendekatan lain menggunakan GPU, lihat teknik simulasi gravitasi N-tubuh berbasis CUDA ini: http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html
Sean Middleditch
3

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.

John McDonald
sumber
0

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).

Alex Hirzel
sumber
Ini pada dasarnya apa yang saya lakukan. Setelah saya mendapatkan semua pasangan yang melibatkan X, saya tidak mengulangi X lagi. Saya menemukan gaya antara X dan Y, X dan Z, dll, dan menerapkan gaya itu ke kedua objek dalam pasangan. Setelah loop selesai, 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 berpikir
Carson Myers
0

Dalam 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.

kaviar melambat
sumber
0

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.

Loren Pechtel
sumber