PENERAPAN MODIFIKASI ALGORITMA A* PATHFINDING DALAM GAME BALAP 3D BERBASIS MOBILE
KOMPETENSI REKAYASA PERANGKAT LUNAK SKRIPSI
OLEH : INDRA MAULANA BACHTIFAR NIM.1108605031
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA 2015
PENERAPAN MODIFIKASI ALGORITMA A* PATHFINDING DALAM GAME BALAP 3D BERBASIS MOBILE
KOMPETINSI REKAYASA PERANGKAT LUNAK [SKRIPSI] Sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana
Tulisan ini merupakan hasil penelitian yang belum pernah dipublikasikan
INDRA MAULANA BACHTIFAR NIM. 1108605031
Pembimbing I
Pembimbing II
I Made Widiartha, S.Si, M.Kom
Ida Bagus Gede Dwidasmara, S.Kom., M.Cs
NIP. 198212202008011008
NIP. 198503152010121007
i
LEMBAR PENGESAHAN TUGAS AKHIR
Judul Skripsi
: Penerapan Modifikasi Algoritma A* Pathfinding Dalam Game Balap 3D Berbasis Mobile
Kompetensi
: Rekaya Perangat Lunak
Nama
: Indra Maulana Bachtifar
NIM
: 1108605031
Tanggal Seminar
: 16 Oktober 2015 Disetujui oleh:
Pembimbing I
Penguji I
I Made Widiartha, S.Si, M.Kom NIP. 198212202008011008
I Gede Santi Astawa, S.T.,M.Cs. NIP. 198012062006041003
Pembimbing II
Penguji II
Ida Bagus Gede Dwidasmara,S.Kom, M.Cs NIP. 198503152010121007
Agus Muliantara, S.Kom,M.Kom NIP. 198006162005011001 Penguji III
I Putu Gede Hendra Suputra, S.Kom.,M.Kom NIP. 198812282014041001
Mengetahui, Jurusan Ilmu Komputer FMIPA UNUD Ketua,
I Komang Ari Mogi, S.Kom., M.Kom. NIP. 198409242008011007
ii
Judul
:
Penerapan Modifikasi Algoritma A* Pathfinding Dalam Game Balap 3D Berbasis Mobile
Nama
:
Indra Maulana Bachtifar
Pembimbing
:
1. I Made Widiartha, S.Si, M.Kom. 2. Ida Bagus Gede Dwidasmara,S.Kom, M.Cs
ABSTRAK Kecerdasan buatan (Artificial Intelligence) menyebabkan lahirnya berbagai teknologi yang bersifat cerdas sehingga dapat menirukan tingkah laku dan fungsi otak manusia. Kecerdasan buatan ini dapat dimanfaatkan diberbagai bidang kebutuhan manusia, misalnya game. Bermain game akan terasa lebih menarik apabila game yang dimainkan memiliki kecerdasan buatan karena pemain bisa berinteraksi dengan komputer itu sendiri, salah satu kecerdasan buatan yang bisa diterapkan dalam game balapan itu sendiri adalah A* pathfinding. A* pathfinding merupakan sebuah algoritma yang digunakan untuk menentukan arah jalan dari titik awal ke titik akhir dengan melalui node-node yang tersedia. A* merupakan algoritma yang mudah untuk diterapkan dan banyak digunakan dalam aplikasi desktop maupun game. Berdasarkan hasil penelitian yang telah dilakukan, bahwa penerapan algoritma A* pathfinding dalam game balap ini mampu menyelesaikan permasalahan dalam hal menghindari rintangan untuk menemukan rute dari titik awal ke titik tujuan.
Kata Kunci : Game Balap, Game Mobil, Algoritma A* (star).
iii
Title
:
Penerapan Modifikasi Algoritma A* Pathfinding Dalam Game Balap 3D Berbasis Mobile
Name
:
Indra Maulana Bachtifar
Supervisors
:
1. I Made Widiartha, S.Si, M.Kom. 2. Ida Bagus Gede Dwidasmara,S.Kom, M.Cs
ABSTRACT Artificial Intelligent cause increasing technology rapidly and can doing like human behavior. This artificial intelligence can be used in various human needs, such as games. Playing the game will be more interesting if the game is played has artificial intelligence because the player can interact with the computer itself, one of the artificial intelligence that can be applied in a racing game itself is A * pathfinding. A * pathfinding is an algorithm used to determine the direction of way from the starting point to the end point through the available nodes. A * algorithm is easy to implement and used in desktop applications and games. Based on the research that has been done, the implementation of the A * pathfinding algorithm in this racing game is able to solve problems in terms of avoiding obstacles to find a route from the starting point to the destination point.
Keywords : Racing Game, Car Game, A* Algorithm.
iv
KATA PENGANTAR
Puji syukur penulis panjatkan kepada Tuhan yang Maha Esa berkat rahmat-Nyalah penulis diberi kelancaran dalam membuat proposal tugas akhir ini, dengan judul “Penerapan Modifikasi Algoritma A* Pathfinding Dalam Game Balap 3D Berbasis Mobile”. Proposal ini disusun dengan harapan dapat menjadi pedoman dan arahan dalam melaksanakan penelitian .Terwujudnya proposal tugas akhir ini tidak lepas dari bantuan berbagai pihak yang telah mendorong dan membimbing penulis, baik tenaga, ide-ide, maupun pemikiran. Secara khusus dalam kesempatan ini penulis ingin mengucapkan terimakasih kepada pihak yang telah membantu proposal ini, yaitu: 1. Bapak I Made Widiartha, S.Si, M.Kom.sebagai Pembimbing I yang telah banyak membantu menyempurnakan proposal ini; 2. Bapak Ida Bagus Gede Dwidasmara,S.Kom, M.Cs sebagai Pembimbing II yang telah banyak membantu menyempurnakan proposal ini; 3. Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer, yang telah meluangkan waktu turut memberikan saran dan masukan dalam penyempurnaan proposal ini; 4. Teman - teman di Jurusan Ilmu Komputer yang telah memberikan dukungan moral dan semangat dalam penyelesaian proposal ini.
Penulis menyadari bahwa proposal ini masih jauh dari kesempurnaan, oleh karena itu kritik dan saran yang membangun dari berbagai pihak sangat penulis harapkan demi perbaikan-perbaikan ke depan
Bukit Jimbaran, September 2015
Penulis
v
DAFTAR ISI
LEMBAR PENGESAHAN TUGAS AKHIR ........................................................ ii ABSTRAK ............................................................................................................. iii KATA PENGANTAR ............................................................................................ v DAFTAR ISI .......................................................................................................... vi DAFTAR TABEL ................................................................................................ viii DAFTAR GAMBAR ............................................................................................. ix BAB I ...................................................................................................................... 1 PENDAHULUAN .................................................................................................. 1 1.1
Latar Belakang ......................................................................................... 1
1.2
Rumusan Masalah .................................................................................... 2
1.3
Batasan Masalah ....................................................................................... 2
1.4
Tujuan ....................................................................................................... 2
1.5
Manfaat ..................................................................................................... 3
BAB II ..................................................................................................................... 4 TINJAUAN PUSTAKA ......................................................................................... 4 2.1
Algoritma A* ............................................................................................ 4
2.2
Algoritma Modifikasi A* ......................................................................... 7
2.3
Autodesk Maya......................................................................................... 7
2.4
Unity 3D ................................................................................................... 8
BAB III ................................................................................................................... 9 METODOLOGI PENELITIAN .............................................................................. 9 3.1
Metode Pengumpulan Data ...................................................................... 9
3.2
Analisis Kebutuhan Sistem ...................................................................... 9
3.3
Desain Sistem ......................................................................................... 10
3.3.1
Use Case Diagram ........................................................................... 10
3.3.2
Activity Diagram ............................................................................. 11
3.3.3
Class Diagram ................................................................................. 13
3.4
Implementasi dan Dokumentasi Sistem ................................................. 15
3.5
Pengujian Sistem .................................................................................... 15
BAB IV ................................................................................................................. 16
vi
HASIL DAN PEMBAHASAN ............................................................................. 16 4.1
Gambaran Umum Sistem ....................................................................... 16
4.2
Pengembangan Sistem ............................................................................ 16
4.2.1
Pengembangan Desain Antarmuka ................................................. 16
4.2.2
Implementasi Algoritma.................................................................. 21
4.2.3
Implementasi Objek 3D .................................................................. 33
4.3
Pengujian Sistem .................................................................................... 34
4.3.1
Pengujian Algoritma ....................................................................... 34
4.3.2
Blackbox Testing ............................................................................ 37
BAB V................................................................................................................... 39 KESIMPULAN DAN SARAN ............................................................................. 39 5.1 Kesimpulan .................................................................................................. 39 5.2 Saran ............................................................................................................ 39 DAFTAR PUSTAKA ........................................................................................... 40 LAMPIRAN .......................................................................................................... 41
vii
DAFTAR TABEL
Tabel 2.1.1 Tabel Elemen Algoritma A* ............................................................ 5 Tabel 4.3.1.1 Tabel Pengujian Algoritma A* .................................................... 24 Tabel 4.3.2.1 Rancangan Tabel Blackbox ......................................................... 26
viii
DAFTAR GAMBAR
Gambar 2.1.1 A* pathfinding ............................................................................ 4 Gambar 2.3.1 Model 3D Maya .......................................................................... 8 Gambar 3.3.1.1 Usecase Diagram ...................................................................... 11 Gambar 3.3.2.1 Activity Diagram Gameplay .................................................... 12 Gambar 3.3.2.2 Activity Diagram Algoritma Komputer .................................... 13 Gambar 3.3.3.1 Class Diagram Game ................................................................. 14 Gambar 4.2.1.1 Menu Utama ............................................................................. 17 Gambar 4.2.1.2 Menu About .............................................................................. 17 Gambar 4.2.1.3 Menu Play ................................................................................ 18 Gambar 4.2.1.4 Game Play ................................................................................ 18 Gambar 4.2.1.5 Sound Engine ............................................................................ 20 Gambar 4.2.2.1 Iterasi ke-1 Algoritma A* ......................................................... 21 Gambar 4.2.2.2 Iterasi ke-2 Algoritma A* ......................................................... 22 Gambar 4.2.2.3 Iterasi ke-3 Algoritma A* ......................................................... 22 Gambar 4.2.2.4 Iterasi ke-4 Algoritma A* ......................................................... 23 Gambar 4.2.2.5 Iterasi ke-5 Algoritma A* ......................................................... 23 Gambar 4.2.2.6 Iterasi ke-6 Algoritma A* ......................................................... 24 Gambar 4.2.2.7 Iterasi ke-7 Algoritma A* ......................................................... 24 Gambar 4.2.2.8 Iterasi ke-8 Algoritma A* ......................................................... 25 Gambar 4.2.2.9 Iterasi ke-9 Algoritma A* ......................................................... 25 Gambar 4.2.2.10 Iterasi ke-10 Algoritma A* ..................................................... 26 Gambar 4.2.2.11 Iterasi ke-11 Algoritma A* ..................................................... 26 Gambar 4.2.2.12 Iterasi ke-12 Algoritma A* ..................................................... 27 Gambar 4.2.2.13 Iterasi ke-1 Algoritma A* Termodifikasi ................................ 28 Gambar 4.2.2.14 Iterasi ke-2 Algoritma A* Termodifikasi ................................ 28 Gambar 4.2.2.15 Iterasi ke-3 Algoritma A* Termodifikasi ................................ 29 Gambar 4.2.2.16 Iterasi ke-4 Algoritma A* Termodifikasi ................................ 29 Gambar 4.2.2.17 Iterasi ke-5 Algoritma A* Termodifikasi ................................ 30 Gambar 4.2.2.18 Iterasi ke-6 Algoritma A* Termodifikasi ................................ 31 Gambar 4.2.2.19 Implementasi A* .................................................................... 32
ix
Gambar 4.2.3.1 Objek 3D Mobil ....................................................................... 34 Gambar 4.2.3.2 Objek 3D Lintasan .................................................................... 36 Gambar 4.3.1.1 Hasil path A* ............................................................................. 37
x
