Walisongo Journal of Information Technology, Vol. 3 No. 1 (2021): 43-48 DOI : http://dx.doi.org/10.21580/wjit.2021.3.1.7042 Copyright © 2021 WJIT: Walisongo Journal of Information Technology
| 43
Implementasi Metode Path Finding dengan Penerapan Algoritma A-Star untuk Mencari Jalur Terpendek p ada Game “Jumrah Launch Story”
Ghani Mutaqin 1 , Juniardi Nur Fadilah 2 , Fresy Nugroho 3 1,2,3 Teknik Informatika, Fakultas Sains dan Teknologi, Universitas Islam Negeri Maulana Malik Ibrahim Malang
18650009@student.uin-malang.ac.id 1 , juniardi.nur@gmail.com 2 , fresysss@gmail.com 3
Abstract
Technology  is  increasingly  developing  from  time  to  time  as  it  is  today, especially the development of game technology. Develop in-game technology so that the  game  can  be  like  in  the  real  world.  To  make  a  realistic  game,  of  course, implement  artificial  intelligence  or  artificial  intelligence  in  the  behavior  of  NPCs (non-player characters) / intelligent agents in games. One of the common behaviors we know about smart agents in games is pathfinding . Pathfinding is one of the basic concepts  of  algorithms  used  to  move  characters  in  the  game.  By  using  the pathfinding method,  intelligent  agents  can  move  intelligently  like  the  real  world. This is what makes the game even more interesting. However, the problem is how the  intelligent  agent  in  the  game  can  find  the  shortest  path  of  the  route  to  be traversed  efficiently.  In  this  study,  we  applied  the  A-Star  algorithm  through  the pathfinding method of NPC behavior in games. As the results of this research, we made a game entitled " Jumrah Launch Story ".
Key words: Game, pathfinding, A-Star, Intelligence
Abstrak
Teknologi  semakin  berkembang  dari  waktu  ke  waktu  seperti  saat  ini, khususnya perkembangan teknologi game. Pengembangkan teknologi dalam game agar game bisa menjadi seperti layaknya di dunia nyata. Untuk membuat game yang realistis  tentunya  mengimplementasikan artificial  intelligence atau  kecerdasan buatan pada perilaku NPC ( non player character ) / agen cerdas dalam game. Salah satu perilaku yang umum kita ketahui pada agen cerdas dalam game adalah path finding. Path finding merupakan salah satu konsep dasar algoritma yang digunakan untuk  menggerakkan  karakter  dalam  game.  Dengan  menggunakan  metode path finding , agen cerdas bisa bergerak dengan cerdas layaknya dunia nyata. Hal ini lah yang  membuat  game  bisa  menjadi  menjadi  lebih  menarik.  Namun  yang  menjadi masalah adalah bagaimana agen cerdas dalam game bisa mencari jalur terpendek dari  rute  yang  akan  dilalui  yang  efisien.  Pada  penelitian  ini  kami  menerapkan algoritma A-Star melalui  metode  path  finding  pada  perilaku  NPC  didalam  game. Hasil dari penelitian ini kami membuat game yang berjudul " Jumrah Launch Story ".
Key words: Game, path finding, A-Star, NPC, Kecerdasan
http://journal.walisongo.ac.id/index.php/jit/index WJIT : Walisongo Journal of Information Technology
Ghani Mutaqin 1 , Juniardi Nur Fadilah 2 , Fresy Nugroho 3

