## IMPLEMENTASI STRUKTUR DATA TREE PADA GAME PACMAN DENGAN C
Hanhan Septian 1 , Ida Suhartini 2 , Irfan Pertrio N 3 , Lubban Ahsanul Jihad 4 , Nur Lia 5 , Toriq Fadilah A 6 Politeknik Negeri Bandung
Jl. Gegerkalong Hilir, Ciwaruga, Kec. Parongpong, Kabupaten Bandung Barat, Jawa Barat 40559 Email : hanhan.septian.tif20@polban.ac.id 1 , ida@jtk.polban.ac.id 2 , irfan.pertrio.tif20@polban.ac.id 3 , lubban.ahsanul.tif20@polban.ac.id 4 , nur.lia.tif20@polban.ac.id 5 , thoriq.fadhillah.tif20@polban.ac.id 6

## ABSTRAK
Pac-Man  merupakan  sebuah  permainan  yang  bisa  dimainkan  oleh  seorang  player  dengan  karakter didalamnya yang biasanya berbentuk bulan dan berwarna kuning. Selain itu, Pac-man mempunyai musuh yang  digambarkan  seperti  hantu  /  ghost  dengan  aturan  yang  telah  ditentukan.  Karakter  dari  permainan Pacman dan jalur permainan dimodelkan menggunakan tree atau pohon. Struktur tree adalah struktur yang mengandung  aspek  hirarki  yang  dibentuk  melalui  pengelompokkan  elemen  atau node dalam  tingkatan tertentu.
Kata kunci: Program, Permainan Pacman, Struktur data tree, Bahasa C

## ABSTRACT
Pac-Man is a game that can be played by a player with characters in it which are usually moon-shaped and yellow. In addition, Pac-man has enemies who are  described as ghosts / ghosts with predetermined rules. The characters from the Pacman game and the game path are modeled using trees. The tree structure is a structure that contains a hierarchical aspect that is formed through grouping elements or nodes in a certain level.
Keywords: Program, Pacman Game, Data tree structure, C language

## 1. PENDAHULUAN

## 1.1 Latar Belakang
Pac-Man adalah sebuah permainan arkade yang dikembangkan Namco dan diterbitkan Midway; dirilis di Jepang pada 22 Mei 1980. Awalnya dirilis di arkade saja, Pac-Man yang masih populer hingga kini telah dirilis  pula  dalam  platform  lainnya  seperti  Game  Boy  dan SNES.  Perancang permainan ini  adalah  Toru Iwatani, yang merupakan karyawan Namco.
Pemain harus mengontrol tokoh berwarna kuning bernama Pac-Man dan membawanya mengelilingi lorong  berlika-liku  sambil  "memakan"  titik-titik  kecil  dan  benda-benda  khusus  lainnya.  Pada  saat  yang sama, terdapat empat "hantu" yang berkeliling di lorong tersebut yang bertugas menangkap Pac-Man. Sang pemain  dapat menyelesaikan satu  level  (tingkat)  jika berhasil  memakan  seluruh  titik  dan  benda khusus. Secara teori, permainan dapat terus berlanjut tanpa batasan tingkat, namun tingkat ke-256 memiliki bug yang menyebabkan gambar di layar tidak beraturan dan karena itu Pac-Man tidak dapat terus dimainkan melewati tingkat tersebut.
Pac-Man  kini  dianggap  sebagai  salah  satu  permainan  video  klasik  serta  merupakan  salah  satu  ikon tahun 1980-an.  Salah  satu  alasan  kesuksesannya  adalah bentuk permainannya  yang  dapat  digemari baik pria maupun wanita dibandingkan dengan permainan arkade lainnya sebelum Pac-Man seperti Space Invaders dan Defender yang merupakan permainan tembak-tembakan.

## 1.2 Tujuan Penelitian
Adapun  yang  menjadi  tujuan  dari  penelitian  ini  adalah  untuk  mengembangkan  program  permainan Pacman yang sudah ada dengan menggunakan struktur data tree yang diterapkan dalam program C.

## 2. KAJIAN PUSTAKA

## 2.1 Struktur Data Tree
Karakter  dari  permainan Pacman dan  jalur  permainan  dimodelkan  menggunakan tree atau  pohon. Struktur tree adalah  struktur  yang  mengandung  aspek  hirarki  yang  dibentuk  melalui  pengelompokkan elemen atau node dalam tingkatan tertentu. Terdapat macam-macam jenis tree beserta cabang ilmu lainnya yang berkaitan dengan jenis-jenis tree tersebut. Salah satunya adalah binary tree . Jenis tree tersebut identik dengan ciri parent yang pasti hanya memiliki dua anak.

