Implementasi Algoritma A* untuk Pencarian Solusi pada Game 8-Puzzle berbasis Android. Abstrak

Implementasi Algoritma A* untuk Pencarian Solusi pada Game 8-Puzzle berbasis Android Gagah Randah Satria1 Jurusan Teknik Informatika, Fakultas Ilmu Komputer Universitas Dian Nuswantoro Jl. Nakula I No 5-11 Semarang 50131 Indonesia Email : [email protected]

Abstrak Aplikasi permainan (game) saat ini telah menjadi bagian yang tidak terpisahkan dari pengguna mobile phone Android. Banyak pengembang aplikasi game yang menyadari potensi berjualan di Play Store dengan menyasar pengguna smartphone dan tablet Android. Dari game puzzle sederhana yang tidak membutuhkan spesifikasi sistem yang tinggi, hingga game-game yang berat. Satu tipe game puzzle adalah 8-puzzle. Pada permainan ini, pemain harus mengurutkan angka-angka dari angka yang diacak dan batasan ruang yang ada. 8puzzle merupakan sebuah permainan yang menggunakan teknik pencarian (searching) yaitu algoritma A*. Tujuan dari penelitian ini adalah penulis dapat menerapkan algoritma A* pada game 8-puzzle, dan juga membangun game 8-puzzle yang berbasis android. Dengan tujuan tersebut tentunya penulis mengharapkan hasil yaitu algoritma A* dapat menjadi pencarian solusi yang tepat untuk menyelesaikan game 8-puzzle dan dapat membangun game 8-puzzle yang berbasis android. Laporan tugas akhir ini akan menguraikan analisa dan desain game 8puzzle yang berbasis android. Penjelasan Algoritma A* pada game 8-puzzle. Lalu pada tahap akhir pengembangan dilakukan evaluasi terhadap proses dan hasilnya pada bagian akhir laporan ini. Kata Kunci : Android, 8-puzzle, Algoritma A*. BAB I PENDAHULUAN 1.1

Latar Belakang Aplikasi permainan (game) saat ini telah menjadi bagian yang tidak terpisahkan dari pengguna mobile phone. Salah satu perangkat yang paling banyak digunakan yaitu Android. Berdasarkan yang dikutip dari kompas.com menyatakan bahwa, "Banyak pengembang aplikasi game yang menyadari potensi berjualan di Play Store dengan menyasar pengguna smartphone dan tablet Android. Mulai dari game sederhana hingga yang bertema olah raga dan strategi, Android memiliki semuanya. Game-game Android banyak

jenisnya. Pengguna bisa memilihnya sesuai dengan spesifikasi smartphone dan tablet yang dimiliki. Dari game puzzle sederhana yang tidak membutuhkan spesifikasi sistem yang tinggi, hingga game-game yang berat" [1]. Puzzle merupakan salah satu permainan yang cukup memeras otak untuk menyelesaikannya. Pemain ditantang untuk berpikir kreatif bagaimana untuk membuat semua bagian puzzle terletak pada posisi sebenarnya. Cara memainkannya cukup mudah, pemain

hanya menggeser puzzle satu demi satu sampai akhirnya semua puzzle terleteak pada posisi sebenarnya [2]. Salah satu tipe game puzzle adalah 8-puzzle. Pada permainan ini, pemain harus mengurutkan angka-angka dari angka yang diacak dan batasan ruang yang ada. Permainan akan berakhir ketika pemain telah mengurutkan angka tersebut [3]. 8-puzzle biasanya diwakili sebagai papan 3 * 3 yang ubinnya terdiri dari angka 1 sampai 8 yang disusun dari atas kiri sampai kanan bawah dari papan permainan (goal board). 8-puzzle merupakan sebuah permainan yang menggunakan teknik pencarian (searching). Teknik pencarian bisa dilakukan dengan menggunakan suatu algoritma untuk mendapatkan suatu solusi atau permasalahan. Banyak sekali teknik pencarian yang bisa dilakukan dan teknikteknik tersebut harus dipilih berdasarkan keriteria permasalahan yang dihadapi dan tingkat kebutuhan yang harus dipenuhi [3]. Salah satu metode searching yang dapat digunakan untuk menyelesaikan permainan 8-Puzzle yaitu algoritma A*. Algoritma ini merupakan algoritma best first search dengan pemodifikasian fungsi heuristik. Heuristik yang diterapkan pada algoritma ini memiliki fungsi untuk meminimumkan total biaya linstasan, dan pada kondisi yang tepat akan memberikan solusi terbaik dalam waktu optimal [4]. Dari berbagai macam metode dan platform yang digunakan untuk menyelesaikan game 8-puzzle, penulis memilih menerapkan metode algoritma A* untuk pencarian solusi pada game 8-puzzle yang ber-platform Android. Pada game 8puzzle, masalah yang sering kali terjadi yaitu saat pemain kesulitan dalam menyelesaikannya. Menurut penelitian yang dilakukan oleh Latius Hermawan dan R. Kristoforus Jawa Bendi mangatakan bahwa, "Terdapat banyak kemungkinan pergeseran yang akan membuat pemain merasa tidak bisa menyelesaikan permainan ini sehingga akan memerlukan banyak waktu untuk dapat

menyelesaikannya" [2]. Untuk itu pemain memerlukan suatu cara yaitu dengan algoritma berpikir komputer yang akan membantu menyelesaikan game 8-puzzle. Berdasarkan analisa dari masalah diatas, maka penulis mengambil judul penelitian "Implementasi algoritma A* untuk Pencarian Solusi pada Game 8puzzle berbasis Android" sehingga diharapkan penerapan algoritma A* dapat menemukan langkah yang optimal dan memudahkan pemain untuk menyelesaikan game 8-puzzle. 1.2

