Kapan quadtree lebih disukai daripada hashing spasial?

Saya membuat platformer 2d dengan banyak objek pada saat bersamaan. Semuanya terdeteksi tabrakan AABB. Saya pertama kali mencoba quadtree untuk mengurangi jumlah objek untuk diperiksa, mencoba beberapa konfigurasi yang berbeda, tetapi tidak terbukti seefektif yang saya butuhkan. Saya menerapkan hash spasial dan jauh lebih efisien, jumlah objek untuk memeriksa setiap tabrakan turun secara drastis.

Apakah ada kasus ketika melakukan deteksi tabrakan 2d menggunakan quadtree lebih disukai daripada hashing spasial? Menurut pengujian saya, sepertinya hashing spasial selalu berakhir dengan lebih sedikit objek yang akan diuji untuk tabrakan?

Saya belum melakukan penentuan waktu atas algoritme, tetapi apakah hashing sangat mahal atau sulit diterapkan ketika Anda, misalnya, mengkode dalam C? Perlu dicatat adalah bahwa saya menulis permainan dalam javascript, di mana Anda memiliki hashing "gratis".

Inilah perbandingannya, apakah saya mengabaikan sesuatu? http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

Keuntungan utama dari quad tree adalah memungkinkan Anda membuang seluruh kelompok bucket dengan cepat.

Sebagai contoh, mari kita asumsikan bahwa saya memiliki pohon quad dengan enam level. Pada level terendah, itu 32x32 kotak; 1024 kotak yang terdiri dari level paling bawah dan paling detail. Sebagai perbandingan, kami juga akan mempertimbangkan "hash spasial" - kotak datar yang juga berisi 32x32 kotak, total 1024 kotak. (pohon quad memiliki total lebih dari 1024 kotak, karena juga berisi kotak yang lebih besar di tingkat yang lebih tinggi)

Mari kita asumsikan bahwa tidak ada objek collidable dalam sistem - semua kotak quad tree dan grid datar kita benar-benar kosong.

Jika Anda menguji tabrakan dari sesuatu yang cukup besar sehingga kotak pembatasnya memotong semua kotak itu, dan Anda menggunakan kotak datar, Anda harus memeriksa setiap satu dari 1024 kotak itu untuk melihat apakah ada sesuatu di dalamnya. mereka.

Tetapi jika Anda menggunakan pohon quad bersarang, tingkat paling atas dapat memberi tahu Anda bahwa tidak ada objek lain dalam sistem, sehingga Anda hanya perlu melihat kotak tunggal itu untuk mengetahui bahwa Anda tidak akan menemukan tabrakan lebih dalam di pohon - Anda dapat segera menghentikan pengujian.

Demikian pula, jika objek hanya ada di wilayah tertentu dari pohon quad, pohon quad secara alami akan memandu pencarian Anda hanya melalui kotak yang berpotensi relevan, sedangkan kotak mengharuskan Anda untuk memeriksa setiap kotak berpotongan tunggal, karena Anda tidak memiliki cara untuk mengetahui terlebih dahulu kotak kotak mana yang akan memiliki objek di dalamnya. Jika sebagian besar pohon quad Anda kosong dan Anda melakukan kueri yang besar dan rumit (katakanlah, frustum kamera besar alih-alih kecil, persegi panjang sederhana), maka Anda mungkin menemukan bahwa Anda mengiterasi kotak yang jauh lebih sedikit secara total jika Anda melakukan menguji terhadap sesuatu yang menggunakan struktur pohon, daripada grid datar. Dan itu bisa membuat perbedaan besar.

Semua itu tidak berarti bahwa struktur pohon selalu merupakan pilihan yang tepat, tentu saja. Flat grid ideal untuk situasi yang Anda miliki dalam contoh Anda - awan tebal benda tersebar merata di mana-mana di dunia, dan kami sedang melakukan tes tabrakan sederhana dan murah. Benar-benar kisi kemungkinan menjadi pendekatan optimal dalam kasus itu!