PEMBUATAN NPC DALAM SIMULATOR GAME “SANG PEDJOEANG” DENGAN IMPLEMENTASI ARTIFICIAL INTELLIGENCE MDP (MARKOV DECISION PROCESS)
Laporan Tugas Akhir
Disusun Untuk Memenuhi Persyaratan Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh : David Siswanto Nugroho 09560403
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
LEMBAR PERSETUJUAN PEMBUATAN NPC DALAM SIMULATOR GAME “SANG PEDJOEANG” DENGAN IMPLEMENTASI ARTIFICIAL INTELLIGENCE MDP (MARKOV DECISION PROCESS)
David Siswanto Nugroho 09560403 Telah Direkomendasikan Untuk Diajukan Sebagai Judul Tugas Akhir Di Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui,
Dosen I
Dosen II
Eko Budi Cahyono, S.Kom,. MT
Hardianto Wibowo, S.Kom
NIP. 10895040330
NIP. 07210386002
I
LEMBAR PENGESAHAN PEMBUATAN NPC DALAM SIMULATOR GAME “SANG PEDJOEANG” DENGAN IMPLEMENTASI ARTIFICIAL INTELLIGENCE MDP (MARKOV DECISION PROCESS)
David Siswanto Nugroho 09560403 Telah Direkomendasikan Untuk Diajukan Sebagai Judul Tugas Akhir Di Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui,
Penguji I
Penguji II
Wahyu Andhyka kusuma, S.Kom
Yufis Azhar, S.kom
II
LEMBAR PERNYATAAN KEASLIAN Yang bertanda tangan dibawah ini: NAMA
: David Siswanto Nugroho
NIM
: 09560403
FAK. / JUR. : TEKNIK / INFORMATIKA Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “PEMBUATAN NPC
DALAM
IMPLEMENTASI
SIMULATOR ARTIFICIAL
GAMESANG
PEDJOEANGDENGAN
INTELLIGENCE
MDP
(MARKOV
DECISION PROCESS)”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. Malang, 11 Oktober 2013 Yang Membuat Pernyataan
DAVID SISWANTO NUGROHO
Pembimbing I
Pembimbing II
EKO BUDI CAHYONO, S.Kom, M.T.
HARDIANTO W, S. Kom
NIP. 10895040330
NIP. 07210386002
III
ABSTRAK NPC atau Non Playable Character adalah objek dalam game yang tidak dapat dikendalikan oleh player, melainkan dikendalikan oleh komputer, karena ini tidak dikendalikan oleh manusia, sehingga komputer memerlukan sebuah algoritma, algoritma ini harus sesuai dengan tuntutan jenis game, pemilihan yang tidak sesuai menyebabkan ketidakcocokan antara NPC dengan jenis game. Dalam proyek ini akan dibuat NPC yang mengimplementasi algortima markov decision process, algoritma ini membantu NPC untuk menentukan state dan aksi yang akan dipilih oleh NPC pada kondisi tertentu berdasarkan aksi dari player. Algoritma ini sesuai untuk sebagian besar jenis game karena algoritma ini tidak terpusat pada pendeteksi tabrakan, atau penemuan jalan, algoritma ini terpusat pada pembuatan keputusan, selama NPC butuh untuk menentukan keputusan maka algoritma ini akan sangat bermanfaat, dalam kasus ini NPC memilih state dimana pada setiap state mempunyai aksi yang berbeda, algoritma membantu NPC untuk memilih state dan aksi dengan memperhitungkan parameter yang terpenuhi seperti yang dibutuhkan oleh masing – masing state dan aksi.
IV
ABSTRACT NPC or Non Playable Character is an object in a game that uncontrollable by a player, it is controlled by computer, because of it is not controlled by human so the computer need an algorithm, this algorithm must be proper for the demand of game‟s genre, the improper selection of algorithms may result in mismatches NPC with the types of games. In this project we will create NPC that implementing Markov Decision Process algorithm, this algorithm helps NPC to decide state and action that will be selected by NPC at certain condition depends on player‟s action. This algorithm is suitable for most genre of game because this algorithm isn‟t focused on collision detection, or path finding, this algorithm is focused on decision making, as long as the NPC need to select some decision this algorithm is very useful, in this case the algorithm helps NPC to decide the state which every state has different action, the algorithm helps NPC to decide the state and action by calculating the parameter that fulfilled as the each state and action is needed.
V
LEMBAR PERSEMBAHAN
Puji syukur kepada Allah SWT atas rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan Tugas Akhir ini. Penulis menyampaikan ucapan terima kasih sebesar – besarnya kepada : 1. Bapak Eko Budi Cahyono, S.Kom., M.T dan Bapak Hardianto Wibowo, S.Kom selaku pembimbing tugas akhir. 2. Bapak/Ibu Dekan Fakultas Teknik Universitas Muhammadiyah Malang. 3. Bapak/Ibu Ketua Jurusan Teknik Informatika Universitas Muhammadiyah Malang. 4. Orang tua saya yang selalu memberikan dukungan penuh terhadap pendidikan. 5. Saudara serta sahabat yang selalu memberikan motivasi kepada saya. 6. Teman – teman khususnya dari angkatan „09 ITH teknik informatika yang tidak dapat disebutkan satu per satu.
VI
KATA PENGANTAR
Dengan memanjatkan puji syukur kehadirat Allah SWT. Atas limpahan rahmat dan hidayah-NYA sehingga peneliti dapat menyelesaikan tugas akhir yang berjudul “PEMBUATAN NPC DALAM SIMULATOR GAME“SANG PEDJOEANG”DENGAN IMPLEMENTASI ARTIFICIAL INTELLIGENCE MDP (MARKOV DECISION PROCESS)” Di dalam tulisan ini disajikan pokok-pokok bahasan yang meliputi beberapa bagian yaitu: a. Pendahuluan Bagian ini berisi tentang alasan penulis memilih judul ini sebagai objek penelitian, tujuan yang ingin dicapai dalam penelitian serta hal-hal yang menjadi batasan selama penelitian. b. Dasar Teori Bagian ini berisi teori-teori yang mendukung dalam penelitian ini, terutama yaitu tentang NPC, dan algoritma markov decision process. c. Analisa dan Perancangan Bagian ini berisi analisa serta perancangan yang dibutuhkan untuk membuat sebuah NPC dan game simulator untuk menguji NPC yang telah dibuat. d. Implementasi dan Pengujian Bagian ini berisi implementasi dari perancangan serta pengujian yang dilakukan dari segifungsionalitas. e. Kesimpulan dan Saran Bagian ini berisi kesimpulan terhadap hasil pengujian serta saran untuk pengembangan NPC dengan algoritma markov decision process dikemudian hari. Peneliti menyadari sepenuhnya bahwa dalam penulisan tugas akhir ini masih banyak kekurangan dan keterbatasan. Oleh karena itu peneliti mengharapkan
saran yang membangun agar tulisan ini bermanfaat bagi
perkembangan ilmu pengetahuan kedepan. Malang, 11 Oktober 2013
Penulis VII
DAFTAR ISI Lembar Persetujuan………………………………………………………….. I Lembar Pengesahan………………………………………………………….. II Lembar Pernyataan Keaslian……………………………………………….... III Abstrak ……………………………………………………………………… IV Abstract …………………………………………………………………….... V Lembar Persembahan ………………………………………………………...VI Kata Pengantar ………………………………………………………………. VII Daftar Isi …………………………………………………………………….. VIII Daftar Gambar ………………………………………………………………. X Daftar Tabel …………………………………………………………………. XI Daftar Istilah ………………………………………………………………… XII Bab I Pendahuluan 1.1. Latar Belakang………………………………………………………01 1.2. Rumusan Masalah…………………………………………………...02 1.3. Tujuan………………………………………………………………. 03 1.4. Batasan Masalah……………………………………………………. 04 1.5. Metodologi…………………………………………………………. 04 1.6. Sistematika Penulisan………………………………………………. 05 Bab II Landasan Teori 2.1 Algoritma…………………………………………………………… 07 2.2 Artificial Intelligence………………………………………………..08 2.3 Artificial Intelligence pada game…………….………………….…. 09 2.4 Agen / NPC………………………………………………………… 11 2.5 Markov Decision Process dalam game……………………………...13 2.1 Tujuan Menggunakan Algoritma ……………………………….….. 14 Bab III Analisa dan Perancangan Sistem 3.1 Deskripsi Umum…………………………..………………………... 16 3.2 Spesifikasi Kebutuhan…………………….………………………... 16 3.3 Analisa Sistem……………………………..……………………….. 18 3.4 Desain Sistem………………………………..……………………... 19 3.5 Game Engine………………………………..…………………….... 30
VIII
3.6 Implementasi Markov Decision Process dalam Game Engine……... 31 3.7 Logika NPC pada simulator………………………………………... 32 3.8 NPC Model ………………………………………………………… 35 Bab IV Implementasi dan Pengujian Sistem 4.1 Implementasi ….…………………………………………………… 36 4.2 Pengujian Sistem …….……………………………………….……. 42 4.3 Kasus dan Hasil Pengujian…………………………………………. 47 4.4 Kesimpulan Hasil Pengujian……………………………………….. 47 Bab V Penutup 5.1 Kesimpulan ….....………………………………………………….. 60 5.2 Saran………….. .…….……………………………………………. 60 Daftar Pustaka …………………………………………………………….. 62
IX
DAFTAR GAMBAR Halaman Gambar 2.4.1 Contoh MDP dengan 2 state dan 2 action ………………………. 14 Gambar 2.4.2 Arsitektur dan pemodelan state dan action ……………………… 15 Gambar 3.4.1.1 State Diagram…………………………………………………. 20 Gambar 3.4.2.1Use case diagram dari NPC…………………………………… 22 Gambar 3.4.3.1Activity Diagram dalam state tenang ……………………….…. 24 Gambar 3.4.3.2 Activity Diagram dalam state Siaga …………………………... 25 Gambar 3.4.3.3 Activity Diagram dalam state lelah …………………………… 26 Gambar 3.4.3.4 Activity Diagram dalam state mati ……………………………. 26 Gambar 3.4.4.1 Sequence diagram state tenang …………………………….….. 27 Gambar 3.4.4.2Sequence diagram state siaga …………………………………. 28 Gambar 3.4.4.3Sequence diagram state lelah………………………………...... 29 Gambar 3.4.4.4 Sequence diagram state mati ………………………………….. 29 Gambar 3.4.5.1 Class diagram pada NPC …………………………………….... 30 Gambar 3.7.1 Model NPC ……………………………………………………… 35 Gambar 4.1.3.1 Model NPC ………………………………………………….… 37 Gambar 4.1.3.2 Model NPC dalam animasi diam …………………………….... 37 Gambar 4.1.3.3 Model NPC dalam animasi siaga ……………………………....38 Gambar 4.1.3.4 Model NPC dalam animasi menyerang …………………….…. 38 Gambar 4.1.3.5 Model NPC dalam animasi menghindar …………………….… 39 Gambar 4.1.3.6 Model NPC dalam animasi mengejar …………………………. 39 Gambar 4.1.3.7 Model NPC dalam animasi lelah …………………………….... 40 Gambar 4.1.3.8 Model NPC dalam animasi terluka ………………………….… 40 Gambar 4.1.3.9 Model NPC dalam animasi mati …………………………….… 41 Gambar 4.1.3.7 Model Terrain dalam simulator ……………………………….. 41 Gambar 4.4.3 Diagram State …………………………………………………… 58
X
DAFTAR TABEL Halaman Tabel 3.4.2.1 Penjelasan Use case Diagram dari NPC …………………………. 23 Tabel 4.4.1 Tabel animasi, state, dan aksi NPC ………………………………… 48 Tabel 4.4.2 Tabel Hasil …………………………………………………………. 57 Tabel 4.4.4 Tabel Parameter ……………………………………………………. 58
XI
DAFTAR ISTILAH Action
Sebuah aksi yang berada dalam sebuah state tertentu
Activity Diagram
Menggambarkan rangkaian aliran dari aktifitas, digunakan untuk mendeskripsikan aktifitas yang dibentuk dalam suatu operasi sehingga dapat juga digunakan untuk aktifitas lainnya seperti use case atau interaksi.
Class Diagram
Dekripsi kelompok obyek-obyek dengan properti, perilaku (operasi) dan relasi yang sama.
Flowchart System
Suatu
bagan
dengan
simbol-simbol
tertentu
yang
menggambarkan urutan proses secara mendetail dan hubungan antara suatu proses (instruksi) dengan proses lainnya dalam suatu program. Game Engine
Perangkat lunak yang dirancang untuk membuat dan mengembangkan video game.
Interface
Sebuah tampilan tatap muka sebagai interaksi user dan sistem
Non Playable
Sebuah objek dalam sebuah game yang tidak dapat
Character
dikendalikan oleh player
Parameter
Tolak ukur atau indikator dalam sebuah sistem
Player
Karakter yang gunakan oleh pemain
Sequence Diagram
Menggambarkan
interaksi
mengindikasikan
komunikasi
antar diantara
obyek
dan
obyek-obyek
XII
tersebut. State
Sebuah kondisi dalam sistem algoritma markov decision process
Use Case Diagram
Abstraksi dari interaksi antara sistem dan aktor, gambar dari beberapa atau seluruh aktor dan use case dengan tujuan mengenali interaksi mereka dalam suatu sistem.
XIII
DAFTAR PUSTAKA
[1]Bourg, David M., Glenn Seeman. 2004. AI for Game Developers. United States of America: O'Reilly Media, Inc. [2]Knuth, Donald E. 1968. The Art of Computer Programming Volume 1.United States: Addison-Wesley. [3]Simon, Herbert A. 1995. Artificial intelligence: an empirical science. United States: Carnegie Mellon University. [4]Brent Ellison. 8 July 2008. "Defining Dialogue Systems". Gamasutra.( http://www.gamasutra.com/view/feature/3719/defining_dialogue_systems.php Diakses pada 13-12-2013). [5]Todorov, Emo. 2012. Markov Decision Processes and Bellman Equations. Applied Mathematics and Computer Science & Engineering University of Washington. Lecture 2. [6]Dani,
Ganial.
10
September
2013.
“Algoritma”.
(http://mahasiswa.ung.ac.id/521413035/home/page/32. Diakses pada 17 - 12 2013). [7]Editors of the American Heritage Dictionaries. 2000. The American Heritage Dictionary of the English Language, Fourth Edition. Houghton Mifflin Company. Boston. [8]Bellman, Richard. 1957. A Markovian Decision Process. Journal of Mathematics and Mechanics volume 6. Indiana University. United States of America.