Rumusan Masalah Untuk memperjelas dan mengarahkan penelitian ini agar hasil yang didapat sesuai dengan yang diharapkan maka masalah yang dirumuskan adalah sebagai berikut : 1. Bagaimana penerapan algoritma A* dalam pencarian solusi pada game 8-Puzzle. 2. Bagaimana membangun game 8puzzle berbasis android. 1.3

Batasan Masalah Mengingat luasnya permasalahan yang dibahas, maka perlu adanya pembatasan masalah. Batasan masalah yang diambil antara lain : 1. Pembahasan difokuskan pada pencarian solusi 8-Puzzle dengan menggunakan algoritma A*. 2. Pembahasan meliputi perancangan game 8-Puzzle berbasis Android dengan bahasa pemrograman Java. 3. Ukuran papan dibatasi 3 * 3 saja dan memiliki 9 kotak, yang berisi angka 1 - 8. 4. Analisis pengembangan sistem menggunakan diagram UML. 1.4

Tujuan Penelitian Berdasarkan rumusan masalah dan batasan masalah di atas, maka tujuan dari Tugas Akhir ini adalah : 1. Menerapkan algoritma A* untuk pencarian solusi pada game 8Puzzle.

2.

Dapat membangun game 8-puzzle berbasis android.

1.5 Manfaat Penelitian 1.5.1 Manfaat Bagi Penulis Menambah pengetahuan dan wawasan penulis tentang pembangunan Aplikasi game berbasis Android dan implementasi algoritma A* pada game 8Puzzle serta sebagai penerapan dan pengembangan ilmu yang didapat pada perkuliahan di kehidupan nyata. 1.5.2 Manfaat Bagi Akademik Sebagai tambahan referensi perpustakaan yang dapat dimanfaatkan untuk menambah pengetahuan mahasiswa tentang Aplikasi game berbasis Android dan implementasi algoritma A* pada game 8-Puzzle untuk mengembangkan kurikulum perkuliahan. Dan dapat dijadikan acuan dalam mendidik dan membekali ilmu kepada mahasiswa. 1.5.3 Manfaat Bagi Pengguna Sebagai pengetahuan pengguna tentang penerapan algoritma A* untuk menemukan solusi yang optimal dan memudahakan pengguna untuk menyelesaikan game 8-puzzle. BAB II TINJAUAN PUSTAKA DAN LANDASAN TEORI 2.1

Tinjauan Pustaka Dalam pembuatan skripsi ini, penulis menggunakan beberapa acuan. Acuan pertama dari skripsi ini adalah penelitian yang berjudul "Penerapan Algoritma A* pada Aplikasi Puzzle" [2]. Dalam jurnal tersebut membahas analisis algoritma A* pada aplikasi puzzle. Perbedaan dari penelitian yang penulis buat adalah penerapan algoritma A* pada aplikasi 8-puzzle yang berbasis Android. Acuan kedua dari skripsi ini adalah penelitian yang berjudul "8-puzzle Menggunakan Algoritma Iterative Deepning Search (IDS)" [3]. Dalam

skripsi tersebut membangun aplikasi game 8-puzzle dengan metode algoritma Iterative Deepning Search (IDS) dengan menggunakan Delphi sebagai bahasa pemrograman. Perbedaan dari aplikasi yang penulis buat adalah metode yang menggunakan Algoritma A* dan platform yang digunakan yaitu Android. Acuan ketiga dari penelitian yang berjudul "Penyelesaian Masalah 8-Puzzle dengan Algoritma Hill Climbing Stepest Ascent Loglist Heuristik Berbasis Java" [5]. Dalam jurnal tersebut membangun aplikasi game 8-puzzle menggunakan Java dengan menggunakan metode algoritma Hill Climbing. Perbedaan dari aplikasi yang penulis buat adalah metode yang menggunakan Algoritma A* dan platform yang digunakan yaitu Android. Acuan keempat dari skripsi ini adalah penelitian yang berjudul "Penelitian Rute Terdekat pada Labirin Menggunakan metode A*" [6]. Dalam penelitian tersebut membahas penerapan algoritma A* pada labirin. Perbedaan dari penelitian yang penulis buat adalah penerapan algoritma A* pada aplikasi 8-puzzle. 2.2 Landasan Teori 2.2.1 Algoritma Algoritma adalah urutan langkahlangkah logis penyelesaian masalah yang disusun secara sistematis dan logis1. Kata logis merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar. Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu2. Pertimbangan dalam pemilihan algoritma adalah, pertama algoritma haruslah benar. Artinya algoritma akan memberikan keluaran yang dikehendaki dari sejumlah masukan yang diberikan. Tidak peduli sebagus apapun algoritma, kalau memberikan keluaran yang salah, pastilah algoritma tersebut bukan algoritma yang baik.

Pertimbangan kedua yang harus diperhatikan adalah kita harus mengetahui seberapa baik hasil yang dicapai oleh algoritma tersebut. Hal ini penting terutama pada algoritma untuk menyelesaikan masalah yang memerlukan aproksimasi hasil (hasil yang hanya berupa pendekatan). Algoritma yang baik harus mampu memberikan hasil yang sedekat mungkin dengan nilai yang sebenarnya. Ketiga adalah efisiensi algoritma. Efisiensi algoritma dapat ditinjau dari 2 hal yaitu efisiensi waktu dan memori. Meskipun algoritma memberikan keluaran yang benar (paling mendekati), tetapi jika kita harus menunggu berjam-jam untuk mendapatkan keluarannya, algoritma tersebut biasanya tidak akan dipakai, setiap orang menginginkan keluaran yang cepat. Begitu juga dengan memori, semakin besar memori yang terpakai maka semakin buruklah algoritma tersebut. Dalam kenyataannya, setiap orang bisa membuat algoritma yang berbeda untuk menyelesaikan suatu permasalahan, walaupun terjadi perbedaan dalam menyusun algoritma, tentunya kita mengharapkan keluaran yang sama. Jika terjadi demikian, carilah algoritma yang paling efisien dan cepat. 2.2.1.1 Algoritma dan Program Program adalah kumpulan pernyataan komputer, sedangkan metode dan tahapan sistematis dalam program adalah algoritma. Program ditulis dengan menggunakan bahasa pemrograman. Jadi bisa disebut bahwa program adalah suatu implementasi dari bahasa pemrograman3. Beberapa pakar memberi formula bahwa: Program = Algoritma + Bahasa (Struktur Data) Bagaimanapun juga struktur data dan algoritma berhubungan sangat erat pada sebuah program. Algoritma yang baik tanpa pemilihan struktur data yang tepat akan membuat program menjadi kurang baik, demikian juga sebaliknya.

