A * navigasi menemukan jalur mesh

Jadi saya telah membuat game Java 2D top-down ini dalam kerangka kerja ini disebut Greenfoot dan saya telah bekerja pada AI untuk orang-orang yang akan Anda lawan. Saya ingin mereka dapat bergerak di seluruh dunia secara realistis sehingga saya segera menyadari, di antara beberapa hal lain, saya akan memerlukan semacam jalan.

Saya telah membuat dua prototipe A *. Satu berbasis grid dan kemudian saya membuat satu yang bekerja dengan titik arah jadi sekarang saya perlu mencari cara untuk mendapatkan dari "peta" 2d dari hambatan / bangunan ke grafik node yang bisa saya buat jalurnya. Pathfinding yang sebenarnya tampak baik-baik saja, hanya daftar saya yang terbuka dan tertutup yang dapat menggunakan struktur data yang lebih efisien, tetapi saya akan membahasnya jika dan ketika saya membutuhkannya.

Saya bermaksud menggunakan navigasi mesh untuk semua alasan yang dijabarkan dalam posting ini di aiblog.net . Namun, masalah yang saya hadapi adalah bahwa apa yang A * pikirkan adalah jalur terpendek dari pusat / tepi poligon belum tentu jalur terpendek jika Anda melakukan perjalanan melalui bagian mana pun dari simpul. Untuk mendapatkan ide yang lebih baik, Anda dapat melihat pertanyaan yang saya ajukan di stackoverflow .

Saya mendapat jawaban yang bagus tentang grafik visibilitas. Sejak itu saya telah membeli buku tersebut ( Komputasi Geometri: Algoritma dan Aplikasi ) dan membaca lebih jauh ke dalam topik, namun saya masih mendukung jala navigasi (Lihat " Mengelola Kompleksitas " dari Catatan Amit tentang Path-Finding ). (Sebagai catatan, mungkin saya bisa menggunakan Theta * untuk mengubah banyak titik arah menjadi satu garis lurus jika yang pertama dan yang terakhir tidak dikaburkan. Atau setiap kali saya kembali periksa ke waypoint sebelum terakhir untuk melihat apakah saya bisa langsung dari itu untuk ini)

Jadi pada dasarnya yang saya inginkan adalah jala navigasi di mana setelah saya memasukkannya melalui algoritma corong (misalnya yang ini dari Digesting Duck ) saya akan mendapatkan jalur terpendek yang benar, daripada mendapatkan satu yang merupakan jalur terpendek mengikuti simpul ke simpul saja, tetapi bukan yang terpendek mengingat Anda dapat melewati beberapa poligon dan melewati node / edge.

Oh dan saya juga ingin tahu bagaimana Anda menyarankan untuk menyimpan informasi mengenai poligon. Sebagai contoh prototipe waypoint yang saya buat, saya hanya punya masing-masing simpul sebagai objek dan menyimpan daftar semua simpul lain yang bisa Anda tempuh dari simpul itu, saya rasa itu tidak akan berfungsi dengan poligon? dan bagaimana cara mengetahui apakah poligon terbuka / dapat dilalui atau jika itu adalah benda padat? Bagaimana cara menyimpan node mana yang membentuk poligon?

Akhirnya, sebagai catatan: Saya ingin memprogram ini sendiri dari awal meskipun sudah ada solusi lain yang tersedia dan saya tidak bermaksud untuk (kembali) menggunakan kode ini selain permainan ini sehingga tidak masalah bahwa kualitasnya pasti buruk.

Saya akan menyarankan bahwa bahkan jika Anda akan menulis semua kode Anda sendiri, bahwa Anda mengunduh Menyusun Kembali dan membangun aplikasi sampel karena memiliki visualisasi yang menunjukkan navmesh yang dihasilkan dan memungkinkan Anda untuk menguji pencarian jalan dengan titik sederhana dan klik antarmuka. Anda bisa belajar banyak hanya dengan bermain dengan itu.

Seperti yang telah Anda sadari, ada dua langkah untuk menghasilkan jalur yang terlihat baik - pencari jalur A * dan kemudian pasca-pemrosesan berikutnya yang mencakup pelurusan jalur (penghapusan setiap belokan yang tidak perlu untuk menghindari rintangan) dan mungkin juga menambahkan kurva pada titik balik.

Menemukan jalan

Anda dapat menguasai bagian A * yang sangat bagus. Anda juga telah membuat pengamatan bahwa A * tidak akan selalu menemukan jalan yang paling lurus. Sangat penting untuk memahami bahwa ini adalah karena A * adalah sebuah algoritma untuk menemukan jalur terpendek melalui grafik (menjadi konsep matematika di mana node tidak berdimensi) ketika Anda menerapkannya ke mesh, Anda harus memetakan node ke elemen mesh entah bagaimana.

