Bagaimana cara kerja A * pathfinding?

Saya ingin memahami pada tingkat dasar cara di mana A * pathfinding bekerja. Setiap implementasi kode atau psuedo-code serta visualisasi akan sangat membantu.

Penolakan

Ada banyak contoh kode dan penjelasan A * yang dapat ditemukan online. Pertanyaan ini juga telah menerima banyak jawaban hebat dengan banyak tautan bermanfaat. Dalam jawaban saya, saya akan mencoba memberikan contoh ilustrasi algoritma, yang mungkin lebih mudah dipahami daripada kode atau deskripsi.

Algoritma Dijkstra

Untuk memahami A *, saya sarankan Anda terlebih dahulu melihat algoritma Dijkstra . Biarkan saya membimbing Anda melalui langkah-langkah algoritma Dijkstra akan melakukan pencarian.

Simpul awal kami adalah Adan kami ingin menemukan jalur terpendek ke F. Setiap tepi grafik memiliki biaya pergerakan yang terkait dengannya (dilambangkan sebagai digit hitam di sebelah tepi). Tujuan kami adalah untuk mengevaluasi biaya perjalanan minimal untuk setiap simpul (atau simpul) dari grafik sampai kami mencapai simpul tujuan kami.

Ini adalah titik awal kita. Kami memiliki daftar node untuk diperiksa, daftar ini saat ini adalah:

{ A(0) }

Amemiliki biaya 0, semua node lainnya diatur hingga tak terbatas (dalam implementasi yang khas, ini akan menjadi sesuatu seperti int.MAX_VALUEatau serupa).

Kami mengambil node dengan biaya terendah dari daftar node kami (karena daftar kami hanya berisi A, ini adalah kandidat kami) dan mengunjungi semua tetangganya. Kami menetapkan biaya masing-masing tetangga ke:

Cost_of_Edge + Cost_of_previous_Node

dan melacak node sebelumnya (ditampilkan sebagai huruf merah muda kecil di bawah node). Adapat ditandai sebagai dipecahkan (merah) sekarang, sehingga kami tidak mengunjunginya lagi. Daftar kandidat kami sekarang terlihat seperti ini:

{ B(2), D(3), C(4) }

Sekali lagi, kami mengambil simpul dengan biaya terendah dari daftar kami ( B) dan mengevaluasi tetangganya. Jalur ke Dlebih mahal daripada biaya saat ini D, oleh karena itu jalur ini dapat dibuang. Eakan ditambahkan ke daftar kandidat kami, yang sekarang terlihat seperti ini:

{ D(3), C(4), E(4) }

Node berikutnya untuk memeriksa sekarang D. Sambungan ke Cdapat dibuang, karena jalurnya tidak lebih pendek dari biaya yang ada. Kami memang menemukan jalur yang lebih pendek E, oleh karena itu biaya untuk Edan simpul sebelumnya akan diperbarui. Daftar kami sekarang terlihat seperti ini:

{ E(3), C(4) }

Jadi seperti yang kami lakukan sebelumnya, kami memeriksa node dengan biaya terendah dari daftar kami, yang sekarang E. Ehanya memiliki satu tetangga yang tidak terpecahkan, yang juga merupakan simpul target. Biaya untuk mencapai simpul target diatur ke 10dan simpul sebelumnya ke E. Daftar kandidat kami sekarang terlihat seperti ini:

{ C(4), F(10) }

Selanjutnya kita periksa C. Kami dapat memperbarui biaya dan simpul sebelumnya untuk F. Karena daftar kami sekarang memiliki Fsimpul dengan biaya terendah, kami selesai. Path kami dapat dibangun dengan menelusuri kembali node terpendek sebelumnya.

Algoritma A *

Jadi Anda mungkin bertanya-tanya mengapa saya menjelaskan Dijkstra kepada Anda alih-alih algoritma A * ? Nah, satu-satunya perbedaan adalah bagaimana Anda menimbang (atau mengurutkan) kandidat Anda. Dengan Dijkstra:

Cost_of_Edge + Cost_of_previous_Node

