## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467

## PENERAPAN ALGORITMA A STAR (A*) PADA GAME LABIRIN
Diana Y.A. Fallo a , Vera Rosalina Bulu b a diana.ucb.ac.id, b verarosalina.ucb.ac.id
a, Program Studi Pendidkan Informatika, b Program Studi Pendidikan Guru Sekolah Dasar a,b Fakultas Keguruan dan Ilmu Pendidikan Universitas Citra Bangsa, Nusa Tenggara Timur

## ABSTRAK
Masa pandemi sekarang telah banyak mengubah pilihan media pembelajaran di dunia pendidikan. Salah satu media pembelajaran yang dapat menarik minat banyak orang adalah game . Game adalah sebuah permainan dengan tujuan bersenang-senang dan mengisi waktu luang. Salah satu permainan klasik yang hingga  saat  ini  masih  sangat  digemari  adalah  labirin  yang  dimana  memerlukan  AI  ( Artificial Intelligence ).  AI yang digunakan dalam pembangunan game petualangan labirin ini adalah algoritma A* (A Star). Dari hasil penelitian yang dilakukan dengan cara menyebar angket maka ditemukan bahwa sebesar  73,4  %  adanya  minat  dan  ketertarikan  siswa  pada game labirin.  Siswa  lebih  antusias  dalam belajar sambil bermain sehingga tujuan dari pembelajaran lebih mudah tercapai dari pada pembelajaran secara konvesional.
Kata kunci : Algoritma Star  (A*), Kecerdasan Buatan , Game, Labirin .

## ABSTRACT
The current pandemic has changed the choice of learning media in the world of education considerably. One of the learning media that can attract the interest of many people is game s which aim for having fun and filling free time. One of the classic game s that are still very popular today is the maze which requires AI (Artificial Intelligence). The AI used in the construction of this maze adventure game is the A* (A Star) algorithm. From the results of this research conducted by distributing questionnaires, it was found that 73.4% of students are interested in the maze game . Students are more enthusiastic in learning while playing so that the objectives of learning are easier to achieve than conventional learning.
Keywords: Algoritma Star (A*), Artificial Intelligence, Game, Maze

