RANCANG BANGUN GAME SCRAMBLE DENGAN ALGORITMA DEPTH FIRST SEARCH (DFS) BERBASIS ANDROID
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh : Hadi Usman 07560299
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
LEMBAR PERSETUJUAN
RANCANG BANGUN GAME SCRAMBLE DENGAN ALGORITMA DEPTH FIRST SEARCH (DFS) BERBASIS ANDROID
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui
Pembimbing I
Pembimbing II
Yuda Munarko, S.Kom,M.Sc. NIP : 108.0611.0443
Nur Hayatin, S.ST. NIP : 108.0907.0476
i
LEMBAR PENGESAHAN
RANCANG BANGUN GAME SCRAMBLE DENGAN ALGORITMA DEPTH FIRST SEARCH (DFS) BERBASIS ANDROID
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : Hadi Usman 07560299
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal
Menyetujui, Penguji I
Penguji II
Eko Budi C, S.Kom, M.T. NIP : 108.9504.0330
Aminudin, S.Kom. NIDN : 0701068603
Mengetahui, Ketua Jurusan Teknik Informatika
Eko Budi C, S.Kom, M.T. NIP : 108.9504.0330
ii
LEMBAR PERNYATAAN
Yang bertanda tangan dibawah ini : NAMA
: HADI USMAN
NIM
: 07560299
FAK./JUR.
: TEKNIK / INFORMATIKA
Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “RANCANG BANGUN GAME SCRAMBLE DENGAN ALGORITMA DEPTH FIRST SEARCH (DFS) BERBASIS ANDROID” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku.
Mengetahui,
Malang, 26 April 2013
Dosen Pembimbing
Yang Membuat Pernyataan
Yuda Munarko S.Kom, M.Sc. NIP : 108.0611.0443
Hadi Usman NIM : 07560299
iii
KATA PENGANTAR Dengan memanjatkan puji syukur kehadirat Alloh SWT. Atas segala limpahan rahmat dan hidayah-NYA sehingga peneliti dapat menyelesaikan Tugas Akhir yang berjudul : “RANCANG BANGUN GAME SCRAMBLE DENGAN ALGORITMA DEPTH FIRST SEARCH (DFS) BERBASIS ANDROID”
Di dalam tulisan ini disajikan pokok-pokok bahasan yang meliputi : 1. Perancangan dan implementsi pembuatan game scramble berbasis mobile berbasis android dengan mengimplementasikan algoritma Depth First Search. 2. Melakukan pengujian dari berbagai sudut pandang dan kemampuaan penelusuran tree dalam penemuan solusi goal state. 3. Pengamatan hasil penelusuran dan penemuan solusi dengan tujuan untuk ditarik sebuah kesimpulan dari keseluruhan kegiatan.
Peneliti menyadari sepenuhnya bahwa dalam penulisan Tugas Akhir ini masih banyak kekurangan dan keterbatasan. Oleh karena itu peneliti mengharapkan saran yang membangun agar tulisan ini bermanfaat bagi perkembangan ilmu pengetahuan kedepan.
Malang, 26 April 2013
Penulis
vii
DAFTAR ISI
LEMBAR PERSETUJUAN .................................................................................. i LEMBAR PENGESAHAN .................................................................................. ii LEMBAR PERNYATAAN ................................................................................ iii ABSTRAK ......................................................................................................... iv ABSTRACT ........................................................................................................ v LEMBAR PERSEMBAHAN .............................................................................. vi KATA PENGANTAR ....................................................................................... vii DAFTAR ISI .................................................................................................... viii DAFTAR GAMBAR .......................................................................................... xi DAFTAR TABEL ............................................................................................ xiv BAB I : PENDAHULUAN 1.1 Latar Belakang ............................................................................................... 1 1.2 Rumusan Masalah .......................................................................................... 2 1.3 Tujuan Masalah.............................................................................................. 2 1.4 Batasan Masalah ............................................................................................ 2 1.5 Metodologi Masalah....................................................................................... 2 1.6 Sistematika Penulisan ..................................................................................... 3 BAB II : LANDASAN TEORI 2.1 Acuan Penelitian Sebelumnya ........................................................................ 5 2.2 Graph ............................................................................................................. 5 2.2.1 Definisi Graph ......................................................................................... 5 2.2.2 Pengelompokan Graph ............................................................................. 6 2.3 Random Pengacakakan .................................................................................. 7 2.4 Algoritma Depth First Search (DFS) .............................................................. 8 2.4.1 Pengertian Algoritma Depth First Search ................................................. 8 2.4.2 Terminologi Penerapan Algoritma Depth First Search (DFS) ................. 10 2.4.3 Tree (Pohon) Pelacakan ......................................................................... 11 2.4.4 Kelebihan dan Kekurangan Depth First Search (DFS) ............................ 17 2.5 Game ........................................................................................................... 17 2.5.1 Sejarah Game ........................................................................................ 17
viii
2.5.2 Definisi Game ........................................................................................ 18 2.5.3 Klasifikasi Game ................................................................................... 19 2.6 Permainan Scramble..................................................................................... 20 2.6.1 Pengertian Permainan Scramble ............................................................. 20 2.6.2 Peraturan Permainan Scramble .............................................................. 20 2.7 Android ........................................................................................................ 21 2.7.1 Sejarah Singkat Android ........................................................................ 21 2.7.2 Definisi Android .................................................................................... 22 2.7.2 Kelebihan Android................................................................................. 23 2.7.4 Arsitektur Android ................................................................................. 24 2.7.4.1 Application Wedgets ................................................................... 24 2.7.4.2 Application Framework ............................................................... 25 2.7.4.3 Android Runtime......................................................................... 26 2.7.4.4 Libraries ..................................................................................... 26 2.7.4.2 Linux Kernel ............................................................................... 27 2.4 Komponen Android ................................................................................... 27 BAB III : ANALISA DAN PERANCANGAN SISTEM 3.1 Analisa Masalah ........................................................................................... 29 3.2 Analisa kebutuhan Sistem ............................................................................ 29 3.3 Perancangan Sistem ..................................................................................... 30 3.4 Perancangan Proses Aplikasi ........................................................................ 32 3.4.1 Pengumpulan Proses Aplikasi ................................................................ 32 3.4.2 Random (Pengacakan) ........................................................................... 34 3.4.3 Alur Diagram Algoritma Depth First Search (DFS)................................ 35 3.4.4 Alur Diagram Permainan ....................................................................... 36 3.4.5 Unified Modelling Language (UML) ..................................................... 38 3.4.5.1 Use Case Diagram ....................................................................... 38 3.4.5.2 Activity Diagram......................................................................... 39 3.4.5.3 Squence Diagram ........................................................................ 44 3.4.5.4 Class Diagram ............................................................................. 48 3.5 Perancangan Antar Muka ............................................................................. 48 3.5.1 Form Menu Utama ................................................................................. 48
ix
3.5.2 Menu Play Game ................................................................................... 49 3.5.3 Form Permainan Scramble ..................................................................... 50 3.5.4 Form Menu Next Level .......................................................................... 50 3.5.5 Form Menu Setting ................................................................................ 51 3.5.6 Form Menu HighScore .......................................................................... 52 3.5.7 Form Menu Help ................................................................................... 52 3.5.8 Form Menu Exit .................................................................................... 53 BAB IV : IMPLEMENTASI DAN ANALISA SISTEM 4.1 Implementasi Perankat Lunak ...................................................................... 54 4.1.1 Implementasi Antar Muka...................................................................... 54 4.1.1.1 Tampilan Menu Home................................................................. 54 4.1.1.2 Tampilan Menu Play Game ......................................................... 55 4.1.1.3 Tampilan Menu Setting ............................................................... 56 4.1.1.4 Tampilan Menu HighScore ......................................................... 56 4.1.1.5 Tampilan Menu Help .................................................................. 57 4.1.1.6 Tampilan Menu Exit.................................................................... 58 4.1.2 Implementasi Proses .............................................................................. 58 4.1.2.1 Kode Program Fungsi Generate .................................................. 58 4.1.2.2 Kode Program Menu Utama ........................................................ 61 4.1.2.3 Kode Program Menu Setting ....................................................... 62 4.1.2.4 Kode Program HighScore............................................................ 63 4.1.3 Pengujian Rule Game ............................................................................ 64 4.1.4 Pengujian Pengguna ............................................................................... 93 BAB V : PENUTUP 5.1 Kesimpulan .................................................................................................. 94 5.2 Saran............................................................................................................ 94 DAFTAR PUSTAKA ....................................................................................... 95 BIOGRAFI PENULIS
x
DAFTAR GAMBAR
Gambar 2.1 Graph Sederhana, Multiplegraph, Graph Semu ................................ 6 Gambar 2.2 Undirected Graph, Directed Graph.................................................... 7 Gambar 2.3 Penelusuran pohon permainan dengan DFS ...................................... 9 Gambar 2.4 Contoh Graph Yang Berisi Path Antar Kota .................................... 11 Gambar 2.5 Sruktur dari Graph Gambar 2.4 ....................................................... 12 Gambar 2.6 Tree untuk Depth First Search ........................................................ 13 Gambar 2.7 Langkah Awal ................................................................................ 13 Gambar 2.8 Langkah 1 ....................................................................................... 14 Gambar 2.9 Langkah 2 ....................................................................................... 14 Gambar 2.10 Langkah 3 ..................................................................................... 15 Gambar 2.11 Langkah 4 ..................................................................................... 15 Gambar 2.12 Langkah 5 ..................................................................................... 16 Gambar 2.13 Arsitektur Android ........................................................................ 24 Gambar 3.1 Sebuah kamus menggunakan trie .................................................... 33 Gambar 3.2 DAWG ........................................................................................... 34 Gambar 3.3 Flowchart Random ......................................................................... 34 Gambar 3.4 Alur DFS dalam pencarian pohon Graf ........................................... 36 Gambar 3.5 Flowchart Sistem Permainan........................................................... 37 Gambar 3.6 Use Case Diagram .......................................................................... 38 Gambar 3.7 Activity Diagram Menu Play Game ................................................ 40 Gambar 3.8 Activity Diagram Menu Add New User ........................................... 41 Gambar 3.9 Activity Diagram Menu Existing User ............................................ 41 Gambar 3.10 Activity Diagram Level Permainan ............................................... 42 Gambar 3.11 Activity Diagram Setting (pengaturan) ......................................... 43 Gambar 3.12 Activity Diagram highscore .......................................................... 43 Gambar 3.13 Activity Diagram Permainan Game .............................................. 44 Gambar 3.14 Sequence Diagram Menu Play Game ............................................ 45 Gambar 3.15 Sequence Diagram Menu Add New User ....................................... 45 Gambar 3.16 Sequence Diagram Menu Existing User ........................................ 46 Gambar 3.17 Sequence Diagram Setting (Pengaturan)....................................... 46
xi
Gambar 3.18 Sequence Diagram Highscore ....................................................... 47 Gambar 3.19 Sequence Diagram Level ............................................................... 47 Gambar 3.20 Class Diagram .............................................................................. 48 Gambar 3.21 Form Menu Utama ....................................................................... 49 Gambar 3.22 Form Menu Play Game ................................................................. 49 Gambar 3.23 Form Menu Permainan Scramble .................................................. 50 Gambar 3.24 Form Menu Nect Level................................................................. 51 Gambar 3.25 Form Menu Setting ....................................................................... 51 Gambar 3.26 Form Menu Highscore .................................................................. 52 Gambar 3.27 Form Menu Help .......................................................................... 52 Gambar 3.28 Form Menu Exit ........................................................................... 53 Gambar 4.1 Tampilan Menu Utama ................................................................... 55 Gambar 4.2 Tampilan Menu User (a) dan Tampilan Menu Play Game (b) ......... 55 Gambar 4.3 Tampilan Menu Setting (a) dan Menu Tampilan board size (b) ....... 56 Gambar 4.4 Tampilan Menu Highscore.............................................................. 57 Gambar 4.5 Uji Coba Menu Help ....................................................................... 57 Gambar 4.6 Tampilan Menu Exit ....................................................................... 58 Gambar 4.7 Uji Coba Tampilan Menulis Username Pemain ............................... 64 Gambar 4.8 Penelusuran Tree Pencarian Solusi Level 1 ..................................... 68 Gambar 4.9 Uji Coba Tampilan Level 1 ............................................................. 69 Gambar 4.10 Uji Coba Temuan Kata Pertama .................................................... 69 Gambar 4.11 Uji Coba Temuan Kata Kedua ...................................................... 70 Gambar 4.12 Uji Coba Temuan Kata ketiga ....................................................... 70 Gambar 4.13 Uji Coba Temuan Kata keempat ................................................... 71 Gambar 4.14 Uji Coba Temuan Kata kelima ...................................................... 71 Gambar 4.15 Uji Coba Next Level 2 .................................................................. 72 Gambar 4.16 Uji Penelusuran Tree Pencarian Solusi Level 2 ............................. 75 Gambar 4.17 Uji Coba Tampilan Level 2 ........................................................... 76 Gambar 4.18 Uji Coba Temuan Kata Pertama .................................................... 76 Gambar 4.19 Uji Coba Temuan Kata Kedua ...................................................... 77 Gambar 4.20 Uji Coba Temuan Kata Ketiga ...................................................... 77 Gambar 4.21 Uji Coba ke Level 3 ...................................................................... 78
xii
Gambar 4.22 Uji Penelusuran Tree Pencarian Solusi Level 3 ............................. 81 Gambar 4.23 Uji Coba Tampilan Level 3 ........................................................... 82 Gambar 4.24 Uji Coba ke Level 4 ...................................................................... 83 Gambar 4.25 Uji Penelusuran Tree Pencarian Solusi Level 4 ............................. 86 Gambar 4.26 Uji Coba Tampilan Level 4 ........................................................... 87 Gambar 4.27 Uji Uji Coba Temuan Kata Pertama .............................................. 87 Gambar 4.28 Uji Coba Temuan Kata Kedua ...................................................... 88 Gambar 4.29 Uji Coba Temuan Kata Ketiga ...................................................... 88 Gambar 4.30 Uji Coba ke Level 5 ...................................................................... 88 Gambar 4.31 Uji Penelusuran Tree Pencarian Solusi Level 5 ............................. 90 Gambar 4.32 Uji Coba Tampilan Level 5 ........................................................... 91 Gambar 4.33 Uji Coba Temuan Kata Pertama .................................................... 91 Gambar 4.34 Uji Coba Tampilan Game Over..................................................... 92 Gambar 4.35 Uji Coba Tampilan HighScore ...................................................... 92
xiii
DAFTAR TABEL
Tabel 3.1 Tabel Kebutuhan Aplikasi .................................................................. 30 Tabel 3.2 Tabel Rincian Use Case Diagram ....................................................... 39 Tabel 4.1 Inisialisai untuk menampung karakter dan Inisialisasi vertek .............. 59 Tabel 4.2 Kode Program pengacakan ................................................................. 60 Tabel 4.3 Penelusuran vertek ............................................................................. 60 Tabel 4.4 Kode Program Menu Utama ............................................................... 61 Tabel 4.5 Kode Program Setting ........................................................................ 62 Tabel 4.6 Kode Program preferences.xml .......................................................... 62 Tabel 4.7 Kode Program Array.xml ................................................................... 62 Tabel 4.8 Kode Program untuk Inisialisasi Menampilkan Board Permainan ....... 63 Tabel 4.9 Kode Program Inisialisasi Variabel High Score ................................ 63 Tabel 4.10 Proses Pemanggilan semua character Huruf yang akan diacak .......... 65 Tabel 4.11 Proses Pengacakan huruf pada Level 1 ............................................. 66 Tabel 4.12 Proses Pemanggilan semua character Huruf yang akan diacak .......... 72 Tabel 4.13 Proses Pengacakan huruf pada Level 2 ............................................. 73 Tabel 4.14 Proses Pemanggilan semua character Huruf yang akan diacak .......... 78 Tabel 4.15 Proses Pengacakan huruf pada Level 3 ............................................. 80 Tabel 4.16 Proses Pemanggilan semua character Huruf yang akan diacak .......... 83 Tabel 4.17 Proses Pengacakan huruf pada Level 4 ............................................. 84 Tabel 4.18 Proses Pengacakan huruf pada Level 5 ............................................. 84 Tabel 4.19 Pengujian Pengguna ......................................................................... 93
xiv
DAFTAR PUSTAKA [1]
Dimas Tri Ciputra, 2011. “Penerapan Algoritma DFS dalam Menemukan Solusi pada Permainan Loop The Loop”, Bandung, ITB.
[2]
Evan, 2008. “Penggunaan Depth-First Search Dalam Pengambilan Keputusan pada Klimaks Permainan Scrabble”, Bandung, ITB.
[3]
Halida Astatin, 2009. “The Application Of Depth First Search And Backtracking in Solving mastermind Game”, Bandung, ITB.
[4]
Ivan Michael Siregar, “Membongkar Source Code Berbagai Aplikasi Android”, Graha Media, 2011.
[5]
Ivan Michael Siregar, “Mengembangkan Aplikasi Enterprise Berbasis Android”, Graha Media, 2010.
[6]
Muhammad Luthfi. “Perbandingan Beberapa Algoritma Penyelesaian Permasalahan Labirin”, Bandung, ITB.
[7]
Noswa Sabdifha, 2010. “Perancangan dan Pembuatan Aplikasi Word Game Scramble pada Dua Dimensi”, Surabaya, ITS.
[8]
Prisyafandiafif Charifa, 2012. “Penerapan Algoritma Depth-First Search dan Backtracking dalam Program pembentukan Maze”, Bandung, ITB.
[9]
Suyanto, 2004. “Depth First Search Antara Fungsional dan Imperatif”, Sumatra Utara, USU.
[10]
Rachmansyah Budi Setiawan.2010. “Penerapan Algoritma DFS dan BFS Dalam Permainan Atlanteine”, Bandung, ITB.
[11]
Tjatur Kandaga, Alvin Hapendi. 2008. “Evaluasi dan Optimalisasi Algoritma Depth First Search dan Breadth Fisrt Search dengan Penerapan pada Aplikasi Rat Race dan Web Peta”, bandung, UKM.
95
