AGEN CERDAS UNTUK 3D GAME LABIRIN MENGGUNAKAN

ALGORITMA A* DAN DIJKSTRA

TUGAS AKHIR

Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1

Teknik Informatika Universitas Muhammadiyah Malang

Oleh :

HARIS KHOIRUDDIN SUKASNO PUTRA

201010370311446

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS MUHAMMADIYAH MALANG

2017

iii

iv

v

vi

KATA PENGANTAR

Puji dan rasa syukur penulis panjatkan kehadirat Allah SWT, karena berkat

limpahan rahmat, hidayah, dan inayah-Nya maka tugas akhir ini dapat diselesaikan

dengan lancar. Sholawat dan salam semoga selalu tercurah pada baginda Rosulullah

Muhammad SAW.

Penyusunan Laporan Tugas Akhir (TA) dengan judul “AGEN CERDAS

UNTUK 3D GAME LABIRIN MENGGUNAKAN ALGORITMA A* DAN

DIJKSTRA” yang diajukan sebagai salah satu syarat untuk meraih gelar Sarjana Strata

1 di Universitas Muhammadiyah Malang.

Penyusunan tugas akhir ini penulis berusaha menerapkan ilmu yang telah didapat

selama menjalani perkuliahan dengan tidak terlepas dari petunjuk, bimbingan, bantuan,

dan dukungan dari berbagai pihak. Penulis menyadari bahwa tugas akhir ini belum

sempurna baik dari segi materi maupun penyajiannya. Untuk itu saran dan kritik yang

membangun sangat diharapkan dalam penyempurnaan tugas akhir ini.

Terakhir penulis berharap semoga tugas akhir ini dapat memberikan hal yang

bermanfaat dan menambah wawasan bagi pembaca dan khususnya bagi penulis.

Malang, 11 Desember 2017

Penulis

vii

DAFTAR ISI

Lembar Persetujuan ............................................................................................. i

Lembar Pengesahan ............................................................................................. ii

Abstrak ................................................................................................................. iv

Abstrack ................................................................................................................ v

Kata Pengantar ..................................................................................................... vi

Daftar Isi .............................................................................................................. vii

Daftar Gambar ..................................................................................................... x

Daftar Tabel .......................................................................................................... xii

BAB I PENDAHULUAN .................................................................................. 1

1.1 Latar Belakang ........................................................................................... 1

1.2 Rumusan Masalah ...................................................................................... 2

1.3 Tujuan Penelitian ....................................................................................... 2

1.4 Batasan Masalah ......................................................................................... 2

1.5 Metodologi ................................................................................................ 2

1.5.1 Studi Literatur ........................................................................................ 2

1.5.2 Perancangan Sistem ............................................................................... 2

1.5.3 Implementasi Sistem .............................................................................. 3

1.5.4 Uji Coba dan Evaluasi ............................................................................ 3

1.6 Sistematika Penulisan ................................................................................ 3

BAB II LANDASAN TEORI ........................................................................... 5

2.1 Game .......................................................................................................... 5

2.1.1 Platform ................................................................................................... 5

2.1.2 Dimensi .................................................................................................... 6

2.1.3 Genre ....................................................................................................... 7

2.2 Labirin ....................................................................................................... 9

2.3 Blender ....................................................................................................... 9

2.4 Algoritma A* & Dijkstra ........................................................................... 11

a. A* ................................................................................................................ 11

viii

b. Dijkstra ....................................................................................................... 13

2.5 Unity3D Engine .......................................................................................... 16

BAB III ANALISA DAN PERANCANGAN SYSTEM ................................. 18

3.1 Analisa Sistem ............................................................................................ 18

3.1.1 Analisa dan Gambaran Umum ............................................................... 18

3.1.2 Perbedaan dan Persamaan dengan Penelitian Sebelumnya .................... 18

3.1.3 Analisa Data . .......................................................................................... 19

3.1.4 Analisa Kebutuhan Sistem ..................................................................... 19

a. Kebutuhan Fungsional ............................................................................ 19

b. Kebutuhan Non Fungsional ..................................................................... 19