2.2.1.2 Metode Searching Pada dasarnya teknik searching (pencarian) dapat dibagi menjadi 2 (dua) kelompok besar, yaitu pencarian buta (blind search) dan pencaraian termbimbing (heuristic search). Untuk mengukur performa metode pencarian, terdapat empat kriteria yang dapat dilakukan, yaitu : 1. Completeness : Apakah metode tersebut menjamin adanya solusi jika solusinya ada? 2. Time Complexity : Berapa lama waktu yang diberikan untuk menemukan solusi tersebut? 3. Space Complexity : Berapa banyak memori yang dibutuhkan untuk menemunkan solusi tersebut? 4. Optimality : Apakah metode tersebut menjamin menemukan solusi terbaik jika terdapat beberapa solusi yang berbeda? Pencarian buta (blind search) atau uninformed search terdiri dari 2 algoritma yaitu : 1. BFS (Breadth-First Search) atau Pencarian Melebar Pertama. 2. DFS (Depth-First Search) atau Pencarian Mendalam Pertama. Teknik pencarian heuristik (heuristic-searching) merupakan suatu strategi untuk melakukan proses pencarian secara selektif dan dapat memandu proses pencarian yang memiliki kemungkinan sukses paling besar, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Untuk menerapkan pencarian heuristik diperlukan suatu Fungsi Heuristik. Fungsi heuristik adalah atura-aturan yang digunakan untuk mendapatkan solusi yang diinginkan. Pencarian Heuristic terdiri dari : 1. Generate and Test (Pembangkitan dan Pengujian) 2. Hill Climbing (Pendakian Bukit) a. Simple Hill Climbing b. Steepest-Ascent Hill Climbing 3. Best First Search 4. Algoritma A*

5. Simulated Annelaing [7]. 2.2.1.3 Algoritma A* Algoritma ini pertama kali ditemukan pada tahun 1968 oleh Peter Hart, Nilsson dan Bertram Raphael. Dalam tulisan mereka, algoritma ini dinamakan Algoritma A. Penggunaan algoritma ini dengan fungsi heuristik yang tepat dapat memberikan hasil yang optimal, maka algoritma inipun disebut A*. A* merupakan salah satu contoh algoritma pencarian yang cukup popular di dunia. Jika kita mengetikkan Algoritma A* pada sebuah mesin pencari, seperti google.com, maka akan kita temukan lebih dari sepuluh ribu literatur mengenai algoritma A*. Algoritma A* merupakan algoritma yang membantu menemukan solusi pencarian ruang keadaan dengan mempertimbangkan total biaya lintasan yang akan dilacak sesuai dnegan node yang akan dilewati. Masalah ruang keadaan disebut juga dengan state space problem. Ruang keadaan (state space) merupakan suatu ruang yang berisi semua keadaan yang mungkin dalam suatu kasus AI. State adalah representasi suatu keadaan pada suatu saat ataupun dekripsi konfigurasi sistem. State space adalah semua state (keadaan) yang mungkin, dan biasanya digambarkan sebagai jaringan dengan verteks merupakan state dan edge merupakan perubahan yang mungkin.[2]. Aliran algoritma A* ditunjukkan pada gambar berikut.

Beberapa terminologi dasar yang terdapat pada Algoritma A* adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable). Starting point adalah sebuah terminologi untuk posisi awal sebuah benda. A adalah node yang sedang dijalankan dalam algoritma pencarian jalan terpendek. Node adalah petak-petak kecil sebagai representasi dari area path finding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga. Open list adalah tempat meyimpan data node yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan. Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan, Simpul tujuan adalah simpul yang akan dituju. Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A. A* memiliki 2 fungsi utama dalam menentukan solusi terbaik. Fungsi pertama disebut sebagai g(n) merupakan fungsi yang digunakan untuk menghitung total cost dari starting point menuju node tertentu. Fungsi kedua yang biasa disebut sebagai h(n) merupakan fungsi perkiraan total cost yang diperkirakan dari suatu node ke node akhir. Pada A*, setiap node dari node awal ditelusuri kemudian dihitung cost dari tiap-tiap node dan dimasukkan ke tabel prioritas. Node dengan cost paling rendah akan diberikan tingkat prioritas paling tinggi. Kemudian pencarian dilanjutkan dengan nilai prioritas tertinggi pada tabel.

Gambar 1. Alur Algoritma A*

f(n) = g(n) + h(n)

