Bagaimana cara menemukan semua entitas dalam radius secara terus menerus secara efisien?

Saya memiliki sejumlah besar entitas (unit). Pada setiap langkah, setiap unit perlu mengetahui posisi semua unit di sekitarnya (jarak kurang dari yang diberikan konstanta R ). Semua unit bergerak terus menerus. Ini dalam 3D.

Rata-rata, akan ada 1% dari total unit dihitung dekat unit lain yang diberikan dengan kendala yang diberikan.

Bagaimana saya bisa melakukan ini secara efisien, tanpa memaksa?

Gunakan salah satu algoritma partisi ruang umum, seperti pohon Quadtree, Octree, BSP, atau bahkan Sistem Grid sederhana. Masing-masing memiliki pro dan kontra sendiri untuk setiap skenario tertentu. Anda dapat membaca lebih lanjut tentang mereka di buku-buku ini .

Secara umum (atau begitulah yang saya dengar, saya tidak terlalu terbiasa dengan alasan di balik ini) Quadtree atau Octree lebih cocok untuk lingkungan luar, sedangkan pohon BSP lebih cocok untuk adegan dalam ruangan. Dan pilihan antara menggunakan Quadtree atau Octree tergantung pada seberapa datar dunia Anda. Jika ada sedikit variasi dalam sumbu Y menggunakan Oktree akan sia-sia. Oktree pada dasarnya adalah Quadtree dengan dimensi tambahan.

Akhirnya, jangan abaikan kesederhanaan solusi Grid. Banyak orang mengabaikan bahwa kisi-kisi sederhana kadang-kadang cukup (dan bahkan lebih efisien) untuk masalah mereka, dan langsung beralih ke solusi yang lebih kompleks.

Menggunakan kisi hanya terdiri dari membagi dunia menjadi wilayah yang berjarak sama dan menyimpan entitas di wilayah yang sesuai di dunia. Kemudian, diberi posisi, menemukan entitas yang berdekatan akan menjadi masalah iterasi pada wilayah yang memotong jari-jari pencarian Anda.

Katakanlah dunia Anda berkisar dari (-1000, -1000) hingga (1000, 1000) di pesawat XZ. Misalnya Anda dapat membaginya menjadi 10x10 kisi, seperti:

var grid = new List<Entity>[10, 10];

Kemudian Anda akan menempatkan entitas ke sel yang sesuai di kisi. Misalnya entitas dengan XZ (-1000, -1000) akan jatuh pada sel (0,0) sedangkan entitas dengan XZ (1000, 1000) akan jatuh pada sel (9, 9). Kemudian diberi posisi dan jari-jari di dunia, Anda bisa menentukan sel mana yang berpotongan dengan "lingkaran" ini dan beralih hanya di atasnya, dengan ganda sederhana untuk.

Bagaimanapun, teliti semua alternatif dan pilih salah satu yang tampaknya lebih cocok dengan gim Anda. Saya akui bahwa saya masih belum cukup berpengetahuan tentang masalah ini untuk memutuskan algoritma mana yang terbaik untuk Anda.

Sunting Ditemukan ini di forum lain dan mungkin membantu Anda dengan keputusan:

Kisi-kisi bekerja paling baik ketika sebagian besar objek masuk dalam kisi-kisi kotak, dan distribusinya cukup homogen. Sebaliknya, quadtrees bekerja ketika objek memiliki ukuran variabel atau dikelompokkan di area kecil.

Dengan uraian Anda yang tidak jelas tentang masalahnya, saya juga bersandar pada solusi grid (yaitu, dengan asumsi unit berukuran kecil dan terdistribusi secara homogen).

Saya menulis ini beberapa waktu lalu. Sekarang ada di situs komersial, tetapi Anda bisa mendapatkan sumbernya untuk penggunaan pribadi secara gratis. Ini mungkin berlebihan dan ditulis dalam Java, tetapi didokumentasikan dengan baik sehingga tidak terlalu sulit untuk memotong dan menulis ulang dalam bahasa lain. Pada dasarnya menggunakan Octree, dengan tweak untuk menangani objek yang sangat besar dan multi-threading.

Saya menemukan Octree menawarkan kombinasi terbaik dari fleksibilitas dan efisiensi. Saya mulai dengan kisi-kisi, tetapi tidak mungkin untuk mengukur kuadrat dengan benar dan petak besar dari kotak kosong menggunakan ruang dan daya komputasi tanpa biaya. (Dan itu hanya dalam 2 dimensi.) Kode saya menangani kueri dari banyak utas, yang menambah banyak kerumitan, tetapi dokumentasi akan membantu Anda mengatasinya jika Anda tidak membutuhkannya.

