## PENERAPAN MARKOV STATE CHAIN, COLLISION DETECTION DAN FISHER YATES PADA GAME ANIMAL RESCUE
Aprisa Rizky Prasetyo, Danang Wahyu Widodo, Danar Putra Pamungkas Program Studi Teknik Informatika S1, Fakultas Teknik Universitas Nusantara PGRI Kediri kikuk486@gmail.com

## ABSTRAK
Game edukasi  merupakan  suatu game yang  dirancang  untuk  mengajarkan  keterampilan  dan  memberikan informasi kepada pemain. Dalam perkembangannya, game memiliki peran besar dalam mendukung proses belajar anak-anak khusunya pada tingkat TK. Dengan menggunakan desain yang menarik dan interaktif anak-anak akan lebih mudah memahami pesan dan pembelajaran yang disampaikan di dalam game. Tujuan dibuatnya game ini adalah  untuk  memudahkan  anak-anak  TK  untuk  mengenal  hewan  melalui  suatu  game  yang  berjudul  “ Animal Rescue”. Metode yang digunakan pada penelitian ini antara  lain Markov State Chain, Collision Detection, dan Fisher-Yates dalam game edukasi. Setelah menyelesaikan game Animal Rescue ,dapat disimpulkan bahwa dalam proses pembuatan game implementasi Markov State Chain diterapkan untuk interaksi  antara NPC dan pemain dalam  kondisi  tertentu.  Implementasi collision  detection digunakan  untuk  interaksi  koin  dan  nyawa  dengan kondisi saat ini. Implementasi Fisher Yates digunakan untuk mengacak puzzle saat permainan dimulai. Gameplay pada permainan  ini  melibatkan penyelamatan  hewan dalam  sangkar dengan  menyelesaikan puzzle. Pergerakan unit dan respons NPC dalam game Animal Rescue berjalan sesuai rencana. Game in hanya dapat dimainkan pada sistem  operasi  Android  saja  untuk  pengembangan  selanjutnya  disarakan  game  in  dapat  ditambahkan  untuk meningkatkan pengetahuan mengenai berbagai hewan yang ada di dunia.
Kata kunci: game edukasi, Artificial Intelligence, Markov state chain, collision detection, fisher yates

