Pathfinding

Jalur yang setara antara A dan B dalam lingkungan 2D

Pathfinding atau pathing adalah merencanakan, dengan aplikasi komputer, dari rute terpendek antara dua titik. Ini adalah varian yang lebih praktis dalam memecahkan labirin . Bidang penelitian ini sangat didasarkan pada algoritma Dijkstra untuk menemukan jalur terpendek pada graf berbobot .

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.

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|)$, atau waktu linier, di mana V adalah jumlah simpul, dan E adalah jumlah sisi di antara simpul.