Sistem Pakar Implementasi Game Maze dengan Java Menggunakan Metode Depth First Search PDF

Preview

Summary

SISTEM PAKAR DEPTH FIRST SEARCH Makalah ini bertujuan untuk memenuhi tugas dalam perkuliahan Sistem Pakar Pengampu: I Made Sunia Raharja, S.Kom.,M.Cs. OLEH: I Kadek Teo Prayoga Kartika 1504505086 I Ketut Wahyu Ariprasasmita 1504505088 Komang Oka Mahardika .A 1504505070 PROGRAM STUDI TEKNOLOGI INFORM...

Description

SISTEM PAKAR DEPTH FIRST SEARCH Makalah ini bertujuan untuk memenuhi tugas dalam perkuliahan Sistem Pakar Pengampu: I Made Sunia Raharja, S.Kom.,M.Cs.

OLEH:

I Kadek Teo Prayoga Kartika

1504505086

I Ketut Wahyu Ariprasasmita

1504505088

Komang Oka Mahardika .A

1504505070

PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS TEKNIK UNIVERSITAS UDAYANA 2017

Daftar Isi

BAB I .................................................................................................................................. 3 A. Latar Belakang ...................................................................................................... 3 B. Rumusan Masalah ................................................................................................ 3 C. Metode Penelitian ................................................................................................. 3 BAB II ................................................................................................................................ 4 A. Review Dasar Depth First Search ........................................................................ 4 B.

Studi Kasus Penggunaan Depth-First-Search Pada Maze Generator ................. 8

C. Implementasi Aplikasi Maze ke dalam Program Java menggunakan Metode Depth First Search ...................................................................................................... 15 BAB III ............................................................................................................................ 29 A. Kesimpulan .......................................................................................................... 29 Daftar Pustaka ............................................................................................................ 30

2

BAB I Pendahuluan

A.

Latar Belakang Permainan maze atau labirin adalah permainan puzzle yang memiliki jalur-

jalur yang bercabang dan mengharuskan pemain untuk mencari rute yang benar dari jalur-jalur ini untuk dapat mencapai target. Pada permainan maze biasa, pemain akan mencari jalur untuk mencapai target, namun dalam User Costumized Maze, pemain tidak mencari jalur tersebut namun diminta untuk menempatkan target di sembarang tempat yang diijinkan dan merancang kembali maze yang sudah ada dengan menggeser penghalang-penghalang yang tersedia untuk menyulitkan pencarian jalur menuju target. Pencarian jalur akan dilakukan oleh komputer dengan agen cerdas yang ada di permainan ini. Selain mencari jalur, komputer juga akan mengumpulkan nilai (score) dengan cara mengumpulkan benda-benda dengan nilai tertentu yang telah diletakkan di jalur-jalur maze. Pemain dinyatakan menang apabila agen cerdas tidak dapat menemukan goal sesuai batas maksimum langkah yang telah ditentukan atau tidak berhasil mengumpulkan score minimum yang telah ditentukan. Pemain dapat mengatur kriteria misi yang akan dilakukan komputer.

B.

Rumusan Masalah

1.

Apa itu Depth First Search?

2.

Bagaimana Studi Kasus Depth First Search?

3.

Bagaimana Program Depth First Search?

C.

Metode Penelitian Metode penelitian yang digunakan penulis adalah menggunakan teknik

library research dimana sumber yang diambil melalui jurnal, buku, serta internet yang menagndung unsur sesuai dengan topik yang dibahas yaitu Depth First Search

3

BAB II ISI

A.

Review Dasar Depth First Search Depth First Search atau tingkatan pertama pencarian adalah algoritma