## 1. PENDAHULUAN
Teknologi  semakin  berkembang dari  waktu  ke  waktu,  khususnya teknologi Game . Industri game adalah salah  satu  usaha  pengembangan industry  kreatif.  Kemajuan  grafis dalam perkembangan game membuat lingkungan  game  dan  jalannya permainan tampak lebih realistis(Theosaksomo, 2017). Namun untuk membuat sebuah game tampak nyata, grafis saja tidak ukup jika tidak didukung dengan penerapan perilaku cerdas  pada  NPC  ( Non  Player Character) (Harsadi & Siswanti, 2019) . Untuk  memberikan  kecerdasan  pada game diperlukan penerapan Artificiall Intelligence.
Salah  satu  metode  yang  banyak kita  ketahui  dalam  kecerdasan  game adalah path finding. Path finding ialah konsep  yang  digunakan  untuk menggerakkan karakter dalam permainan.  Metode  ini  biasanya digunakan  sebagai  initi  pergerakan AI(Rahadiansyah et al., 2016). Dengan algoritma  ini,  karakter  dalam  game dapat  bergerak  seperti  perilaku manusia  di  dunia  nyata.  AI  ialah kecerdasan  buatan  yang  didesain kedalam suatu sistem untuk mensimulasikan  kecerdasan  manusia dan  menyelesaikan  permasalahan dengan menggunakan computer seperti  di  dunia  nyata(Wijaya  et  al.,
2017). Banyak hal yang dapat diamati dari perilaku kecerdasan dalam game. Agar  NPC  sebagai  pelaku  kecerdasan dapat  bergerak  senatural  mungkin. Pada  game  ini  penulis  menggunakan algoritma A-Star sebagai  algoritma path  finding yang  akan  diterapkan
pada kecerdasan karakter pada game yang berjudul “ Jumrah Launch Story ”.

## 2. METODE
Metode dari penelitian ini adalah menggunakan algoritma A-Star. Untuk menguji  ketepatan  algoritma  ini penulis  menggunakan  model  dasar agar  metode  yang  digunakan  dapat berjalan  maksimal.  Metodologi  ini digunakan  dengan  menitik-beratkan pada  aspek  desain,  fungsi,  dan User Interface (Prasetyo  et  al.,  2017) .
Sistem ini digunakan untuk mengembangkan  secara  sederhana dari  sistem  yang  akan  diteliti  untuk evaluasi  dan  perbaikan(Verma  et  al., 2015). Tahapan  yang  akan  dilakukan dalam  penelitian  ini  terdiri  dari analisa, studi literatur, dan perancangan aplikasi game. Analisa  digunakan  untuk  melihat apa  saja  yang  dibutuhkan  dalam proses  pembuatan game ini.  Analisa difokuskan  pada  NPC  di  dalam permainan. Parameter sangat dibutuhkan dalam sebuah permainan untuk  menyelesaikan  sebuah  misi. Berdasarkan analisa, parameter yang digunakan disini ialah nyawa, akurasi, ketinggian,  dan  skor.  NPC  berfungsi menyerang pemain di dalam game(Kholil,  2017).  Bos  sebagai  NPC menggunakan  AI  sehingga  dapat menemukan pemain secara tepat dan efektif.  Litertur  seperti  jurnal  dan paper yang  berkaitan  dengan game dan  kecerdasan  buatan  digunakan dalam  memperkuat  dan  mendukung argument yang akan digunakan dalam pengembangan  permainan  ini(Sazaki et al., 2018).