3.2 Perancangan Sistem .................................................................................. 19

3.2.1 Flowchart Sistem ..................................................................................... 19

a. Flowchart Game Play ................................................................................ 19

b. Flowchart Algoritma A* ........................................................................... 21

c. Flowchart Algoritma Dijkstra ................................................................... 23

3.2.2 Desain Interface Sistem .......................................................................... 24

a. Form Tampilan Awal ................................................................................. 24

b. Form Tampilan Find Match ....................................................................... 25

c. Form Tampilan Create Game .................................................................... 26

d. Form Tampilan Search Game .................................................................... 26

BAB IV IMPLEMENTASI DAN PENGUJIAN ............................................. 28

4.1 Implementasi Sistem ................................................................................... 28

4.1.1 Implementasi Method Pada Aplikasi yang dibangun ............................. 28

a. Implementasi Kelas MainMenu ................................................................. 29

1) Implementasi Method OnGUI ................................................................ 29

2) Implementasi Method WindowCreateGame .......................................... 32

3) Implementasi Method WindowSearchGame ......................................... 33

b. Implementasi Kelas PathFinding Algoritma AStar ................................... 35

ix

1) Implementasi Kelas Grid ........................................................................ 35

a) Implementasi Method CreateGrid ...................................................... 35

b) Implementasi Method NodeFromWorldPoint ................................... 36

c) Implementasi Method GetNeighbours ............................................... 36

d) Implementasi Method GenerateMapData .......................................... 37

e) Implementasi Method GenerateMapVisual ....................................... 40

2) Implementasi Kelas Node ...................................................................... 41

3) Implementasi Kelas PathFinding ........................................................... 43

a) Implementasi Method FindPath ......................................................... 44

b) Implementasi Method RetracePath .................................................... 46

c) Implementasi Method GetDistance .................................................... 46

4) Implementasi Kelas Unit ........................................................................ 47

c. Implementasi Kelas PathFinding Algoritma Dijkstra ................................ 48

1) Implementasi Kelas DijkstraMap ........................................................... 48

a) Implementasi Method CreateGrid ...................................................... 48

b) Implementasi Method Getneighbour ................................................. 49

c) Implementasi Method NodeFromWorldPoint ................................... 50

d) Implementasi Method GenerateMapData .......................................... 50

e) Implementasi Method GenerateMapVisual ....................................... 53

2) Implementasi Kelas DijkstraPathFind .................................................... 54

a) Implementasi Method FindPath ......................................................... 55

b) Implementasi Method RetracePath .................................................... 57

3) Implementasi Kelas DijkstraUnit ........................................................... 58

4.2 Pengujian Sistem ......................................................................................... 59

4.2.1 Pengujian Fungsionalitas Sistem dan Analisa Aplikasi ........................... 59

BAB V PENUTUP ............................................................................................. 69

5.1 Kesimpulan ................................................................................................ 69

5.2 Saran ........................................................................................................... 69

x

DAFTAR GAMBAR

Gambar 2.1 Pseudocode Algoritma A* ......................................................... 12

Gambar 2.2 Pseudocode Algoritma Dijkstra ................................................. 14

Gambar 3.1 Flowchart Game Play ............................................................... 20

Gambar 3.2 Flowchart Algoritma A* ............................................................ 22

Gambar 3.3 Flowchart Algoritma Dijkstra .................................................... 24

Gambar 3.4 Form Tampilan Awal ................................................................. 25

Gambar 3.5 Form Tampilan Find Match ....................................................... 25

Gambar 3.6 Form Create Game ..................................................................... 26

Gambar 3.7 Form Search Game ..................................................................... 26

Gambar 4.1 Implementasi Method OnGUI ................................................... 30

Gambar 4.2 Form Main Menu ........................................................................ 31

Gambar 4.3 Form Find Match ........................................................................ 31

Gambar 4.4 Implementasi Method WindowCreateGame ............................. 32

Gambar 4.5 Form Create Game ..................................................................... 33

Gambar 4.6 Implementasi Method WindowSearchGame ............................. 34