pencarian yang digunakan untuk mencari atau melintasi grafik yang diberikan atau pohon struktur data. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya (misalnya prioritas penelusuran berdasarkan anak pertama simpul sebelah kiri ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam. Strategi yang digunakan dalam metode pencarian Depth First Search ini adalah mencari lebih dalam pada grafik hingga mendapatkan hasil yang diinginkan. Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner (simpul sebelah kanan) lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya. Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L. Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita akan membahas dengan cara yang

4

menggunakan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ? Berikut ini adalah urutan algoritmanya: No.

Algoritma

1.

Masukkan simpul root ke dalam tumpukan dengan push

2.

Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas

3.

Hapus isi stack teratas dengan prosedur pop

4.

Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul

5.

Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack

6.

Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stacknya setiap iterasi adalah:

Dari gambar diatas dapat dijelaskan

bahwa kita dapat mengetahui

kelemahan dan kelebihan dari algoritma Depth First Search, yaitu pada tabel berikut. Kelebihan

Kelemahan

Membutuhkan memori relatif kecil, Memungkinkan

tidak

ditemukannya

karena hanya node-node pada lintasan tujuan yang diharapkan, karena jika yang aktif saja yang disimpan

pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga)

Secara kebetulan, akan menemukan Hanya mendapat 1 solusi pada setiap solusi tanpa harus menguji lebih banyak pencarian, karena jika terdapat lebih dari lagi dalam ruang keadaan, jadi jika satu solusi yang sama tetapi berada pada

5

solusi yang dicari berada pada level level yang berbeda, maka DFS tidak yang dalam dan paling kiri, maka DFS menjamin untuk menemukan solusi akan menemukannya dengan cepat

yang paling baik

Pada subbab berikutnya akan menjelaskan mengenai implementasi dari algoritma Depth First Search dimana implementasi dalam bentuk aplikasi yang telah dibuat di kota Solo adapun landasan teori pembuatan aplikasi sebagai berikut: Menurut Sommerville, waterfall model meliputi kegiatan proses dasar spesifikasi, pengembangan, validasi, dan evolusi dan menyajikannya sebagai fase proses yang terpisah seperti spesifikasi persyaratan, desain perangkat lunak, implementasi, pengujian dan sebagainya. (Sommerville,2011, h.30). Sommerville memecah model waterfall ini menjadi 5 tahapan meskipun secara garis besar sama dengan tahapan-tahapan model waterfall pada umumnya. a.

Analisis dan definisi kebutuhan (Requirmnets Definition) Fitur, pembatas, dan tujuan dari sistem dibuat berdasarkan konsultasi

dengan user. Hal – hal itu kemudian menjadi spesifikasi dari sistem tersebut. b.

Perancangan sistem dan piranti lunak (System and Software Design) Proses ini mengalokasi kebutuhan – kebutuhan yang ada ke perangkat

keras atau sistem perangkat lunak dengan membuat arsitektur sistem secara keseluruhan. Desain perangkat lunak melibatkan identifikasi dan penjelasan fundamental dari abstrak sistem dan hubungannya. c.

Implementasi dan unit testing Pada tahap ini, desain perangkat lunak diwujudkan dalam bentuk unit –

unit program. Unit testing bertujuan untuk memastikan bahwa setiap unit program dibuat sesuai dengan spesifikasinya. d.

Penggabungan dan pengujian sistem (Integration dan System Testing) Unit – unit program di uji sebagai satu sistem yang utuh untuk memastikan

bahwa semua spesifikasi telah dipenuhi. Setelah diuji, sistem dikirimkan ke user. e.

Pengoperasian dan Pemeliharaan (Operation and Maintenance) Pada tahap ini tidak harus dilakukan, namun merupakan tahap yang

kadang sangat diperlukan untuk melakukan pengembangan dan membutuhkan

6

waktu paling lama. Pemeliharaan meliputi perbaikan kesalahan yang tidak ditemukan pada tahap – tahap sebelumnya, memperbaiki sistem dan menjadikan sistem lebih baik untuk memenuhi spesifikasi yang baru. Pemeliharaan perangkat lunak mengaplikasi lagi setiap fase sebelumnya, lalu memperbaiki program sebelumnya dan tidak membuat yang baru lagi.