## Implementasi  Metode  Path  Finding  dengan  Penerapan  Algoritma  A-Star  untuk
Mencari Jalur Terpendek pada Game “Jumrah Launch Story”
| 45
Rancangan dibuat sebagai gambaran dalam pembuatan game ini. Perancangan  antar  muka  game  pada menu, akan terdapat beberapa tombol seperti start untuk memulai permainan, dan exit untuk keluar dari permainan.  Antar  muka  game, menggambarkan
keadaan
saat pemain  sudah  pada  posisi  memulai permainan.  Alur  permainan  pada game  “ Jumrah  Launch  Story” pemain harus  mengalahkan  semuah  musuh atau  NPC  untuk  bias  memenangkan permainan. Cara memainkan game ini juga  cukup  mudah,  pemain  dapat menekan tombol arah untuk menentukan  akan  kemana  karakter tersebut bergerak(kanan, kiri, space).
Metode  yang  akan  diterapkan untuk menentukan perilaku NPC pada permainan  ini  adalah  algortima A- Star . Agar game dapat berjalan seperti yang  diinginkan,  maka  penerapan algoritma tersebut untuk metode path finding sangat  diperlukan.  Algoritma ini  membuat  total  biaya  lintasan menjadi  seminimal  mungkin(Harsadi &  Siswanti,  2019).  Algoritma A-Star memerlukan  dua  antrian  yaitu Open dan Closed. Open berisi simpul-simpul yang masih berpeluang untuk dipilih, sedangkan Closed adalah  simpul- simpul yang sudah pernah digunakan dan  tidak  mungkin  terpilih  sebagai simpul terbaik(Pramono, 2015). Dalam  penerapanya,  akan  lebih  baik jika  fungsi  ini  didefinisikan  sebagai pendekatan yang sebenarnya terhadap  node  n.  Nilai  yang didapatkan  merupakan  jumlah  yang diperoleh  melalui  sepanjang  lintasan terbaik  menuju  simpul.  Secara matematis,  fungsi  terhadap  node  n ialah sebagai berikut:
Gambar 1 . Persamaan Matematis Fungsi Algoritma A-Star
Gambar 2 . Diagram A-Star Pada NPC

## 3. HASIL DAN PEMBAHASAN
Implementasi sistem ini bertujuan  agar  mengetahui  apakah sistem yang dijalankan sesuai dengan langkah  yang  ditentukan  untuk mengetahui apakah sistem kecerdasan yang telah menerapkan A- Star dapat  berjalan  sesuai  keinginan dan dapat diimplementasikan kedalam game. Pada  Menu  halaman  utama  dari game Jumrah  Launch  Story terdapat pilihan tombol play untuk mengkonfirmasi pemain untuk
Ghani Mutaqin 1 , Juniardi Nur Fadilah 2 , Fresy Nugroho 3
memulai  permainan,  dan  tombol exit untuk keluar dari permainan.
Pada  uji  coba  metode,  akan dibahas  pengujian  dari  algoritma A- Star yang  diterapkan.  Algoritma  ini digunakan untuk
mengatur pergerakan  NPC.  NPC  tersebut  ialah musuh sebagai NPC tanpa AI dan Bos yaitu “Jumrah” sebagai NPC dengan AI. Pengujian  ini  dilakukan  terhadap algoritma  tersebut  dengan  acuan perbedaan  perilaku  karakter  yang menggunakan AI dan tidak menggunakan AI ketika game
dimainkan .
Dari hasil implentasi,  pergerakan NPC  tanpa A-Star hanya  bergerak sesuai  inputan  di  awal,  tidak  akan mengejar  pemain  utama  seperti  di dunia  nyata.  Sedangkan  pergerakan NPC  menggunakan  algoritma A-Star seperti  nyata,  menjadi  lebih  aktif dalam  mengejar  dan  menyerang pemain.  Jalur  yang  ditempuh  juga menjadi  lebih  efisien  dan  NPC  tetap bias  mengajar  pemain  meskipun pemain  sedang  bersembunyi  dan terhalang sebuah objek.
Tabel 1 . Hasil Uji Coba NPC Menyerang Player
Berdasarkan Tabel 1 hasil uji coba penelitian tersebut yaitu pengaruh NPC menggunakan Ai dan tidak menggunakan AI, ketika NPC tidak menggunakan AI maka pergerakan akan tidak beraturan. Hasil uji coba tersebut menunjukkan keberhasilan menggunakan AI adalah 80% sedangkan NPC tanpa AI hanya 20%.