Hal yang paling jelas untuk dilakukan adalah menavigasi dari titik pusat poligon ke titik pusat dan mendasarkan biaya pada jarak ini, tetapi ini memiliki beberapa masalah. Pertama adalah bahwa ia tidak akan selalu menemukan jalur terpendek geometris dan yang kedua adalah bahwa jika Anda mencoba dan mengikuti jalur yang telah Anda hitung di sana Anda akan melihat bahwa garis lurus dari satu pusat ke yang berikutnya dapat melintasi poligon yang tidak bukan bagian dari jalur (dan mungkin tidak dapat dilayari sama sekali). Ini bukan cara yang buruk untuk membuat biaya grafik traversal saat melakukan A * tetapi jelas tidak memadai untuk tujuan traversal apa pun.

Solusi paling sederhana berikutnya adalah melakukan A * dari ujung ke ujung melalui mesh. Anda akan menemukan ini lebih mudah untuk dipikirkan jika Anda membayangkan bahwa alih-alih satu simpul per poligon, Anda memiliki satu per-tepi per-poligon. Jadi jalur Anda bergerak dari titik awal ke tepat di dalam tepi terdekat, menyeberang ke tepat di dalam tepi poligon yang berdekatan dan kemudian ke dalam tepi berikutnya di poligon yang sama dan seterusnya. Ini menghasilkan jalur terpendek lebih sering dan juga memiliki manfaat yang dapat dilalui jika Anda tidak ingin melakukan langkah pelurusan jalur.

Jalan diluruskan

Algoritma yang digunakan dalam Detour (perpustakaan navigasi yang menyertai Recast) cukup sederhana. Anda harus mengamati bahwa itu hanya akan meluruskan jalur dalam batas-batas poligon yang ditemukan selama pencarian A *. Dengan demikian, jika itu tidak menemukan jalur terketat di sekitar rintangan, Anda tidak akan mendapatkan jalur ketat setelah menjalankan algoritma itu. Dalam prakteknya navmeshes yang dihasilkan oleh recast cenderung memiliki poligon tunggal yang dapat Anda lewati saat menavigasi titik choke (titik terdekat antara dua rintangan) dan A * akan selalu menghasilkan daftar node yang sedekat mungkin dengan rintangan bisa jadi. Jika Anda menggunakan petak sebagai navmesh, ini tidak akan terjadi dan algoritma yang sangat sederhana ini akan menyisipkan putaran palsu.

Algoritma pelurusan jalur Detour tidak cukup O (n) dalam kompleksitas karena ketika menentukan bahwa ia perlu memasukkan belokan, ia menyisipkannya pada titik terakhir pengetatan saluran ke kiri (saat belok kiri dan sebaliknya) dan kemudian mulai menelusuri node dari titik itu lagi.

Jika Anda ingin meluruskan jalur di luar poligon yang merupakan bagian dari rute A *, segalanya menjadi jauh lebih kompleks. Anda harus menerapkan rutinitas ray-cast yang dapat menguji apakah dua titik di navmesh Anda dapat saling melihat (Anda harus tetap memilikinya sehingga Anda dapat melihat apakah Anda perlu menggunakan A * sama sekali). Anda melakukan ini dengan memotong segmen garis yang dibentuk oleh target-> target dengan tepi penghubung poligon yang berisi asal, kemudian menguji tepi penghubung poligon yang menggerakkan Anda ke dan seterusnya. Jika Anda memotong tepi yang tidak terhubung (saya menyebutnya tepi perbatasan), maka Anda telah menemukan penghalang.

Anda kemudian dapat melakukan tes ray-cast ini setiap kali algoritma saluran menentukan perlu memasukkan giliran untuk melihat apakah itu benar-benar, tapi saya pikir Anda harus terus melakukan tes itu di setiap node sampai Anda memasukkan putaran (pada titik mana Anda dapat kembali ke algoritma saluran sederhana). Itu akan menjadi mahal, membuat jalan lurus sekitar O (n ^ 2).

Mewakili navmesh

Anda bisa mewakili jala Anda sebagai array kelas poligon. Kelas poligon dapat sesederhana array simpul dan array referensi ke poligon yang berdekatan untuk setiap tepi jika ada satu. Tentu saja Anda mungkin bisa memikirkan cara untuk menyimpannya dengan lebih kompak. Karena sebuah vertex biasanya dibagi oleh beberapa poligon, itu normal untuk memiliki satu array besar simpul dan kemudian masing-masing indeks menyimpan poligon ke dalam array itu. Tergantung pada karakteristik navmesh Anda, Anda mungkin memiliki jumlah rata-rata tepi penghubung yang hanya 50% atau kurang dari jumlah tepi. Dalam hal ini Anda mungkin ingin menyimpan tautan ke poligon lain dan indeks tepi daripada menyimpan tautan untuk setiap sisi. Juga saya sarankan Anda menyimpan indeks poligon dalam array poligon navmesh daripada menggunakan referensi kelas.