## PENDAHULUAN
Masa  pandemi  sekarang  telah  banyak mengubah  media  pembelajaran  di  dunia pendidikan.
Pembelajaran dengan memanfaatkan teknologi saat ini khususnya multimedia pada audio-visual ataupun software komputer  merupakan salah  satu  media  pembelajaran  yang cukup  efektif  dan  menarik  untuk meningkatkan  mutu  pembelajaran  di dunia pendidikan. Dalam dunia pendidikan seiring dengan perkembangan  teknologi  sudah  banyak media  pembelajaran  multimedia  dari anak-anak sampai orang dewasa (Kusuma, 2016).
Salah  satu  media  pembelajaran  yang
dapat menarik minat banyak orang adalah game .  Dunia  bermain  sudah  tidak  lagi harus diluar ruangan. Manusia menciptakan  permainan  bukan  hanya sebagai  penghilang  rasa  bosan,  tetapi banyak  hal  bisa  dijadikan  alasan  untuk mengawali  sebuah  permaian,  termasuk untuk belajar. Belajar dengan permainan merupakan  metode  yang  cukup  bagus digunakan karena tidak membuat pelajar menjadi cepat jenuh, sehingga semangat belajar selalu ada (Nugraha, 2018). Game dianggap  penting  oleh  seseorang  karena adanya hiburan dan mampu menyegarkan otak. Game banyak diminati oleh semua kalangan.
Game sendiri  dapat  dijadikan  sarana

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
pembelajaran  yang  dapat  menarik  minat siswa.  Hampir  semua game memiliki unsur adventure walaupun tidak spesifik.
Game adventure biasanya  memiliki  satu tokoh  atau  objek  utama  yang  dimainkan dan dijalankan secara langsung dari awal sampe  akhir.  Salah  satu  contoh game petualangan  adalah  permainan  labirin (Ahmad & Widodo, 2017).
Labirin  adalah  sebuah puzzle dalam bentuk percabangan jalan yang kompleks dan  memiliki  banyak  jalan  buntu  (H, 2011).  Prinsip  permainannya  adalah pemain  harus  menemukan  jalan  keluar dari  sebuah  pintu  masuk  ke  satu  atau lebih pintu keluar. Untuk menyelesaikan permainan  ini  memerlukan  penalaran- penalaran akan ketidakpastian,
selayaknya  proses  pemecahan  masalah dalam  melakukan  pencarian  jalur  yang dilakukan  secara  alami  oleh  manusia (Ahmad  &  Widodo,  2017).  Dan  labirin pada  masa  kini  lebih  sering  dinikmati sebagai  sebuah  permainan  pemecahan masalah.  Labirin  biasanya  berawal  dari sebuah jalur yang merupakan jalur buntu, dan  hanya  satu  jalur  yang  merupakan jalan  keluar,  namun  untuk  membuat menarik,  labirin  dapat  dibuat  berujung banyak atau memiliki banyak jalan keluar sehingga  misi  penyelesaian  masalah bertambah yang semula hanya satu jalan keluar menjadi banyak, terlebih lagi bila ada  beberapa  musuh  yang  menghalangi jalan keluar (Nugraha, 2018).
Algoritma A* merupakan algoritma yang digunakan untuk menentukan rute terpendek  objek  menuju  ke  tujuan, dengan  menghitung  harga  yang  harus dipakai  untuk  mencari  harga  terkecil yang harus dibayarkan. Algoritma diperlukan  untuk  membuat game lebih menarik. Hal ini berbanding lurus dengan jumlah pengguna, semakin menarik game yang  dimainkan,  semakin  banyak  orang yang akan memainkan game tersebut. Di dalam  sebuah game algoritma  biasa digunakan  untuk  menentukan  level,
tingkat  kesulitan,  skor/nilai,  hingga sebagai pengambil keputusan (Oktanugraha & Nudin, 2020).
AI  merupakan  faktor  terpenting  dalam meningkatkan game play  pada  semua jenis  permainan.  Hal  penting  dalam menentukan  keberhasilan  suatu  aplikasi game yang  menerapkan  AI  adalah kesuksesan dalam pencarian dan pelacakan. Pada dasarnya ada dua teknik pencarian dan pelacakan yang digunakan, yaitu  pencarian  buta  ( blindsearch )  dan pencarian
terbimbing ( heuristicsearch ).Dalam pencarian terbimbing ada beberapa algoritma salah satunya  algoritma  A*.  Algoritma  ini dapat menyelesaikan permasalahan secara  optimal  untuk  menemukan  jalan terpendek menuju suatu tujuan  (Ahmad & Widodo, 2017).
Algoritma  A*  menggunakan  estimasi jarak  terdekat  (cost/  jarak  sebenarnya) untuk  mencapai  tujuan  (goal)  dan memiliki  nilai  heuristik  yang  digunakan sebagai  dasar  pertimbangan  pemilihan jalur  (Deviana,  2015).  Algoritma  A*  ini memeriksa node dengan menggabungkan g(n),  yaitu cost yang  dibutuhkan  untuk mencapai sebuah node dan h(n) yaitu cost yang didapat dari node ke tujuan (Dewa, 2016).  Sehingga  dapat  dirumuskan sebagai  berikut  (Erniyati  &  Mulyati, 2019) :
f(n) =g(n) + h(n) [1]
f(n)=  perkiraan  total cost terendah  dari setiap path yang akan dilalui dari node n ke node tujuan
g(n) = biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n
h(n) = perkiraan heuristic atau cost atau path dari node n ke tujuan

