Implementasi Algoritma A* untuk Pencarian Solusipada Game 8-Puzzle berbasis Android

Gagah Randah Satria1

Jurusan Teknik Informatika, Fakultas Ilmu KomputerUniversitas Dian Nuswantoro

Jl. Nakula I No 5-11 Semarang 50131 Indonesia

Email : 111201005349@mhs.dinus.ac.id

Abstrak

Aplikasi permainan (game) saat ini telah menjadi bagian yang tidak terpisahkan daripengguna mobile phone Android. Banyak pengembang aplikasi game yang menyadaripotensi berjualan di Play Store dengan menyasar pengguna smartphone dan tablet Android.Dari game puzzle sederhana yang tidak membutuhkan spesifikasi sistem yang tinggi, hinggagame-game yang berat. Satu tipe game puzzle adalah 8-puzzle. Pada permainan ini, pemainharus mengurutkan angka-angka dari angka yang diacak dan batasan ruang yang ada. 8-puzzle merupakan sebuah permainan yang menggunakan teknik pencarian (searching) yaitualgoritma A*. Tujuan dari penelitian ini adalah penulis dapat menerapkan algoritma A* padagame 8-puzzle, dan juga membangun game 8-puzzle yang berbasis android. Dengan tujuantersebut tentunya penulis mengharapkan hasil yaitu algoritma A* dapat menjadi pencariansolusi yang tepat untuk menyelesaikan game 8-puzzle dan dapat membangun game 8-puzzleyang berbasis android. Laporan tugas akhir ini akan menguraikan analisa dan desain game 8-puzzle yang berbasis android. Penjelasan Algoritma A* pada game 8-puzzle. Lalu pada tahapakhir pengembangan dilakukan evaluasi terhadap proses dan hasilnya pada bagian akhirlaporan ini.

Kata Kunci : Android, 8-puzzle, Algoritma A*.

BAB I PENDAHULUAN

1.1 Latar BelakangAplikasi permainan (game) saat ini

telah menjadi bagian yang tidakterpisahkan dari pengguna mobile phone.Salah satu perangkat yang paling banyakdigunakan yaitu Android. Berdasarkanyang dikutip dari kompas.com menyatakanbahwa, "Banyak pengembang aplikasigame yang menyadari potensi berjualan diPlay Store dengan menyasar penggunasmartphone dan tablet Android. Mulai darigame sederhana hingga yang bertema olahraga dan strategi, Android memilikisemuanya. Game-game Android banyak

jenisnya. Pengguna bisa memilihnyasesuai dengan spesifikasi smartphone dantablet yang dimiliki. Dari game puzzlesederhana yang tidak membutuhkanspesifikasi sistem yang tinggi, hinggagame-game yang berat" [1].

Puzzle merupakan salah satupermainan yang cukup memeras otakuntuk menyelesaikannya. Pemainditantang untuk berpikir kreatif bagaimanauntuk membuat semua bagian puzzleterletak pada posisi sebenarnya. Caramemainkannya cukup mudah, pemain

hanya menggeser puzzle satu demi satusampai akhirnya semua puzzle terleteakpada posisi sebenarnya [2].

Salah satu tipe game puzzle adalah8-puzzle. Pada permainan ini, pemainharus mengurutkan angka-angka dariangka yang diacak dan batasan ruang yangada. Permainan akan berakhir ketikapemain telah mengurutkan angka tersebut[3]. 8-puzzle biasanya diwakili sebagaipapan 3 * 3 yang ubinnya terdiri dariangka 1 sampai 8 yang disusun dari ataskiri sampai kanan bawah dari papanpermainan (goal board).

8-puzzle merupakan sebuahpermainan yang menggunakan teknikpencarian (searching). Teknik pencarianbisa dilakukan dengan menggunakan suatualgoritma untuk mendapatkan suatu solusiatau permasalahan. Banyak sekali teknikpencarian yang bisa dilakukan dan teknik-teknik tersebut harus dipilih berdasarkankeriteria permasalahan yang dihadapi dantingkat kebutuhan yang harus dipenuhi [3].

Salah satu metode searching yangdapat digunakan untuk menyelesaikanpermainan 8-Puzzle yaitu algoritma A*.Algoritma ini merupakan algoritma bestfirst search dengan pemodifikasian fungsiheuristik. Heuristik yang diterapkan padaalgoritma ini memiliki fungsi untukmeminimumkan total biaya linstasan, danpada kondisi yang tepat akan memberikansolusi terbaik dalam waktu optimal [4].

Dari berbagai macam metode danplatform yang digunakan untukmenyelesaikan game 8-puzzle, penulismemilih menerapkan metode algoritma A*untuk pencarian solusi pada game 8-puzzleyang ber-platform Android. Pada game 8-puzzle, masalah yang sering kali terjadiyaitu saat pemain kesulitan dalammenyelesaikannya. Menurut penelitianyang dilakukan oleh Latius Hermawan danR. Kristoforus Jawa Bendi mangatakanbahwa, "Terdapat banyak kemungkinanpergeseran yang akan membuat pemainmerasa tidak bisa menyelesaikanpermainan ini sehingga akan memerlukanbanyak waktu untuk dapat

menyelesaikannya" [2]. Untuk itu pemainmemerlukan suatu cara yaitu denganalgoritma berpikir komputer yang akanmembantu menyelesaikan game 8-puzzle.

Berdasarkan analisa dari masalahdiatas, maka penulis mengambil judulpenelitian "Implementasi algoritma A*untuk Pencarian Solusi pada Game 8-puzzle berbasis Android" sehinggadiharapkan penerapan algoritma A* dapatmenemukan langkah yang optimal danmemudahkan pemain untuk menyelesaikangame 8-puzzle.

1.2 Rumusan MasalahUntuk memperjelas dan

mengarahkan penelitian ini agar hasil yangdidapat sesuai dengan yang diharapkanmaka masalah yang dirumuskan adalahsebagai berikut :

