Alternatif partisi spasial 2D untuk hash dan quadtrees spasial

11

Saya sudah mencoba menerapkan algoritma partisi spasial dalam game saya, tetapi hash spasial dan quadtrees bukan yang saya cari.

Ukuran level saya tidak seharusnya memiliki batas (hanya batas Int32). Saya membutuhkan algoritme partisi spasial yang tidak memerlukan "Level Width" dan "Level Height".

Saya memiliki banyak objek fisik yang bergerak. Saya perlu algoritma yang cukup cepat untuk mendukung 500 objek.

Ada alternatif?

c# collision-detection physics tree Vittorio Romeo
sumber

Jawaban:

13

Pohon Dinamis

Box2D adalah mesin yang dioptimalkan dengan baik yang dirancang oleh programmer fisika / game berpengalaman . Awalnya Box2D menggunakan kotak hash yang membutuhkan tinggi dan lebar tetap.

Ketika Erin meningkatkan ke algoritma broadphase yang lebih baik, ia pergi dengan btDbvt Nathanael Presson. Ini adalah broadphase yang digunakan oleh Bullet Physics. Erin memodifikasi dan mengoptimalkan algoritme untuk 2d.

Anda dapat membaca overiew level super tinggi di manual Box2D (§4.11, atau mencari Dynamic Tree).

Berikut ini kecuali dari dokumentasi kode dalam (yang sangat bagus mengingat itu bukan bagian dari API publik).

Fase lebar pohon AABB yang dinamis, terinspirasi oleh btDbvt Nathanael Presson. Pohon dinamis mengatur data dalam pohon biner untuk mempercepat kueri seperti kueri volume dan gips. Leafs adalah proksi dengan AABB. Di pohon kami memperluas proxy AABB oleh b2_fatAABBFactor sehingga proxy AABB lebih besar dari objek klien. Ini memungkinkan objek klien untuk bergerak dalam jumlah kecil tanpa memicu pembaruan pohon.

Node dikumpulkan dan direlokasi, jadi kami menggunakan indeks node daripada pointer.

Pemahaman saya tentang algoritma Dynamic Tree adalah ini. Pohon Dinamis adalah persilangan antara pohon biner avl klasik dan quadtree. Efek akhirnya adalah quadtree yang hanya membelah setiap node menjadi dua, dan garis split tidak tetap (dua bagian tidak sama ukurannya seperti pohon quad). AVL masuk karena kuadrat dengan pemisahan dinamis dapat berubah menjadi dasarnya daftar (O (n) kecepatan pencarian). AVL digunakan untuk menyeimbangkan kembali subtree sehingga untuk memastikan kecepatan pencarian O lg (N).

Yang terbaik dari semua kode adalah MIT sehingga merasa bebas untuk menyalin / berasal / mencuri-malu / dll.

deft_code
sumber
Tampak ... kompleks! Aku akan melihatnya. Seseorang menyarankan saya menggunakan teknik "sweep and prune" atau "sort and sweep" tetapi saya tidak dapat menemukan apa pun tentang implementasi C # atau .NET. Saya menemukan contoh c ++ tetapi membingungkan dan tidak berhasil (saya tetap mencoba mengimplementasikannya). Apakah Anda pikir SAP akan lebih mudah diimplementasikan? Apakah ada implementasi .NET?
Vittorio Romeo
8

Ini sangat dekat dengan pertanyaan serupa yang diajukan di sini di Gamedev, tetapi karena Anda khawatir dengan kinerja dan bukan penyimpanan file, mungkin jawaban saya akan lebih bermanfaat bagi Anda. Saya akan memasukkan sebagian besar di sini untuk kelengkapan, tetapi jawaban aslinya memberikan sedikit lebih mendalam jika Anda ingin melihatnya.

Saya mengalami masalah yang sama dan memutuskan untuk membuat struktur sendiri untuk menangani data. Ini didasarkan longgar pada quadtree, tetapi memiliki ekspansi yang tak terbatas (setidaknya sebesar Int) di semua arah. Itu dirancang untuk menangani data berbasis grid yang diperluas dari titik pusat, seperti Minecraft sekarang. Ini adalah ruang yang efisien dalam memori, dan sangat cepat.

Kode saya dapat ditemukan di sini . Kode lengkap, teruji (tes unit dan beban), dan cukup optimal. Namun, cara kerja bagian dalam belum terdokumentasi dengan baik, tetapi semua metode publik harus digunakan. Jika ada yang memutuskan untuk mencobanya, jangan ragu untuk menghubungi saya dengan pertanyaan atau komentar.

dlras2
sumber
1

Ketika bekerja dengan jumlah yang relatif kecil (<beberapa ribu) objek bertubuh kecil (sebagian besar objek tidak cukup besar untuk berpotensi bertabrakan dengan banyak objek lain) Saya menemukan bahwa daftar sederhana x-order dari kotak pembatas selaras aksial (AABBs) bekerja cukup baik. Saya hanya meletakkan objek dalam daftar, lalu setiap frame setelah memindahkan objek, saya cepat mengurutkan daftar berdasarkan nilai x, lalu membuat satu melewati daftar memeriksa kedekatan AABB. Untuk setiap objek, saya memeriksa objek di depannya dalam daftar sampai saya mencapai akhir daftar atau objek yang berada di luar rentang x; artinya, nilai x tepi kiri adalah> nilai x tepi kanan objek yang sedang diuji. Ini pada dasarnya secara dinamis membagi ruang menjadi irisan berukuran lebar AABB-x yang terkadang tumpang tindih. Itu'

Shavais
sumber
0

Mungkin algoritma r-tree adalah apa yang Anda cari.

Saya bekerja sangat baik untuk geometri statis, tetapi Anda juga dapat menggunakannya untuk memindahkan objek dengan menghapus dan menambahkan objek pada posisi baru mereka.

LaZe
sumber
Saya mencoba implementasi C #, dan kinerjanya terlalu buruk ketika "menghapus dan menambahkan objek di posisi baru mereka".
Vittorio Romeo