Saya mencari algoritme yang bagus untuk masalah berikut: Diberi kisi-kisi voxel 3D (yang mungkin kosong atau terisi), jika saya memilih dua voxel yang tidak berdekatan, saya ingin tahu apakah mereka terhubung satu sama lain oleh voxel lainnya.
Misalnya (untuk menggambarkan situasi dalam 2D), di mana # adalah kotak yang diisi:
1 2 3
a # # #
b # #
c # # #Jika saya memilih a3 dan c3, saya ingin menentukan secepat mungkin jika mereka terhubung; jika ada jalur antara a3 dan c3 melalui piksel yang diisi. (Situasi sebenarnya adalah dalam kotak voxel 3D, tentu saja.)
Saya telah melihat algoritma penimbunan banjir dan algoritma pencarian jalur, tetapi saya tidak yakin mana yang harus dipilih. Keduanya melakukan pekerjaan yang tidak perlu: Flood fill mencoba mengisi semua voxel, tetapi ini tidak diperlukan. Algoritma pencarian jalur biasanya berkaitan dengan menemukan jalur terpendek, yang juga tidak perlu. Aku hanya perlu tahu apakah ada yang jalan.
Algoritma apa yang harus saya gunakan?
Sunting: berdasarkan komentar, saya pikir harus menambahkan yang berikut: isi voxel tidak diketahui sebelumnya, dan juga, algoritma diperlukan untuk mendeteksi jika penghapusan (pengosongan) voxel akan menyebabkan kelompok voxel pecah menjadi dua atau lebih kelompok kecil.
sumber
c3->c2->b2->a2->a3?Jawaban:
A * akan bekerja dengan baik. Menemukan jalan adalah apa yang Anda inginkan, menemukan jalan terpendek sama cepat (atau lebih cepat) daripada menemukan jalan apa pun. Dalam situasi ini A * kemungkinan yang paling cocok mengingat Anda memiliki titik awal dan akhir. ini berarti Anda memiliki heuristik tambahan untuk mempercepat pencarian.
Dengan A * biasanya jalur pertama yang Anda temukan adalah jalur terpendek, jadi itu tidak melakukan pekerjaan ekstra setelah sudah menemukan jalur.
Untuk beberapa optimasi, lihat jawaban saya di sini .
sumber
Jika Anda siap untuk melakukan beberapa pra-pemrosesan dan memakan biaya penyimpanan, maka mempartisi voxel ke dalam grup yang terhubung pada waktu pembuatan memberikan jawaban yang jelas untuk 'apakah ada jalan sama sekali'. Ada jalur antara dua voxel jika mereka berada di grup yang sama. Masalahnya jelas bahwa Anda harus menyimpan informasi grup di suatu tempat, dan itu tergantung pada tata letak data Anda. Jika Anda menyimpan daftar sederhana, Anda dapat memecahnya menjadi beberapa daftar, satu untuk setiap grup yang terhubung secara spasial. Jika Anda mengorganisir dalam beberapa jenis BVH, maka Anda mungkin bisa mendapatkan efisiensi yang cukup baik jika Anda bisa mengatakan "semua voxel di node ini dan di bawah ini milik grup X".
Sebagai alternatif, Anda dapat melakukan beberapa pra-perpisahan spasial dan menyimpan beberapa set 'hub' voxel yang lebih kecil untuk setiap grup yang terhubung. Kemudian Anda bisa mencari jalur dari sumber dan target voxel ke hub voxel terdekat, yang seharusnya menjadi jalur yang jauh lebih pendek / lebih murah untuk menghitung. Jika Anda dapat menemukan jalur dari voxel ke voxel hub, maka voxel adalah bagian dari grup hub voxel. Dengan pemilihan voxels hub yang cerdas, Anda dapat meminimalkan jumlah lintasan jalur. Misalnya bola mungkin hanya memiliki satu hub voxel di tengahnya, tetapi kelompok tipis panjang mungkin memiliki hub voxel setiap X voxel sepanjang panjangnya. Jika sumber dan target voxel Anda berada di kedua ujung panjangnya, mereka hanya harus pergi paling banyak voxels untuk menemukan hub, dan meskipun mungkin ada sejumlah besar voxels antara awal dan akhir panjang,
Itu semua tergantung pada seberapa patologis kelompok voxel Anda: jika Anda mengharapkan sejumlah besar kelompok terputus yang bertubuh kecil, peningkatan biaya penyimpanan akan secara besar-besaran lebih besar daripada kinerja yang dicapai hanya dengan merintis jalan. Jika Anda mengharapkan grup yang terhubung relatif sedikit tetapi dari topologi aneh, maka pathfinding naif mungkin sangat mahal dan biaya penyimpanan dan pathfinding minimal adalah pilihan yang jauh lebih murah.
sumber
Saya tidak terlalu terbiasa dengan voxel, tetapi saya akan membayangkan bahwa Anda bisa mendapatkan kinerja yang cukup baik dengan menggunakan algoritma pencarian terbaik-pertama seperti A *. Masalah dengan menggunakan A * dalam contoh ini adalah bahwa heuristik yang biasanya akan digunakan dirancang untuk memprioritaskan menemukan jalur terpendek dan bukan hanya 'jalur apa saja' secepat mungkin.
Anda mungkin beruntung menggunakan heuristik alternatif yang memperluas lebih sedikit node seperti
f (p) = g (p) + w (p) * h (p)
di mana w> = 1. Anda menurunkan nilai 'w' semakin dekat Anda ke tujuan, sehingga memberikan prioritas yang lebih tinggi pada biaya jalur 'g' semakin dekat Anda dengan voxel yang Anda cari.
Saya harap ini membantu!
sumber