1. Bagaimana penerapan algoritmaA* dalam pencarian solusi padagame 8-Puzzle.

2. Bagaimana membangun game 8-puzzle berbasis android.

1.3 Batasan MasalahMengingat luasnya permasalahan

yang dibahas, maka perlu adanyapembatasan masalah. Batasan masalahyang diambil antara lain :

1. Pembahasan difokuskan padapencarian solusi 8-Puzzle denganmenggunakan algoritma A*.

2. Pembahasan meliputi perancangangame 8-Puzzle berbasis Androiddengan bahasa pemrograman Java.

3. Ukuran papan dibatasi 3 * 3 sajadan memiliki 9 kotak, yang berisiangka 1 - 8.

4. Analisis pengembangan sistemmenggunakan diagram UML.

1.4 Tujuan PenelitianBerdasarkan rumusan masalah dan

batasan masalah di atas, maka tujuan dariTugas Akhir ini adalah :

1. Menerapkan algoritma A* untukpencarian solusi pada game 8-Puzzle.

2. Dapat membangun game 8-puzzleberbasis android.

1.5 Manfaat Penelitian1.5.1 Manfaat Bagi Penulis

Menambah pengetahuan danwawasan penulis tentang pembangunanAplikasi game berbasis Android danimplementasi algoritma A* pada game 8-Puzzle serta sebagai penerapan danpengembangan ilmu yang didapat padaperkuliahan di kehidupan nyata.1.5.2 Manfaat Bagi Akademik

Sebagai tambahan referensiperpustakaan yang dapat dimanfaatkanuntuk menambah pengetahuan mahasiswatentang Aplikasi game berbasis Androiddan implementasi algoritma A* pada game8-Puzzle untuk mengembangkankurikulum perkuliahan. Dan dapatdijadikan acuan dalam mendidik danmembekali ilmu kepada mahasiswa.1.5.3 Manfaat Bagi Pengguna

Sebagai pengetahuan penggunatentang penerapan algoritma A* untukmenemukan solusi yang optimal danmemudahakan pengguna untukmenyelesaikan game 8-puzzle.

BAB IITINJAUAN PUSTAKA DAN

LANDASAN TEORI

2.1 Tinjauan PustakaDalam pembuatan skripsi ini,

penulis menggunakan beberapa acuan.Acuan pertama dari skripsi ini adalahpenelitian yang berjudul "PenerapanAlgoritma A* pada Aplikasi Puzzle" [2].Dalam jurnal tersebut membahas analisisalgoritma A* pada aplikasi puzzle.Perbedaan dari penelitian yang penulisbuat adalah penerapan algoritma A* padaaplikasi 8-puzzle yang berbasis Android.

Acuan kedua dari skripsi ini adalahpenelitian yang berjudul "8-puzzleMenggunakan Algoritma IterativeDeepning Search (IDS)" [3]. Dalam

skripsi tersebut membangun aplikasi game8-puzzle dengan metode algoritmaIterative Deepning Search (IDS) denganmenggunakan Delphi sebagai bahasapemrograman. Perbedaan dari aplikasiyang penulis buat adalah metode yangmenggunakan Algoritma A* dan platformyang digunakan yaitu Android.

Acuan ketiga dari penelitian yangberjudul "Penyelesaian Masalah 8-Puzzledengan Algoritma Hill Climbing StepestAscent Loglist Heuristik Berbasis Java"[5]. Dalam jurnal tersebut membangunaplikasi game 8-puzzle menggunakan Javadengan menggunakan metode algoritmaHill Climbing. Perbedaan dari aplikasiyang penulis buat adalah metode yangmenggunakan Algoritma A* dan platformyang digunakan yaitu Android.

Acuan keempat dari skripsi iniadalah penelitian yang berjudul "PenelitianRute Terdekat pada Labirin Menggunakanmetode A*" [6]. Dalam penelitian tersebutmembahas penerapan algoritma A* padalabirin. Perbedaan dari penelitian yangpenulis buat adalah penerapan algoritmaA* pada aplikasi 8-puzzle.

2.2 Landasan Teori2.2.1 Algoritma

Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yangdisusun secara sistematis dan logis1. Katalogis merupakan kata kunci dalamalgoritma. Langkah-langkah dalamalgoritma harus logis dan harus dapatditentukan bernilai salah atau benar.

Dalam beberapa konteks, algoritmaadalah spesifikasi urutan langkah untukmelakukan pekerjaan tertentu2.Pertimbangan dalam pemilihan algoritmaadalah, pertama algoritma haruslah benar.Artinya algoritma akan memberikankeluaran yang dikehendaki dari sejumlahmasukan yang diberikan. Tidak pedulisebagus apapun algoritma, kalaumemberikan keluaran yang salah, pastilahalgoritma tersebut bukan algoritma yangbaik.

Pertimbangan kedua yang harusdiperhatikan adalah kita harus mengetahuiseberapa baik hasil yang dicapai olehalgoritma tersebut. Hal ini pentingterutama pada algoritma untukmenyelesaikan masalah yang memerlukanaproksimasi hasil (hasil yang hanya berupapendekatan). Algoritma yang baik harusmampu memberikan hasil yang sedekatmungkin dengan nilai yang sebenarnya.

Ketiga adalah efisiensi algoritma.Efisiensi algoritma dapat ditinjau dari 2 halyaitu efisiensi waktu dan memori.Meskipun algoritma memberikan keluaranyang benar (paling mendekati), tetapi jikakita harus menunggu berjam-jam untukmendapatkan keluarannya, algoritmatersebut biasanya tidak akan dipakai, setiaporang menginginkan keluaran yang cepat.Begitu juga dengan memori, semakin besarmemori yang terpakai maka semakinburuklah algoritma tersebut.