7

B.

Studi Kasus Penggunaan Depth-First-Search Pada Maze Generator

B.1

PENDAHULUAN Labirin atau maze merupakan tempat yg penuh dengan jalan dan lorong

yang

berliku-liku

seringkali

dijadikan

dan simpang siur dan dipisahkan oleh tembok. Labirin tantangan

dalam

permainan seperti puzzle, dimana

terdapat objek dalam posisi awal harus menemukan jalan keluar pada posisi yang ditentukan. Dalam ilmu komputer, terdapat beberapa algoritma yang dapat digunakan untuk membuat Kruskal’s

Algorithm,

sebuah

labirin

misalnya

Recursive Backtracker,

Prim’s Algorithm, dan Depth-First-Search. Depth-

First-Search atau DFS merupakah salah satu cara paling mudah dalam membuat sebuah labirin yang tidak terlalu kompleks. Dalam kehidupan sehari-hari terdapat beberapa aplikasi labirin yang dapat dijumpai terutama dalam industry game, karena labirin menantang pemain untuk mencari jalan keluar dari titik yang ditentukan sebelumnya. Selain itu dibeberapa Negara dibuat labirin dengan ukuran manusia dan menantang orang-orang untuk masuk kedalamnya, sebagai salah satu atraksi untuk menarik wisatawan. Walter D. Pullen membagi labirin menjadi beberapa jenis berdasarkan properti antara lain Dimension , Hyper-dimension, Topology , Tessellation , Routing, Texture, dan Focus. Berdasarkan properti routing , terdapat 5 jenis labirin yaitu : 1.

Perfect Labirin Perfect memiliki sifat yaitu tidak terdapat jalan yang berulang(loop) selain itu tidak ada sel yang terisolasi pada labirin.

Gambar 1.1 Labirin Perfect

8

2.

Braid Labirin Braid tidak memiliki jalan buntu, semua jalan terhubung satu sama lain, sehingga dapat meningkatkan tingkat kesulitan pada labirin.

Gambar 1.2 Labirin Braid

3.

Unicursal Labirin Unicursal adalah labirin yang tidak memiliki persimpangan atau cabang, sehingga untuk mencapai titik selesai dari titik mulai hanya perlu mengikuti jalan yang telah disediakan.

Gambar 1.3 Labirin Unicursal

4.

Sparseness Labirin Sparseness merupakan labirin dimana tidak seluruh dindingnya dibuat jalan sehingga seolah-olah seperti pulau yang dikelilingi lautan.

Gambar 1.4 Labirin Sparseness

9

5.

Partial Braid Labirin Partial Braid merupakan labirin dengan kombinasi antara jalan buntu, dan jalan perulangan (loop) sehingga meningkatkan kesulitan dalam mencari jalan. Algoritma DFS merupakan algoritma yang digunakan untuk membuat

sebuah labirin perfect.

B.2

PEMBAHASAN Untuk membuat labirin dengan metode DFS, secara garis besar dapat

dibuat sebagai berikut : 1.

Pilih sembarang sel X dan tandai sebagai sel aktif dan visited (telah dikunjungi).

2.

Selama ada sel yang belum dikunjungi (unvisited cells) maka : a.

Jika sel aktif X memiliki tetangga T4 yang belum dikunjungi maka : §

Pilih acak salah satu T

§

Push(T) kedalam Stack S

§

Hapus dinding pemisah antara sel X dan T

§

Tandai T sebagai aktif dan visited

b. Selain itu jika Stack S tidak kosong maka : §

Pop() dari Stack S

§

Tandai keluaran Pop() sebagai sel aktif

c. Selain itu maka §

Pilih acak sel yang belum dikunjungi, dan tandai sebagai sel aktif dan visited

10

Berikut merupakan ilustrasi dari algoritma diatas :

Gambar 3.1 Pilih acak sel dan tandai aktif