dengan : n = posisi koordinat node f(n) = fungsi evaluasi g(n) = biaya (cost) yang sudah dikeluarkan dari keadaan awal sampai keadaan n h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n [8]. 2.2.1.4 Fungsi Heuristik Manhattan Distance Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individiual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. A* sebagai algoritma pencarian yang menggunakan fungsi heuristik untuk pencarian rute node-node pada peta [8]. Heuristik yang paling umum digunakan adalah jarak Manhattan. Fungsi heuristik ini hanya akan menjumlahkan selisih nilai x dan nilai y dari dua buah titik. Heuristik dinamakan Manhattan mungkin karena di kota Manhattan di Amerika, jarak dari dua lokasi umumnya dihitung dari blok-blok yang harus dilalui saja dan tentunya tidak bisa dilintasi secara diagonal. Perhitungannya dalat ditulis sebagai berikut: h(n) = abs(n.x-tujuan.x) + abs(n.ytujuan.y) [2]. Dimana h(n) adalah sebuah fungsi heuristik. D (distance) adalah jarak dari node awal (strating point) menuju node tujuan (goal) [8]. 2.2.2 Game Game adalah sesuatu yang dapat dimainkan dengan aturan tertentu sehingga ada yang menang dan ada yang kalah, biasanya dalam konteks tidak serius atau

dengan tujuan refreshing. Suatu cara belajar yang digunakan dalam menganalisa interaksi antara sejumlah pemain maupun perorangan yang menunjukkan strategistrategi yang rasional [8]. 2.2.2.1 Permainan Puzzle Permainan 8-puzzle ini mempunyai peraturan yang cukup sederhana. Pada permainan ini, pemain harus mengurutkan angka-angka dari angka yang diacak dan batasan ruang yang ada. Permainan akan berakhir ketika pemain telah mengurutkan angka tersebut [3]. 8-puzzle biasanya diwakili sebagai papan 3 * 3 yang ubinnya terdiri dari angka 1 sampai 8 yang disusun dari atas kiri sampai kanan bawah dari papan permainan (goal board). Permainan ini diwakili dengan papan n * n yang memiliki angka dari 0 sampai (n 2 – 2) sebagimana pada masing-masing kolom dan baris merupakan indeks dari 0.

Gambar 2. Permainan 8-Puzzle

Ubin yang tersisa (kanan bawah) adalah kosong, karena akan digunakan untuk pergeseran ubin yang lain yang berada dalam papan permainan. Teka-teki dimainkan dengan menyusun ubin ke papan dan mencoba untuk menyelesaikannya dengan menciptakan kembali papan tujuan. Hal ini dicapai dengan menggerakkan ubin kembali ke posisi papan tujuan pada ruang kosong disekitar papan [2]. Adapun status dari 8-puzzle ini adalah ubin (tile) yang bisa dipindah posisinya, 8-puzzle memiliki maksmial 4 aksi yaitu ubin digeser ke atas, digeser ke kiri, digeser ke kanan, dan digeser ke

bawah dilihat dari letak ubin yang kosong. Jadi pada kasus ini ubin yang kosong harus digeser untuk menghasilkan solusi yang diinginkan [3]. 2.2.3 Android Android adalah sebuah sistem operasi untuk perangkat mobile berbasis linux yang mencakup sistem operasi, middleware dan aplikasi. Android menyediakan platform terbuka bagi para pengembang untuk menciptakan aplikasi mereka. Awalnya, Google Inc. membeli Android Inc. yang merupakan pendatang baru yang membuat piranti lunak untuk ponsel/smartphone. Kemudian untuk mengembangkan Android, dibentuklah Open Handset Alliance, konsorsium dari 34 perusahaan peranti keras, peranti lunak dan telekomunikasi, termasuk Google, HTC, Intel, Motorola, Qualcomm, TMobile dan Nvidia. Android dipuji sebagai “platform mobile pertama yang Lengkap, Terbuka dan Bebas”. 2.2.3.1 IDE Eclipse Pengembang memiliki beberapa pilihan ketika membuat aplikasi yang berbasis Android. Sebagian besar pengembang menggunakan Eclipse yang tersedia secara bebas untuk merancang dan mengembangkan aplikasi Android. Eclipse adalah IDE yang paling populer untuk pengembangan Android, karena memiliki Android plug-in yang tersedia untuk memfasilitasi pengembangan Android. Selain itu, Eclipse juga mendapat dukungan langsung dari Google untuk menjadi IDE pengembangan aplikasi Android, ini terbukti dengan adanya penambahan plugins untuk eclipse untuk membuat project android di mana source software langsung dari situs resminya Google. Akan tetapi, hal diatas tidak menutup kemungkinan untuk menggunakan IDE yang lain seperti Netbeans untuk melakukan pengembangan Android.

2.2.3.2 Android SDK (Software Development Kit) Android SDK adalah tools API (Application Programming Interface) yang diperlukan untuk mulai mengembangkan aplikasi pada platform Android menggunakan bahasa pemrograman Java. Android merupakan subset perangkat lunak untuk ponsel yang meliputi sistem operasi, middleware dan aplikasi kunci yang di-release oleh Google. Saat ini disediakan Android SDK (Software Development Kit) sebagai alat bantu dan API untuk mulai mengembangkan aplikasi pada platform Android menggunakan bahasa pemrograman Java. Sebagai platform aplikasi-netral, Android memberi Anda kesempatan untuk membuat Aplikasi yang kita butuhkan yang bukan merupakan aplikasi bawaan Handphone/Smarphone. 2.2.3.3 ADT (Android Development Tools) Android Development Tools (ADT) adalah plugin yang didesain untuk IDE Eclipse yang memberikan kita kemudahan dalam mengembangkan aplikasi android dengan menggunakan IDE Eclipse. Dengan menggunakan ADT untuk Eclipse akan memudahkan kita dalam membuat aplikasi project android, membuat GUI aplikasi dan menambahkan komponenkomponen yang lainnya, begitu juga kita dapat melakukan running aplikasi menggunakan Android SDK melalui Eclipse. Dengan ADT juga kita dapat melakukan pembuatan package Android (.apk) yang digunakan untuk distribusi aplikasi android yang kita rancang. 2.2.4 Pemodelan dan UML Pada perkembangan teknologi perangkat lunak, diperlukan adanya bahasa yang digunakan untuk memodelkan perangkat lunak yang akan dibuat dan perlu adanya standarisasi agar orang di berbagai negara dapat mengerti pemodelan perangkat lunak. Seperti yang kita ketahui bahwa menyatukan banyak kepala untuk