Dalam kenyataannya, setiap orangbisa membuat algoritma yang berbedauntuk menyelesaikan suatu permasalahan,walaupun terjadi perbedaan dalammenyusun algoritma, tentunya kitamengharapkan keluaran yang sama. Jikaterjadi demikian, carilah algoritma yangpaling efisien dan cepat.

2.2.1.1 Algoritma dan ProgramProgram adalah kumpulan

pernyataan komputer, sedangkan metodedan tahapan sistematis dalam programadalah algoritma. Program ditulis denganmenggunakan bahasa pemrograman. Jadibisa disebut bahwa program adalah suatuimplementasi dari bahasa pemrograman3.Beberapa pakar memberi formula bahwa:

Program = Algoritma + Bahasa(Struktur Data)

Bagaimanapun juga struktur datadan algoritma berhubungan sangat eratpada sebuah program. Algoritma yang baiktanpa pemilihan struktur data yang tepatakan membuat program menjadi kurangbaik, demikian juga sebaliknya.

2.2.1.2 Metode SearchingPada dasarnya teknik searching(pencarian) dapat dibagi menjadi 2 (dua)kelompok besar, yaitu pencarian buta(blind search) dan pencaraian termbimbing(heuristic search). Untuk mengukurperforma metode pencarian, terdapatempat kriteria yang dapat dilakukan,yaitu :

1. Completeness : Apakah metodetersebut menjamin adanya solusijika solusinya ada?

2. Time Complexity : Berapa lamawaktu yang diberikan untukmenemukan solusi tersebut?

3. Space Complexity : Berapa banyakmemori yang dibutuhkan untukmenemunkan solusi tersebut?

4. Optimality : Apakah metodetersebut menjamin menemukansolusi terbaik jika terdapatbeberapa solusi yang berbeda?

Pencarian buta (blind search) atau un-informed search terdiri dari 2 algoritmayaitu :

1. BFS (Breadth-First Search) atauPencarian Melebar Pertama.

2. DFS (Depth-First Search) atauPencarian Mendalam Pertama.Teknik pencarian heuristik

(heuristic-searching) merupakan suatustrategi untuk melakukan proses pencariansecara selektif dan dapat memandu prosespencarian yang memiliki kemungkinansukses paling besar, namun dengankemungkinan mengorbankan kelengkapan(completeness). Untuk menerapkanpencarian heuristik diperlukan suatuFungsi Heuristik. Fungsi heuristik adalahatura-aturan yang digunakan untukmendapatkan solusi yang diinginkan.Pencarian Heuristic terdiri dari :

1. Generate and Test (Pembangkitandan Pengujian)

2. Hill Climbing (Pendakian Bukit)a. Simple Hill Climbingb. Steepest-Ascent Hill Climbing3. Best First Search4. Algoritma A*

5. Simulated Annelaing [7].

2.2.1.3 Algoritma A*Algoritma ini pertama kali

ditemukan pada tahun 1968 oleh PeterHart, Nilsson dan Bertram Raphael. Dalamtulisan mereka, algoritma ini dinamakanAlgoritma A. Penggunaan algoritma inidengan fungsi heuristik yang tepat dapatmemberikan hasil yang optimal, makaalgoritma inipun disebut A*. A*merupakan salah satu contoh algoritmapencarian yang cukup popular di dunia.Jika kita mengetikkan Algoritma A* padasebuah mesin pencari, seperti google.com,maka akan kita temukan lebih dari sepuluhribu literatur mengenai algoritma A*.

Algoritma A* merupakanalgoritma yang membantu menemukansolusi pencarian ruang keadaan denganmempertimbangkan total biaya lintasanyang akan dilacak sesuai dnegan nodeyang akan dilewati. Masalah ruangkeadaan disebut juga dengan state spaceproblem. Ruang keadaan (state space)merupakan suatu ruang yang berisi semuakeadaan yang mungkin dalam suatu kasusAI. State adalah representasi suatu keadaanpada suatu saat ataupun dekripsikonfigurasi sistem. State space adalahsemua state (keadaan) yang mungkin, danbiasanya digambarkan sebagai jaringandengan verteks merupakan state dan edgemerupakan perubahan yang mungkin.[2].Aliran algoritma A* ditunjukkan padagambar berikut.

Beberapa terminologi dasar yangterdapat pada Algoritma A* adalahstarting point, simpul (nodes), A, open list,closed list, harga (cost), halangan(unwalkable). Starting point adalah sebuahterminologi untuk posisi awal sebuahbenda. A adalah node yang sedangdijalankan dalam algoritma pencarian jalanterpendek. Node adalah petak-petak kecilsebagai representasi dari area path finding.Bentuknya dapat berupa persegi,lingkaran, maupun segitiga. Open listadalah tempat meyimpan data node yangmungkin diakses dari starting pointmaupun simpul yang sedang dijalankan.Closed list adalah tempat menyimpan datasimpul sebelum A yang juga merupakanbagian dari jalur terpendek yang telahberhasil didapatkan.

Harga (F) adalah nilai yangdiperoleh dari penjumlahan nilai G, jumlahnilai tiap simpul dalam jalur terpendek daristarting point ke A, dan H, jumlah nilaiperkiraan dari sebuah simpul ke simpultujuan, Simpul tujuan adalah simpul yangakan dituju. Rintangan adalah sebuahatribut yang menyatakan bahwa sebuahsimpul tidak dapat dilalui oleh A.

A* memiliki 2 fungsi utama dalammenentukan solusi terbaik. Fungsi pertamadisebut sebagai g(n) merupakan fungsiyang digunakan untuk menghitung totalcost dari starting point menuju nodetertentu. Fungsi kedua yang biasa disebutsebagai h(n) merupakan fungsi perkiraantotal cost yang diperkirakan dari suatunode ke node akhir.

Pada A*, setiap node dari nodeawal ditelusuri kemudian dihitung costdari tiap-tiap node dan dimasukkan ketabel prioritas. Node dengan cost palingrendah akan diberikan tingkat prioritaspaling tinggi. Kemudian pencariandilanjutkan dengan nilai prioritas tertinggipada tabel.