## 1. PENDAHULUAN
Perkembangan  teknologi  informasi  saat  ini memiliki  beragam  manfaat  salah  satunya  mendorong inovasi pembelajaran menjadi lebih menarik dan dapat dilakukan  dimana  saja.  Tidak  dapat  dipungkiri, perkembangan teknologi turut menyumbang peningkatan  motivasi  belajar.  Tidak  hanya  belajar secara  konvesional  menggunakan  buku,  metode pembelajaran berbasis teknologi menghadirkan pengalaman  belajar  lebih  baik  dengan  menyediakan media belajar berbasis audio visual.  Salah satu media pembelajaran yang berkembang saat ini adalah game . Penggunaan game sebagai  media  pembelajaran menjadi  lebih  menyenangkan  dimana  anak  akan mendapat  berbagai  informasi  dan  mematuhi  aturan permainan.
Penggunaan game sebagai  media  pembelajaran sangat tepat digunakan pada anak-anak dalam rentang usia 3 – 5 tahun atau dapat dikategorikan sebagai anak- anak  usia  TK. Game edukasi  merupakan  suatu game yang  dirancang  dengan  tujuan  untuk  mengajarkan keterampilan  dan  memberikan  informasi  kepada pemain. Game ini menggabungkan konsep permainan yang  menyenangkan  dengan  konten  pendidikan. Tujuan  lain  dari game edukasi  ini  adalah  untuk meningkatkan  motivasi  belajar  dan  memperkuat pemahaman  konsep. Game ini  dapat  dimainkan melalui  berbagai platform dan  telah  terbukti  efektif dalam  meningkatkan  keterlibatan  pemain  dalam proses belajar [1].
Dalam  perkembangan game edukasi  untuk  usia Taman Kanak-Kanak (TK), penting untuk memperhatikan  berbagai  faktor  guna  mendukung efektivitas  penggunaan game tersebut.  Hal  ini  dapat
diperhatikan  misalnya  dengan  membuat  desain game sesuai  dengan  usia  pengguna  hal  ini  bertujuan  agar game dapat memberikan tantangan yang sesuai dengan kemampuan  mereka.  Umpan  balik  positif  seperti pujian  dan  penghargaan  visual  juga  perlu  diberikan untuk  meningkatkan  motivasi  dan  keterlibatan  anak- anak  dalam  proses  pembelajaran.  Selain  itu, penggunaan game edukasi harus diawasi dan dibatasi oleh  orang  dewasa  sesuai  dengan  pedoman  yang direkomendasikan  oleh  ahli  untuk  memastikan keamanan dan keseimbangan waktu layar anak-anak. Dengan  memperhatikan  aspek-aspek  ini, game edukasi  dapat  menjadi  alat  yang  efektif  untuk memperkaya  pengalaman  belajar  anak-anak  pada tingkatan  Taman  Kanak-Kanak  (TK)  dan  membantu mereka  mengembangkan  keterampilan  kognitif, sosial, dan motorik dengan cara yang menyenangkan.
Dalam game edukasi  ini  penggunaan  metode Markov State Chain, Collision Detection , dan Fisher- Yates dapat  memberikan  pengalaman  interaktif  yang menarik dan efektif bagi pemain. Di dalam penelitian ini  digunakan  beberapa  metode  dalam  proses pembuatan game dimana  metode tersebut terdiri  dari metode Markov State Chain dimana metode ini adalah pengembangan dari metode Markov Chain . Perbedaan metode  ini  dengan  metode Markov  Chain adalah memperhitungkan  keadaan  atau state dari  sistem  [2]. Dalam game edukasi,  metode  ini  dapat  digunakan untuk  membuat  alur  permainan  yang  lebih  kompleks dengan  mempertimbangkan  situasi  dan  keputusan pemain.  Selanjutnya  adalah metode Collision Detection .  Metode Collision  Detection digunakan untuk mendeteksi interaksi antara objek di dalam game [3].  Dalam game edukasi, Collision  Detection
digunakan untuk memastikan bahwa pemain berinteraksi dengan objek yang relevan dengan tujuan pembelajaran.  Yang  terakhir  adalah    metode Fisher- Yates dimana pada  metode Fisher-Yates ini digunakan untuk mengacak urutan elemen dalam suatu daftar atau himpunan  [4].  Dalam game edukasi,  metode  ini berguna  untuk  mengacak  gambar  pada puzzle agar tidak  mengikuti  urutan  yang  sama  setiap  kali permainan  dimulai.  Hal  ini  membantu  meningkatkan variasi dan tantangan dalam permainan.
Penelitian  ini  bertujuan  untuk  membuat game edukasi  dengan  menggunakan  metode Markov  State Chain sebagai NPC, metode Collision Detection untuk mendeteksi interaksi karakter dengan obyek disekitarnya.  Serta  metode Fisher-Yates untuk mengacak puzzle yang  nantinya  membentuk  suatu karakter  hewan  sebagai  bentuk reward atas  upaya pemain dalam misinya menyelematkan hewan.
Pada  penelitian  ini  dilakukan  beberapa  batasan untuk  menyesuaikan  penggunaan  game  di  kalangan anak – anak usia TK. Adapun batasan yang digunakan dalam penelitian diantaranya penggunaan jumlah level pada  game  maksimal  ada  pada  level  5.  Selain  itu jumlah  hewan  yang  digunakan  pada  penelitian  ini terdiri  dari  5  hewan  yang  sering  dijumpai  pada kehidupan  sehari-hari.  Terakhir game ini  dirancang dengan  konsep single  player agar  anak-anak  lebih fokus  untuk  menemukan  hewan  melalui  aktivitas adventure daripada  bersaing  untuk  menemukan hewan.

