A * navigasi menemukan jalur mesh

15

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.

angrydust
sumber
Saya tidak yakin tetapi tautan ini dapat membantu: gamedev.stackexchange.com/questions/1327/… gamedev.stackexchange.com/questions/8087/… juga ada pertanyaan lain tentang pencarian jalur yang tidak dapat saya temukan saat ini , yang mendapat hadiah dan memiliki jawaban yang sangat bagus.
Ali1S232
Ya, di tautan kedua Anda dapat melihat perhatian utama saya, algoritma A * akan memberikan jalur di bagian bawah sebagai yang terpendek menggunakan titik tengah tepi tetapi jalur di bagian atas hambatan sebenarnya yang terpendek. Saya ingin tahu bagaimana saya bisa mendapatkan A * untuk memberi saya jalan di bagian atas yang kemudian akan saya luruskan (dengan algoritma corong misalnya) untuk mendapatkan jalur terpendek yang benar, di mana seolah-olah itu memberi saya jalan di bagian bawah kemudian bahkan jika saya meluruskannya masih mengambil jalan memutar.
angrydust
Sebenarnya, saya baru saja membaca artikel di gamedev.stackexchange.com/questions/8087/… dan sepertinya berhasil dengan menemukan rute dengan A *, kemudian menghitung biaya sebenarnya dengan algoritma corong yang dimodifikasi dan kemudian menemukan rute lain dan menghitungnya benar biaya lagi dan melihat apakah itu lebih pendek daripada yang lain. Mengulangi sampai tahu itu menemukan rute terpendek. Ini memang menyelesaikan masalah saya, namun, ini sepertinya akan sangat lambat karena Anda mengulangi baik pelurusan maupun pencarian jalan, yang akan sangat mahal.
angrydust
Penyimpanan poligon: hanya simpan poligon yang terlihat - atau kaitkan tag dengan setiap poligon (ingat setiap poligon harus berupa daftar simpul lingkaran); sama dengan node Anda dapat menyimpan ID poligon yang berasal dari - tetapi saya tidak perlu memberitahu Anda ini: ini penyimpanan data dasar. Akhirnya mengapa Anda peduli tentang jalan terpendek yang benar? Gim Anda dapat menjalankan anjing dengan lambat atau Anda dapat memiliki jalur yang sedikit salah: pilih satu. Memperoleh jalur terpendek yang sebenarnya MEMBUTUHKAN pencarian luas-pertama penuh (setidaknya lebih dari satu simpul grafik).
Jonathan Dickinson
@JonathanDickinson Aku tahu aku tidak perlu jalan yang akan 100% akurat ke pixel terakhir, dan saya tahu saya bisa menggunakan A * untuk menghasilkan jalur yang akan paling p diterima. Masalahnya akan menjadi kendala yang sangat jelas, seperti pada pertanyaan saya sebelumnya tentang stack overflow atau di gamedev.stackexchange.com/questions/8087/… terlalu banyak. Saya tidak bisa membiarkan AI saya berjalan seperti itu di sekitar rintangan!
angrydust

Jawaban:

14

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.

U62
sumber
Saya baru saja membaca singkat tentang ini, tapi saya mengerti Anda tidak boleh menggunakan kuadrat jarak (atau tidak akar kuadrat itu) untuk A *: theory.stanford.edu/~amitp/GameProgramming/…
angrydust
Saya tidak benar-benar khawatir tentang bagaimana untuk benar-benar pergi tentang jalan meluruskan atm, apa yang saya khawatirkan adalah apa yang Anda katakan: "Anda harus mengamati bahwa itu hanya akan meluruskan jalan 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 juga. "
angrydust
Saya ingin memiliki nav mesh di mana A * akan selalu menemukan jalan yang pernah diluruskan adalah yang terpendek, terlepas dari biaya perjalanan melalui simpul / titik tengah. Saya menghargai bahwa ini dapat dilakukan dengan grafik visibilitas tetapi saya ingin menggunakan navmesh karena memiliki banyak manfaat lain dan karena kompleksitas grafik visibilitas dapat tumbuh sangat cepat: theory.stanford.edu/~amitp/GameProgramming/…
angrydust
@ theguywholikeslinux Anda dapat menggunakan jarak Euclidean sqrt(x*x + y*y)- tetapi bukan yang lebih murah per node x*x + y*y.
Jonathan Dickinson
@ JonathanDickinson, saya tahu, itu maksud saya.
angrydust