f(n) = g(n) + h(n)Gambar 1. Alur Algoritma A*

dengan :

n = posisi koordinat nodef(n) = fungsi evaluasig(n) = biaya (cost) yang sudah dikeluarkandari keadaan awal sampai keadaan nh(n) = estimasi biaya untuk sampai padasuatu tujuan mulai dari n [8].

2.2.1.4 Fungsi Heuristik Manhattan Distance

Heuristik adalah sebuah teknikyang mengembangkan efisiensi dalamproses pencarian, namun dengankemungkinan mengorbankan kelengkapan(completeness). Fungsi heuristikdigunakan untuk mengevaluasi keadaan-keadaan problema individiual danmenentukan seberapa jauh hal tersebutdapat digunakan untuk mendapatkan solusiyang diinginkan.

A* sebagai algoritma pencarianyang menggunakan fungsi heuristik untukpencarian rute node-node pada peta [8].Heuristik yang paling umum digunakanadalah jarak Manhattan. Fungsi heuristikini hanya akan menjumlahkan selisih nilaix dan nilai y dari dua buah titik. Heuristikdinamakan Manhattan mungkin karena dikota Manhattan di Amerika, jarak dari dualokasi umumnya dihitung dari blok-blokyang harus dilalui saja dan tentunya tidakbisa dilintasi secara diagonal.Perhitungannya dalat ditulis sebagaiberikut:

h(n) = abs(n.x-tujuan.x) + abs(n.y-tujuan.y) [2].

Dimana h(n) adalah sebuah fungsiheuristik. D (distance) adalah jarak darinode awal (strating point) menuju nodetujuan (goal) [8].

2.2.2 GameGame adalah sesuatu yang dapat

dimainkan dengan aturan tertentu sehinggaada yang menang dan ada yang kalah,biasanya dalam konteks tidak serius atau

dengan tujuan refreshing. Suatu carabelajar yang digunakan dalam menganalisainteraksi antara sejumlah pemain maupunperorangan yang menunjukkan strategi-strategi yang rasional [8].

2.2.2.1 Permainan PuzzlePermainan 8-puzzle ini mempunyai

peraturan yang cukup sederhana. Padapermainan ini, pemain harus mengurutkanangka-angka dari angka yang diacak danbatasan ruang yang ada. Permainan akanberakhir ketika pemain telah mengurutkanangka tersebut [3]. 8-puzzle biasanyadiwakili sebagai papan 3 * 3 yang ubinnyaterdiri dari angka 1 sampai 8 yang disusundari atas kiri sampai kanan bawah daripapan permainan (goal board). Permainanini diwakili dengan papan n * n yangmemiliki angka dari 0 sampai (n2 – 2)sebagimana pada masing-masing kolomdan baris merupakan indeks dari 0.

Ubin yang tersisa (kanan bawah)adalah kosong, karena akan digunakanuntuk pergeseran ubin yang lain yangberada dalam papan permainan. Teka-tekidimainkan dengan menyusun ubin kepapan dan mencoba untukmenyelesaikannya dengan menciptakankembali papan tujuan. Hal ini dicapaidengan menggerakkan ubin kembali keposisi papan tujuan pada ruang kosongdisekitar papan [2].

Adapun status dari 8-puzzle iniadalah ubin (tile) yang bisa dipindahposisinya, 8-puzzle memiliki maksmial 4aksi yaitu ubin digeser ke atas, digeser kekiri, digeser ke kanan, dan digeser ke

Gambar 2. Permainan 8-Puzzle

bawah dilihat dari letak ubin yang kosong.Jadi pada kasus ini ubin yang kosong harusdigeser untuk menghasilkan solusi yangdiinginkan [3].

2.2.3 AndroidAndroid adalah sebuah sistem

operasi untuk perangkat mobile berbasislinux yang mencakup sistem operasi,middleware dan aplikasi. Androidmenyediakan platform terbuka bagi parapengembang untuk menciptakan aplikasimereka.

Awalnya, Google Inc. membeliAndroid Inc. yang merupakan pendatangbaru yang membuat piranti lunak untukponsel/smartphone. Kemudian untukmengembangkan Android, dibentuklahOpen Handset Alliance, konsorsium dari34 perusahaan peranti keras, peranti lunakdan telekomunikasi, termasuk Google,HTC, Intel, Motorola, Qualcomm, T-Mobile dan Nvidia.

Android dipuji sebagai “platformmobile pertama yang Lengkap, Terbukadan Bebas”.

2.2.3.1 IDE EclipsePengembang memiliki beberapa

pilihan ketika membuat aplikasi yangberbasis Android. Sebagian besarpengembang menggunakan Eclipse yangtersedia secara bebas untuk merancang danmengembangkan aplikasi Android. Eclipseadalah IDE yang paling populer untukpengembangan Android, karena memilikiAndroid plug-in yang tersedia untukmemfasilitasi pengembangan Android.Selain itu, Eclipse juga mendapatdukungan langsung dari Google untukmenjadi IDE pengembangan aplikasiAndroid, ini terbukti dengan adanyapenambahan plugins untuk eclipse untukmembuat project android di mana sourcesoftware langsung dari situs resminyaGoogle. Akan tetapi, hal diatas tidakmenutup kemungkinan untukmenggunakan IDE yang lain sepertiNetbeans untuk melakukan pengembanganAndroid.

2.2.3.2 Android SDK (Software Development Kit)