## 2. TINJAUAN PUSTAKA
2.1. AI ( Artificial Intelligence ) Artificial  Intelligence (AI)  adalah  kecerdasan yang ditambahkan kepada suatu sistem dalam konteks ilmiah  [5].  Kemudian,  pandangan  lain  mengartikan kecerdasan  buatan  (AI)  sebagai  kapabilitas  sistem dalam mengartikan informasi dari luar dengan akurat, mengambil  pelajaran  dari  informasi  tersebut,  dan menerapkan  pembelajaran  tersebut  guna  mencapai sasaran dan aktivitas khusus melalui penyesuaian yang cekatan.  [6].  Biasanya,  AI  dianggap  sebagai  bentuk komputasi. Kecerdasan ini dirancang dan dimasukkan ke dalam perangkat mesin/komputer untuk melaksanakan  tugas  sebagaimana  yang  mampu dilakukan  oleh  manusia.  Beberapa  domain  yang mengaplikasikan  AI  meliputi  ekspert  sistem,  hiburan digital  (games),  logika  kabur,  model  jaringan  saraf tiruan, serta ilmu robotika.[7]
2.2. Markov State Chain Markov Chain adalah metode yang mempelajari suatu  variabel  saat  ini  berdasarkan  sifatnya  di  masa lalu,  untuk  kemudian  digunakan  dalam  estimasi  sifat di  masa  depan  [8].  secara  umum  menunjukkan karakteristik  yang  bersifat  acak,  di  mana  keadaan sebelumnya  tidak  berdampak  pada  perkembangan keadaan  di  masa  yang  akan  datang  asalkan  keadaan saat  ini  sudah  diketahui.  Pendekatan  ini  memberikan hasil  berbentuk  probabilitas  yang  berguna  untuk membantu  dalam  pengambilan  keputusan.  Oleh
karena  itu,  metode  ini  bukanlah  pendekatan  untuk optimisasi,  tetapi  lebih  merupakan  pendekatan  yang bersifat deskriptif [9]
2.3. Collision Detection
Collision Detection adalah langkah menginspeksi  tabrakan  di  antara  objek-objek  yang telah  ditetapkan  dalam  koordinat  khusus.  Agar  lebih simpel untuk identifikasi, objek yang telah ditetapkan yang  terlibat  lazimnya  digambarkan  secara  visual dalam bentuk bidang datar (koordinat 2D) atau volume ruang  (koordinat  3D).  Representasi  ini  kerap  dikenal dengan  sebutan  Bounding  Box  atau  Bounding  Circle [9]
2.4. Fisher-Yates Fisher-Yates adalah algoritma untuk menghasilkan permutasi acak dari himpunan terhingga [10].  Algoritma  ini  juga  dikenal  dengan  nama Knuth Shuffle yang  diambil  dari  nama  Donald  Knuth. Terdapat  dua  metode  dalam  algoritma Fisher-Yates , yaitu  metode  orisinal  dan  metode  modern.  Dalam pengembangan  game,  umumnya  digunakan  metode modern  karena  lebih  cocok  untuk  pengacakan  dalam sistem  komputerisasi,  sehingga  menghasilkan  variasi yang lebih beragam [11]
3. METODE PENELITIAN
3.1. Flowchart game
Pada Flowchart game berfungsi untuk menggambarkan alur proses dimulainya game hingga selesai yang ditunjukkan pada gambar 1.
Gambar 1. Desain System
3.2. Struktur Menu Pada game  “Animal  Rescue ”  terdiri  dari beberapa menu yaitu Play, Gallery Animal, Opsi dan Exit. Diagram struktur menu di tunjukan pada gambar 2

## Gambar 2. Struktur Menu
3.3. Penerapan Markov State Chain pada game Dalam  analisis  ini,  digunakan  pendekatan Markov  State  Chain yang  melibatkan  penggunaan matriks  probabilitas  transisi  untuk  memproyeksikan kemungkinan kejadian di masa mendatang saat pemain berada dalam kondisi saat ini.
A. Analisa Metode Markov State Chain Langkah  untuk  mengatur  tingkah  laku  pada karakter non-pemain (NPC) melibatkan menetapkan  perilaku  NPC  dengan  rentang  nilai parameter  yang  memiliki  nilai  maksimal  dan minimal pada tabel 1.
Tabel 1 . Perilaku NPC Kondisi Perilaku Range 5-20 Diam Range 0-5 Kejar Pengimplementasian perilaku dari
NPC diilustrasikan pada gambar
Gambar 3. Diagram Implementasi NPC

