IMPLEMENTASI ALGORITMA PRIM DAN DEPTH FIRST SEARCH PADA

PEMBUATAN MAZE GAME BERBASIS ANDROID OS MOBILE

M Khoiril Anwar 1, Cucun Very Angkoso 2 , Arik Kurniawati 3

1,2,3Jurusan Teknik Informatika, Fakultas Teknik, Universitas Trunojoyo Madura

Jl. Raya Telang, PO. BOX. 2 Kamal, Bangkalan-Madura

1anwarkhoiril@gmail.com,2cucunvery@if.trunojoyo.ac.id, 3ayyiik@yahoo.com

Abstrak

Teknologi mobile game beroperating system open source berkembang dengan sangat pesat. Operating system google android menjadi operating system yang sedang ramai dikembangkan para developer game. Karena keragaman variasinya, mobile game memiliki banyak peminat dari berbagai kalangan, hal inilah yang menjadi dasar bagi para pengembang untuk terus mengembangkan mobile game. Game yang sederhana/simple dengan target pengguna yang tidak dibatasi umur menjadi orientasi para pengembang game sehingga mampu menarik sebanyak mungkin pengguna. Pada penelitian ini dirancang sebuah maze mobile game berbasis operating system Android untuk mengasah kemampuan berfikir dikembangkan dengan mengimplementasikan algoritma Prim dan Depth First Search. Dalam perancangan game, algoritma Prim diterapkan untuk pembuatan lintasan dari maze sedangkan algoritma Depth First Search diterapkan pada saat melakukan proses pencarian solusi permasalahan dalam game.

Dalam pengujian telah dilakukan pada beberapa perangkat mobile dan selanjutnya hasilnya dapat disimpulkan bahwa algoritma Prim dan Depth First Search dapat berfungsi dengan baik pada resolusi screen 320 x 480 pixels dalam pembentukan lintasan dan pencarian solusi dari maze.

Kata kunci : Mobile Game, Android, Algoritma Prim, Algoritma Depth First Search.

Abstract

Mobile game technology with an open source operating system has grown rapidly. A Google Android is one of the most popular open source operating system which being intensively discuss among game developer. Mobile game has a lot of interest from various parties, because of the diversity of its variations. This is the basis for the developers to continue to develop mobile games. In this study, a mobile game to hone thinking ability has been developed to implement the algorithm Prim and Depth First Search. Game developing is starting with applying Prim algorithm at the time creating the track of the maze then the process go through by applying Depth First Search algorithm for searching the best solution of the game.

From the experiment that was done, we can make a conclusion of the test results is that the algorithm Prim and Depth First Search can perform best when creating formation of the track and searching for the solutions of the maze at the screen resolutions of the mobile device with 320 x 480 pixels.

Key words : Mobile Game, Android, Prim Algorithm, Depth First Search Algorithm.

PENDAHULUAN

Perkembangan teknologi game sangatlah pesat, tidak hanya pada komputer dan perangkat-perangkat yang

khusus di desain untuk memainkan game seperti Playstation, X-box dan sejenisnya melainkan juga pada handphone. Kebanyakan orang memainkan game untuk menghilangkan stress dan mengisi

waktu luang. Karena handphone memiliki kepraktisan untuk dibawa kemana-mana dibandingkan dengan perangkat elektronik lainnya, maka saat ini telah banyak pihak yang berminat untuk mengembangkan fitur-fitur yang ada di handphone termasuk fitur game.

Dalam pengembangan teknologi handphone, hal mendasar yang perlu di pertimbangkan adalah masalah operating system yang dipakai, karena sudah tentu suatu aplikasi tidak akan bisa berjalan di operating system yang berbeda, para pengembang pun sudah pasti memilih untuk memgembangkan suatu aplikasi pada handphone yang memiliki operating system yang dianggap terbaik.

Operating system Android adalah operating system yang free dan open source. Hal inilah yang menjadi dasar perkembangan teknologi Android yang begitu pesat dibandingkan dengan teknologi-teknologi handphone yang lainnya.

Pada proyek akhir ini, penulis ingin membuat sebuah aplikasi mobile game tentang permainan maze / labirin yang nantinya akan di implementasikan pada Android OS mobile. Game engine yang dipakai untuk membantu dalam pembuatan aplikasi ini adalah LIBGDX yaitu salah satu framework 2D dan 3D

untuk     Android yang berbasis

OpenGL. LIBGDX di kembangkan oleh Badlogic games yang bersifat open sources dan menggunakan bahasa java sebagai bahasa pemrogramannya.