Android SDK adalah tools API(Application Programming Interface) yangdiperlukan untuk mulai mengembangkanaplikasi pada platform Androidmenggunakan bahasa pemrograman Java.Android merupakan subset perangkatlunak untuk ponsel yang meliputi sistemoperasi, middleware dan aplikasi kunciyang di-release oleh Google. Saat inidisediakan Android SDK (SoftwareDevelopment Kit) sebagai alat bantu danAPI untuk mulai mengembangkan aplikasipada platform Android menggunakanbahasa pemrograman Java. Sebagaiplatform aplikasi-netral, Android memberiAnda kesempatan untuk membuat Aplikasiyang kita butuhkan yang bukan merupakanaplikasi bawaan Handphone/Smarphone.

2.2.3.3 ADT (Android Development Tools)

Android Development Tools (ADT)adalah plugin yang didesain untuk IDEEclipse yang memberikan kita kemudahandalam mengembangkan aplikasi androiddengan menggunakan IDE Eclipse.Dengan menggunakan ADT untuk Eclipseakan memudahkan kita dalam membuataplikasi project android, membuat GUIaplikasi dan menambahkan komponen-komponen yang lainnya, begitu juga kitadapat melakukan running aplikasimenggunakan Android SDK melaluiEclipse. Dengan ADT juga kita dapatmelakukan pembuatan package Android(.apk) yang digunakan untuk distribusiaplikasi android yang kita rancang.

2.2.4 Pemodelan dan UMLPada perkembangan teknologi

perangkat lunak, diperlukan adanya bahasayang digunakan untuk memodelkanperangkat lunak yang akan dibuat danperlu adanya standarisasi agar orang diberbagai negara dapat mengerti pemodelanperangkat lunak. Seperti yang kita ketahuibahwa menyatukan banyak kepala untuk

menceritakan sebuah ide dengan tujuanuntuk memahami hal yang sama tidaklahmudah, oleh karena itu di perlukan sebuahbahasa pemodelan perangkat lunak yangdapat dimengerti oleh banyak orang.

2.2.4.1 Use Case DiagramUse Case atau diagram use casemerupakan pemodelan untuk kelakuan(behavior) sistem informasi yang akandibuat. Use case digunakan untukmengetahui fungsi apa saja yang ada didalam sebuah sistem informasi dan siapasaja yang berhak menggunakan fungsi-fungsi itu. Contoh dari diagram use caseditunjukkan pada gambar berikut.

2.2.4.2 Activity DiagramDiagram aktivitas atau activity

diagram menggambarkan workflow (alirankerja) atau aktivitas dari sebuah sistematau proses bisnis atau menu yang adapada perangkat lunak. Contoh activitydiagram ditunjukkan pada gambar berikut.

2.2.4.3 Sequence DiagramDiagram sekuen menggambarkan kelakuanobjek pada use case denganmendeskripsikan waktu hidup objek danmessage yang dikirimkan dan diterimaantar objek.

BAB III

METODOLOGI PENELITIAN

3.1 Instrumen PenelitiansMeliputi bahan dan peralatan

dalam melakukan penelitian, dalampenelitian ini diperlukan beberapaperangkat agar penelitian dapat berjalandengan lancar dan sesuai dengan temapenelitian. Perangkat tersebut dibagimenjadi dua yaitu perangkat lunak danperangkat keras.

3.1.1 Perangkat LunakMerupakan perangkat lunak yang

digunakan dalam penelitian ini. Softwareyang digunakan antara lain :

1. Microsoft Windows 7 Ultimate 64-bit (6.1, Build 7601) digunakansebagai sistem operasi.

2. Eclipse IDE, yang merupakanplatform yang bersifat open source.

3. ADT (Android Development Tools)plug-in yang merupakan plug-intambahan untuk pengembanganaplikasi menggunakan Ecplise IDE.

4. Android SDK (SoftwareDevelopment Kit), digunakan untukmengembangkan aplikasi pada OSAndroid pada komputer denganmenyediakan platform Android

Gambar 4. Use Case Diagram

Gambar 5. Activity Diagram

Gambar 3. Sequence Diagram

beserta tools tambahan untuk yangdimiliki pada perangkat Android.

5. Android AVD (Android VirtualDevice), digunakan sebagai virtualdevice untuk menjalankan aplikasipada OS Android.

6. Enterprise Architect, digunakanuntuk membantu penulis dalampembuatan diagram-diagram UML.

3.1.2 Perangkat KerasMerupakan perangkat keras yang

digunakan dalam penelitian ini. Hardwareyang digunakan antara lain :

1. Notebook HP Pavilion g4.a. Intel(R) Core(TM) i3-2310, CPU2.10GHzb. Radeon (TM) HD 6470M 1GBc. RAM 8GB DDR3d. Hardisk 500GB

2. Perangkat Bergerak (mobilephone).Sony Xperia M C1905, AndroidJellybean 4.1.2, 540 x 960 pixels,4.0 inches.

3.1.3 Objek PenelitianObjek penelitian merupakan

permasalahan yang diteliti. Objek daripenelitian ini adalah buku, jurnal danpenelitian yang telah diteliti oleh penulissebagai tinjauan pustaka.

3.2 Jenis dan Sumber dataData merupakan keterangan

tentang suatu hal, dapat berupa sesuatuyang diketahui atau yang dianggap atauanggapan, atau suatu fakta yangdigambarkan berupa angka, simbol, kodedan lain-lain.

Dalam tugas akhir ini, jenis datayang digunakan adalah :

1. Data KualitatifData kualitatif dibutuhkan untukmengedintifikasi mekanisme utama daridata yang harus dianalisis sepertikomposisi tampilan. Dalam tugas akhir inimenggunakan software pendukung yangmeliputi IDE Eclipse, Android SDK,Android AVD dan Enterprise Architect.

2. Data KuantitatifData kuantitatif digunakan untukmengetahui materi pembelajaran yangdiperoleh dari buku-buku, dokumen sertailmu pengetahuan dari berbagai sumberyang dibaca penulis dan berhubungandengan tugas akhir ini. Data ini berupamateri tentang Android dan metodepencarian algoritma A*.

3.3 Metode Pengumpulan DataAdapun metode yang digunakan

