Algoritma pencarian jalur apa yang ada? [Tutup]

Jawaban:

34

Jika Anda mencari untuk meneliti dan belajar tentang merintis jalan secara umum, saya pasti akan menyarankan belajar lebih dari satu algoritma. Anda akan ingin memahami konsep keseluruhan tetapi dapat menerapkannya pada apa pun yang sedang Anda kerjakan. Sebagian besar pengembang game yang perlu melakukan pathfinding serius pada akhirnya menulis algoritma kustom mereka sendiri, meskipun sangat didasarkan pada solusi yang diketahui, setiap game berbeda dan akan memiliki persyaratan yang berbeda.

Saya akan mulai dengan membaca beberapa metode yang lebih dikenal seperti pencarian A *, Algoritma, Kedalaman dan pencarian Breadth-First Dijkstra. Ada banyak informasi bagus di internet tentang masing-masing ini. ( http://en.wikipedia.org/wiki/Pathfinding )

Saat membacanya, catat apa kelebihan dan kekurangan masing-masing pendekatan, serta jenis data yang dapat dioperasikan algoritma. Bisakah itu diterapkan pada jalur 3 dimensi? Bisakah itu dimodifikasi untuk menjelaskan AI manusia kita yang ingin menghindari ranjau darat di peta?

Ketika datang ke pathfinding, A * cukup banyak tiket emas yang digunakan semua orang. Anda pasti harus tahu cara kerjanya. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Berikut ini adalah contoh yang baik dari A * yang berlaku untuk game RTS, yang perlu memperhitungkan entitas dengan ukuran berbeda: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

Semoga berhasil!

dcarrigg
sumber
2
+1 untuk sedikit tentang programmer yang harus belajar mengadaptasi solusi yang dikenal. Ini adalah sesuatu yang tidak dipahami oleh banyak calon pengembang game.
Insinyur
22

Algoritma pathfinding pada dasarnya adalah algoritma pemecahan masalah pencarian grafik.

http://en.wikipedia.org/wiki/Pathfinding#Algorithms

Paling dikenal adalah algoritma Djikstra: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

dan variannya algoritma pencarian A *: http://en.wikipedia.org/wiki/A*

Keyframe
sumber
2
Tautan terakhir rusak karena * tidak terlihat sebagai bagian dari tautan: en.wikipedia.org/wiki/A%2A
Hendrik Brummermann
fixx0r3d kedua tautan
tenpn
Algoritma pencarian grafik sederhana hanyalah dasar untuk merintis jalan.
martinkunev
13

Ini adalah sumber daya awal yang bagus yang melihat semua aspek penemuan jalur dalam pendekatan yang sangat mudah dicerna.

Catatan Amit tentang Pencarian Jalan

... Pathfinding mengatasi masalah menemukan jalur yang baik dari titik awal ke tujuan ― menghindari rintangan, menghindari musuh, dan meminimalkan biaya (bahan bakar, waktu, jarak, peralatan, uang, dll.). Gerakan membahas masalah mengambil jalan dan bergerak di sepanjang itu. Mungkin untuk menghabiskan upaya Anda hanya pada salah satu dari ini. Pada satu ekstrim, pathfinder canggih yang digabungkan dengan algoritma gerakan sepele ...

David Young
sumber
1
+1 untuk Amit. Saya belajar A * dari situs webnya 10+ tahun yang lalu.
tenpn
Ilustrasi yang bagus juga. Kualitas tinggi.
Monyet
5

Pathfinding adalah masalah yang cukup terpecahkan ... seperti yang disebutkan di hampir setiap jawaban di sini, beberapa variasi pada A * akan menjadi apa yang Anda gunakan.

Tantangan terbesar bagi saya adalah bagaimana Anda ingin mewakili jalan Anda . Menggunakan kisi, pathnode, navmeshes, kisi hierarkis, atau struktur kompleks lainnya, dll.

Saya tidak memiliki referensi spesifik dalam pikiran, tetapi menjelajahi AIGameDev akan memberi Anda semua jenis ide tentang apa yang ada di luar sana.

Ingatlah bahwa setiap perwakilan memiliki pro dan kontra; ini bukan tentang menemukan yang terbaik, ini tentang menemukan yang paling cocok untuk gameplay Anda .

Ipsquiggle
sumber
5

Ada daftar yang bagus di Wikipedia: Pathfinding

Sejauh yang saya tahu, A * dan D * keduanya cukup populer.

Craig Martek
sumber
+1 untuk menyebutkan dinamis A * lebih dikenal sebagai D *
David Young
4

Ada beberapa algoritma pencarian jalur di luar sana.

Salah satu yang paling populer mungkin adalah A * ( A-Star ). Ini adalah algoritma yang sangat berguna jika Anda memiliki fungsi heuristik yang dapat memberi Anda perkiraan biaya untuk mencapai tujuan (contohnya adalah jarak pandang ke target). A * sangat berguna untuk menemukan jalur terpendek dari awal hingga akhir.

Selain itu ada juga algoritma Dijkstra yang sangat berguna untuk menemukan item terdekat dari beberapa item. Misalnya. jika Anda ingin mengetahui mana power-up (atau serupa) yang paling dekat dengan karakter game Anda.

Ada beberapa algoritma lain di luar sana, tapi saya kira A * adalah yang paling populer. Mat Buckland memiliki bab yang sangat baik tentang jalan-Finding dalam Kitab Pemrograman Game AI dengan Contoh . Saya sangat menganjurkan Anda untuk mendapatkan salinannya. Kalau tidak, Anda akan menemukan banyak informasi online dengan mencari "Pencarian Bintang".

bummzack
sumber
Astaga. Saat saya mengetik ini, jawaban yang sama diberikan sekitar trilyun kali. Maaf :)
bummzack
Hanya perhatikan bahwa buku yang disebutkan juga ada di Google-Buku (walaupun tidak lengkap). Baca di sini: books.google.com/books?id=gDLpyWtFacYC
bummzack
2

