Bagaimana cara kerja A * pathfinding?

67

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

Daniel X Moore
sumber
Berikut adalah artikel kecil dengan GIF animasi yang menunjukkan Algoritma Dijkstra bergerak.
Ólafur Waage
Am * A * Pages adalah pengantar yang bagus untuk saya. Anda dapat menemukan banyak visualisasi bagus yang mencari AStar Algorithm di youtube.
jdeseno
Saya bingung dengan sejumlah penjelasan tentang A * sebelum saya menemukan tutorial yang hebat ini: policyalmanac.org/games/aStarTutorial.htm saya lebih sering merujuk hal itu ketika saya menulis implementasi A * dalam ActionScript: newarteest.com/flash /astar.html
jhocking
4
-1 wikipedia memiliki artikel tentang A * dengan penjelasan, kode sumber, visualisasi dan ... . Beberapa jawaban di sini memiliki Tautan Eksternal dari halaman wiki itu.
user712092
4
Juga, karena ini adalah subjek yang cukup kompleks yang sangat menarik bagi pengembang game, saya pikir kami ingin informasinya di sini. Saya ingat Joel pernah mengatakan bahwa ia ingin StackOverflow menjadi hit teratas ketika orang bertanya tentang pemrograman Google.
jhocking

Jawaban:

63

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.

Dijkstra diilustrasikan, bagian 1

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).

Dijkstra diilustrasikan, bagian 2

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) }

Dijkstra diilustrasikan, bagian 3

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) }

Dijkstra diilustrasikan, bagian 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) }

Dijkstra diilustrasikan, bagian 5

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) }

Dijkstra diilustrasikan, bagian 6

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.

bummzack
sumber
2
Perlu dicatat bahwa heuristik tidak akan selalu mendorong pencarian untuk menemukan rute terbaik. Misalnya, jika heuristik Anda adalah jarak ke target, tetapi rute yang layak berada di sekitar tepi peta - pencarian dalam hal ini akan mencari seluruh peta sebelum mendapatkan rute yang benar. Tentunya, Anda pasti berpikir, ada sesuatu yang tidak saya dapatkan? Ini tidak berfungsi! - hal yang perlu dipahami adalah bahwa tujuan heuristik adalah untuk mengurangi pencarian dalam PALING kasus, dan tugas Anda adalah menemukan yang terbaik dari semua solusi yang tersedia untuk kebutuhan spesifik Anda.
SirYakalot
2
@ AsherEinhorn Masih akan lebih baik (atau dalam kasus terburuk sama) dari pencarian yang tidak diinformasikan seperti Djikstra.
bummzack
ya ya, Anda memang benar. Mungkin saya tidak jelas, contoh yang saya bicarakan dalam komentar di atas adalah senario teoretis 'kasus terburuk' untuk A * dengan heuristik TETAPI itu yang akan dilakukan Dijkstra SETIAP kali. Sebagian besar waktu A * akan lebih baik bahkan dengan heuristik yang sangat sederhana. Maksud saya adalah heuristik dapat membingungkan pada awalnya karena 'jarak ke sasaran' tidak selalu masuk akal untuk setiap skenario - intinya adalah bahwa heuristik untuk sebagian besar.
SirYakalot
Juga, lihat ini: qiao.github.io/PathFinding.js/visual
David Chouinard
Jawaban ini bisa menggunakan penyebutan apa yang membuat heuristik dapat diterima, dalam arti menjamin bahwa A * akan menemukan jalur terpendek. (Secara singkat: Agar dapat diterima, heuristik tidak boleh melebih-lebihkan jarak sebenarnya ke target. Heuristik yang tidak dapat diterima kadang-kadang berguna, tetapi mereka dapat menyebabkan A * mengembalikan jalur suboptimal.)
Ilmari Karonen
26

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.

Sean James
sumber
1
Penjelasan dengan grafik, node, tepi, akan lebih jelas daripada hanya tentang ubin. Tidak membantu memahami bahwa apa pun struktur ruang permainan Anda, Anda dapat menerapkan algoritma yang sama sejauh Anda memiliki informasi posisi yang saling terkait di ruang ini.
Klaim
Saya berpendapat bahwa itu akan menjadi kurang jelas sebenarnya, karena lebih sulit untuk divisualisasikan. Tapi ya penjelasan ini harus menyebutkan bahwa kotak ubin tidak diperlukan; sebenarnya, saya akan mengedit titik itu di.
jhocking
14

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
David McGraw
sumber
4
Contoh Python Anda ada di C ++.
Roti Aluminium
@finish - Senang melihat seseorang menangkap itu! Kegiatan sehari-hari berputar di sekitar Python hari ini. Terima kasih!
David McGraw
3
Contoh C ++ Anda mungkin juga C.
deceleratedcaviar
4
Contohnya mungkin juga di assembler untuk semua struktur yang dimilikinya. Bahkan bukan A *, bagaimana ini jawaban yang diterima?
4
Maaf itu tidak normal, itu adalah salah satu upaya pengkodean pertama saya kembali ketika saya mulai. Silakan berkontribusi sesuatu untuk komentar / edit posting untuk membagikan solusi Anda sendiri.
David McGraw
6

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.

VirtuosiMedia
sumber
4

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.

Karantza
sumber
1
Ini sebenarnya bukan deskripsi yang akurat tentang perbedaan antara A * dan Dijkstra. Memang benar bahwa Dijkstra memecahkan sumber tunggal ke semua poin, tetapi ketika digunakan dalam permainan biasanya terputus segera setelah Anda menemukan jalan ke tujuan. Perbedaan nyata antara keduanya adalah bahwa A * diinformasikan oleh heuristik dan dapat menemukan tujuan itu dengan cabang yang lebih sedikit.
Untuk menambah penjelasan Joe: A * akan menemukan jalur ke semua poin juga, jika Anda membiarkannya, tetapi dalam permainan kami biasanya ingin berhenti lebih awal. A * berfungsi seperti algoritma Dijsktra, kecuali heuristik yang membantu menyusun ulang node untuk menjelajahi jalur yang paling menjanjikan terlebih dahulu. Dengan begitu Anda biasanya dapat berhenti lebih awal daripada dengan algoritma Dijkstra. Misalnya, jika Anda ingin menemukan jalur dari pusat peta ke sisi timur, algoritme Dijkstra akan menjelajah secara sama di semua arah, dan berhenti ketika menemukan sisi timur. A * akan menghabiskan lebih banyak waktu ke timur daripada barat, dan lebih cepat sampai di sana.
amitp
3

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.

pembuat kode
sumber
3

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.
Kylotan
sumber