penulis untuk mendapatkan data-datadiatas adalah sebagai berikut :

a. Studi LiteraturStudi Literatur yaitu

mengumpulkan bahan-bahan yang tertulisberupa data-data yang diperoleh darijurnal-jurnal yang diteliti oleh penulis danberhubungan dengan penelitian yangdigunakan. Jurnal yang diteliti antara lainyang berjudul "Penyelesaian Masalah 8-Puzzle dengan Algoritma Hill ClimbingStepest Ascent Loglist Heuristik BerbasisJava", "8-puzzle Menggunakan AlgoritmaIterative Deepning Search (IDS)", "Penelitian Rute Terdekat pada LabirinMenggunakan metode A*" dan "PenerapanAlgoritma A* pada Aplikasi Puzzle".

3.4 Metode Pengembangan Sistem3.4.1 Extreme Programming

Extreme Programming (XP) adalahmetode pengembangan perangkat lunakyang ringan dan termasuk salah satu agilemethods yang dipelopori oleh Kent Beck,Ron Jeffries dan Ward Cunningham. XPmerupakan agile methods yang palingbanyak digunakan dan menjadi sebuahpendekatan yang sangat terkenal. SasaranXP adalah tim yang dibentuk berukuranantara kecil sampai medium saja, tidakperlu menggunakan sebuah tim yang besar.Hal ini dimaksudkan untuk menghadapirequirements yang tidak jelas maupunterjadinya perubahan-perubahanrequirements yang sangat cepat.

3.4.1.1 Tahapan Extreme ProgrammingAdapun tahapan-tahapan yang ada

pada metode pengembangan sistemExtreme Programming yaitu [12] :

1. XP PlanningAktivitas planning pada model

proses XP berfokus pada mendapatkangambaran fitur serta fungsi dari perangkatlunak yang akan dibangun.

2. XP DesignAktivitas design dalam pengembanganaplikasi bertujuan untuk mengatur polalogika dalam sistem. Sebuah design yangbaik, dapat mengurangi ketergantunganantar setiap proses pada sebuah sistem.

3. XP CodingSetelah menyelesaikan

pengumpulan cerita danmenyelesaikan design untuk aplikasisecara keseluruhan, XP lebihmerekomendasikan tim untuk terlebihdahulu membuat modul unit tes yangbertujuan untuk melakukan uji coba setiapcerita yang didapat dari klien..

4. XP TestingTahapan uji coba pada XP sudah

dilakukan juga pada saat tahapansebelumnya yaitu coding. XP menerapkanperbaikan masalah kecil dengan sesegeramungkin akan lebih baik dibandingkanmenyelesaikan masalah pada saat akanmencapai tenggat akhir.

BAB IV

RANCANGAN SISTEM DAN IMPLEMENTASI

4.1 Rancangan SistemMeliputi rencana dan

design atau model yang dibuat berdasarkanlangkah-langkah pada metode penelitianyang diusulkan penulis. Design rancangansistem yang digunakan adalah ExtremeProgramming. Dengan tahapan-tahapannya adalah XP Planning, XPDesign dan XP Coding.

4.1.1 XP PlanningBerisikan tentang gambaran

sederhana tentang aplikasi game 8-puzzledan analisa algoritma A* yang akanditerapkan. Penjelasan tentang game 8-puzzle, algoritma A* dan analisiskebutuhan sistem yang merupakanidentifikasi dan evaluasi permasalahanyang ada, sehingga sistem yang dibangunsesuai dengan kriteria yang diharapkan.

4.1.1.1 Analisis Game 8-Puzzle berbasis Android

Proses permainan 8-puzzle secaraumum dapat berlangsung apabila memiliki1 pemain. Permainan ini dilakukan padapapan permainan yang berbentukbujursangkar dengan ukuran 3x3 yangterdapat 1 ubin kosong sebagai tempatuntuk menggeser ubin yang lain.

Pembangunan game 8-puzzle akandilakukan pada platform Android. Untukpembangunannya menggunakan software

Gambar 6. Tahapan XP

Gambar 7. Initial-goal state

Eclipse IDE yang merupakan aplikasiuntuk meng-coding dalam bahasapemrograman Java, karena pada dasarnyaandroid berbasis Java.

4.1.1.2 Analisis Algoritma A* Ada berbagai algoritma yang dapat

digunakan untuk menyelesaikan game inidiantaranya yaitu Iterative DeepningSearch yang merupakan penggabungandari 2 algoritma yaitu Breadth-first Searchdan Depth-first Search. Penggabunganalgoritma ini mungkin menjadi salah satuyang terbaik dari algoritma lain karenamenggabungkan 2 algoritma menjadi satu.Tetapi algoritma ini masih memilikibanyak kekurangan.

Selain Iterative Deepning Search,algoritma lain yang dapat digunakanadalah Hill Climbing. Ada 2 tipe HillClimbing yaitu Simple dan Stepest Ascent.Dalam kasus ini, akan dibahas StepestAscent Hill Climbing karena lebih baikdari Simple Hill Climbing. Walaupun lebihbaik, Stepest Ascent HC masih memilikikekurangan juga.

Untuk mengatasi kekurungan dariberbagai algoritma berpikir yangdigunakan untuk menyelesaikan game 8-puzzle ini, algoritma berpikir komputerakan dirancang dengan menggunakanalgoritma A*. Rumusan algoritma A* inidibuat sedemikian rupa sehingga pemaindapat melihat solusi dari permainan yangtelah dijalankan.

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

n = posisi koordinat nodef(n) = fungsi evaluasig(n) = biaya (cost) yang sudah dikeluarkandari keadaan awal sampai keadaan nh(n) = estimasi biaya untuk sampai padasuatu tujuan mulai dari n (fungsiheuristik).

dimana,

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

Awal = Initial StateAkhir = Goal State

Pada keempat keadaan tersebutkomputer 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* dapatdijelaskan sebagai berikut:

1. Analisa apakah posisi puzzle sudahterurut atau h(n) = 0?

2. Jika "Tidak", cari kotak-kotak yangmungkin untuk digerakkan (yangberbatasan langsung denganspace/ruang kosong).

3. Hitung f(n) = g(n) + h(n). Simpanpada open list.

4. Cari pada kotak di dalam open list,apakah terdapat lebih dari satu nilaif(n) terkecil.

5. Jika "Tidak", maka gerakkan f(n)yang terkecil. Jika "Ya", makagerakkan f(n) yang pertama kalidicari. 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 puzzleterurut.

Gambar 8. Flowchart A*

4.1.1.3 Analisis Kebutuhan SistemAnalisis kebutuhan sistem

merupakan proses identifikasi dan evaluasipermasalahan-permasalahan yang ada,sehingga sistem yang dibangun sesuaidengan kriteria yang diharapkan. Aplikasiyang dihasilkan harus memenuhikebutuhan sebagai berikut :

1. Aplikasi harus mampumenjalankan permainan 8-puzzlesesuai dengan aturan yang ada.

2. Aplikasi harus memiliki menu hintdan solve yang merupakan bantuandan pencarian solusi. Algoritmaberpikir komputer ini dibuatdengan mengikuti Algoritma A*.

3. Aplikasi harus dapat menggantikecepatan solver menjadi cepatatau lambat.

4. Aplikasi harus mempunyai menureshuffle untuk mengacak ulangpuzzle dan me-restart permainan.

5. Aplikasi harus mampu mencatatberapa langkah yang telah ditempuh user setelah menyelesaikanpermainan.

4.1.2 XP DesignXP design berisikan tentang

pemodelan sistem yaitu use case diagram,activity diagram dan sequence diagramuntuk menjelaskan model aplikasi yangakan dibangun.

4.1.2.1 Use Case Diagram

4.1.2.2 Activity Diagram

4.1.2.3 Sequence Diagram

4.2.1 XP CodingSetelah menyelesaikan

pengumpulan cerita danmenyelesaikan design untuk aplikasisecara keseluruhan, maka harus diimplementasikan menjadi bentuk programaplikasi. XP Coding berisi langkah-langkah membuat game 8-puzzle, solveralgoritma A*, heuristik manhattan dansebagian codingnya.

Gambar 9. Diagram Use Case

Gambar 10. Diagram Aktivitas

Gambar 11 Diagram Sekuen

4.2.1.1 Game 8-PuzzlePermainan ini dilakukan pada

papan permainan yang berbentukbujursangkar dengan ukuran 3x3 yangterdapat 1 ubin kosong sebagai tempatuntuk menggeser ubin yang lain.

4.2.1.2 Solver Algoritma A*Pada game 8-puzzle terdapat

banyak kemungkinan pergeseran yangakan membuat pemain merasa tidak bisamenyelesaikan permainan ini sehinggaakan memerlukan banyak waktu untukdapat menyelesaikan permainan ini.Pemain memerlukan suatu cara yaitudengan menggunakan algoritma A* yanglebih cepat membantu menyelesaikanpermainan. Pemain akan berhasil bila telahmenyusun kembali ubin secara terurut.

4.2.1.3 Heuristik ManhattanA* sebagai algoritma pencarian

yang menggunakan fungsi heuristik untukpencarian rute node-node pada peta.Heuristik yang paling umum digunakanadalah jarak Manhattan. Fungsi heuristikini hanya akan menjumlahkan selisih nilaix dan nilai y dari dua buah titik. Berikutadalah perintah perhitungan heuristikmanhattan pada class Heuristic.java.

BAB VHASIL PENGUJIAN DAN

PEMBAHASAN

5.1 Hasil PenelitianHasil penelitian merupakan hasil

pengujian yang telah diimplementasikan.Tujuan dari tahap ini ialah untukmengetahui apakah sistem yang dibuatsudah sesuai dengan tujuan pembuatanlaporan tugas akhir atau belum. Pada tahapini dilakukan pengujian denganmenggunakan tahapan terakhir ExtremeProgramming yaitu XP Testing.

5.1.1 XP TestingXP Testing merupakan Pada

pembangunan aplikasi yang penulis buat,

XP Testing berisikan 2 macam testingyaitu Blackbox dan Whitebox. Berikutadalah Blackbox Testing dan poin-poinbagian dari perangkat lunak yang akandiuji.

Tabel 1. BlackBox Testing

No

Input Pengujian

Fungsi Hasil Yang Diharapkan

Hasil

1. Icon Game 8-puzzle

Menuju halamanawal game 8-puzzle

Menampilkan awal game 8-puzzle

Memenuhi

2. ButtonTap toPlay

Menuju tampilan gameplay

Menampilkan tampilangame play danmemainkan game.

Memenuhi

3. Menu Lihat Hint

Menuju halamanLihat Hint

Menampilkan tampilanlihat hint.

Memenuhi

4. Menu Solve Puzzle!

Mengurutkan puzzle yang acak menjadibentuk awal.

Puzzle bergerakmenuruti eksekusialgoritma A*

Memenuhi

5. Menu Reshuffle

Mengacak Ulang Puzzle

Puzzle teracak kembali secara random.

Memenuhi

6. Menu Ganti kecepatan Solve

Menuju Tampilan Ganti Kecepatan Solve

Menampilkan Pilihan Cepat dan Lambat

Memenuhi

7. ButtonCepat

Mengganti Kecepat

Kecepatan Solveberganti

Memenuhi

an Solve menjadicepat

menjadi cepat

8. ButtonLambat

Mengganti Kecepatan Solve menjadilambat

Kecepatan Solveberganti menjadi lambat

Memenuhi

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

V(G) = E - N + 2= 25 - 19 + 2= 8

Dimana :E = jumlah edge pada grafik alirN = jumlah node pada grafik alir