Perumusan Masalah

Dari latar belakang yang sudah dijelaskan sebelumnya dimunculkan sebuah masalah yaitu membuat sebuah maze game berbasis Android OS mobile dengan mengimplementasikan algoritma Prim dan Depth First Search.

Tujuan Proyek

1.            Dapat    mengimplementasikan

algoritma Prim pada pembentukan lintasan maze.

2.            Dapat    mengimplementasikan

algoritma Depth First Search dalam

pencarian solusi dari maze yang telah terbentuk.

3.            Dapat mengimplementasikan maze game pada Android OS mobile.

TEORI PENUNJANG Maze game

Maze game adalah sebuah permainan yang bertujuan untuk mencari jalan keluar dari labirin / jalan yang membingungkan. Terdapat banyak sekali variasi dari maze game untuk membuatnya menjadi lebih menarik. Pada penelitian kali ini akan di buat sebuah maze game klasik yaitu pencarian jalan keluar dengan dibatasi oleh waktu tertentu yang nantinya akan diterapkan pada Android OS mobile. Di bawah ini adalah contoh tampilan lintasan dari maze game.

Android

Android adalah operating system untuk handphone yang berbasis Linux. Android menyediakan platform terbuka bagi para pengembang untuk

menciptakan       aplikasi  mereka

sendiri,Awalnya Google Inc. membeli Android Inc., pendatang baru yang membuat peranti lunak untuk ponsel. Kemudian untuk mengembangkan Android, dibentuklah Open Handset Alliance, konsorsium dari 34 perusahaan peranti keras, peranti lunak, dan telekomunikasi, termasuk Google, HTC, Intel, Motorola, Qualcomm, T-Mobile, dan Nvidia.

Pada saat perilisan perdana Android, 5 November 2007, Android bersama Open Handset Alliance menyatakan mendukung pengembangan standar terbuka pada perangkat seluler. Di lain pihak, Google merilis kode–kode Android di bawah lisensi Apache, sebuah lisensi perangkat lunak dan standar terbuka perangkat seluler.

Di dunia ini terdapat dua jenis distributor operating system Android. Pertama yang mendapat dukungan penuh dari Google atau Google Mail Services (GMS) dan kedua adalah yang benar– benar bebas distribusinya tanpa

dukungan langsung Google atau dikenal sebagai Open Handset Distribution (OHD) [1].

LIBGDX

LIBGDX adalah salah satu framework 2D&3D untuk Android yang berbasis OpenGL. LIBGDX ini dikembangkan oleh BadLogic Games dan bersifat Open Source dengan lisensi Apache 2.0 sehingga dapat digunakan untuk proyek game komersil. LIBGDX menggunakan bahasa Java sebagai bahasa pemrogramannya dan dapat berjalan di semua platform yang mendukung Java (Windows, Mac, Linux, Android). Saat ini LIBGDX telah mencapai versi 0.9.2

dan        masih    terus      berlanjut

perkembangannya didukung oleh komunitas yang sangat aktif [2].

Algoritma Prim

Algoritma Prim digunakan untuk mencari pohon pembangkit minimum dari graph terhubung berbobot dengan cara mengambil sisi / ruas garis yang memiliki bobot terkecil dari graph, dimana ruas garis tersebut bersisian dengan pohon terentang yang telah dibuat dan yang tidak membentuk siklus [3].

Untuk mencari pohon pembangkit minimum T dari graph G dengan Algoritma Prim dapat dilakukan dengan langkah-langkah sebagai berikut:

1. Ambilah satu simpul sembarang (misalnya v1 € G) dan masukkan simpul tersebut ke dalam graph T yang merupakan graph kosong.

2. Tambahkanlah satu rusuk yang terhubung dengan v dengan bobot yang paling minimum (misalnya e ) dan titik ujung lainnya ke T sehingga T terdiri dari sebuah rusuk e dan dua buah simpul yang merupakan titik-titik ujung dari rusuk e (salah satu titik ujung harus memuat simpul v ).

3. Pada langkah berikutnya, pilihlah sebuah rusuk dalam E(G) yang bukan E(T) dengan syarat yang harus dipenuhi sebagai berikut:

a.            Rusuk tersebut menghubungkan salah satu simpul V(T).

b.            Rusuk tersebut mempunyai bobot minimal.

4. Ulangilah langkah tersebut (langkah 2-3) hingga diperoleh (n-1) rusuk dalam E(T) dengan n adalah banyaknya simpul dalam G.

Algoritma Depth First Search

