Pertimbangkan pencarian A * pada peta berbasis ubin. Kode lurus ke depan adalah: Jika ada unit di dalam sel itu, maka itu tidak dapat dijangkau, ini ok.
Tetapi ada masalah resolusi peta. Ketika saya melihat ke Warcraft 3, ada monster dan struktur yang memiliki radius berbeda, dan Anda dapat berjalan sangat dekat, yang lebih mirip berbasis vektor, bagaimana ini diterapkan?
Juga, apa solusi standar untuk menggabungkan deteksi hambatan tabrakan bergerak dengan algoritma pencarian jalur, seperti Warcraft 3?
Jawaban:
Saya tidak bisa mengatakan dengan pasti pendekatan seperti apa yang digunakan oleh pengembang WC3, tetapi sepertinya pendekatan Hierarchical Annotated A *. Jari-jari satuan yang didefinisikan dalam WC3Editor digunakan apa adanya untuk penskalaan model 3d, tetapi ukuran unit sebenarnya untuk merintis jalur terpisah, mungkin sesuatu seperti unitSize = (int) (unitRadius / 10). Itu bukan berbasis vektor, itu sudah pasti.
Katakanlah ada banyak node jalur yang membuat simpul node resolusi tinggi. Unit sederhana seperti ghoul memiliki ukuran 2, jadi untuk menempatkannya di suatu tempat dalam sebuah grid, kita membutuhkan 4 node jalur bebas berdekatan satu sama lain. Pahlawan ksatria kematian sedikit lebih besar dengan ukuran 3, mengambil total 9 jalur node. Sekarang kita menempatkan 2 ziggurat bersama-sama meninggalkan ruang 2 simpul selebar di antara, dan mengirim hantu dan ksatria kematian di sisi lain. Ghoul akan bisa melewati antara dua ziggurats, sementara ksatria kematian harus bergerak. Bagaimana itu bisa ditentukan?
Untuk melihat apakah sebuah simpul dapat mengakomodasi unit dengan ukuran tertentu, mari tetapkan nilai izin khusus untuk setiap node yang mendefinisikan ukuran unit maksimum yang diperbolehkan. Pada dasarnya, ini berarti bahwa beberapa pemeriksaan pembatas dibuat untuk sebuah node, dan batas yang paling besar diingat sebagai clearance node. Jadi ketika kita ingin menempatkan ksatria kematian pada beberapa simpul, itu menjadi sesederhana membandingkan jarak simpul dengan ukuran ksatria kematian. Tentu saja, hal-hal akan menjadi jauh lebih kompleks ketika ada beberapa unit yang berlomba-lomba untuk mendapatkan node, tapi itu cerita lain.
Untuk detail lebih lanjut Anda mungkin ingin memeriksa artikel ini:
http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
sumber
Itu akan menggunakan tessellation untuk membuat daerah pathing jala navigasi AKA. Artikel ini menjelaskan konsep dengan diagram lengkap.
Anda masih dapat mempertahankan A * sebagai pendekatan penelusuran jalan Anda, namun jaringan Anda bukan lagi kisi (grafik yang terhubung 4), tetapi grafik yang menunjukkan konektivitas arbitrer antara wilayah poligonal Anda. Jadi, Anda harus menyesuaikan algoritme Anda agar sesuai.
sumber