menceritakan sebuah ide dengan tujuan untuk memahami hal yang sama tidaklah mudah, oleh karena itu di perlukan sebuah bahasa pemodelan perangkat lunak yang dapat dimengerti oleh banyak orang.

2.2.4.3 Sequence Diagram Diagram sekuen menggambarkan kelakuan objek pada use case dengan mendeskripsikan waktu hidup objek dan message yang dikirimkan dan diterima antar objek.

2.2.4.1 Use Case Diagram Use Case atau diagram use case merupakan pemodelan untuk kelakuan (behavior) sistem informasi yang akan dibuat. Use case digunakan untuk mengetahui fungsi apa saja yang ada di dalam sebuah sistem informasi dan siapa saja yang berhak menggunakan fungsifungsi itu. Contoh dari diagram use case ditunjukkan pada gambar berikut.

Gambar 3. Sequence Diagram

BAB III METODOLOGI PENELITIAN 3.1 Gambar 4. Use Case Diagram

2.2.4.2 Activity Diagram Diagram aktivitas atau activity diagram menggambarkan workflow (aliran kerja) atau aktivitas dari sebuah sistem atau proses bisnis atau menu yang ada pada perangkat lunak. Contoh activity diagram ditunjukkan pada gambar berikut.

Gambar 5. Activity Diagram

Instrumen Penelitian sMeliputi bahan dan peralatan dalam melakukan penelitian, dalam penelitian ini diperlukan beberapa perangkat agar penelitian dapat berjalan dengan lancar dan sesuai dengan tema penelitian. Perangkat tersebut dibagi menjadi dua yaitu perangkat lunak dan perangkat keras. 3.1.1 Perangkat Lunak Merupakan perangkat lunak yang digunakan dalam penelitian ini. Software yang digunakan antara lain : 1. Microsoft Windows 7 Ultimate 64bit (6.1, Build 7601) digunakan sebagai sistem operasi. 2. Eclipse IDE, yang merupakan platform yang bersifat open source. 3. ADT (Android Development Tools) plug-in yang merupakan plug-in tambahan untuk pengembangan aplikasi menggunakan Ecplise IDE. 4. Android SDK (Software Development Kit), digunakan untuk mengembangkan aplikasi pada OS Android pada komputer dengan menyediakan platform Android

beserta tools tambahan untuk yang dimiliki pada perangkat Android. 5. Android AVD (Android Virtual Device), digunakan sebagai virtual device untuk menjalankan aplikasi pada OS Android. 6. Enterprise Architect, digunakan untuk membantu penulis dalam pembuatan diagram-diagram UML. 3.1.2 Perangkat Keras Merupakan perangkat keras yang digunakan dalam penelitian ini. Hardware yang digunakan antara lain : 1. Notebook HP Pavilion g4. a. Intel(R) Core(TM) i3-2310, CPU 2.10GHz b. Radeon (TM) HD 6470M 1GB c. RAM 8GB DDR3 d. Hardisk 500GB 2. Perangkat Bergerak (mobile phone). Sony Xperia M C1905, Android Jellybean 4.1.2, 540 x 960 pixels, 4.0 inches. 3.1.3 Objek Penelitian Objek penelitian merupakan permasalahan yang diteliti. Objek dari penelitian ini adalah buku, jurnal dan penelitian yang telah diteliti oleh penulis sebagai tinjauan pustaka. 3.2

Jenis dan Sumber data Data merupakan keterangan tentang suatu hal, dapat berupa sesuatu yang diketahui atau yang dianggap atau anggapan, atau suatu fakta yang digambarkan berupa angka, simbol, kode dan lain-lain. Dalam tugas akhir ini, jenis data yang digunakan adalah : 1. Data Kualitatif Data kualitatif dibutuhkan untuk mengedintifikasi mekanisme utama dari data yang harus dianalisis seperti komposisi tampilan. Dalam tugas akhir ini menggunakan software pendukung yang meliputi IDE Eclipse, Android SDK, Android AVD dan Enterprise Architect.

2. Data Kuantitatif Data kuantitatif digunakan untuk mengetahui materi pembelajaran yang diperoleh dari buku-buku, dokumen serta ilmu pengetahuan dari berbagai sumber yang dibaca penulis dan berhubungan dengan tugas akhir ini. Data ini berupa materi tentang Android dan metode pencarian algoritma A*. 3.3

Metode Pengumpulan Data Adapun metode yang digunakan penulis untuk mendapatkan data-data diatas adalah sebagai berikut : a. Studi Literatur Studi Literatur yaitu mengumpulkan bahan-bahan yang tertulis berupa data-data yang diperoleh dari jurnal-jurnal yang diteliti oleh penulis dan berhubungan dengan penelitian yang digunakan. Jurnal yang diteliti antara lain yang berjudul "Penyelesaian Masalah 8Puzzle dengan Algoritma Hill Climbing Stepest Ascent Loglist Heuristik Berbasis Java", "8-puzzle Menggunakan Algoritma Iterative Deepning Search (IDS)", " Penelitian Rute Terdekat pada Labirin Menggunakan metode A*" dan "Penerapan Algoritma A* pada Aplikasi Puzzle". 3.4 Metode Pengembangan Sistem 3.4.1 Extreme Programming Extreme Programming (XP) adalah metode pengembangan perangkat lunak yang ringan dan termasuk salah satu agile methods yang dipelopori oleh Kent Beck, Ron Jeffries dan Ward Cunningham. XP merupakan agile methods yang paling banyak digunakan dan menjadi sebuah pendekatan yang sangat terkenal. Sasaran XP adalah tim yang dibentuk berukuran antara kecil sampai medium saja, tidak perlu menggunakan sebuah tim yang besar. Hal ini dimaksudkan untuk menghadapi requirements yang tidak jelas maupun terjadinya perubahan-perubahan requirements yang sangat cepat.

