Algoritma pencarian jalur apa yang ada? [Tutup]

Saya ingin membaca tentang algoritma pencarian jalur. Apakah ada primer yang tersedia atau materi atau tutorial di Internet yang akan menjadi awal yang baik bagi saya?

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!

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*

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

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 .

Ada daftar yang bagus di Wikipedia: Pathfinding

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

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

Berikut tutorial tentang penggunaan Algoritma Dijkstra untuk merintis jalan.

Berikut adalah contoh yang baik dari A * yang digunakan dalam permainan dengan beberapa kode psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

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.

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.

Yang ini terlihat menarik:

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