Ini bukan primer, tapi kami membahas algoritma grafik secara ekstensif di kelas algoritme kami pada musim gugur lalu. Kami menggunakan buku ini,

Pengantar Algoritma, Edisi Ketiga oleh Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest dan Clifford Stein

http://mitpress.mit.edu/algorithms/

dan juga telah menyertai kuliah youtube dari kelas MIT.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Bab 17, 18, dan 19 berurusan dengan jalur terpendek.

bluedes
sumber
2

Lihat [Algoritma pencarian grafik dan pohon] di Wikipedia 1 . Mereka cukup banyak hanya variasi Pencarian Luar Angkasa Negara, Anda hanya perlu melalui semua ini dan menemukan di mana mereka berbeda.

Ada juga Collaborative Difusion , yang merupakan salah satu algoritma yang disebutkan sebelumnya yang dilakukan dengan cara yang menarik.

user712092
sumber
+1 Dokumen tentang Difusi Kolaborasi itu cukup menarik.
Insinyur
1
Saya pikir tautannya rusak. Mungkin ini yang benar: scalablegamedesign.cs.colorado.edu/gamewiki/index.php/…
pek
-2

Yang ini terlihat menarik:

http://www.codeproject.com/Articles/455 Saya ingin tahu apakah ini lebih baik daripada A *?

Tom
sumber
Selamat datang di situs ini. Apa yang Anda berikan dikenal sebagai jawaban tautan saja, yang tidak disarankan. Akan lebih baik untuk meringkas kualitas metode dalam jawaban Anda. Anda kemudian dapat berdebat apakah lebih baik daripada A * sederhana, daripada merenungkan isinya dalam teks.
Seth Battin
Saya melihat jawaban Anda kurang lebih setara untuk pertanyaan ini (yang sangat disayangkan). Saya tidak bermaksud memilih Anda, saya hanya melewati entri Anda di antrian ulasan posting pertama . Apapun, meningkatkan jawaban Anda selalu diterima.
Seth Battin
Saya hanya akan mengulangi apa yang dikatakan Seth. Meringkaskan.
Gray