## 2. METODE PENELITIAN
Adapun  teknik  pembuatan game labirin dilakukan melalui beberapa tahap

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
berikut antara lain : 1) tahap pengumpulan data; 2) tahap analisa dan perancangan; 3) tahap implementasi.
1) Tahap  pengumpulan  data  yang digunakan adalah sebagai berikut :
a. Observasi
Observasi  dilakukan  untuk  mengetahui responden  terhadap  penggunaan game pembelajaran  di  lingkungan  sekolah. Dalam penelitian ini, peneliti melakukan observasi  pada  semua  warga  sekolah, kepada sekolah, guru dan siswa.
b. Studi Literatur
Dalam penelitian ini proses pengumpulan  data  yang  dilakukan dengan  mempelajari  berbagai  bentuk bahan tertulis seperti buku, dokumen dan jurnal  yang  ada  kaitannya  secara langsung.
c. Angket
Pada angket dilakukan pengumpulan data dengan  cara  menyebarkan  sejumlah lembar  kertas  yang  berisi  pertanyaan- pertanyaan  yang  harus  di  jawab  oleh responden.  Selanjutnya  untuk  dilakukan perhitungan terhadap angket maka digunakan rumus sebagai berikut menurut
(Sugiyono, 2017) : [2]
Keterangan :
P = Presentase yang dicari
X = Jumlah jawaban
Xi  =  Jumlah  nilai  ideal  untuk keseluruhan item 100% = bilangan konstan
Tabel.  1 Rentangan  Kategori  Nilai
Instrumen Tingkat Pencapaian Kualifikasi Kelayakan 90 – 100 % Sangat baik 75 – 85 % Baik 65 – 74 % Cukup 55 – 64 % Kurang 0 – 54 % Sangat kurang
2) Tahap analisa dan perancangan
Pada tahap ini dilakukan perancangan melalui  aplikasi  Star  UML  untuk membuat  rancangan use  case  dan class  diagram yang  menggambarkan peran aktor dalam game labirin.
3) Tahap Implementasi
Selanjutnya  pada  tahap  implementasi merupakan  tahap  akhir  dimana  peneliti memastikan  sistem  diimplementasikan kedalam  program adobe  flash  player berdasarkan  hasil  perancangan  UML yang dibuat apakah sistem dapat berjalan dengan  baik  atau  tidak.  Setelah  game labirin  diimplementasi  game  labirin  di lakukan  pengujian  untuk  mengetahui apakah game masih di temukan kesalahan ( error ).