## 4. KESIMPULAN
Perkembangan industri game saat ini  membuat  kita  menjadi  lebih tertarik  saat  memainkan  game tersebut. Berbagai cara dikembangkan  untuk  menarik  minat dari  pemain  untuk  memainkan sebuah  game.  Salah  satunya  ialah mengembangkan  teknologi  yang  ada pada game. Teknologi diterapkan agar membuat  game  seperti  dunia  nyata, salah  satunya  adalah  kecerdasan buatan.  Dari  banyak  teknologi  yang ada, algoritma A-Star adalah teknologi yang  digunakan  dalam  penelitian  ini. Algoritma  A-Star  adalah  metode  dari pathfinding    dimana  NPC  dapat mencari  jalur  terpendek  dari  rute yang akan ditempuh. Hasil penelitian penerapan algoritma  A-Star  ini  adalah  berhasil. NPC yang menggunakan algoritma ini dapat mengejar player dan membunuh  saat  player  kurang berhati-hati.  NPC  juga  bias  mengejar walaupun  player  bersembunyi  dan terdapat penghalang. Sedangkan NPC tanpa  algoritma  A-Star  hanya  dapat bergerak sesuai dengan program yang telah dibuat di awal. Percobaan NPC Tanpa AI NPC Dengan AI
1
2 X 3 X 4 X 5 X

## Implementasi  Metode  Path  Finding  dengan  Penerapan  Algoritma  A-Star  untuk
Mencari Jalur Terpendek pada Game “Jumrah Launch Story”
| 47

## REFERENCE
Harsadi, P., & Siswanti, S. (2019). Penerapan Pathfinding Menggunakan Algoritma A* Pada Non Player Character (NPC) Di Game. Jurnal Ilmiah SINUS , 17 (2), 39. https://doi.org/10.30646/sinus.v17i2.423
Kholil,  M.  (2017).  Pergerakan  Pasukan  Untuk  Mengejar  Musuh  Bergerak Menggunakan D* Lite Berbasis Algoritma Pathfinding. Journal of Animation & Games Studies , 2 (1), 45. https://doi.org/10.24821/jags.v2i1.1413
Pramono, A. (2015). Algoritma Pathfinding A* Pada Game RPG Tanaman Higienis.
Jurnal Edukasi Dan Penelitian Informatika (JEPIN) , 1 (2). https://doi.org/10.26418/jp.v1i2.12517
Prasetyo, F. R., Muh, E., Jonemaro, A., & Akbar, M. A. (2017). Penerapan Algoritma Hybrid  Pathfinding  A  *  dan  Boids  untuk  Game  Pesawat  Tempur. Jurnal Pengembangan  Teknologi  Informasi  Dan  Ilmu  Komputer  (J-PTIIK)  Universitas Brawijaya , 1 (12), 1616 – 1621.
Rahadiansyah, D. A., Bandung, I. T., Bandung, J. G., & Ai, A. G. (2016). Kompleksitas Algoritma A * Pada Implementasi PassiveAI Untuk Game Mobile AI .
Sazaki, Y., Satria, H., Primanita, A., & Syahroyni, M. (2018). Analisa  Perbandingan Algoritma A* dan Dynamic Pathfinding Algorithm dengan Dynamic Pathfinding Algorithm untuk NPC pada Car Racing Game. Jurnal Teknologi Informasi Dan Ilmu Komputer , 5 (1), 95. https://doi.org/10.25126/jtiik.201851544
Theosaksomo,  D.  (2017).  Pembuatan  Pathfinding  untuk  Game  Platformer  dengan Memanfaatkan  Library  A*  Karya  Aron  Granberg  pada  Unity  Engine. Institut Teknologi Bandung .
Verma, S., Mehta, P., Shah, H., Shukla, S., Professor, A., Nmims, M., Sturtevant, N. R., Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., & Thrun, S. (2015). A Review on  Algorithms  for  Pathfinding  in  Computer  Games. IEEE  Transactions  on Computational Intelligence and AI in Games , March 2015 , 262 – 271.
Wijaya, A. A., Bukhori, S., & Oktavia, N. (2017). Perancangan dan Pembuatan Serious Game  Sebagai  Simulasi  Aktivitas  Bisnis  dan  Akuntansi  Menggunakan Pendekatan  Agent-Based  Modelling. Berkala  Sainstek , 5 (2),  66. https://doi.org/10.19184/bst.v5i2.5532
Ghani Mutaqin 1 , Juniardi Nur Fadilah 2 , Fresy Nugroho 3
This page intentionally left blank.