PENERAPAN ALGORITMA A* PATHFINDING DALAM MENGATUR PRILAKU PERGERAKAN KERBAU DALAM GAME 3D MAKEPUNG
KOMPETENSI REKAYASA PERANGKAT LUNAK
SKRIPSI
I PUTU AGUS EDY SAPUTRA NIM. 1108605050
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2015
ii
Judul
:
Penerapan
Algoritma
A*Pathfinding
Dalam
Mengatur
Prilaku Pergerakan Kerbau Dalam Game 3D Makepung. Nama
:
I Putu Agus Edy Saputra
Pembimbing
:
1. Ida Bagus Made Mahendra, S.Kom., M.Kom. 2. Made Widiartha, S.Si., M.Kom.
ABSTRAK Untuk media promosi budaya, peranan game sangatlah penting, dikarenakan banyak produsen game dari Asia bahkan Eropa yang terkenal secara tidak langsung mempromosikan budaya mereka dalam game yang mereka buat, maka dari itu tidak heran bahwa anak Indonesia khususnya Bali banyak mengenal budaya luar ketimbang budaya lokal, karena pengaruh game yang di mainkan anak-anak tersebut bernuansa budaya dari produsen game yang membuatnya. Penelitian ini merancang game yang memberikan informasi bagaimana dan apa sebenarnya permainan tradisional bali "Makepung". Game ini dirancang berbasis mobile atau dekstop dengan bahasa pemrograman C# yang menggunakan unity3D untuk menggabungkan bahasa pemrograman dan model 3D supaya menjadi sebuah game. Game "Makepung" ini diimplementasikan menggunakan pencarian heuristik A*(star). Metode pencarian A*(star) akan meminimumkan total biaya lintasan dan pada kondisi yang tepat akan memberikan solusi yang terbaik. Metode ini menggunakan fungsi heuristik yang memprediksi keuntungan setiap node yang dibuat. Hal ini akan memungkinkan algoritma A*(star) untuk melakukan proses pencarian lintasan yang lebih dapat diharapkan berdasarkan node-node yang dipilih. Dari hasil penelitian yang telah dilakukan bahwa penerapan algoritma pencarian A*(star) dalam game "Makepung" ini mampu memecahkan permasalahan bagaimana lawan menghindar melewati rintangan. Disamping itu, penerapan algoritma A*(star) dapat pula membuat game "Makepung" menjadi interaktif dikarenakan lawan yang sudah di implementasikan algoritma A*(star) mampu menghindari halangan layaknya user yang memainkan game "Makepung" ini. Kata Kunci : 3D Game, Algoritma A* (star), Game Makepung, Game Tradisional, Pencarian Heuristik.
iii
Title
:
The Application of Algorithm A * Path-finding In Adjusting the Buffalo Movement Behavior In the 3D Game of Makepung.
Name
:
I Putu Agus Edy Saputra
Supervisors
:
1. Ida Bagus Made Mahendra, S.Kom., M.Kom. 2. Made Widiartha, S.Si., M.Kom.
ABSTRACT For media promotion of culture, the role of game is very important, because many famous game manufacturers from Asia and even Europe indirectly promote their culture in a game that they made, therefore it is no wonder that the children of Indonesia, especially in Bali are more familiar with foreign cultures rather than their own local culture, because of the influence of the games that they play contain cultural nuances of the game manufacturers. This research is to design a game that provide information on how and what actually the traditional Balinese game of the "Makepung"/ the buffalo race. This game was designed based on mobile or desktop, with the C # programming language that uses the Unity 3D to combine programming languages and 3D models in order to become a game. This game of the "Makepung" is implemented by using a heuristic search A * (star). A * (star) searching method will minimize the total cost of the paths and in the right conditions; it will provide the best solution. This method uses a heuristic function that predicts the advantages of each node made. This will allow the algorithm A * (star) to perform the more expected path finding process based on the selected nodes. From the research that has been done, it was found out that the implementation of the search algorithm A * (star) in the game of the "Makepung" was able to solve the problem of how the opponent avoids the barriers. In addition, the implementation of the algorithm A * (star) can also make the game "Makepung" to be interactive because the opponent already implemented by the algorithm A * (star) was able to avoid barriers, like the user who plays the game of the "Makepung". Keywords : 3D Game, Algorithm A * (star), Game of the Makepung, Traditional Game, Heuristic Search.
iv
KATA PENGANTAR Puji dan syukur penulis panjatkan kehadapan Ida Sang Hyang Widhi Wasa, karena atas karuniaNya lah, penulis dapat menyelesaikan laporan tugas akhir “Penerapan Algoritma A* Pathfinding Dalam Mengatur Prilaku Pergerakan Kerbau Dalam Game 3D Makepung” tepat pada waktunya. Selama proses penyusunan tugas akhir ini, penulis telah banyak memperoleh bimbingan, pengarahan, petunjuk dan saran yang keseluruhannya membantu hingga akhir penyusunan laporan ini. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada yang terhormat: 1. Bapak Drs. I Wayan Santiyasa, M.Si., selaku Ketua Jurusan Ilmu Komputer yang telah memberikan dukungan dalam penyelesaian tugas akhir ini. 2. Bapak I.B. Made Mahendra, S.Kom., M.Kom. selaku pembimbing I yang senantiasa
membimbing
dan
mengarahkan
penulis
dalam
guna
menyempurnakan tugas akhir ini. 3. Bapak Made Widiartha, S.Si., M.Kom. selaku pembimbing II yang telah bersedia mengoreksi, memberi kritik dan saran dalam penyusunan dan penyempurnaan tugas akhir ini. 4. Keluarga dan rekan-rekan yang telah memberikan kontribusi dalam penyelesaian tugas akhir ini. Akhir kata penulis berharap semoga laporan ini bermanfaat bagi semua pihak, dan penulis menyadari laporan ini masih jauh dari kesempurnaan, penulis mengharapkan kritik dan saran yang membangun demi kesempurnaan laporan ini.
Bukit Jimbaran, Agustus 2015 Penyusun
I Putu Agus Edy Saputra
v
DAFTAR ISI
HALAMAN JUDUL................................................................................................ i LEMBAR PENGESAHAN TUGAS AKHIR ....... Error! Bookmark not defined. ABSTRAK ………………………………………………………………………..iv ABSTRACT ........................................................................................................... iv KATA PENGANTAR ............................................................................................ v DAFTAR ISI .......................................................................................................... vi DAFTAR TABEL ................................................................................................ viii DAFTAR GAMBAR ............................................................................................. ix DAFTAR LAMPIRAN ......................................................................................... 10 BAB I PENDAHULUAN ...................................... Error! Bookmark not defined. 1.1 Latar Belakang ............................................. Error! Bookmark not defined. 1.2 Rumusan Masalah ........................................ Error! Bookmark not defined. 1.3 Tujuan Penelitian ......................................... Error! Bookmark not defined. 1.4 Batasan Masalah........................................... Error! Bookmark not defined. 1.5 Manfaat Penelitian ....................................... Error! Bookmark not defined. BAB II TINJAUAN PUSTAKA............................ Error! Bookmark not defined. 2.1 Algoritma A* (star) ..................................... Error! Bookmark not defined. 2.2 Unity 3D ....................................................... Error! Bookmark not defined. BAB III METODOLOGI PENELITIAN............... Error! Bookmark not defined. 3.1 Metode Pengumpulan Data .......................... Error! Bookmark not defined. 3.2 Analisis Sistem ............................................. Error! Bookmark not defined. 3.3 Desain Sistem ............................................... Error! Bookmark not defined. 3.3.1 Use Case Diagram ................................ Error! Bookmark not defined. 3.3.2 Activity Diagram ................................... Error! Bookmark not defined. 3.3.3 Class Diagram ...................................... Error! Bookmark not defined. 3.4 Implementasi dan Dokumentasi Sistem ....... Error! Bookmark not defined. 3.5 Pengujian Sistem .......................................... Error! Bookmark not defined. 3.5.1 Pengujian Alpha ( Alpha Test ) ............. Error! Bookmark not defined. BAB IV HASIL DAN PEMBAHASAN ............... Error! Bookmark not defined. 4.1 Lingkungan Perancangan dan Implementasi Sistem . Error! Bookmark not defined. 4.2 Pengembangan Sistem ................................. Error! Bookmark not defined. vi
4.2.1 Pengembangan Desain GUI dan Model 3D ........ Error! Bookmark not defined. 4.2.2 Implementasi Program .......................... Error! Bookmark not defined. 4.3 Pengujian Sistem .......................................... Error! Bookmark not defined. 4.3.1 Pengujian Sistem dengan Metode Alpha Test ..... Error! Bookmark not defined. 4.4 Analisis Hasil Pengujian .............................. Error! Bookmark not defined. BAB V KESIMPULAN DAN SARAN ................. Error! Bookmark not defined. 5.1 Kesimpulan .................................................. Error! Bookmark not defined. 5.2 Saran ............................................................. Error! Bookmark not defined. DAFTAR PUSTAKA ............................................ Error! Bookmark not defined.
vii
DAFTAR TABEL Tabel 2.1 Proses algoritma A* ............................... Error! Bookmark not defined. Tabel 4.1 Penentuan open list ................................ Error! Bookmark not defined. Tabel 4.2 Perulangan proses 1 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.3 Perulangan proses 2 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.4 Perulangan proses 3 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.5 Perulangan proses 4 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.6 Perulangan proses 5 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.7 Perulangan proses 6 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.8 Perulangan proses 7 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.9 Perulangan proses 8 untuk mendapatkan openlist baru ................. Error! Bookmark not defined. Tabel 4.10 Perulangan proses 9 untuk mendapatkan openlist baru ............... Error! Bookmark not defined. Tabel 4.11 Proses terakhir menemukan end point . Error! Bookmark not defined. Tabel 4.12 Potongan code untuk mengecek halangan ......... Error! Bookmark not defined. Tabel 4.13 Potongan code modifikasi A* .............. Error! Bookmark not defined. Tabel 4.14 Potongan code untuk trigger lintasan dan lintasan finish ............ Error! Bookmark not defined. Tabel 4.15 Potongan code untuk lintasan supaya looping ... Error! Bookmark not defined. Tabel 4.16 Potongan code untuk main menu ......... Error! Bookmark not defined.
viii
Tabel 4.17 Potongan code untuk pembuatan object ............ Error! Bookmark not defined. Tabel 4.18 Potongan code untuk merubah tombol tiles menjadi transparant Error! Bookmark not defined. Tabel 4.19 Potongan code untuk menambah kecepatan player .. Error! Bookmark not defined. Tabel 4.20 Potongan code untuk reset kecepatan player ..... Error! Bookmark not defined. Tabel 4.21 Potongan code untuk membuat game berakhir .. Error! Bookmark not defined. Tabel 4.22 Hasil Pengujian Proses Algoritma A* . Error! Bookmark not defined. Tabel 4.23 Hasil Uji Jarak...................................... Error! Bookmark not defined.
ix
DAFTAR GAMBAR Gambar 2.1 Modifikasi A*(star) ............................ Error! Bookmark not defined. Gambar 2.2 Path Modifikasi A*(star) .................... Error! Bookmark not defined. Gambar 3.1 Use Case Diagram .............................. Error! Bookmark not defined. Gambar 3.2 Activity Diagram Play Game ............. Error! Bookmark not defined. Gambar 3.3 Activity Diagram NPC (Non-Playable Character) .. Error! Bookmark not defined. Gambar 3.4 Activity Diagram Menentukan Jalur .. Error! Bookmark not defined. Gambar 3.5 Activity Diagram Membuat Lintasan Baru ...... Error! Bookmark not defined. Gambar 3.6 Activity Diagram Menentukan Lintasan Baru . Error! Bookmark not defined. Gambar 3.7 Class Diagram .................................... Error! Bookmark not defined. Gambar 4.1 Antarmuka Main Menu ...................... Error! Bookmark not defined. Gambar 4.2 Antarmuka Option Menu ................... Error! Bookmark not defined. Gambar 4.3 Antarmuka Game Play ....................... Error! Bookmark not defined. Gambar 4.4 Antarmuka Finish Game .................... Error! Bookmark not defined. Gambar 4.5 Path hasil algoritma A*(star) pada Unity 3D .. Error! Bookmark not defined. Gambar 4.6 Lintasan awal game makepung .......... Error! Bookmark not defined. Gambar 4.7 Lintasan awal game makepung dengan trigger Error! Bookmark not defined. Gambar 4.8 Lintasan baru dengna halangan .......... Error! Bookmark not defined. Gambar 4.9 lintasan 1 dengan object halangan berada di kanan Error! Bookmark not defined. Gambar 4.10 lintasan 2 dengan tidak ada object halangan .. Error! Bookmark not defined. Gambar 4.11 lintasan 3 dengan object halangan di kiri ....... Error! Bookmark not defined. Gambar 4.12 lintasan finish ................................... Error! Bookmark not defined.
x
Gambar 4.13 sound di unity 3D ............................. Error! Bookmark not defined. Gambar 4.14 Main menu........................................ Error! Bookmark not defined. Gambar 4.15 Game Play ........................................ Error! Bookmark not defined. Gambar 4.16 Trigger finish .................................... Error! Bookmark not defined.
xi
DAFTAR LAMPIRAN
12
13