## 3. HASIL DAN PEMBAHASAN
Hasil  dari  penelitian  yang  telah dicapai oleh peneliti setelah melalui berbagai tahap antara lain:
1) Rancangan diagram Rancangan  diagram  terdiri  antara lain:
a) Use  Case diagram  berguna  untuk mendeskripsikan  fungsi  fungsi  dari sebuah  sistem  dari  sudut  pandang pengguna  (aktor)  dengan  sistemnya sendiri. Skrenario
use case
P = 𝑋 𝑋𝑖 𝑥 100 %

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
menjelaskan tentang bagaimana memulai permainan labirin ini.
Gambar 1. Tampilan Use Case b. Class Diagram Class Diagram berfungsi untuk menggambarkan  hubungan  antar  class dengan  game  yang  dibuat.  Pada  saat aplikasi  dijalankan  game  menu  akan memanggil  class-class  yang  diperlukan dalam proses berjalannya aplikasi. Selain itu class  diagram juga  berfungsi  untuk meningkatan pemahaman pemain tentang skema dari aplikasi labirin yang dibuat.
Gambar 2. Tampilan Class Diagram
2) Rancangan Tampilan Game
Labirin Setelah perancangan telah dilakukan maka  langkah  selanjutnya  adalah mendesign game .  Permainan  labirin di  mainkan  secra  tunggal  ( single player )  Berikut  merupakan  gambar tampilan game.
Gambar 3. Tampilan menu awal Tampilan  menu  awal  menunjukkan aktor dapat memilih game dengan cara melakukan  klik  pada play maka permainan akan dimulai jika dilakukan klik pause maka  permaian  akan terhenti.
Gambar 4. Tampilan Game Labirin Pada  gambar  4  tampilan  game  labirin menunjukkan  game  dapat  dimainkan dengan  menganut  prinsip  algoritma  A* dimana  akan  di  lakukan  pencarian  secara buta  melalui  banyak  jalan  dan  akan ditemukan  jalan  keluar.  Game  ini dimainkan dengan cara player menjalankan  anak  panah  pada keyboard dan  jika  menemukan  hambatan  secara otomatis akan muncul soal yang harus di jawab  oleh player setelah  itu player bisa melanjutkan perjalanannya lagi.
Actor File About Help Exit Play Pause Riwayat Skor <<include>> <<include>> <<include>> Nilai <<include>> Plays +Open () +Load () Pauses +Open () +Load () Musik +Open () +Load () Exit1 +Open () +Load () Skor +Add Skor () +Load () Pemain +Load () +Gerak () +Klik ()

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
Gambar 5. Tampilan skor akhir Pada gambar 5 tampilan skor
menunjukkan  skor  akhir  dari  palyer  dan riwayat skor dari player sebelumnya.
3) Pengujian Algoritma A*
Adapun  langkah  dalam  pencarian  jalur terpendek adalah sebagai berikut :
Gambar 6. Visualisasi Labirin
Selanjutnya adalah perhitungan secara manual untuk algoritma A* yaitu :
1. Masukkan node awal
2. Cari  node  (n)  dengan  nilai  (f)  paling rendah  dalam  openlist  dan  akan  di jadikan current node
3. Jika tidak dapat dilalui maka abaikan
4. Jika  sudah  ada  dalam  open  list  maka maka cek nilai (g)
5. Jika telah menemukan rute maka dapat di hentikan perulangan
4) Analisis Angket Setelah  melakukan design  game dan  di implementasikan kepada siswa maka dilakukan  sebar  angket  untuk  mengetahui tingkat kepuasan siswa terhadap game yang diberikan.  Berikut  merupakan  perhitungan berdasarkan angket yang disebar.
Tabel 2. Hasil Perhitungan Presentase No. Nama Jumlah Hasil Rata-rata Tingkat Pencapaian 1 Samuel Radja 37 / 50 * 100 74 % Baik 2 Grevi Takaeb 36 / 50 * 100 72 % Baik 3 Christian Leu 38 / 50 * 100 76 % Baik 4 Gilberth Riwu 37 / 50 * 100 74% Baik 5 Gava Tunu 37 / 50 * 100 74 % Baik 6 Elin Lily 36 / 50 * 100 72 % Baik 7 Gareth Selan 36 / 50 * 100 72 % Baik 8 Azariel 38 / 50 * 100 76 % Baik 9 Sarah Pah 37 / 50 * 100 74 % Baik 10 Eflin Leob 38 / 50 * 100 76 % Baik 11 Melani Oematan 36 / 50 * 100 72 % Baik 12 Kristi Sanam 35 / 50 * 100 70 % Baik 13 Sariwati Ndun 37 / 50 * 100 74 % Baik 14 Diana Tanesib 36 / 50 * 100 72 % Baik 15 Sandro Dethan  38 / 50 * 100 76 % Baik 16 Oktavia Lassa 35 / 50 * 100 70 % Baik 17 Rafael Baitanu 36 / 50 * 100 72 % Baik 18 Elisabeth Koro  36 / 50 * 100 72 % Baik
19 Eunike Bessie 38 / 50 * 100 76 % Baik
20 Hana Sriyuningsih 36 / 50 * 100 72 % Baik

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
Selanjutnya  di  tampilkan  dalam  bentuk grafik perhitungan adalah sebagai berikut:
Gambar 6. Tampilan Grafik Game Labirin
Analisis ini dilakukan pada 20 siswa maka diperoleh tingkat persentase untuk masing-masing siswa.
5) Pengujian Black Box
Selanjutnya  pengujian  aplikasi.  Pada tahap  ini  aplikasi  diuji  sebelum  diujikan kepada siswa.   Pengujian  yang dilakukan berdasarkan  pengujian Black  Box . Black Box adalah  pengujian  untuk  mengethaui apakah  semua  fungsi  perangkat  lunak telah berjalan dengan kebutuhan fungsional yang telah didefinisikan.
Tabel 3 . Hasil Uji Coba