3.4.1.1 Tahapan Extreme Programming Adapun tahapan-tahapan yang ada pada metode pengembangan sistem Extreme Programming yaitu [12] :

BAB IV RANCANGAN SISTEM DAN IMPLEMENTASI 4.1

Gambar 6. Tahapan XP

1.

XP Planning Aktivitas planning pada model proses XP berfokus pada mendapatkan gambaran fitur serta fungsi dari perangkat lunak yang akan dibangun. 2. XP Design Aktivitas design dalam pengembangan aplikasi bertujuan untuk mengatur pola logika dalam sistem. Sebuah design yang baik, dapat mengurangi ketergantungan antar setiap proses pada sebuah sistem. 3.

XP Coding Setelah menyelesaikan pengumpulan cerita dan menyelesaikan design untuk aplikasi secara keseluruhan, XP lebih merekomendasikan tim untuk terlebih dahulu membuat modul unit tes yang bertujuan untuk melakukan uji coba setiap cerita yang didapat dari klien.. XP Testing Tahapan uji coba pada XP sudah dilakukan juga pada saat tahapan sebelumnya yaitu coding. XP menerapkan perbaikan masalah kecil dengan sesegera mungkin akan lebih baik dibandingkan menyelesaikan masalah pada saat akan mencapai tenggat akhir.

Rancangan Sistem Meliputi rencana dan design atau model yang dibuat berdasarkan langkah-langkah pada metode penelitian yang diusulkan penulis. Design rancangan sistem yang digunakan adalah Extreme Programming. Dengan tahapantahapannya adalah XP Planning, XP Design dan XP Coding. 4.1.1 XP Planning Berisikan tentang gambaran sederhana tentang aplikasi game 8-puzzle dan analisa algoritma A* yang akan diterapkan. Penjelasan tentang game 8puzzle, algoritma A* dan analisis kebutuhan sistem yang merupakan identifikasi dan evaluasi permasalahan yang ada, sehingga sistem yang dibangun sesuai dengan kriteria yang diharapkan. 4.1.1.1 Analisis Game 8-Puzzle berbasis Android Proses permainan 8-puzzle secara umum dapat berlangsung apabila memiliki 1 pemain. Permainan ini dilakukan pada papan permainan yang berbentuk bujursangkar dengan ukuran 3x3 yang terdapat 1 ubin kosong sebagai tempat untuk menggeser ubin yang lain.

4.

Gambar 7. Initial-goal state

Pembangunan game 8-puzzle akan dilakukan pada platform Android. Untuk pembangunannya menggunakan software

Eclipse IDE yang merupakan aplikasi untuk meng-coding dalam bahasa pemrograman Java, karena pada dasarnya android berbasis Java.

h(n) = |(Awal.x - Akhir.x) + (Awal.y Akhir.y)|

4.1.1.2 Analisis Algoritma A* Ada berbagai algoritma yang dapat digunakan untuk menyelesaikan game ini diantaranya yaitu Iterative Deepning Search yang merupakan penggabungan dari 2 algoritma yaitu Breadth-first Search dan Depth-first Search. Penggabungan algoritma ini mungkin menjadi salah satu yang terbaik dari algoritma lain karena menggabungkan 2 algoritma menjadi satu. Tetapi algoritma ini masih memiliki banyak kekurangan. Selain Iterative Deepning Search, algoritma lain yang dapat digunakan adalah Hill Climbing. Ada 2 tipe Hill Climbing yaitu Simple dan Stepest Ascent. Dalam kasus ini, akan dibahas Stepest Ascent Hill Climbing karena lebih baik dari Simple Hill Climbing. Walaupun lebih baik, Stepest Ascent HC masih memiliki kekurangan juga. Untuk mengatasi kekurungan dari berbagai algoritma berpikir yang digunakan untuk menyelesaikan game 8puzzle ini, algoritma berpikir komputer akan dirancang dengan menggunakan algoritma A*. Rumusan algoritma A* ini dibuat sedemikian rupa sehingga pemain dapat melihat solusi dari permainan yang telah dijalankan.

Pada keempat keadaan tersebut komputer akan menghitung nilai f(n) dengan menjumlahkan nilai g(n) dan h(n). Lalu komputer akan memilih nilai f(n) yang terkecil. Alur algoritma A* dapat dijelaskan sebagai berikut: 1. Analisa apakah posisi puzzle sudah terurut atau h(n) = 0? 2. Jika "Tidak", cari kotak-kotak yang mungkin untuk digerakkan (yang berbatasan langsung dengan space/ruang kosong). 3. Hitung f(n) = g(n) + h(n). Simpan pada open list. 4. Cari pada kotak di dalam open list, apakah terdapat lebih dari satu nilai f(n) terkecil. 5. Jika "Tidak", maka gerakkan f(n) yang terkecil. Jika "Ya", maka gerakkan f(n) yang pertama kali dicari. Simpan pada closed list. 6. Ulangi kembali langkah no. 1. Jika "Ya" maka permainan selesai. Jika "Tidak" maka lanjut ke langkah no. 2 dan seterusnya sampai puzzle terurut.

Awal = Initial State Akhir = Goal State

Rumus : f(n) = g(n) + h(n) n = posisi koordinat node f(n) = fungsi evaluasi g(n) = biaya (cost) yang sudah dikeluarkan dari keadaan awal sampai keadaan n h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n (fungsi heuristik). dimana,

