tugas akhireprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · tugas...

13
IMPLEMENTASI ALGORITMA A* PATHFINDING UNTUK ENEMY AI DI GAME WAYANG ROBOT TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang Oleh : Ilham Hasymi Effendi 09560242 JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2012

Upload: trinhhanh

Post on 19-Mar-2019

221 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

IMPLEMENTASI ALGORITMA A* PATHFINDING

UNTUK ENEMY AI DI GAME WAYANG ROBOT

TUGAS AKHIR

Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1

Teknik Informatika Universitas Muhammadiyah Malang

Oleh :

Ilham Hasymi Effendi

09560242

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS MUHAMMADIYAH MALANG

2012

Page 2: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

LEMBAR PERSETUJUAN

IMPLEMENTASI ALGORITMA A* PATHFINDING

UNTUK ENEMY AI DI GAME WAYANG ROBOT

TUGAS AKHIR

Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1

Teknik Informatika Universitas Muhammadiyah Malang

Menyetujui,

Pembimbing I

Yuda Munarko, S. Kom, M. Sc

NIP: 10806110443

Pembimbing II

Hardianto Wibowo, S.Kom

NIDN : 07210386002

Page 3: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

LEMBAR PENGESAHAN

IMPLEMENTASI ALGORITMA A* PATHFINDING

UNTUK ENEMY AI DI GAME WAYANG ROBOT

TUGAS AKHIR

Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1

Teknik Informatika Universitas Muhammadiyah Malang

Disusun Oleh :

Ilham Hasymi Effendi

09560242

Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

31 Januari 2013

Menyetujui,

Penguji I

Ali Sofyan Kholimi, S. Kom

Penguji II

Galih Wasis Wicaksono, S. Kom

Mengetahui,

Ketua Jurusan Teknik Informatika

Eko Budi Cahyono, S.Kom, MT

Page 4: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

LEMBAR PERNYATAAN

Yang bertanda tangan dibawah ini :

NAMA : ILHAM HASYMI EFFENDI

NIM : 09560242

FAK. / JUR. : TEKNIK / TEKNIK INFORMATIKA

Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “IMPLEMENTASI

ALGORITMA A* PATHFINDING UNTUK ENEMY AI DI GAME WAYANG ROBOT”

beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain,

baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang telah disebutkan

sumbernya.

Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan

adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain

terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang

berlaku.

Mengetahui

Dosen Pembimbing

Yuda Munarko, S. Kom, M. Sc

Malang, 19 Januari 2013

Yang Membuat Pernyataan

Ilham Hasymi Effendi

Page 5: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

i

ABSTRAK

Wayang Robot adalah game 3D edukasi bergenre 3rd

Person Platformer Game yang dibuat

untuk mempelajari Aksara Jawa dengan cara yang lebih mudah, menarik, dan menyenangkan.

Game ini mengemas pembelajaran Aksara Jawa dengan skenario yang diadaptasi dari kisah

pewayangan Ramayana namun direpresentasikan dengan model yang futuristik yaitu robot.

Di dalam game tersebut dibutuhkan kecerdasan buatan (Artificial Intelligence) dan

algoritma pathfinding untuk sebuah level di dalamnya. Lebih tepatnya adalah karakter robot Tiny

Blaster yang membutuhkan kedua hal tersebut untuk mencari dan mengejar karakter pemain.

Algoritma A* (A Star) adalah salah satu algoritma pathfinding yang dirasa sangat tepat untuk

diterapkan di game ini karena algoritma tersebut dapat berjalan cepat dan relatif mudah dalam

penerapannya.

Hasil penerapan Algoritma A* ini tidak hanya terhenti pada karakter robot Tiny Blaster

saja, namun juga bisa diterapkan di seluruh karakter game yang mempunyai perilaku serupa

dengan robot Tiny Blaster, baik di dalam game Wayang Robot itu sendiri maupun karakter di

game lain.

Kata kunci: 3D, Game, A*, Pathfinding, Artificial Intelligence

Page 6: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

ii

ABSTRACT

Wayang Robot is a 3D educational 3rd

Person Platformer Game which is made to study the

Aksara Jawa in a more convenient, attractive, and fun. This game is packed with scenarios of

learning Aksara Jawa adapted from the story of Wayang Ramayana but is represented by a

futuristic model of robot.

This game needs an Artificial Intelligence and pathfinding algorithm for a level in it. More

precisely, Tiny Blaster robot character that requires both of them to locate and pursue the

player's character. A* (A Star) Algorithm is one of the pathfinding algorithm that seems very

appropriate to be applied in this game because the algorithm can run fast and relatively easy to

use.

Later, the implementation of the A* Algorithm is not to be applied in Tiny Blaster robot

characters only. Expected results of this study could also be applied throughout the game

characters that have a similar behavior to the Tiny Blaster robot, which is in the Wayang Robot

game itself or characters in other games.

Keyword: 3D, Game, A*, Pathfinding, Artificial Intelligence

Page 7: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

iii

LEMBAR PERSEMBAHAN