Pada gambar 3.1 pilih secara acak salah satu sel dalam grid dan tandai sebagai aktif dan push kedalam Stack S.

Gambar 3.2 Acak tetangga dan push(T)

Pada gambar 3.2 dari sel aktif atau X, acak salah satu dari kemungkinan sel tetangga T yang belum dikunjungi dan push ke dalam S, kemudian tandai sel T beserta sel antara T dan X dengan visited.

11

Gambar 3.3 Tandai T beserta sel diantara T dan X sebagai visited

Pada gambar 3.3 , pindahkan posisi aktif ke sel posisi teratas dari S. Dari sel X pilih acak sel tetangga T dan push kedalam S.

Gambar 3.4 Acak Tetangga dan Push(T)

Gambar 3.5 Tandai T beserta sel diantara T dan X sebagai visited

12

Pada gambar 3.4 dan 3.5 tandai sel T berserta sel antara T dan X sebagai visited. Kemudian pindahkan posisi aktif ke sel posisi teratas pada S dan pilih salah satu sel tetangga T yang belum pernah dikunjungi.

Gambar 3.6 Posisi Sel X tidak memiliki tetangga

Gambar 3.7 Pop() seluruh sel hingga sel yang memiliki tetangga yang belum dikunjungi

Pada gambar 3.6 setelah berulang-ulang dilakukan langkah sebelumnya sel X tidak memiliki tetangga, sehingga pada gambar 3.7 dilakukan pop pada S5 hingga menjumpai sel dalam S yang masih memiliki tetangga, dan proses diulang kembali.

13

Gambar 3.8 Proses diulang dari awal

Pada gambar 3.8 setelah sel X dipilih, maka proses akan diulang lagi dari awal dan dilakukan terus menerus hingga seluruh sel pada S kosong.

B.3

HASIL PEMBAHASAN Berikut gambar 5.1 merupakan hasil yang didapatkan setelah seluruh

proses dilakukan hingga akhir :

Gambar 5.1 Labirin dengan ukuran 21 x 31

Hal yang sama tetap berlaku untuk labirin dengan ukuran yang berbedabeda, hal ini dapat dilihat pada gambar 5.2

14

C.

Implementasi Aplikasi Maze ke dalam Program Java menggunakan Metode Depth First Search Sebelum beranjak untuk memulai proses running aplikasi yang akan kita

buat ada baiknya sebelum membuat kita mengetahui bagaimana alur aplikasi akan berjalan saat di running atau eksekusi, maka yang kita butuhkan adalah flowchart sebagai berikut:

Flowchart diatas menjelaskan bahwa setiap user melakukan input atau aksi berupa input maka program akan mengecek apakah inputan benar atau salah jika salah baka kursor akan tetap diam, jika benar maka kursor akan berpindah tempat sesuai perintah yang dimasukkan sampai kursor sampai pada titik akhir maka program berhenti. C.1

Kode Program menggunakan Bahasa Pemrograman Java dengan Netbeans 8.0 Sekarang pada subbab ini akan membahas tentang bagaimana kode

program yang terjadi didalam program saat dijalankan dan bagaimana implementasinya,

untuk

mengetahuinya

pertama

bagaimana struktur dalam netbeans sebagai berikut:

15

kita

harus

mengetahui

Gambar diatas merupakan tampilan struktur project yang kita buat dalam IDE Netbeans 8.0. Kelas Maze.java merupakan kelas utama yang akan menjalankan aplikasi serta eksekusinya. Untuk kelas MainMenu.java sebagai berikut: import import import import

java.awt.event.ActionEvent; java.awt.event.ActionListener; java.io.File; java.util.ArrayList;

import import import import import

javax.swing.ImageIcon; javax.swing.JButton; javax.swing.JComboBox; javax.swing.JFrame; javax.swing.JLabel;