Berdasarkan cyclometic complexitytersebut terdapat 8 path sebagai berikut :Path 1 : 1, 2, 5, 6, 7, 8, 13, 14, 15, 20, 23,24, 1, 25Path 2 : 1, 2, 3, 4, 5, 6, 7, 8, 13, 14, 15, 20,23, 24, 1, 25

Path 3 : 1, 2, 5, 6, 7, 8, 9, 11, 12, 13, 14,15, 20, 23, 24, 1, 25Path 4 : 1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13,14, 15, 20, 23, 24, 1, 25Path 5 : 1, 2, 5, 6, 7, 8, 13, 14, 21, 22, 6, 7,8, 13, 14, 15, 20, 23, 24, 1, 25Path 6 : 1, 2, 5, 6, 7, 8, 13, 14, 16, 19, 15,20, 23, 24, 1, 25Path 7 : 1, 2, 5, 6, 7, 8, 13, 14, 16, 17, 18,19, 15, 20, 23, 24, 1, 25Path 8 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,13, 14, 16, 17, 18, 19, 15, 20, 23,

24, 1, 25V(G) Type of Procedure Risk1 - 4 A simple procedure Low5 - 10 A well sturctured

and stableprocedure

Low

11 -20

A more complexprocedure

Moderate

20 -50

A complexprocedure, alarming

High

5.2. PembahasanDari pengujian sistem yang

menggunakan XP Testing, sebagaian besarberjalan dengan lancar. Berikut adalahhasil dari game 8-Puzzle yang telahdibangun.

5.2.1 Halaman AwalHalaman awal merupakan tampilan

awal ketika user membuka aplikasi game8-puzzle.Gambar 12 Whitebox

Gambar 13 Halaman Awal

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

5.2.2 Halaman GameplayHalaman gameplay merupakan

tampilan dimana user dapat memainkangame 8-puzzle. Puzzle akan teracak secararandom. Dan juga user memilih menu-menu yang tersedia.

5.2.3 Tampilan Lihat HintHalaman Lihat Hint menampilkan

gambar awal dari puzzle yang dapatmembantu pemain.

5.2.4 Tampilan Game SelesaiTampilan Game selesai hanya akan

menampilkan alert dialog berupa jumlahlangkah yang telah ditempuh User.

BAB VIKESIMPULAN DAN PENELITIAN

SELANJUTNYA

6.1 KesimpulanKesimpulan dari penelitian yang

penulis buat adalah sebagai berikut :1. Algoritma A* yang diterapkan

pada game 8-puzzle merupakanalgoritima yang optimal, karenamerupakan penjumlahan darilangkah yang ditempuh dan fungsiheuristik.

2. Game 8-puzzle yang dibangunberbasis Android lebih mudahdikembangkan lagi, karena androidmemiliki bahasa, desain dan modelyang modern dan masih terusberkembang.

Gambar 14 Gameplay

Gambar 15 Lihat Hint

Gambar 16 Game Selesai

6.2 Penelitian SelanjutnyaRekomendasi merupakan future

works yang akan dilakukan sebagaitahapan penelitian selanjutnya dari tugasakhir yang dibuat sebagai berikut :

1. Dapat mengembangkan game 8-puzzle sebagai sarana edukasi.

2. Pembuatan antarmuka/interfaceyang lebih menarik, sepertipenambahan background, tampilanmenu dan sebagainya.

3. Dapat menggunakan gambar yanglain sebagai objek 8-puzzle, danjuga mengambil gambar dari imagegallery masing-masing gadgetAndroid.

4. Dapat menambahkan cacatanwaktu penyelesaian dan high score.

5. Diharapkan dapat menggunakanalgoritma lain seperti IterativeDeepning A*, genetik, greedy dansebagainya.

DAFTAR PUSTAKA

[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 JawaBendi, "Penerapan Algoritma A* padaAplikasi Puzzle," Seminar NasionalTeknologi Informasi dan Komunikasi, pp.23-28, 2013.

[3] Muhammad Nasrul Anwar, "8-PuzzleDengan Menggunakan Algoritma IterativeDeepning Search (IDS)," AMIKOM,Jogjakarta, 2010.

[4] Chandra Usman, Kenedy Candra, HendriSopryadi, and Willy, "Rancang BangunGame Slider Puzzle Berbasis AndroidMenggunakan Metode Heuristik denganTeknik Best First Search," STMIK MDP,p. 10, 2013.

[5] Azizah Zakiah, "Penyelesaian Masalah 8-Puzzle dengan Algoritma Hill Climbing

Stepest Ascent Loglist Heuristik BerbasisJava," Seminar Nasional Teknologi danKomunikasi, pp. 158-163, March 2012.

[6] Rengga Dionata Putra, Ir. MuhammadAswin, and Waru Djuriatno, "PencarianRute Terdekat Pada Labirin MenggunakanMetode A*," EECCIS, vol. 6, pp. 1-4,Desember 2012.

[7] T. Sutojo, Edy Mulyanto, and Dr. VincentSuhartono, Kecedasan Buatan.Yogyakarta: ANDI, 2011.

[8] Wahyudi Fauzan, "Pembangunan AplikasiGame Puzzle and The Solver," UniversitasKomputer Indonesia, Bandung, 2013.

[9] Nazruddin Safaat H, PemrogramanAplikasi Mobile Smartphone dan TabletPC Berbasis Android. Bandung:INFORMATIKA, 2012.

[10] Rosa A. S and M. Shalahuddin, RekayasaPerangkat Lunak. Bandung:INFORMATIKA, 2013.

[11] Mohammed Ekhlaif and Sulaf A. Elshaar,"A Systematic Study of ExtremeProgramming and Their Implementationin Libyan Software," World AppliedSciences Journal, pp. 410-417, March2013.

[12]

Roger Pressman, "Introduction toSoftware Engineering," SoftwareEngineering: A Praccitioner's Approach,p. 27, 2009.