Segala puji bagi Allah SWT Tuhan Semesta Alam atas petunjuk, hidayah dan karunia-Nya

sehingga Tugas Akhir ini dapat terselesaikan. Melalui lembar persembahan ini penulis

menyampaikan ucapan terima kasih kepada:

1. Bapak M. Yusuf Effendi, Ibu Dewi Rukmini, dan Mbak Isna Hidayati Effendi. Keluarga

penulis tercinta yang selalu memberikan berbagai dukungan, semangat, serta doanya.

2. Bapak Yuda Munarko, S. Kom, M. Sc dan Bapak Hardianto Wibowo, S.Kom selaku

dosen pembimbing dalam proses penulisan Tugas Akhir ini.

3. Seluruh dosen dan staf Jurusan Teknik Informatika Universitas Muhammadiyah

Malang.

4. Saudara-saudara seperjuangan di Infotech UMM yang selama ini selalu berbagi ilmu

dengan penulis.

5. Teman-teman terbaik penulis, Hari Sulistiyo, Afif Hidayat, Muhammad Yudhi dan

Rizky Anggriawan atas semua suka dan duka yang dialami bersama penulis selama di

perkuliahan.

6. Seluruh penghuni kost Cahaya Hati yang telah berbagi banyak pelajaran hidup selama

penulis tinggal di sana.

7. Andri Viyono atas kerjasamanya membuat model karakter dan environment 3D yang

super keren untuk game “Wayang Robot”.

8. Sri Wahyuningsih yang telah memberikan bantuan dan dukungannya kepada penulis.

9. Rekan-rekan Lotus Game Studio Jakarta yang telah membuka cakrawala pengetahuan

penulis tentang game development dan game programming.

10. Serta semua pihak yang telah berjasa dalam proses pengerjaan Tugas Akhir ini yang

tidak bisa penulis sebutkan satu-persatu.

Page 8: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

iv

KATA PENGANTAR

Rasa syukur yang amat dalam penulis panjatkan kepada Allah SWT, karena atas berkat

limpahan rahmat dan hidayah-Nya penulis mampu menyelesaikan Tugas Akhir ini yang berjudul:

“IMPLEMENTASI ALGORITMA A* (A STAR) PATHFINDING

UNTUK ENEMY AI DI GAME WAYANG ROBOT”

Melalui kata pengantar ini penulis ingin menyampaikan permintaan maaf jika terdapat

berbagai kekurangan di dalam penulisannya. Penulis menyadari bahwa penulisan Tugas Akhir ini

masih jauh dari sempurna. Oleh karena itu penulis mengharapkan kritik dan saran yang

membangun dari semua pihak sebagai koreksi untuk penulis. Semoga karya yang sederhana ini

dapat membuka cakrawala pengetahuan seluruh pembaca dan dapat mendatangkan ilmu yang

bermanfaat. Aamiin.

Malang, 18 Januari 2013

Penulis

Page 9: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

v

DAFTAR ISI

ABSTRAK ...................................................................................................................................... i

ABSTRACT................................................................................................................................... ii

LEMBAR PERSEMBAHAN ....................................................................................................... iii

KATA PENGANTAR .................................................................................................................. iv

DAFTAR ISI...................................................................................................................................v

DAFTAR GAMBAR ................................................................................................................... vii

DAFTAR TABEL....................................................................................................................... viii

1. PENDAHULUAN ....................................................................................................................1

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

1.2 Perumusan Masalah .............................................................................................................2

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

1.4 Batasan Permasalahan ..........................................................................................................2

1.5 Metodologi Penelitian ..........................................................................................................3

1.6 Sistematika Penulisan ..........................................................................................................4

2. LANDASAN TEORI ................................................................................................................6

2.1 Game Wayang Robot ...........................................................................................................6

2.1.1 Sekilas Game wayang robot.....................................................................................6

2.1.2 Teknologi Game.......................................................................................................6

2.1.3 Desain Karakter .......................................................................................................7

2.1.4 Kontrol Karakter ......................................................................................................7

2.1.5 Skenario dan Gameplay ...........................................................................................8

2.2 Unity 3D Game Engine ........................................................................................................9

2.3 Kecerdasan Buatan.............................................................................................................11

2.4 Waypoint ............................................................................................................................13

2.5 Algoritma A* .....................................................................................................................13

Page 10: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

vi

3. ANALISA DAN PERANCANGAN SISTEM .......................................................................16

3.1 Analisa Sistem ...................................................................................................................16

3.1.1 Spesifikasi Perangkat Lunak ..................................................................................16

3.1.2 Fungsionalitas Sistem ............................................................................................16

3.2 Perancangan Sistem ...........................................................................................................17

3.2.1 Menyiapkan Environment Game ...........................................................................17

3.2.2 Menyiapkan Karakter.............................................................................................18

3.2.3 Menyapkan dan Merancang Game Object .............................................................20

3.2.4 Menyiapkan Script .................................................................................................20

4. IMPLEMENTASI DAN PENGUJIAN ..................................................................................23

