Analisis pengaruh penggunaan Nilai Heuristik Terhadap Performansi Algoritma A* pada game Pathfinding

by Wina Witanti,Dewi Nurul Rahayu
( Kopertis Wilayah IV dpk Jurusan Informatika, Fakultas MIPA Universitas Jenderal Achmad Yani )

Date Published: 02 Dec 2013
Published In: Seminar Nasional Sistem Informasi Indonesia (SESINDO)
Volume: 2013
Publisher: Departemen Sistem Informasi, Institut Teknologi Sepuluh Nopember
Language: id-ID

Keywords: pathfinding,A*,heuristik

Abstract

Salah satu implementasi algoritma A* adalah sebuah game pathfinding. Game pathfinding merupakan game untuk mencari jalan terpendek dari titik awal menuju titik tujuan pada sebuah peta.Algoritma ini digunakan untuk menentukan jalan terpendek menuju tujuan. Performansi yang akan dihasilkan algoritma A* pada game pathfinding yaitu waktu pencarian, jumlah langkah dari titik awal menuju titik tujuan dan simpul yang diperiksa. Algoritma A* merupakan perbaikan dari metode Best-First Search (BFS) dengan menggunakan fungsi heuristik. Fungsi heuristik sering jugadisebut f(n) yang merupakan penentuan urutan titik yang akan dikunjungi terlebih dahulu.Pada penelitian ini, dilakukan analisis terhadap penggunaan nilai heuristik yang berbeda untuk menentukan performansi algoritma A* pada sebuah game pathfinding dengan ordo maksimal 31x39. Hasil pengujian aplikasi pada penelitian ini,adalah selain didapatkan jalan menuju tujuan pada sebuah map dan pelacakan cabangnya, juga memberikan hasil pencarian jalan optimal yang merupakan jalan terpendek, dengan maksimal penghalang sebanyak 1207 penghalang, maka akan didapatkan maksimal sebanyak 38 jalan.


© 2019 Open Access Journal of Information Systems (OAJIS) | created by : radityo p.w (http://about.me/radityopw) and rully a.h (eraha99 [at] gmail.com)