Partisi ruang saat semuanya bergerak

Latar Belakang

Bersama dengan seorang teman saya sedang mengerjakan game 2D yang diatur dalam ruang. Untuk menjadikannya se-immersif dan seinteraktif mungkin, kami ingin ada ribuan objek melayang bebas, beberapa berkerumun bersama, yang lain terapung di ruang kosong.

Tantangan

Untuk melepaskan beban rendering dan mesin fisika kita perlu mengimplementasikan semacam partisi spasial. Ada dua tantangan yang harus kita atasi. Tantangan pertama adalah bahwa semuanya bergerak sehingga merekonstruksi / memperbarui struktur data harus sangat murah karena harus dilakukan setiap frame. Tantangan kedua adalah distribusi objek, seperti yang dikatakan sebelumnya mungkin ada kelompok objek bersama-sama dan potongan-potongan besar ruang kosong dan untuk membuatnya lebih buruk lagi tidak ada batas ruang.

Teknologi yang ada

Saya telah melihat teknik yang ada seperti BSP-Trees, QuadTrees, kd-Trees dan bahkan R-Trees tetapi sejauh yang saya tahu struktur data ini tidak cocok karena memperbarui banyak objek yang telah pindah ke sel lain relatif mahal.

Apa yang saya coba

Saya membuat keputusan bahwa saya membutuhkan struktur data yang lebih diarahkan pada penyisipan cepat / pembaruan daripada memberikan kembali jumlah paling sedikit dari kemungkinan hit yang diberikan kueri. Untuk tujuan itu saya membuat sel-sel tersirat sehingga setiap objek, mengingat posisinya, dapat menghitung sel mana yang seharusnya. Lalu saya menggunakan HashMapyang memetakan koordinat sel ke ArrayList(isi sel). Ini bekerja cukup baik karena tidak ada memori yang hilang pada sel 'kosong' dan mudah untuk menghitung sel mana yang akan diperiksa. Namun membuat semua ArrayListitu (kasus terburuk N) mahal dan begitu juga tumbuh HashMapbanyak kali (walaupun itu sedikit dikurangi dengan memberikannya kapasitas awal yang besar).

Masalah

OK jadi ini berfungsi tetapi masih tidak terlalu cepat. Sekarang saya dapat mencoba untuk mengoptimalkan kode JAVA mikro. Namun saya tidak berharap terlalu banyak karena profiler memberi tahu saya bahwa sebagian besar waktu dihabiskan untuk membuat semua objek yang saya gunakan untuk menyimpan sel. Saya berharap ada beberapa trik / algoritma lain di luar sana yang membuat ini jauh lebih cepat, jadi inilah struktur data ideal saya:

• Prioritas nomor satu adalah memperbarui / merekonstruksi seluruh struktur data dengan cepat
• Ini kurang penting untuk membagi benda menjadi tempat sampah berukuran sama, kita bisa menggambar beberapa objek tambahan dan melakukan beberapa pemeriksaan tabrakan tambahan jika itu berarti memperbarui sedikit lebih cepat
• Memori tidak terlalu penting (permainan PC)

Teknik yang Anda gunakan sangat mirip dengan teknik fisika komputasi yang disebut dinamika molekul, di mana lintasan atom (biasanya sekarang dalam kisaran partikel 100k hingga 10M) diikuti dengan langkah waktu yang sangat kecil. Masalah utama adalah bahwa untuk menentukan gaya pada satu partikel, Anda harus membandingkan posisinya dengan posisi setiap partikel lainnya, yang skalanya sangat buruk (n kuadrat).

Ada trik yang bisa saya sarankan, yang mengharuskan Anda memilih jarak maksimum yang dapat berinteraksi. Sebagai titik awal, saya akan mulai dengan sesuatu seperti 1/10 dari dimensi panjang ruang Anda, dan menyesuaikan dengan selera (cutoff yang lebih panjang berarti lebih akurat, tetapi lebih banyak perhitungan).

Metode ini adalah untuk mengulang setiap partikel (i). (I) mendapatkan array di mana semua partikel dalam kisaran i ditambahkan ke array. Apa yang Anda dapatkan pada akhirnya adalah array 2d, di mana entri ke-i adalah array dari partikel dalam kisaran i. Untuk menghitung kekuatan untuk i, Anda hanya perlu memeriksa entri dalam array i.

Seni metode ini adalah memilih jarak cutoff, dan bantalan ekstra (misalnya 20%). Peningkatan kecepatan adalah Anda hanya perlu memeriksa beberapa interaksi untuk setiap partikel, dan Anda menghitung ulang tetangga hanya setiap beberapa langkah. Saya sarankan memilih kecepatan yang agak cepat, dan mencari tahu berapa langkah waktu yang diperlukan untuk melintasi wilayah "padding". Membuat padding lebih besar (50% atau bahkan 100% dari cutoff) memberi Anda lebih banyak langkah antara penghitungan ulang tetangga, tetapi membuat setiap langkah sedikit lebih lambat. Keseimbangan ini adalah tradeoff.

Satu trik lain dalam menghitung jarak adalah bekerja dengan d ^ 2 alih-alih d, menghapus banyak panggilan ke pow () dan sqrt ().

Sunting: Sulit menemukan tautan referensi yang tidak super teknis. Ini adalah satu-satunya yang bisa kutemukan.

Solusi Anda sendiri kedengarannya cukup bagus jika Anda dapat mencapai membangun struktur data di o (n) maka saya akan mengatakan optimasi harus dilakukan pada pilihan struktur data daripada pada algoritma.

Saya memiliki implementasi yang sama dengan beberapa perbedaan: Struktur data utama adalah array ukuran tetap (seperti ArrayList) yang merupakan yang terbaik untuk akses langsung ke suatu elemen. Setiap sel array berisi daftar tertaut, yang merupakan yang terbaik untuk penyisipan dan sebaik daftar array untuk diulang. Kita nanti perlu menghapus elemen dari daftar yang ditautkan, jadi untuk membuat operasi ini sangat cepat idenya adalah menyimpan di setiap elemen daftar sebuah iterator yang menunjuk ke dirinya sendiri (Anda bilang memori bukan masalah, kan?)

Untuk inisialisasi, setiap "partikel" dimasukkan di akhir daftar tertaut yang sesuai dengan sel dalam larik yang sesuai dengan posisinya di ruang, dengan asumsi bahwa ruang dipartisi dalam petak ukuran tetap. Jadi kami masih dengan kompleksitas (n), tetapi kami mengoptimalkan semuanya dengan menggunakan wadah yang lebih pas untuk digunakan.

Setiap "partikel" memiliki referensi ke daftar tertautnya yang berisi untuk menyediakan akses cepat ke tetangganya.

Pada setiap bingkai kita dapat melakukan interaksi antara setiap partikel dengan daftar tetangganya, dan saya akan mengatakan juga dengan 8 ubin di sekitarnya untuk menghindari efek treshold di dekat batas ubin.

Tidak perlu menghitung ulang seluruh partisi di setiap frame; kita hanya perlu menghapus dan meletakkan kembali item ketika bergerak lebih dari jarak tertentu atau, dengan keamanan, setiap frame X. Gagasannya adalah untuk menyimpan posisi masing-masing item pada saat dimasukkan dalam daftar tertaut, dan pada setiap frame membandingkan posisi saat ini dengan yang lama.