Path Finding

Path Finding

Path Finding  & Waypoint
Path Finding merupakan salah satu materi yang sangat penting didalam Artificial Intelligence. Path Finding biasanya digunakan untuk menyelesaikan masalah pada sebuah graph. Dalam matematika graph merupakan himpunan titik-titik atau biasa disebut dengan node yang tehubung oleh edge. Edge yang menghubungkan setiap node merupakan suatu vektor yang memiliki arah dan besaran tertentu. Untuk dapat menemukan jalan dari Node Awal menuju Node Tujuan, dilakukan penelusuran terhadap graph tersebut. Penelusuran biasanya dilakukan dengan mengikuti arah edge yang menghubungkan antar node.
Pathfinding adalah salah satu masalah paling dasar dari kece

rdasan buatan (Artificial Intelligence / AI) yang ada pada game. Pathfinding yang buruk dapat membuat karakter yang ada pada game terlihat brainless (bodoh). Penanganan masalah pathfinding secara efektif dapat membuat game lebih menyenangkan dan memberikan pengalaman bermain yang mendalam bagi player (David M. Broug dan Glenn Seemann, 2004).
Untuk mencari jalan dari titik awal ke titik tujuan, kita perlu tahu tentang peta(map) yang ada seperti posisi jalan yang bisa dilalui dan posisi hambatan. Untuk itu peta akan direpresentasi ke dalam bentuk yang lain, salah satunya dalam bentuk grid yang disebut dengan grid graph. Selain grid graph, ada beberapa bentuk representasi peta diantaranya waypoint graph, dan navigation mesh. Waypoint graph merepresentasi peta dengan bentuk penempatan node secara bebas dengan tiap node saling terhubung satu sama lain. Sedangkan navigation mesh merepresentasi peta dalam beberapa bentuk segitiga mesh. Mesh tersebut menggambarkan area yang bisa dilalui (Aron Granborg, 2013). Grid graph menghasilkan node dalam pola grid lebar*panjang.
Grid graph adalah graph yang paling mudah. Selain itu, grid graph berkerja sangat baik terutama saat ada perubahan graph yang dibutuhkan secara runtime seperti pada game RTS dan Tower Defence (Aron Granborg, 2013). Grid graph banyak digunakan pada beberapa game. Bahkan game genre RTS seperti Age of Empires dan Warcraft III menggunakan grid graph (Steve Rabin, 2010).

TAKTIK DAN STRATEGI AI
Implementasi metode pathfinding banyak digunakan dalam video game. Metode pathfinding ini banyak digunakan pada game genre Real Time Strategy (RTS) dan Tower Defence (TD). Selain game genre RTS dan TD, game dengan genre action puzzle juga ada yang mengimplementasikan metode pathfinding.
Real Time Strategy (RTS)
Pada game jenis ini, kita dapat mengendalikan pasukan secara langsung, dari mencari sumber daya, hingga menghancurkan musuh. Semua pertempuran ini dapat kita saksikan secara langsung.

Turn Based Strategy (TBS)
Game Jenis ini adalah game yang di jalankan secara bergiliran, saat kita mengambil keputusan dan menggerakan pasukan, saat itu pihak lawan harus menunggu, begitu pula sebaliknya, layaknya catur.


Algoritma A*
Untuk dapat menyelesaikan permasalahan pencarian rute terpendek, dapat digunakan suatu algoritma A* (A Star). Algoritma A* merupakan salah satu algoritma path finding yang umum digunakan. Dalam menemukan rute yang disebutkan diatas dapat menggunakan perhitungan algoritma A* dan metode Heuristik. Hasil yang didapat yaitu jarak terpendek yang bisa dilalui.
Pada tahun 1967 Bertram Raphael membuat perbaikan-perbaikan dramatis atas algoritma ini, tapi gagal menunjukkan keoptimasiannya. Ia menyebut algoritma ini A2. Kemudian pada tahun 1968 Peter E. Hart memperkenalkan sebuah argumen yang membuktikan A2 optimal ketika menggunakan heuristik konsisten hanya dengan perubahan kecil. Pembuktiannya atas algoritma tersebut juga termasuk bagian yang menunjukkan bahwa algoritma A2 yang baru adalah algoritma terbaik. Maka dari itu, ia menamai algoritma baru ini dalam sintaksis Kleene Star untuk menjadi algoritma yang berawal dari A dan memasukkan semua nomor-nomor yang mungkin dari A*. Dalam sains komputer, A* (dibaca “A star”) adalah algoritma komputer yang digunakan secara luas dalam mencari jalur (pathfinding) dan grafik melintang (graph traversal), proses plotting sebuah jalur melintang secara efisian antara titik-titik, disebut node (Suyanto, 2014).

Algoritma A Star atau A* adalah salah satu algoritma pencarian yang menganalisa input, mengevaluasi sejumlah jalur yang mungkin dilewati dan menghasilkan solusi. Algoritma A* adalah algoritma komputer yang digunakan secara luas dalam graph traversal dan penemuan jalur serta proses perencanaan jalur yang bisa dilewati secara efisien di sekitar titik-titik yang disebut node (Reddy, 2013).
Algoritma A* memberikan solusi efektif untuk masalah pathfinding. Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Algoritma A* memberikan hasil keluaran yang complete dan optimal (Suyanto, 2007).
Karakteristik yang menjelaskan algoritma A* adalah pengembangan dari “daftar tertutup” untuk merekam area yang dievaluasi. Daftar tertutup ini adalah sebuah daftar untuk merekam area berdekatan yang sudah dievaluasi, kemudian melakukan perhitungan jarak yang dikunjungi dari “titik awal” dengan jarak diperkirakan ke “titik tujuan” (Reddy, 2013).

Pada tahun 1964 Nils Nilsson menemukan heuristik berdasarkan pendekatan untuk menambah kecepatan pada Algoritma Dijkstra. Algoritma ini disebut dengan A1



Pada gambar diatas, suatu graph dengan Node Awal 𝑆𝑁 dan Node Tujuan 𝐺𝑁 terhubung dengan node - node lain oleh edge yang memiliki besaran yang berbeda. Jika ditelusuri, terdapat banyak kombinasi rute yang dapat dilalui untuk menuju node tujuan. Bisa dikatakan dari graph tersebut, setiap node akan memberikan solusi arah menuju node tujuan. A* merupakan bentuk yang paling dari Best First Search (BFS). A* mengevaluasi node dengan menggabungkan g(n), yaitu cost untuk mencapai node, dan h(n), yaitu cost yang diperlukan dari node untuk mencapai tujuan, dalam notasi matematika dituliskan sebagai: f(n)=g(n)+h(n) (1)
Dimana:
f(n) = Biaya evaluasi
g(n) = Biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n
h(n) = Estimasi biaya untuk sampai pada suatu tujuan mulai dari n

Algoritma Djikstra
Djikstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian  lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek.
Algoritma Dijkstra merupakan algoritma yang dipakai dalam penentuan lintasan terpendek dari suatu titik tertentu ke setiap titik lain pada suatu graf. Strategi yang digunakan pada algoritma Dijkstra yaitu dengan membentuk suatu pohon Dijkstra pada setiap pengulangan dengan menggunakan fungsi
Dijkstra-nextEdge. Pohon Dijkstra yang dibentuk setelah pengulangan terakhir merupakan pohon
pembangun dari graf awal.

Untuk bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan, yaitu :
1.     Beberapa Titik/simpul/daerah, titik/simpul/daerah yang bisa dijangkau secara langsung, dan juga jarak antara mereka.
2.     Titik/simpul/daerah awal.
3.     Titik/simpul/daerah tujuan.