Perpustakaan judul masih dalam tahap pengembangan, admin siap menampung kritik dan saran
Penerapan Algoritma A*(A Star) Dalam Pencarian Jalan Terpendek Pada Game Pathfinding
Dewi Nurul Rahayu (2011) | Skripsi | Teknik Informatika
Bagikan
Ringkasan
Game pathfinding merupakan game untuk mencari jalan terpendek dari titik awal menuju titik tujuan pada sebuah map. Game pathfinding yang dibuat dengan AI (Artificial Intelligence) tersebut menerapkan algoritma A* (A Star). Algoritma ini digunakan untuk menentukan pilihan jalan terpendek menuju titik tujuan. Untuk mengetahui performansi dalam hal waktu pencarian, jumlah langkah dari titik awal menuju titik tujuan dan simpul yang diperiksa pada game pathfinding.
Penerapan algoritma A* dalam game pathfinding dibuat berdasarkan prosedur A* untuk mendapatkan langkah terbaik dari posisi titik awal. Algoritma A* merupakan perbaikan dari metode best-first search (BFS) dengan menggunakan fungsi heuristic. Fungsi heuristic sering juga disebut f(n) yang merupakan penentuan urutan titik yang akan dikunjungi terlebih dahulu. Fungsi heuristic ini sebenarnya menyimbolkan seberapa baik atau mungkin titik yang dikunjungi untuk mencapai titik tujuan. A* akan meminimumkan total biaya lintasan dan akan memberikan solusi yang terbaik dalam waktu yang optimal. Aplikasi ini dibuat menggunakan Borland Delphi 7.0.
Hasil pengujian aplikasi ini, selain didapatkan jalan menuju tujuan pada sebuah map dan pelacakan cabangnya, algoritma A* search memberikan hasil pencarian jalan optimal yang merupakan jalan terpendek. Pengujian alpha yang dihasilkan oleh A* search dalam jumlah langkah lebih kecil, tetapi simpul yang diperiksa lebih besar sehingga memerlukan waktu yang lama. Tingkat performansi yang dihasilkan A* tergantung pada posisi titik awal, titik tujuan, penghalang dan nilai heuristic.
Ringkasan Alternatif
Pathfinding game is a game to find the shortest path from the starting point towards the destination point on a map. Pathfinding game made with AI (Artificial Intelligence) implement a specific A* (A Star) algorithm. This algorithm is used to determine the choice of the shortest path to destination point. To determine the performance in terms of search time, the total of steps from a starting point toward the destination point and the node that is checked in pathfinding game.
Implementation of A* algorithm in pathfinding game are based on the A* procedure to obtain the best move from the position of starting point. A * Algorithm is a improvement of the best-first search (BFS) method using the heuristic function. Heuristic function is also called f (n) which is the determination of the sequence point to be visited first. Heuristic function is actually symbolize how well or maybe point visited to reach the destination point. A * will minimize the total cost of the track and will provide the best solutions in optimal time. This application was created using Borland Delphi 7.0.
The results of testing this application, other than get on a path to destination map and the tracking branches, algorithm A * search provides of search results path which is the optimal shortest path. Alpha test resulting by A* search in a total steps of smaller, but node of checked is bigger so take a long time. Performance level resulting A * depends on the position of starting point, destination point, the barrier and heuristic value.