Dengan A * itu:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Di mana Estimated_Cost_to_reach_Target_frombiasa disebut fungsi Heuristic . Ini adalah fungsi yang akan mencoba memperkirakan biaya untuk mencapai target-node. Fungsi heuristik yang baik akan mencapai bahwa lebih sedikit node harus dikunjungi untuk menemukan target. Sementara algoritma Dijkstra akan diperluas ke semua sisi, A * akan (berkat heuristik) mencari ke arah target.

Halaman Amit tentang heuristik memiliki tinjauan yang baik atas heuristik umum.

Temuan * path adalah pencarian tipe pertama-terbaik yang menggunakan heuristik tambahan.

Hal pertama yang perlu Anda lakukan adalah membagi area pencarian Anda. Untuk penjelasan ini, peta adalah kotak petak kotak, karena sebagian besar permainan 2D menggunakan kotak petak dan karena itu mudah divisualisasikan. Perhatikan bahwa area pencarian dapat dipecah sesuai keinginan Anda: kotak hex mungkin, atau bahkan bentuk sewenang-wenang seperti Risiko. Berbagai posisi peta disebut sebagai "simpul" dan algoritme ini akan bekerja kapan pun Anda memiliki banyak simpul untuk dilintasi dan memiliki koneksi yang ditentukan di antara simpul tersebut.

Lagi pula, mulai dari ubin awal yang diberikan:

• 8 ubin di sekitar ubin awal "dinilai" berdasarkan a) biaya perpindahan dari ubin saat ini ke ubin berikutnya (umumnya 1 untuk gerakan horizontal atau vertikal, sqrt (2) untuk gerakan diagonal).

• Setiap ubin kemudian diberi skor "heuristik" tambahan - perkiraan nilai relatif pindah ke setiap ubin. Heuristik yang berbeda digunakan, yang paling sederhana adalah jarak garis lurus antara pusat ubin yang diberikan dan ubin ujung.

• Ubin saat ini kemudian "ditutup", dan agen bergerak ke ubin tetangga yang terbuka, memiliki skor gerakan terendah, dan skor heuristik terendah.

• Proses ini diulangi sampai node tujuan tercapai, atau tidak ada lagi node terbuka (artinya agen diblokir).

Untuk diagram yang menggambarkan langkah-langkah ini, lihat tutorial pemula yang baik ini .

Ada beberapa perbaikan yang dapat dilakukan, terutama dalam meningkatkan heuristik:

• Memperhatikan perbedaan medan, kekasaran, kecuraman, dll.

• Kadang-kadang juga berguna untuk melakukan "sapuan" di grid untuk memblokir area peta yang bukan jalur yang efisien: bentuk U yang menghadap agen, misalnya. Tanpa tes pembersihan, agen pertama-tama akan memasuki U, berbalik, lalu pergi dan pergi di sekitar tepi U. Agen cerdas "nyata" akan mencatat perangkap berbentuk U dan hanya menghindarinya. Menyapu dapat membantu mensimulasikan ini.

Ini jauh dari yang terbaik, tapi ini implementasi yang saya lakukan dari A * di C ++ beberapa tahun yang lalu.

Mungkin lebih baik saya mengarahkan Anda ke sumber daya daripada mencoba menjelaskan keseluruhan algoritma. Juga, saat Anda membaca artikel wiki, mainkan dengan demo dan lihat apakah Anda dapat memvisualisasikan cara kerjanya. Tinggalkan komentar jika Anda memiliki pertanyaan tertentu.

1. A * di Wikipedia
2. A * demonstrasi Java

Anda mungkin menemukan artikel ActiveTut tentang Path Finding berguna. Ini membahas Algoritma A * dan Dijkstra dan perbedaan di antara mereka. Ini diarahkan untuk pengembang Flash, tetapi harus memberikan wawasan yang baik tentang teori bahkan jika Anda tidak menggunakan Flash.

Satu hal yang penting untuk divisualisasikan ketika berhadapan dengan Algoritma A * dan Dijkstra adalah bahwa A * diarahkan; ia mencoba menemukan jalur terpendek ke titik tertentu dengan "menebak" ke arah mana harus mencari. Algoritma Dijkstra menemukan jalur terpendek ke / setiap / titik.