Gambar 4.7 Form Search Game .................................................................... 34

Gambar 4.8 Implementasi Method CreateGrid ............................................. 36

Gambar 4.9 Implementasi Method NodeFromWorldPoint ............................ 36

Gambar 4.10 Implementasi Method GetNeighbours........................................ 37

Gambar 4.11 Implementasi Method GenerateMapData ................................... 40

Gambar 4.12 Implementasi Method GenerateMapVisual ................................ 40

Gambar 4.13 Tampilan Kelas Grid .................................................................. 41

Gambar 4.14 Implementasi Kelas Node ........................................................... 43

Gambar 4.15 Implementasi Kelas PathFinding ................................................ 43

Gambar 4.16 Implementasi Method FindPath ................................................. 46

Gambar 4.17 Implementasi Method RetracePath ............................................. 46

Gambar 4.18 Implementasi Method GetDistance ............................................ 47

Gambar 4.19 Implementasi Kelas Unit ............................................................ 47

Gambar 4.20 Tampilan A* Pathfinding ........................................................... 48

Gambar 4.21 Implementasi Method CreateGrid .............................................. 49

xi

Gambar 4.22 Implementasi Method GetNeighbour ......................................... 49

Gambar 4.23 Implementasi Method NodeFromWorldPoint ............................ 50

Gambar 4.24 Implementasi Method GenerateMapData ................................... 53

Gambar 4.25 Implementasi Method GenerateMapVisual ................................ 53

Gambar 4.26 Tampilan Kelas DijkstraMap...................................................... 54

Gambar 4.27 Implementasi Kelas DijkstraPathFind ........................................ 55

Gambar 4.28 Implementasi Method FindPath ................................................. 57

Gambar 4.29 Implementasi Method RetracePath ............................................. 58

Gambar 4.30 Implementasi Kelas DijkstraUnit ............................................... 58

Gambar 4.31 Tampilan Dijkstra Pathfinding ................................................... 59

Gambar 4.32 Implementasi Server1 ................................................................. 60

Gambar 4.33 Implementasi Server2 ................................................................. 60

Gambar 4.34 Implementasi Server3 ................................................................. 61

Gambar 4.35 Implementasi Server Connection................................................ 61

Gambar 4.36 Implementasi Client .................................................................... 62

Gambar 4.37 Implementasi Client Connection ................................................ 62

Gambar 4.38 Implementasi Disconnection ...................................................... 63

Gambar 4.39 A* Petak Acak1 .......................................................................... 64

Gambar 4.40 A*Petak Acak2 ........................................................................... 64

Gambar 4.41 A*Petak Acak3 ........................................................................... 65

Gambar 4.42 A*Petak Acak4 ........................................................................... 66

Gambar 4.43 Dijkstra Petak Acak1 .................................................................. 67

Gambar 4.44 Dijkstra Petak Acak2 .................................................................. 67

Gambar 4.45 Dijkstra Petak Acak3 .................................................................. 68

xii

DAFTAR TABEL

Tabel 4.1 Pengujian Fitur pada Perangkat Lunak .............................................. 68

xiii

DAFTAR PUSTAKA

[1] Saman A. B. S., Abdramane Issa, Solving a Reconfigurable Maze using Hybrid Wall

Follower Algorithm, November 2013.

[2] Fauzi Imron, Penggunaan Algoritma Dijkstra Dalam Pencarian Rute Tercepat Dan Rute

Terpendek, Maret 2011.

[3] Patrick Lester, A* Pathfinding for Beginners, 2003.

[4] Enka Muhammad, Game Sebagai Sarana Edukasi, 2010.

[5] Anonim, Gemastik Pelopori Game Edukas, Oktober 20 2010.

[6] Fajar, E., Peran Komputer Bagi Pendidikan Anak, Oktober 20, 2010.

[7] P, M. G., Pengantar Teknologi Game, Oktober 19, 2010.

[8] I Gede S. A., Penggunaan Metode Kecerdasan Buatan Runut Maju Dalam Memecagkan

Permasalahan Game Labirin. April 2012.