Gambar 8. Flowchart A*

4.1.1.3 Analisis Kebutuhan Sistem Analisis kebutuhan sistem merupakan proses identifikasi dan evaluasi permasalahan-permasalahan yang ada, sehingga sistem yang dibangun sesuai dengan kriteria yang diharapkan. Aplikasi yang dihasilkan harus memenuhi kebutuhan sebagai berikut : 1. Aplikasi harus mampu menjalankan permainan 8-puzzle sesuai dengan aturan yang ada. 2. Aplikasi harus memiliki menu hint dan solve yang merupakan bantuan dan pencarian solusi. Algoritma berpikir komputer ini dibuat dengan mengikuti Algoritma A*. 3. Aplikasi harus dapat mengganti kecepatan solver menjadi cepat atau lambat. 4. Aplikasi harus mempunyai menu reshuffle untuk mengacak ulang puzzle dan me-restart permainan. 5. Aplikasi harus mampu mencatat berapa langkah yang telah di tempuh user setelah menyelesaikan permainan.

4.1.2.2 Activity Diagram

Gambar 10. Diagram Aktivitas

4.1.2.3 Sequence Diagram

4.1.2 XP Design XP design berisikan tentang pemodelan sistem yaitu use case diagram, activity diagram dan sequence diagram untuk menjelaskan model aplikasi yang akan dibangun. 4.1.2.1 Use Case Diagram Gambar 11 Diagram Sekuen

4.2.1 XP Coding Setelah menyelesaikan pengumpulan cerita dan menyelesaikan design untuk aplikasi secara keseluruhan, maka harus di implementasikan menjadi bentuk program aplikasi. XP Coding berisi langkahlangkah membuat game 8-puzzle, solver algoritma A*, heuristik manhattan dan sebagian codingnya. Gambar 9. Diagram Use Case

4.2.1.1 Game 8-Puzzle Permainan ini dilakukan pada papan permainan yang berbentuk bujursangkar dengan ukuran 3x3 yang terdapat 1 ubin kosong sebagai tempat untuk menggeser ubin yang lain. 4.2.1.2 Solver Algoritma A* Pada game 8-puzzle terdapat banyak kemungkinan pergeseran yang akan membuat pemain merasa tidak bisa menyelesaikan permainan ini sehingga akan memerlukan banyak waktu untuk dapat menyelesaikan permainan ini. Pemain memerlukan suatu cara yaitu dengan menggunakan algoritma A* yang lebih cepat membantu menyelesaikan permainan. Pemain akan berhasil bila telah menyusun kembali ubin secara terurut. 4.2.1.3 Heuristik Manhattan A* sebagai algoritma pencarian yang menggunakan fungsi heuristik untuk pencarian rute node-node pada peta. Heuristik yang paling umum digunakan adalah jarak Manhattan. Fungsi heuristik ini hanya akan menjumlahkan selisih nilai x dan nilai y dari dua buah titik. Berikut adalah perintah perhitungan heuristik manhattan pada class Heuristic.java. BAB V HASIL PENGUJIAN DAN PEMBAHASAN 5.1

Hasil Penelitian Hasil penelitian merupakan hasil pengujian yang telah diimplementasikan. Tujuan dari tahap ini ialah untuk mengetahui apakah sistem yang dibuat sudah sesuai dengan tujuan pembuatan laporan tugas akhir atau belum. Pada tahap ini dilakukan pengujian dengan menggunakan tahapan terakhir Extreme Programming yaitu XP Testing. 5.1.1 XP Testing XP Testing merupakan Pada pembangunan aplikasi yang penulis buat,

XP Testing berisikan 2 macam testing yaitu Blackbox dan Whitebox. Berikut adalah Blackbox Testing dan poin-poin bagian dari perangkat lunak yang akan diuji. Tabel 1. BlackBox Testing

N Input Fungsi o Pengu jian

Hasil Yang Dihara pkan 1. Icon Menuju Menam Game halaman pilkan 8awal awal puzzle game 8- game 8puzzle puzzle 2. Button Menuju Menam Tap to tampila pilkan Play n tampilan gamepl game ay play dan memain kan game. 3. Menu Menuju Menam Lihat halaman pilkan Hint Lihat tampilan Hint lihat hint. 4. Menu Mengur Puzzle Solve utkan bergerak Puzzle puzzle menurut ! yang i acak eksekusi menjadi algoritm bentuk a A* awal. 5. Menu Mengac Puzzle Reshu ak teracak ffle Ulang kembali Puzzle secara random. 6. Menu Menuju Menam Ganti Tampila pilkan kecep n Ganti Pilihan atan Kecepat Cepat Solve an dan Solve Lambat 7. Button Mengga Kecepat Cepat nti an Solve Kecepat berganti

Hasil

Meme nuhi

Meme nuhi

Meme nuhi

Meme nuhi

Meme nuhi

Meme nuhi

Meme nuhi

an Solve menjadi cepat 8. Button Mengga Lamb nti at Kecepat an Solve menjadi lambat

menjadi cepat Kecepat an Solve berganti menjadi lambat

Meme nuhi

Berikut adalah WhiteBox Testing yang akan menguji alur algoritma A* dengan pseudocode yang ada :