Pencarian dengan algoritma Depth First Search (DFS) dilakukan dari node awal secara mendalam hingga yang paling akhir atau sampai ditemukan tujuan. Dengan kata lain simpul cabang atau anak terlebih dahulu yang dikunjungi. Sebagai ilustrasi dapat dilihat pada gambar 1.

Gambar 1 Pencarian dengan DFS

( Sumber: Pratiwi, 2011 )

Berdasarkan       gambar,               proses

pencarian            dilakukan             dengan

mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika masih ada cabangnya. Begitu seterusnya sampai ditemukan tujuannya (goal).

DFS memiliki kelebihan diantaranya adalah cepat mencapai kedalaman ruang pencarian. Jika diketahui lintasan solusi permasalahan akan panjang maka DFS tidak akan memboros waktu untuk melakukan sejumlah besar keadaan ‘dangkal’ dalam permasalahan graph / pohon. DFS jauh lebih efisien untuk ruang pencarian dengan banyak cabang karena tidak perlu mengevaluasi semua simpul pada suatu level tertentu [4].

PERANCANGAN SISTEM

Pada perancangan sistem menjelaskan tentang uraian dan bahan yang akan digunakan dan cara kerja system dalam tugas akhir implementasi algoritma Prim dan Depth First Search pada pembuatan maze game berbasis Android os mobile .

Deskripsi Sistem

Sistem ini dirancang dengan menggunakan software Android SDK, Eclipse dengan tambahan plugin ADT(Android development tools) untuk mengembangkan aplikasi Android dan LIBGDX sebagai frameworknya.

Aplikasi yang dibuat berupa game labirin, dimana inti dari permainannya adalah menemukan jalan keluar dari labirin dengan waktu secepat cepatnya.

Berikut adalah penerapan algoritma Prim dalam proses pembentukan maze:

1.            Pilih random sel sebagai titik awal

2.            Jadikan random sel tersebut sebagai titik mulai

3.            Pilih random sel sebagai titik selesai

4.            Jadikan tepi-tepi dari kotak lintasan sebagai wall

5.            Pilih random sel tetangga

6.            Jika sel yang terpilih kosong lakukan langkah 7, jika tidak ulangi langkah 4

7.            Jadikan sel tetangga yang dipilih = path

8.            Jadikan sel tetangga sebelah samping belakang path = wall

9.            Ulangi langkah 5, 6, 7, 8 sampai tidak ada sel yang kosong

Dalam pencarian solusinya, di gunakan algoritma Depth First Search, berikut algoritma penyelesaiannya :

1.            Pilih titik mulai sebagai titik awal, akan dikenali sebagai current sel

2.            Pilih secara acak sel terdekat yang bisa dikunjungi, sama seperti proses pembuatan maze. Hanya ada 4 gerakan yang diperbolehkan yaitu atas, bawah, kiri dan kanan.

3.            Apabila sel belum pernah di datangi maka pindah current sel ke sel tersebut. Pilih lagi sel tetangga secara acak.

4.            Apabila sel menemui tembok atau wall, maka kembali ke sel sebelumnya.

5.            Lakukan langkah-langkah ini sampai menemukan sel yang menjadi selesai atau pintu keluar.

Skenario Game

Pada penelitian tugas akhir maze game ini skenario disusun berdasarkan waktu.

1.            Pada level pertama dan kedua, waktu tidak dibatasi, jadi seorang player akan dituntut untuk mencari jalan keluar dengan waktu secepat cepatnya yang nantinya waktu tercepatlah yang akan ditulis di menu nilai tertinggi / highscore.

2.            Pada level ketiga, waktu dibatasi hanya 1,5 menit.Jika dalam waktu 1,5 menit player dapat menemukan

pintu keluar,       maka player

memenangkan permainan.

3.            Sebaliknya, Jika dalam waktu 1,5

menit player       tidak dapat

menemukan pintu keluar dari labirin, maka player dinyatakan kalah.

IMPLEMENTASI DAN ANALISIS

Uji Coba Skenario

Untuk memastikan bahwa sistem berjalan sebagaimana mestinya, penulis akan menyusun skenario yang akan diuji coba antara lain :

1.            Pengujian dengan menggunakan emulator.

2.            Pengujian dengan handphone android.

Dalam bab ini dibahas mengenai skenario hasil uji coba yang telah dirancang oleh penulis. Uji coba dilakukan untuk mengetahui apakah sistem dapat berjalan sebagaimana mestinya dengan lingkungan uji coba yang telah ditentukan serta dilakukan sesuai dengan sekenario uji coba.

Pengujian Dengan Emulator 1. Main Menu Maze Game