/** * * @author student */ public class MainMenu { JFrame Menu = new JFrame("Maze"); JButton Start = new JButton("Play"); JButton Exit = new JButton("Exit"); JButton MapMaker = new JButton("Map Maker"); ImageIcon picture = new ImageIcon("res/Images/MazePicture.png"); JLabel imageLabel = new JLabel(picture); ArrayList mapList = new ArrayList(); JComboBox lvlList; int menuWidth = 100; //Width of each button/item on display int menuHeight = 30;//Height of each button/item on display int menuY = 460; //Button/item location on display int WIDTH = 490; int HEIGHT = 530; public MainMenu() { //Load map list

16

getMapList(); lvlList = new JComboBox(mapList.toArray(new String[mapList.size()])); //Menu Variables Menu.setResizable(false); Menu.setSize(WIDTH, HEIGHT); Menu.setLayout(null); Menu.setLocationRelativeTo(null); Menu.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); //Start Button Variables Start.setSize(menuWidth,menuHeight); Start.setLocation(10, menuY); Menu.add(Start); Start.addActionListener(new ActionListener(){ @Override public void actionPerformed(ActionEvent arg0) { new Maze(lvlList.getSelectedItem().toString()); Menu.setVisible(false); } }); //Map Maker Button Variables MapMaker.setSize(menuWidth,menuHeight); MapMaker.setLocation(120, menuY); Menu.add(MapMaker); MapMaker.addActionListener(new ActionListener(){ @Override public void actionPerformed(ActionEvent e) { new MazeMapMaker(); Menu.setVisible(false); } }); //Level Selector lvlList.setSize(menuWidth+35, menuHeight); lvlList.setLocation(230, menuY); Menu.add(lvlList); //Exit Button Variables Exit.setSize(menuWidth,menuHeight); Exit.setLocation(375,menuY); Menu.add(Exit); Exit.addActionListener(new ActionListener(){ @Override public void actionPerformed(ActionEvent e) { System.exit(0); } }); //Display Picture imageLabel.setBounds((WIDTH-412)/2, 25, 412, 412); imageLabel.setVisible(true);

17

Menu.add(imageLabel); Menu.setVisible(true); } static boolean levelsExistAlready = false; public void getMapList(){ for(int i = 0; i < 99; i++){ File map = new File("./Level "+i+".map"); if(map.exists()){ System.out.println("Level "+i+" exists"); mapList.add("Level "+i+".map"); levelsExistAlready = true; } } } }

Kode Program Diatas merupakan kode program untuk menampilkan main menu saat user melakukan pertama kali running program akan tampil menu dan menggunakan kelas ini, selanjutnya adalah kelas MapMakerTile.java kode program sebagai berikut: import java.awt.Color; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; import javax.swing.JPanel; public class MapMakerTile extends JPanel{ int x, y; public MapMakerTile(int x, int y){ this.x = x; this.y = y; addMouseListener(new MouseAdapter(){ public void mousePressed(MouseEvent e) { if(e.getButton() == MouseEvent.BUTTON1){ setBackground(Color.WHITE); MazeMapMaker.map[x][y] = 1; } if(e.getButton() == MouseEvent.BUTTON3){ setBackground(Color.GRAY); MazeMapMaker.map[x][y] = 0; } } }); } }

Pada kode program diatas menjelaskan bahwa kode program diatas bertujuan atau berfungsi untuk melakukan proses pengambilan data map untuk

18

dijadikan tempat untuk kursor nantinya, atau saat pengguna menjalankan program dengan sudah mengklik tombol play maka kode program ini akan berjalan. Selanjutnya kelas Maze.java kode program sebagai berikut: import import import import import import import

java.awt.Color; java.awt.event.KeyEvent; java.awt.event.KeyListener; java.awt.event.WindowAdapter; java.awt.event.WindowEvent; java.io.BufferedReader; java.io.FileReader;

import javax.swing.JFrame; import javax.swing.JOptionPane; import javax.swing.JPanel; public...