## B. Tahap perancangan Sistem
Game yang diciptakan memiliki genre Petualangan,  di  mana  terdapat  protagonis  yang melaksanakan  sebuah  tugas  penyelamatan  hewan
dengan  mengatasi  berbagai  hambatan  seperti semak  berduri.  Selama  perjalanan,  ada  seekor anjing  penjaga  yang  perlu  mengatasi puzzle kecil untuk  membuka  kandang  dan  menyelamatkan hewan.  Fokus  utama  dari  permainan  ini  adalah pada pergerakan karakter. Untuk pemahaman lebih lanjut,  berikut  beberapa  karakter  dan  aturan  yang akan  muncul  dalam  permainan di  tunjukan  pada tabel 2. Tabel 2. Perancangan sistem No. Nama Karakter/ rules 1. Rudi
2. Anjing 3. Semak- semak berduri

## C. Tabel Variabel Parameter
Dari  tabel  3  ini  nantinya  bisa  dilihat  NPC  akan melakukan diam, kejar.
Tabel 3 . Variabel parameter Input Output >5 Diam <5 Kejar
Setelah  selesai  ditetapkan  akan  menentukan  aksi NPC  terhadap Player dengan  menghitung  jarak terdekat
3.4. Analisa metode Collision Detection
Mengimplementasikan bouding  box sebagai collider  keater player -nya  yang  berfungsi  sebagai initiator ketika player bertabrakan  dengan  objek  lain pada game .  Deteksi collison akan  dimulai  ketika collider karakter player mulai  bergerak  dan  saling sentuh  dengan collider objek  lain.  Kemudian  apabila dua  objek  bertabrakan  makaa event yang  telah  di tetapkan  akan  muncul.  Maka  berikut event  collision detection yang diterapkan pada game ini : 1. Saat player bertabrakan  dengan  poin,  maka variabel  pada  poin  di  atas  akan  bertambah  dan memaikan soun pada coin.
2. Saat player bertabrakan dengan NPC anjing dan Semak-semak berduri. Maka varibel nyawa akan berkurang.
3.5. Analisa Metode Fisher-Yates
Mengimplementasikan  algoritma Fisher  Yates yang  dimana  akan  mengacak  suatu  gambar  yang memiliki value. Maka akan mengacak gambar dengan menggunakan fisher yates pada tabel 4.
Tabel 4 . analisa metode fisher yates No. Value Keterangan 1. 1 Potongan gambar orang utan 1 2. 2 Potongan gambar orang utan 2 3. 3 Potongan gambar orang utan 3 4. 4 Potongan gambar orang utan 4

## 4. HASIL DAN PEMBAHASAN

## 4.1. Tampilan Menu Utama
Menu utama yiatu tampilan awal pada game yang akan  muncul  pada  saat  pemain  menjalankan  game. Pada  tampilan  awal  ini  ada  berisikan  tombol Play, Gallery  Animal,  Opsi,  Exit .  Tombol Play untuk menampilkan  jendela  level  yang berisikan  level pada game ,tombol Gallery  Animal akan  menampilkan edukasi  mengenai  Hewan,  Tombol  Opsi  akan menampilkan  keterangan  mengenai game  “Animal Rescue” ,  Tombol exit untuk  keluar  dari  game. Tampilan menu utama pada gambar 6.
Gambar 6. Main menu

## 4.2. Tampilan pilih Level
Pilih level adalah tampilan yang akan menentukan misi yang akan dilakukan pada gambar 7.
Gambar 7. Pilih Level
4.3. Tampilan gallery animal Gallery animal adalah tampilan untuk pengetahuan  hewan  yang  sudah  diselamatkan  pada gambar 8.
Gambar 8. Gallery animal

## 4.4. Tampilan Gameplay
Tampilan  ini adalah tampilan saat game Animal Rescue memulai misi pada gambar 9.
Gambar 9. Gameplay