Path 3 : 1, 2, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 20, 23, 24, 1, 25 Path 4 : 1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 23, 24, 1, 25 Path 5 : 1, 2, 5, 6, 7, 8, 13, 14, 21, 22, 6, 7, 8, 13, 14, 15, 20, 23, 24, 1, 25 Path 6 : 1, 2, 5, 6, 7, 8, 13, 14, 16, 19, 15, 20, 23, 24, 1, 25 Path 7 : 1, 2, 5, 6, 7, 8, 13, 14, 16, 17, 18, 19, 15, 20, 23, 24, 1, 25 Path 8 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 15, 20, 23, 24, 1, 25 V(G) Type of Procedure Risk 1-4 A simple procedure Low 5 - 10 A well sturctured Low and stable procedure 11 A more complex Moderate 20 procedure 20 A complex High 50 procedure, alarming 5.2. Pembahasan Dari pengujian sistem yang menggunakan XP Testing, sebagaian besar berjalan dengan lancar. Berikut adalah hasil dari game 8-Puzzle yang telah dibangun.

Gambar 12 Whitebox

5.2.1 Halaman Awal Halaman awal merupakan tampilan awal ketika user membuka aplikasi game 8-puzzle.

V(G) = E - N + 2 = 25 - 19 + 2 =8 Dimana : E = jumlah edge pada grafik alir N = jumlah node pada grafik alir Berdasarkan cyclometic complexity tersebut terdapat 8 path sebagai berikut : Path 1 : 1, 2, 5, 6, 7, 8, 13, 14, 15, 20, 23, 24, 1, 25 Path 2 : 1, 2, 3, 4, 5, 6, 7, 8, 13, 14, 15, 20, 23, 24, 1, 25

Gambar 13 Halaman Awal

Gambar 15 Lihat Hint

Jika tombol tap-to-play diklik, maka user akan dapat memulai memainkan game 8puzzle.

5.2.4 Tampilan Game Selesai Tampilan Game selesai hanya akan menampilkan alert dialog berupa jumlah langkah yang telah ditempuh User.

5.2.2 Halaman Gameplay Halaman gameplay merupakan tampilan dimana user dapat memainkan game 8-puzzle. Puzzle akan teracak secara random. Dan juga user memilih menumenu yang tersedia.

Gambar 16 Game Selesai

Gambar 14 Gameplay

BAB VI KESIMPULAN DAN PENELITIAN SELANJUTNYA 6.1

5.2.3 Tampilan Lihat Hint Halaman Lihat Hint menampilkan gambar awal dari puzzle yang dapat membantu pemain.

Kesimpulan Kesimpulan dari penelitian yang penulis buat adalah sebagai berikut : 1. Algoritma A* yang diterapkan pada game 8-puzzle merupakan algoritima yang optimal, karena merupakan penjumlahan dari langkah yang ditempuh dan fungsi heuristik. 2. Game 8-puzzle yang dibangun berbasis Android lebih mudah dikembangkan lagi, karena android memiliki bahasa, desain dan model yang modern dan masih terus berkembang.

6.2

Penelitian Selanjutnya Rekomendasi merupakan future works yang akan dilakukan sebagai tahapan penelitian selanjutnya dari tugas akhir yang dibuat sebagai berikut : 1. Dapat mengembangkan game 8puzzle sebagai sarana edukasi. 2. Pembuatan antarmuka/interface yang lebih menarik, seperti penambahan background, tampilan menu dan sebagainya. 3. Dapat menggunakan gambar yang lain sebagai objek 8-puzzle, dan juga mengambil gambar dari image gallery masing-masing gadget Android. 4. Dapat menambahkan cacatan waktu penyelesaian dan high score. 5. Diharapkan dapat menggunakan algoritma lain seperti Iterative Deepning A*, genetik, greedy dan sebagainya.

[6]

[7] [8] [9]

[10] [11]

DAFTAR PUSTAKA [1 2] [1] Reska K. Nistanto. (2014, January) kompas.com. [Online]. http://tekno.kompas.com/read/2014/01/01/ 0832360/50.Game.Android.Terpopuler.di. 2013. [2] Latius Hermawan and R. Kristoforus Jawa Bendi, "Penerapan Algoritma A* pada Aplikasi Puzzle," Seminar Nasional Teknologi Informasi dan Komunikasi, pp. 23-28, 2013. [3] Muhammad Nasrul Anwar, "8-Puzzle Dengan Menggunakan Algoritma Iterative Deepning Search (IDS)," AMIKOM, Jogjakarta, 2010. [4] Chandra Usman, Kenedy Candra, Hendri Sopryadi, and Willy, "Rancang Bangun Game Slider Puzzle Berbasis Android Menggunakan Metode Heuristik dengan Teknik Best First Search," STMIK MDP, p. 10, 2013. [5] Azizah Zakiah, "Penyelesaian Masalah 8Puzzle dengan Algoritma Hill Climbing

Stepest Ascent Loglist Heuristik Berbasis Java," Seminar Nasional Teknologi dan Komunikasi, pp. 158-163, March 2012. Rengga Dionata Putra, Ir. Muhammad Aswin, and Waru Djuriatno, "Pencarian Rute Terdekat Pada Labirin Menggunakan Metode A*," EECCIS, vol. 6, pp. 1-4, Desember 2012. T. Sutojo, Edy Mulyanto, and Dr. Vincent Suhartono, Kecedasan Buatan. Yogyakarta: ANDI, 2011. Wahyudi Fauzan, "Pembangunan Aplikasi Game Puzzle and The Solver," Universitas Komputer Indonesia, Bandung, 2013. Nazruddin Safaat H, Pemrograman Aplikasi Mobile Smartphone dan Tablet PC Berbasis Android. Bandung: INFORMATIKA, 2012. Rosa A. S and M. Shalahuddin, Rekayasa Perangkat Lunak. Bandung: INFORMATIKA, 2013. Mohammed Ekhlaif and Sulaf A. Elshaar, "A Systematic Study of Extreme Programming and Their Implementation in Libyan Software," World Applied Sciences Journal, pp. 410-417, March 2013. Roger Pressman, "Introduction to Software Engineering," Software Engineering: A Praccitioner's Approach, p. 27, 2009.