## Halaman Menu Permainan
No Tombol yang diuji Status 1 Tombol Play ( ) Gagal (√ ) Berhasil 2 Tombol Pause ( ) Gagal (√ ) Berhasil 3 Tombol Musik ( ) Gagal (√ ) Berhasil 4 Tombol Exit ( ) Gagal (√ ) Berhasil Halaman Menu Utama 5 Tombol File ( ) Gagal (√ ) Berhasil 6 Tombol About ( ) Gagal (√ ) Berhasil 7 Tombol Help ( ) Gagal (√ ) Berhasil
8 Tombol Exit ( ) Gagal (√ ) Berhasil
Berdasarkan  hasil  perhitungan  angket yang  sebar  menunjukkan  hasil  dengan rata-rata 73,4 %. Sehingga game labirin diminati oleh siswa dan dapat dijadikan media pembelajaran yang menyenangkan.

## 4. KESIMPULAN
Adapun kesimpulan yang diperoleh dari penelitian ini adalah sebagai berikut : 1) Setelah melakukan proses perancangan, design dan pengujian aplikasi game labirin maka terlihat bahwa game ini  dapat  menjadi hiburan  dan  mengasah  kecerdasan dari pemainnya.
2) Pada  tahap  pengujian  sistem (pengujian black box ) maka diperoleh tombol menu permainan dan  menu  utama  dapat  berjalan dengan baik (berhasil).
3) Analisis  data  berdasarkan  angket yang  di  sebar  maka  menunjukkan hasil  dengan  rata-rata  73,4  %. Dengan  demikian  menunjukkan ketertarikan  siswa  pada game labirin.  Adanya  tingkat  kepuasan siswa dengan game . Dimana siswa dapat  bermain  sambil  belajar sehingga tujuan pembelajaran dapat tercapai.

## DAFTAR PUSTAKA
1) Ahmad, I. & Widodo, W., 2017. Penerapan Algortima A Start (A*) pada game Petualangan Labirin Berbasis Android. Jurnal Ilmu Komputer dan Informatika, 3(2), p. 57.
2) Deviana, R., 2015. Implementasi Pathfinding Algoritma A* pada game petulangan labirin rahasia, Batam: s.n.

## Jurnal Pendidikan Teknologi Informasi (JUKANTI) Volume (5) No (1) April 2022–eISSN : 2621-1467
3) Dewa, C. K., 2016. Game Labirin
Berbasis Pengolah Bahasa Alami untuk Pengenalan Logika Pemrograman Sederhana. INACL.
4) E. & M., 2019. Pencarian Jalur
Terdekat menuju Rumah Sakit di Kota
Bogor dengan menggunakan Algoritma
A*. Jurnal Ilmiah Ilmu Komputer dan Matematika (KOMPUTASI), 16(1), pp. 235-253.
5) Sugiyono, 2017. Metodelogi Penelitian.
Bandung: s.n.
6) H, T., 2011. Penerapan Algortima A- Star (A*) untuk menyelesaikan masalah mase. jurnal teknik informatika, institut teknologi bandung
7) Kusuma, G. A., 2016. Perkembangan Permainan Labirin Membantu
Perkembangan Motorik. Jurnal Protek , 3(2), pp. 46-89.
8) Nugraha, N. B., 2018. Rancang Bangun Game Labirin Menggunakan Algoritma
A Star Berbasis Mobile. UNITEX , 11(2)
9) Oktanugraha, R. F. & Nudin, S. R.,
2020. Implementasi Algoritma A* dalam Penentuan Rute Terpendek yang dapat dilalui non player character pada game good thief. JINACS , 2(1)