## 4.5. Pengujian Metode M arkov State Chain
Tujuan  dari  pengujian  ini  adalah  untuk memverifikasi  apakah  metode  yang  diterapkan  pada karakter  non-pemain  (NPC)  anjing  telah  berhasil berjalan  sesuai  dengan  harapan.  Hasil  pengujian terhadap karakter NPC anjing ini pada tabel 5.
Tabel 5 . Hasil implementasi markov state chain Kondisi Perilaku Ket. Range 5-20 Diam Sesuai Range 0-5 Kejar Sesuai 4.6. Pengujian Metode Collision Detection
Pengujian collision detection dilaksanakan untuk mengevaluasi  keberhasilan  penerapan  metode  pada deteksi tabrakan pada koin dan nyawa. Hasil pengujian terhadap koin dan nyawa akan dipaparkan. pada tabel 6.
Tabel 6 . Hasil implementasi collision detection No. Event Harapan Hasil 1. Karakter menabrak koin coin bertambah, soun coin Sesuai 2. Karakter menabrak Semak berduri dan NPC anjing Nyawa berkurang Sesuai 4.7. Pengujian metode Fisher Yates Pengujian  ini  dilakukan  dengan  maksud  untuk memahami apakah metode yang telah diimplementasikan  pada  gambar puzzle berhasil beroperasi dengan benar. Hasil pengujian pada puzzle akan dipresentasikan pada tabel 7.
Tabel 7 . Hasil implementasi fisher yates No. Keterangan Keluaran harapan Hasil 1. Potongan gambar orang utan 1 Potongan gambar orang utan 3 Sesuai 2. Potongan gambar orang utan 2 Potongan gambar orang utan 1 Sesuai 3. Potongan gambar orang utan 3 Potongan gambar orang utan 4 Sesuai 4. Potongan gambar orang utan 4 Potongan gambar orang utan 2 Sesuai
4.8. Pengujian Fungsionalitas
Setiap  fitur  dan  fungsi  yang  diimplementasikan dalam permainan "Animal Rescue" telah diuji. Berikut adalah hasil dari pengujian ditampilkan pada tabel 8.
Tabel 8 . Fungsionalitas No. Item Uji Berhasil Gagal 1. Splash Screen √ - 2. Main menu √ - 3. Btn  Play √ - 4. Btn Galley √ - 5. Btn Opsi √ - 6. Btn Exit √ - 7. Pilih level √ - 8. NPC dapat mengejar √ - 9. Nyawa berkurang ketika bertabarakan dengan Semak berduri dan NPC √ - 10. Animasi musuh √ - 11. Sound effect √ - 12. Backgound sound √ - 13. Player mati ketika nyawa = 0 √ - 14. Menampilkan kemenangan √ - 15. Button puase √ - 16. Button main ulang dari awal √ - 17. Membuka level yang baru √ -

## 4.9. Pengujian kontrol player
Pengujian  ini  merujuk  pada  pengujian  dari masing-masing  fungsi  yang  telah  diterapkan,  dengan fokus pada pergerakan karakter pemain. Berikut hasil pengujian  pergerakan  karakter  pemain  ditampilkan pada tabel 9.
Tabel 9 . Kontrol player Tombol Fungsi Hasil Button kanan Player berjalan kearah kanan Sesuai Button kiri Player berjalan kearah kiri Sesuai Button atas Untuk player melompat Sesuai Button serang Menjalankan fungsi serang Sesuai

## 5. KESIMPULAN DAN SARAN
Dalam  proses  pengembangan  game  "Animal Rescue,"  beberapa  kesimpulan  dapat  ditarik  oleh penulis  sebagai  berikut:    Penerapan Markov  State Chain dapat diimplementasikan pada game 2D untuk memungkinkan  NPC  berinteraksi  dengan  pemain dalam  situasi  tertentu.  Penerapan collision  detection dapat diaplikasikan pada game 2D untuk memungkinkan  interaksi  antara  pemain  dengan elemen seperti koin dan nyawa sesuai dengan kondisi saat  itu.  Penerapan  metode Fisher-Yates dapat diterapkan pada puzzle utama untuk mengacak urutan awal permainan bagi setiap pemain. Gameplay dalam game  ini  menekankan  pada  misi  pemain  untuk menyelamatkan  hewan  dalam  kandang  dengan menyelesaikan puzzle .  Pergerakan  karakter  dan respons  karakter  NPC  dalam  game  "Animal  Rescue" berjalan sesuai dengan rencana yang telah ditetapkan.
Setelah  proses  pembuatan  dan  pengujian  game "Animal Rescue" selesai, masih terdapat ruang untuk pengembangan  lebih  lanjut,  dan  rekomendasi  yang diajukan  adalah  sebagai  berikut:  Menambahkan Karakter  hewan  agar  tujuan  pada  game  ini  sesuai dengan  judulnya  yang  dimana  untuk  bahan  edukasi hewan. Menambahan level pada game Animal Rescue , karena  pada game ini  hanya  terdapat  5  level, Menambahan NPC dengan karakter yang berbeda agar game  lebih  menarik.  Penambahan  Metode  AI  agar game menjadi lebih menarik dan lebih menantang.