Jadi seperti pernyataan pertama, A * pada dasarnya adalah algoritma eksplorasi grafik. Biasanya dalam game kami menggunakan ubin atau geometri dunia lain sebagai grafik, tetapi Anda dapat menggunakan A * untuk hal-hal lain. Dua algoritma-ur untuk grafik traversal adalah pencarian mendalam-pertama dan luas-pertama-pencarian. Di DFS Anda selalu mengeksplorasi sepenuhnya cabang Anda saat ini sebelum melihat saudara kandung dari simpul saat ini, dan di BFS Anda selalu melihat saudara kandung terlebih dahulu dan kemudian anak-anak. A * mencoba untuk menemukan jalan tengah di antara ini di mana Anda menjelajahi cabang (jadi lebih seperti DFS) ketika Anda semakin dekat dengan tujuan yang diinginkan tetapi kadang-kadang berhenti dan coba saudara kandung jika mungkin memiliki hasil yang lebih baik di cabang. Matematika sebenarnya adalah bahwa Anda menyimpan daftar node yang mungkin untuk dijelajahi berikutnya di mana masing-masing memiliki "kebaikan" skor menunjukkan seberapa dekat (dalam beberapa arti abstrak) itu dengan tujuan, skor yang lebih rendah lebih baik (0 berarti Anda menemukan tujuan). Anda memilih mana yang akan digunakan selanjutnya dengan menemukan skor minimum ditambah jumlah node yang jauh dari root (yang umumnya merupakan konfigurasi saat ini, atau posisi saat ini dalam pencarian jalan). Setiap kali Anda menjelajahi sebuah simpul, Anda menambahkan semua anak-anaknya ke daftar ini dan kemudian memilih yang terbaik.

Pada level abstrak, A * berfungsi seperti ini:

• Anda memperlakukan dunia sebagai sejumlah node yang terhubung, misalnya. kisi, atau grafik.
• Untuk menemukan jalur melintasi dunia itu, Anda perlu menemukan daftar 'simpul' yang berdekatan dalam ruang itu, yang mengarah dari awal hingga tujuan.
• Pendekatan naif adalah sebagai berikut: hitung setiap permutasi yang mungkin dari node yang dimulai dengan simpul awal dan selesai pada simpul akhir, dan pilih yang termurah. Ini jelas akan membutuhkan selamanya, kecuali ruang terkecil.
• Oleh karena itu pendekatan alternatif mencoba menggunakan beberapa pengetahuan tentang dunia untuk menebak permutasi mana yang perlu dipertimbangkan terlebih dahulu, dan untuk mengetahui apakah solusi yang diberikan dapat dikalahkan. Perkiraan ini disebut heuristik.
• A * membutuhkan heuristik yang dapat diterima . Ini berarti tidak pernah melebih-lebihkan.
  • Heuristik yang baik untuk masalah merintis jalan adalah jarak Euclidean karena kita tahu bahwa rute terpendek antara 2 titik adalah garis lurus. Ini tidak pernah melebih-lebihkan jarak dalam simulasi dunia nyata.
• A * dimulai dengan simpul awal, dan mencoba permutasi berturut-turut dari simpul itu ditambah setiap tetangga, dan tetangga tetangganya, dll., Menggunakan heuristik untuk memutuskan permutasi mana yang akan dicoba berikutnya.
• Pada setiap langkah, A * melihat jalur yang paling menjanjikan sejauh ini dan memilih simpul tetangga berikutnya yang tampaknya 'terbaik', berdasarkan jarak yang ditempuh sejauh ini, dan perkiraan heuristik tentang seberapa jauh akan tersisa untuk pergi dari itu simpul
• Karena heuristik tidak pernah melebih-lebihkan, dan jarak yang ditempuh sejauh ini diketahui akurat, itu akan selalu memilih langkah selanjutnya yang paling optimis.
  • Jika langkah berikutnya mencapai tujuan, Anda tahu itu telah menemukan rute terpendek dari posisi terakhir, karena ini adalah tebakan paling optimis dari yang masih tersisa.
  • Jika tidak mencapai tujuan, dibiarkan sebagai titik yang memungkinkan untuk dijelajahi dari nanti. Algoritme sekarang memilih kemungkinan yang paling menjanjikan berikutnya, sehingga logika di atas masih berlaku.