Gambar 2 menampilkan menu utama dari maze game yaitu menu mulai, petunjuk dan pembuat

Gambar 4 Nilai tertinggi

2.            Tampilan Pilih Level

Jika tombol mulai pada gambar 2 diklik, maka akan muncul screen baru yaitu screen pilih level seperti di tunjukkan oleh gambar 3.

Perbedaan antara level pertama,kedua dan ketiga adalah pada besar dimensi lintasan dan waktunya. Untuk level pertama, besar lintasannya adalah 20 x 20 sedangkan level kedua dan ketiga adalah 30 x 30. Pada level pertama dan kedua,waktu yang diberikan tidak terbatas, player dituntut untuk mencari jalan keluar dengan waktu secepat-cepatnya agar bisa mengalahkan nilai tertinggi/highestscore. Sedangkan pada level ketiga, waktu dibatasi hanya 1,5 menit. Jika dalam waktu tersebut player tidak dapat menemukan jalan keluar, maka player dinyatakan kalah.

3.            Tampilan Nilai Tertinggi

Waktu terbaik akan dicatat tiap level pada menu nilai tertinggi. Seperti di tunjukkan pada gambar 4.

4.            Level Pertama

Gambar 5 menunjukkan level pertama dari maze game. Pada level pertama, ukuran dimensi dari labirin adalah 20 x 20 dengan waktu tak terbatas. Pada game ini terdapat menu ganti lintasan, lihat solusi,gerak otomatis dan menu utama. Jika menu gerak otomatis di klik, maka kotak hijau / player akan bergerak secara otomatis mencari jalan keluar dengan mengimplementasikan algoritma DFS.

5.            Level Kedua

Gambar 6 menunjukkan level kedua dari maze game. Pada level kedua, ukuran dimensi dari labirin adalah 30 x 30 dengan waktu tak terbatas. Tiap level memiliki menu yang sama yaitu menu ganti lintasan, lihat solusi, gerak otomatis dan menu utama. Dengan waktu yang tak terbatas, seorang player berusaha menemukan jalan keluar dengan waktu secepat- cepatnya untuk di catat pada menu nilai tertinggi.

6.            Level Ketiga

Gambar 7 menunjukkan level ketiga dari maze game. Pada level ketiga, ukuran dimensi dari labirin adalah 30 x 30 dengan waktu yang dibatasi hanya dengan 1,5 menit. Jika dalam waktu tersebut seorang player tidak dapat menemukan jalan keluar, maka player dinyatakan kalah.

Gambar 7 Level ketiga

7.            Menu Petunjuk

Gambar 8 menunjukkan menu petunjuk dari maze game. Pada menu ini akan ditampilkan informasi mengenai aturan dan bagaimana cara memainkan maze game ini.

8.            Tampilan Gerak Otomatis

Jika menu solusi otomatis diklik maka player akan bergerak secara otomatis mencari jalan keluar dengan menerapkan

algoritma Depth First Search. Seperti di tunjukkan pada gambar 9.

Pengujian Dengan Handphone

Untuk pengujian pertama digunakan handphone Samsung Galaxy Ace dengan resolusi 480 x 320 pixels, Android versi 2.3.4.

1. Main Menu Maze Game Pada Samsung

Untuk main menu dapat tampil dengan normal seperti di tunjukkan oleh gambar 10. Semua menu dapat berfungsi dengan baik, mulai dari menu mulai, menu petunjuk dan menu pembuat. Tampilan pada main menu sesuai dengan tampilan yang ada di emulator.

Gambar 10 Main menu pada Samsung

galaxy ace

2.            Tampilan Maze Game Pada Samsung

Pada pengujian dengan menggunakan handphone Samsung galaxy ace, pembentukan lintasan dari maze game dengan mengimplementasikan algoritma Prim dapat berjalan dengan baik seperti di tunjukkan pada gambar 11.

3.            Tampilan Gerak Otomatis Pada Samsung

Jika menu solusi otomatis diklik maka player akan bergerak secara otomatis mencari jalan keluar dengan menerapkan algoritma Depth First Search seperti di tunjukkan pada gambar 12.

Gambar 11 maze game pada Samsung

galaxy ace

Gambar 12 Solusi otomatis pada

Samsung galaxy ace

Untuk pengujian kedua digunakan handphone Motorola droid X dengan resolusi 840 x 420 pixels, Android versi 2.3.3.

2. Main Menu Maze Game Pada Motorola

Gambar 13 Main menu pada Motorola

