Pathfinding

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu. Cari sumber: "Pathfinding" – berita · surat kabar · buku · cendekiawan · JSTOR

Pathfinding atau pathing adalah merencanakan, dengan aplikasi komputer, dari rute terpendek antara dua titik. Untuk memperkirakan jalur terpendek dalam situasi nyata, seperti peta, permainan di mana bisa ada banyak rintangan. Sehingga dapat mempertimbangkan grid 2D yang memiliki beberapa rintangan dan kita mulai dari sel sumber (diwarnai merah di bawah) menuju sel tujuan (diwarnai hijau di bawah). Ini adalah varian yang lebih praktis dalam memecahkan labirin . Bidang penelitian ini sangat didasarkan pada algoritma Dijkstra untuk menemukan jalur terpendek pada graf berbobot.^[1]

Pathfinding erat kaitannya dengan masalah jalur terpendek, dalam teori graf, yang mengkaji bagaimana mengidentifikasi jalur yang paling memenuhi beberapa kriteria (terpendek, termurah, tercepat, dll) antara dua titik dalam jaringan besar.

Algoritma

Pada intinya, metode pathfinding mencari graf dengan memulai dari satu simpul dan menjelajahi simpul yang berdekatan sampai simpul tujuan tercapai, umumnya dengan maksud untuk menemukan rute termurah. Meskipun metode pencarian grafik seperti pencarian luas pertama akan menemukan rute jika diberi waktu yang cukup, metode lain, yang "menjelajahi" grafik, akan cenderung mencapai tujuan lebih cepat. Analoginya adalah seseorang berjalan melintasi ruangan; daripada memeriksa setiap kemungkinan rute terlebih dahulu, orang tersebut umumnya akan berjalan ke arah tujuan dan hanya menyimpang dari jalur untuk menghindari halangan, dan membuat penyimpangan sekecil mungkin.^[2]

Dua masalah utama pencarian jalur adalah (1) menemukan jalur antara dua node dalam graf ; dan (2) masalah jalur terpendek —untuk menemukan jalur terpendek yang optimal . Algoritme dasar seperti pencarian pertama dan mendalam mengatasi masalah pertama dengan menghabiskan semua kemungkinan; mulai dari node yang diberikan, mereka mengulangi semua jalur potensial hingga mencapai node tujuan. Algoritma ini berjalan masuk O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} , atau waktu linier, di mana V adalah jumlah simpul, dan E adalah jumlah sisi di antara simpul.

Referensi