## DAFTAR PUSTAKA
[1]  A.  Setiawan,  H.  Praherdhiono,  and  S.  Suthoni, “Penggunaan  Game  Edukasi  Digital  Sebagai Sarana Pembelajaran Anak Usia Dini,” JINOTEP (Jurnal  Inov.  dan  Teknol.  Pembelajaran)  Kaji. dan Ris. dalam Teknol. Pembelajaran , vol. 6, no.
1, pp. 39–44, 2019, doi: 10.17977/um031v6i12019p039.
[2]  L.  Lestari,  S.  Dur,  and  H.  Cipta, Penerapan Rantai Markov Dalam Menganalisis Persaingan Bisnis Situs Belanja Online , vol. 3, no. 1. 2021. doi: 10.54196/jme.v3i1.40.
[3]  Z. F. Fahlevy, “Implementasi Collision Detection Permainan Fly Bee menggunakan Game Maker,” Fak.  Teknol.  Informasi,  Univ.  Stikubank. Semarang , 2017.
[4]  E.  Ekojono,  R.  Cahyaningrum,  and  K.  S. Batubulan,  “Implementasi  Metode  Fisher-Yates Shuffle  Dan  Fuzzy  Tsukamoto  Pada  Game  2D Gopoh Berbasis Android,” J. Inform. Polinema , vol. 4, no. 3, p. 174, 2018, doi: 10.33795/jip.v4i3.203.
[5]  M. K. Rakhmat Kurniawan. R, S.T., KECERDASAN BUATAN ( ARTIFICIAL INTELLIGENCE  )  Edisi  Revisi  I  Oleh : RAKHMAT KURNIAWAN . R , S . T ., M . KOM FAKULTAS SAINS DAN TEKNOLOGI . Fakultas Sains  dan  Teknologi  UIN  Sumatera  Utara Medan, 2020.
[6]  B.  E.  Hunt, Artificial  Intelligence .  Washington DC:  Subsidiary  of  Harcount,  2014.  [Online]. Available:
https://books.google.co.id/books?hl=id&lr=&id =9y2jBQAAQBAJ&oi=fnd&pg=PP1&dq=artik el+tentang+artificial+intelligence&ots=uP_t1id0 rB&sig=C_NXHG3ZBYWHiW_GKqesudPdcU E&redir_esc=y#v=onepage&q&f=false
[7]  M.  Siahaan,  C.  H.  Jasa,  K.  Anderson,  and  M. Valentino, “Penerapan Artificial Intelligence ( AI )  Terhadap  Seorang  Penyandang  Disabilitas Tunanetra,” Inf.  Syst.  Technol. ,  vol.  01,  no.  02, pp. 186–193, 2020.
[8]  N.  A.  Maemunah,  “Penerapan  Teori  Rantai Markov  Pada  Data  Curah  Hujan  Harian  di Wilayah Tangerang,” pp. 1–63, 2020.
[9]  S.  L.  R  and  D.  A.  Dermawan,  “Implementasi Algoritma  Collision  Detection  dan  Markov Chain  untuk  Menentukan  Behaviour  NPC  dan Karakter Player pada  Game  Higiea,” J.
Informatics Comput. Sci. , vol. 3, no. 01, pp. 12– 19, 2021, doi: 10.26740/jinacs.v3n01.p12-19.
[10]  B. K. Fikria, “IMPLEMENTASI ALGORITMA FISHER-YATES SHUFFLE SEBAGAI
PENGACAK POSISI NON PLAYABLE CHARACTER (NPC) PADA GAME TANTRA BAHARI,”  UIN  Maulana  Malik  Ibrahim Malang, 2014.
[11]   h  sopryadi  S.  luarsa,  D.  marpolo,  “Penerapan Algoritme Fisher Yates pada Game Edukasi Eco Mania Berbasis Unity 3D,” J. Inform. , no. x, pp. 1–12, 2020.