## 2.2 AVL Tree
Guna  meminimalisir  kompleksitas  waktu  dalam  proses  pengolahan  data  pada tree yang  diterapkan, maka  diperlukan  metode  otomatisasi  penyeimbangan  tinggi  pohon.  Metode  ini  disebut AVL  tree yang dimanfaatkan  pada  pohon  biner  ( binary  tree ).  Waktu  yang  dibutuhkan  dalam  pencarian  data,  dijamin bernilai konstan apabila metode ini diterapkan.
Penyeimbangan  tinggi  pohon  dilakukan  dengan  proses  rotasi.  Proses  rotasi  tersebut  menyebabkan adanya pergeseran pointer yang menunjuk root pada tree serta terbentuknya jalur node baru. Jalur node baru tersebut pastinya memiliki nilai seimbang ketika dihitung oleh otomatisasi AVL .

## 3. METODE PENELITIAN
Berdasarkan metode yang telah dipaparkan serta penggambaran program yang akan dikembangkan, analisis  terhadap  implementasi  pun  dilakukan.  Struktur  data tree beserta AVL  tree hanya  dapat diimplementasikan pada karakter permainan yaitu Pacman . Karakter  permainan Pacman digambarkan  memiliki  bentuk  bulat  yang  biasanya  berwarna  kuning dengan musuh yang digambarkan seperti ghost.
Implementasi binary  tree dirasa  akan  lebih  efisien  karena  nantinya  dapat  diterapkan AVL yang mempercepat proses pengolahan data pada tree . Sehingga program dapat bekerja secara lebih optimal.

## 3.1 Metode Perancangan
Dalam pembuatan permainan Pacman tentunya dibutuhkan sebuah tahapan perancangan agar permainan yang dibuat sesuai dengan yang diinginkan. Secara garis besar terbagi menjadi beberapa tahapan berikut :
1. Tahap Riset dan Penyusunan Konsep Dasar
Pada  tahap  ini  konsep  dasar,  tema,  teknologi,  media  ( platform ),  serta  berbagai  batasan  lain dirumuskan. Tahapan riset ini menjadi sebuah tahapan penting, berbagai elemen dasar dari permainan disusun di sini.
2. Perumusan Mekanika Permainan Pada tahap ini tim pengembang merumuskan mekanika permainan. Mekanika permainan merupakan pola, aturan, atau mekanisme yang mengatur bagaimana proses interaksi pemain dengan permainan yang dibuat.
3. Penyusunan Asset dan Level Design
Tahapan  ini  fokus  pada  penyusunan  konsep  dari  semua  karakter  serta asset termasuk  suara/musik yang diperlukan. Pada tahap ini pula tim pengembang melakukan pengelompokan tingkat kesulitan serta berbagai asset yang tepat sehingga permainan dapat menghadirkan pengalaman bermain yang optimal.
4. Development
Pada  tahap  ini  seluruh  konsep  yang  sebelumnya  telah  tersusun  mulai  dikembangkan  secara  penuh serta semua elemen mulai dipadukan.
5. Testing
Pada  tahap  ini  berfokus  untuk  mengetahui  apakah  semua  komponen  utama  permainan  mampu memberikan pengalaman bermain yang diharapkan serta dapat diketahui apakah ada masalah teknis yang belum terdeteksi sebelumnya.

## 3.2 Perancangan Modul
Dalam  pembuatan  program,  tentu  saja  diperlukan  beberapa  modul  yang  mana  dalam  modul-modul tersebut  berisi  logika  yang  menjadi  dasar  berjalannya  program.  Modul-modul  utama  yang  akan diimplementasikan sebagai berikut :
1. Modul  dengan  fungsi  umum  yaitu  menampilkan.  Misalnya  menampilkan  arena  permainan,  papan jumlah  perolehan  skor  dan  nyawa  karakter,  menampilkan  karakter Pacman ,  dan  objek  makanan karakter Pacman .
2. Modul dengan fungsi yang bersangkutan dengan logika dalam pemodelan karakter Pacman dengan struktur data tree.
3. Modul  dengan  fungsi  untuk  mengatur  gerakan  karakter.  Modul  ini  memiliki  ciri  umum  pada penamaan  modulnya,  yaitu  terdapat  kata  yang  merujuk  ke  macam-macam  arah,  misalnya  kanan ( right ) dan kiri ( left ).

## 3.3 Perancangan Tampilan
Antarmuka  dari  program  menjadi  salah  satu  unsur  penting,  guna  menarik  minat  pengguna  serta kenyamanan visual. Antarmuka yang menjadi output dari program permainan Pacman ini dirancang untuk menampilkan, 1. Karakter Pacman, yang berbentuk bulat berwarna kuning
2. Objek makanan karakter, terbagi menjadi makanan utama, dan makanan bonus.
3. Latar belakang/ background ,
4. Button , terdiri dari button play game , credits, highscore dan button exit,
5. Area permainan dengan tiga pilihan map yang dirancang berbeda.