4.1 Implementasi Sistem .........................................................................................................23

4.1.1 Mengatur Environment ..........................................................................................23

4.1.2 Peletakan dan Pengaturan Game Object ................................................................24

4.1.3 Pengaturan Karakter...............................................................................................25

4.1.4 Menampilkan HUD ................................................................................................26

4.1.5 Pembuatan Script A* .............................................................................................26

4.1.6 Penyempurnaan Script A* .....................................................................................36

4.1.7 Pengimplementasian Script A* ke Dalam Game ...................................................37

4.2 Pengujian Sistem ................................................................................................................38

4.2.1 Pengujian Alpha ....................................................................................................38

4.2.1.1 Pengujian Script FindWP.cs .......................................................................39

4.2.1.2 Pengujian Script Actor.cs ...........................................................................41

4.2.1.3 Pengujian Kompatibilitas Script A* ...........................................................41

4.2.2 Pengujian Beta .......................................................................................................42

5. PENUTUP ..............................................................................................................................45

5.1 Kesimpulan ........................................................................................................................45

5.2 Saran ..................................................................................................................................46

DAFTAR PUSTAKA ...................................................................................................................47

BIOGRAFI PENULIS ..................................................................................................................48

Page 11: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

vii

DAFTAR GAMBAR

Gambar 1.1 Preview Game Wayang Robot ...............................................................................3

Gambar 2.1 RM-04 Sebagai Karakter Utama Game Wayang Robot ........................................7

Gambar 2.2 RM-04 Mengoleksi Box Aksara Jawa ...................................................................8

Gambar 2.3 RM-04 Dihalangi Sekumpulan Robot Tiny Blaster ...............................................9

Gambar 3.1 Environment Game Sci-fi Room ..........................................................................15

Gambar 3.2 Environment Game Nature Combination ............................................................15

Gambar 3.3 Karakter Robot RM-04 ........................................................................................16

Gambar 3.4 Karakter Robot Tiny Blaster ................................................................................17

Gambar 3.5 Karakter Robot Doodle ........................................................................................17

Gambar 3.6 Box Aksara Jawa ..................................................................................................18

Gambar 4.1 Mengatur Skybox ..................................................................................................21

Gambar 4.2 Mengatur Stage dan Pencahayaannya ..................................................................22

Gambar 4.3 Peletakan dan Pengaturan Kamera .......................................................................22

Gambar 4.4 Peletakan Box Aksara Jawa..................................................................................23

Gambar 4.5 Pengimplementasian Script RM-04 .....................................................................24

Gambar 4.6 Pengimplementasian Script Tiny Blaster .............................................................24

Gambar 4.7 Peletakan Posisi Spawner .....................................................................................25

Gambar 4.8 Penyebaran Waypoint di Stage .............................................................................34

Gambar 4.9 Mengatur Tiny Blaster dengan Spawner ..............................................................35

Gambar 4.10 Denah Posisi Karakter ........................................................................................36

Gambar 4.11 Garis Hijau Muncul Ketika Jalur Ditemukan ....................................................37

Page 12: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

viii

DAFTAR TABEL

Tabel 4.1 Data Hasil Pengujian Script FindWP.cs ..................................................................39

Tabel 4.2 Data Hasil Pengujian Script Actor.cs ......................................................................40

Tabel 4.3 Data Hasil Menggunakan Doodle ............................................................................41

Tabel 4.4 Data Hasil Kuesioner Pertanyaan 1 .........................................................................42

Tabel 4.5 Data Hasil Kuesioner Pertanyaan 2 .........................................................................42

Tabel 4.6 Data Hasil Kuesioner Pertanyaan 3 .........................................................................42

Tabel 4.7 Data Hasil Kuesioner Pertanyaan 4 .........................................................................43

Page 13: TUGAS AKHIReprints.umm.ac.id/27752/2/jiptummpp-gdl-ilhamhasym-32089... · 2016-04-22 · Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal

47

DAFTAR PUSTAKA

[1] Creighton, Ryan Hanson. 2011. Unity 3.x Game Development by Example.

Birmingham: Packt Publishing

[2] Goldstone, Will. 2009. Unity 3.x Game Development Essentials. Birmingham:

Packt Publishing

[3] Russell, StuartJ., Peter Norvig. 1995. Artificial Intelligence A Modern Approach.

New Jersey: Prentice-Hall Inc.

[4] Buckland, Mat. 2005. Programming Game AI by Example. Texas. Wordware

Publishing, Inc.

[5] Cui, Xiao., Hao Shi. 2011. A*-based Pathfinding in Modern Computer Games.

Meulbourne, IJCSNS(11): 1-2

[6] Blackman, Sue. 2011. Beginning 3D Game Development with Unity. Ney York:

Appress

[7] http://docs.unity3d.com/Documentation/Components/class-Skybox.html diakses

pada tanggal 04 Desember 2012

[8] http://docs.unity3d.com/Documentation/Components/class-Camera.html diakses

pada tanggal 01 Januari 2013