Untuk meningkatkan efisiensi Anda, cobalah untuk menolak 99% "unit" sepele yang tidak di dekat unit target menggunakan kotak centang pembatas yang sangat murah. Dan saya berharap Anda bisa melakukan ini tanpa menyusun data Anda secara spasial. Jadi, jika semua unit Anda disimpan dalam struktur data datar, Anda dapat mencoba memacunya dari awal hingga selesai dan pertama-tama memeriksa apakah unit saat ini berada di luar kotak pembatas unit yang diminati.

Tetapkan kotak pembatas yang terlalu besar untuk unit yang diinginkan sehingga dapat dengan aman menolak item yang tidak memiliki peluang dianggap "dekat" dengannya. Pemeriksaan untuk pengecualian dari kotak pembatas dapat dibuat lebih murah daripada pemeriksaan radius. Namun pada beberapa sistem di mana ini diuji ternyata tidak menjadi kasus. Keduanya tampil hampir sama. Ini diedit setelah banyak perdebatan di bawah ini.

Pertama: klip kotak pembatas 2D.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

Dibandingkan dengan yang seperti ini (dalam 3D):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

Jika objek tidak ditolak sepele maka Anda melakukan tes tabrakan yang lebih mahal dan akurat. Tetapi Anda hanya mencari kedekatan sehingga tes bola cocok untuk itu, tetapi hanya untuk 1% objek yang bertahan dari penolakan sepele.

Artikel ini mendukung kotak untuk penolakan sepele. http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

Jika pendekatan linear ini tidak memberi Anda kinerja yang Anda butuhkan, maka struktur data hierarkis mungkin diperlukan seperti poster lain yang telah dibicarakan. R-Trees patut dipertimbangkan. Mereka mendukung perubahan dinamis. Mereka adalah BTree dari dunia spasial.

Aku hanya tidak ingin kamu repot-repot memperkenalkan kompleksitas seperti itu jika kamu bisa menghindarinya. Ditambah lagi bagaimana dengan biaya menjaga struktur data yang kompleks ini tetap up to date karena objek bergerak beberapa kali per detik?

Ingatlah bahwa kisi adalah struktur data spasial sedalam satu tingkat. Batas ini berarti bahwa itu tidak benar-benar dapat diukur. Saat dunia tumbuh dalam ukuran, demikian juga jumlah sel yang Anda butuhkan untuk menutupi. Akhirnya jumlah sel itu sendiri menjadi masalah kinerja. Namun, untuk dunia berukuran tertentu, ini akan memberi Anda peningkatan kinerja besar-besaran tanpa partisi spasial.

Saya harus membuat ini sebagai jawaban karena saya tidak punya poin untuk berkomentar atau mendukung. Bagi 99% orang yang mengajukan pertanyaan ini, kotak pembatas adalah solusinya, seperti yang dijelaskan oleh Ciaran. Dalam bahasa yang dikompilasi, itu akan menolak 100.000 unit irrelevent dalam sekejap mata. Ada banyak overhead yang terlibat dengan solusi non-brute-force; dengan angka yang lebih kecil (katakanlah di bawah 1000) mereka akan lebih mahal dalam hal waktu pemrosesan daripada memeriksa brute force. Dan mereka akan mengambil lebih banyak waktu pemrograman.

Saya tidak yakin apa artinya "jumlah yang sangat besar" dalam pertanyaan, atau apa yang orang lain maksudkan dengan jawaban di sini. Saya menduga angka saya di atas adalah konservatif dan dapat dikalikan dengan 10; Saya pribadi cukup berprasangka terhadap teknik brute force dan saya benar-benar kesal pada seberapa baik mereka bekerja. Tetapi saya tidak ingin seseorang dengan, katakanlah, 10.000 unit untuk membuang waktu dengan solusi mewah ketika beberapa baris kode cepat akan melakukan trik. Mereka selalu bisa menjadi mewah nanti jika mereka perlu.

Juga, saya akan mencatat bahwa sphere check membutuhkan perkalian di mana kotak pembatas tidak. Perkalian, berdasarkan sifatnya, membutuhkan beberapa kali sepanjang penambahan dan perbandingan. Pasti ada beberapa kombinasi bahasa, OS, dan perangkat keras di mana sphere check akan lebih cepat daripada check box, tetapi di sebagian besar tempat dan waktu check box harus lebih cepat, bahkan jika sphere menolak beberapa unit yang tidak relevan. kotak menerima. (Dan ketika sphere lebih cepat, rilis baru dari compiler / interpreter / optimizer sangat mungkin untuk mengubahnya.)