rancang bangun game scramble dengan … · gambar 3.4 alur dfs dalam pencarian pohon graf ......
TRANSCRIPT
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
i
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
Yuda Munarko, S.Kom,M.Sc.
NIP : 108.0611.0443
Pembimbing II
Nur Hayatin, S.ST.
NIP : 108.0907.0476
ii
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
Eko Budi C, S.Kom, M.T.
NIP : 108.9504.0330
Penguji II
Aminudin, S.Kom.
NIDN : 0701068603
Mengetahui,
Ketua Jurusan Teknik Informatika
Eko Budi C, S.Kom, M.T.
NIP : 108.9504.0330
iii
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,
Dosen Pembimbing
Yuda Munarko S.Kom, M.Sc.
NIP : 108.0611.0443
Malang, 26 April 2013
Yang Membuat Pernyataan
Hadi Usman
NIM : 07560299
vii
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
viii
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
ix
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
x
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
xi
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
xii
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
xiii
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
xiv
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
95
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.