Gambar 13 menunjukkan tampilan main menu dari maze game. Untuk tampilan main menu dapat berjalan dengan baik sesuai harapan walau

dengan resolusi yang berbeda. Semua menu dapat berfungsi dengan baik, mulai dari menu mulai, menu petunjuk dan menu pembuat. Tampilan pada main menu sesuai dengan tampilan yang ada di emulator.

2.            Tampilan Pilih Level Pada Motorola Pada tampilan pilih level, tampilan hanya muncul pada sisi pojok bawah sebelah kiri seperti di tunjukkan oleh gambar 14. Menu-menu yang ada pada tampilan pilih level tidak bisa berjalan dengan baik.

Gambar 14 Pilih level pada Motorola

3.            Tampilan Maze Game Pada Motorola

Sama seperti tampilan pilih level, tampilan maze game juga hanya muncul pada sisi pojok bawah sebelah kiri dengan tombol-tombol menu semuanya tidak berfungsi. Seperti di tunjukkan pada gambar 15.

Gambar 15 Maze Game pada

Motorola

4.            Tampilan Menu Petunjuk Pada Motorola

Tampilan menu petunjuk hanya berada pada sisi pojok bawah sebelah kiri dengan tombol-tombol menu tidak berfungsi dengan baik. Seperti di tunjukkan pada gambar 16.

Gambar 16 Petunjuk pada Motorola ANALISA HASIL UJI COBA

Setelah dilakukan uji coba dengan beberapa perangkat dapat dijelaskan pada Tabel 1 di bawah ini.

Tabel 1 Perbedaan resolusi screen

Tipe

Smart

phone    Resolu si

Screen   Tam it

p

an           Algoritm

a             Prim

(Generat e Labirin)           Algori tma

(Pen carian solusi)

Emulat or            320        x

480        sesuai    sesuai    sesuai

Samsun g Galaxy Ace       320        x

480 pixels            sesuai    sesuai    sesuai

Motorol a Droid

X             420        x

820 pixels            Tidak sesuai        Tidak sesuai        Tidak sesuai

Setelah dicoba ternyata smartphone android tipe Motorola Droid X dengan resolusi 420 x 820 pixels tidak bisa menjalankan perangkat lunak ini dengan sempurna (tampilan game hanya berada di pojok bawah sebelah kiri). Karena dalam pembuatannya sangat ditentukan oleh koordinat. Perubahan ukuran layar dapat membuat game tidak berjalan dengan semestinya.

Berdasarkan hasil pengujian, “maze game” membutuhkan standart spesifikasi untuk dapat berjalan dengan baik. Untuk lebih jelas melihat spesifikasi tersebut daapt dilihat pada tabel 2

Tabel 2 Spesifikasi untuk maze game

Type      Requirements

Processor            800 MHz

RAM      278MB

Resolusi Screen  320 x 480 pixels

OS          Android 2.3 Gingerbread

KESIMPULAN

Dari hasil pengujian dan analisa pada bab sebelumnya maka diambil kesimpulan

1.            Dari hasil pengujian dan analisa maze game dapat berjalan dengan baik pada smartphone android yang memiliki resolusi screen 320 x 480 pixels. Aplikasi game ini masih belum bisa berjalan lancar pada tipe smartphone android yang memiliki resolusi screen lebih besar dari 320 x 480 pixels.

2.            Algoritma Prim dapat berfungsi dengan baik dalam pembentukan lintasan dari labirin pada handphone dengan resolusi 320 x 480 pixels.

3.            Algoritma DFS dapat berfungsi dengan baik dalam pencarian jalan keluar dari labirin yang telah terbentuk pada handphone dengan resolusi 320 x 480 pixels.

DAFTAR PUSTAKA

[1]          Bernard Y.A. Arti Android beserta fasilitas yang ada di dalamnya. April 2011. URL: http://www.infoteknologi .com/selular/apa-itu-Android/. Diakses tanggal 14 Desember 2011.

[2]          Zechner M.          Introduction.

Agustus 2011.URL:http://code.google.co m/p/libgdx/wiki/Introduction. Diakses tanggal 14 Desember 2011.

[3]          Emut. Aplikasi algoritma Prim dalam menentukan pohon pembangkit minimum pada suatu Graph. Pendidikan Matematika. Universitas Negeri Yogyakarta. 1: 3-5. 2008

[4] Pratiwi E.A., Efendi R dan Malik            Solving Hashi dan Depth First        R.F. Penyelesaian Game Puzzle    Search. Teknik Informatika.          Hashiwokakero dengan teknik     Universitas Sriwijaya. 1: 2. 2011