## 4. IMPLEMENTASI SISTEM

## 4.1 Implementasi Modul
Modul-modul yang diimplementasikan pada pembuatan permainan Pacman sebagai berikut : Tabel 1. Implementasi Modul dalam Permainan Pacman
No Nama Modul Deskripsi 1. iniBagianMenu Modul ini berfungsi untuk menampilkan tampilan loading pada game 2. sprite *sprite_create Modul ini bertujuan mengalokasikan data pada maps agar gambar dapat terbaca 3. Makelist Untuk membuat list maps 4. map_view Untuk menampilkan gambar maps pada layar
4.2 Implementasi Alur Program 4.2.1 Tampilan Opening
Gambar 1. Tampilan Opening
4.2.2 Tampilan Loading
Gambar 2. Tampilan Loading

## 4.2.3 Main Menu
Gambar 3. Tampilan Opening

## 4.2.4 Aturan Permainan
Gambar 4. Tampilan Aturan Permainan
4.2.5 Profil Kelompok
Gambar 5. Tampilan Profil Kelompok

## 4.2.6 Tampilan highscore
Gambar 6. Tampilan Highscore
4.2.7 Tampilan game
Gambar 7. Tampilan Game

## 4.2.8 Tampilan Game Over
Gambar 8. Tampilan Game Over

## 4.2.9 Tampilan win
4.2.10 Karakter
1. Pac-Man
a. Pacman ke atas
Gambar 10. Tampilan Pac-Man ke atas
b. Pacman ke bawah
Gambar 11. Tampilan Pac-Man ke bawah
c. Pacman ke kanan
Gambar 12. Tampilan Pac-Man ke kanan
d. Pacman ke kiri
Gambar 13. Tampilan Pac-Man ke kiri
2. Hantu
Gambar 14. Tampilan Hantu

## 3. Maps
Gambar 15. Tampilan Maps
4. Pelet
Gambar 16. Tampilan Pelet

## 5. Gerbang
Gambar 17. Tampilan Gerbang
6. Rules
Gambar 18. Tampilan Rules Permainan

## 5. KESIMPULAN
Tujuan  dibuatnya  dari game Pac-Man  ini  ialah  untuk  menduplikasi  dan  juga  membuat  kembali permainan  dengan  struktur  dan  pemrograman  C.  Penerapan  struktur  data  Tree  pada  perancangan,  dapat menghasilkan karakter dan juga bentuk permainan yang sama dengan permainan sebelumnya. Walaupun masih ada keterbatasan, namun dari hasil implementasinya dapat menampilkan permainan Pac-Man seperti permainan aslinya.

## DAFTAR PUSTAKA
[1] RINI  WONGSO,  S.  2017,  March  15.  School  of  Computer  Science.  Single  Linked  List. https://socs.binus.ac.id/2017/03/15/single-linked-list/
[2] Wikipedia.org. 2011, March 15.Kontributor dari proyek Wikimedia. layanan pesan singkat mobile dan media sosial yang dimiliki Facebook
[3] https://id.wikipedia.org/wiki/WhatsApp
[4] Wikipedia.org. 2011, December 11.Kontributor dari proyek Wikimedia. layanan hos untuk proyek perangkat lunak yang menggunakan Git..
[5] https://id.wikipedia.org/wiki/GitHub
[6] Jefri  Yonata.  2021,  April  19.Panduan  Lengkap  Cara  Menggunakan  Google  Meet  di  Semua Perangkat. Blog Dewaweb.
[7] https://www.dewaweb.com/blog/cara-pakai-google-meet/
[8] Wikipedia.org.  2014,January  10.  Kontributor  dari  proyek  Wikimedia.  Code::Blocks. https://id.wikipedia.org/wiki/Code::Blocks
[9] Wikipedia.org. 2007, September 27. Kontributor dari proyek Wikimedia. Adobe Photoshop.
[10] https://id.wikipedia.org/wiki/Adobe_Photoshop
[11] MALIKI EDULOGI NUSANTARA. 2020, January 6. Pengenalan DEV-C++
[12] https://maliki.id/pengenalan-dev-c/
[13] rizkidoank .2016, October 17. Double Linked List.
[14] https://www.rizkidoank.com/2016/10/17/double-linked-list/
[15] GeeksforGeeks.2020,  April  16.  Construct  a  Doubly  linked  linked  list  from  2D  Matrix https://www.geeksforgeeks.org/construct-a-doubly-linked-linked-list-from-2d-matrix/
[16] Modul Perkuliahan “ Struktur Data”, Ade Chandra