ImplementasiPathfindingdenganAlgoritma A* padaGame Funny EnglishMenggunakan Unity 3D Berbasis Graf Navmesh Riwinoto 1, Alfian2 PoliteknikNegeriBatam JurusanTeknik Multimedia Jaringan Parkway Street, Batam Centre, Batam 29461, Indonesia E-mail: 1
[email protected], 2
[email protected]
Abstrak Penggunaan bahasa Inggris telah men jadi bagian dalam keh idupan sehari-hari. Di Indonesia, mata pelajaran bahasa Inggris telah masuk kedalam kurikulu m pendidikan dasar. Salah satu aspek penting dalam proses pembelajaran bahasa Inggris adalah pengenalan kosakata. Game Funny English dikembangkan dengan Un ity 3D 4.34 bertujuan mempermudah pengenalan kosakata bahasa Inggris yang disajikan dalam bentuk objek 3D serta audio pengucapan objek tersebut. Untuk men ingkatkan minat anak dalam bermain, maka ditambahkan fitur artificial intelligence (AI) didalam game. Penerapan artificial intelligence pada non-playable character (NPC) yang tindakannya tidak dapat dikendalikan pemain, misalnya dalam hal mencari rute untuk menuju ke suatu tempat, diharapkan dapat menambah kesenangan bermain dan menambah variasi gameplay. Kata kunci: Game edukasi, bahasa Inggris, NPC, kecerdasan buatan, Uni ty 3D, pencarian rute, Navmesh
Abstract English as language has become a part of everyday life. In Indonesia, English has become a subject in preliminary school’s curriculu m. An important element in the process of learning English is vocabulary. Game Funny English developed with the purpose to facilitate English vocabulary in the form of 3D objects as well as audio pronunciation of those objects. To increase children's interest in play ing the game , artificial intelligence (AI) feature has been added in the game. Application of AI on a non-playable character (NPC) which cannot be controlled by the player, for examp le when searching for a route to go somewhere, is expected to enhance player’s gaming experience and various gameplay. Keywords: Educati on g ame, English, NPC, Artificial Intelligence, Uni ty 3D, pathfindi ng, Navmesh
1
Pendahuluan
Berdasarkanstatistik [1] BahasaInggrisadalahbahasaketiga yang digunakansebagaibahasautamadenganlebihdari 335 jutapengguna.BahasaInggrismerupakanbahasaasingno morsatu yang diajarkan di lebih 100 negara di dunia [2].Di Indonesia sendiri, bahasaasingterutamabahasaInggrismerupakanbahasain ternasional yang sangatpentingkegunaannyadalampergaulan global [3]. DibutuhkanbeberapaelemenuntukmempelajaribahasaI nggris, yaitukosakata (vocabulary), tatabahasa (grammatical), aturan-aturan (rules),danpengucapan
(pronounciation). Pembelajarankosakata(vocabulary) bahasaInggris, merupakanelemendasar yang harusdiajarkankarenamemilikiperan yang krusialuntuktahappembelajaranselanjutnya, terutamabagianak-anak.Berbedadengan orang dewasa yang telahmemilikikosakatabahasautama yang lebihbanyak, menurutreferensi [4], menyatakanbahwaanakakan mengalamikendalaketika mempelajaribahasaasingkarenaterbenturbahasautama (mother’s tongue) yang ada di lingkunganru mahsertamasihsedikitnyaju mlahpemben daharaan kata yang merekaketahui. Beberapapenelitiantelahdilakukanuntukmenu mbuhke mbangkan minatanakdalammempelajaribahasaInggris.
Menurutpenelitianoleh[5], metodebelajaruntukmempelajaribahasaInggrismenggu nakan media bonekajaridankartunbergambar.Menurutreferensi [6] penelitian yang dilakukan menggunakanmetodeberceritadanbernyanyis ertamelakukangerakan-gerakansesuaidengan kata-kata dalamliriklagu.Penelit ian[7], telahmembangunaplikasipembelajaranbahasaInggrisu ntukanak TK berbasis mult imed ia, danmenyarankanpenggunaangamedalampengembanga nnya. Salah satuGamedengantemaedukasiBahasaInggrisyaitugame Home Sweet Homeo leh [8]. Game inimengenalkan kosakatabahasaInggrismelalu iob jek-objek yang adadilingkunganrumahsepertiruangkeluarga (living room), dapur (kitchen), kamartidur (bedroom) dankamarmandi (bathroom). Gamedandikembangkan menggunakansoftware Adobe Flash dengan Action Script 3.0.danberbasis 2D. Penulis [9] pada tahun 2012 telah mengembangkan Game Funny English menggunakan Blender 3D. Pada penelitian tersebut, objek yang dikembangkan adalah benda mati dan kurang interaktif dengan pemain sehingga mengurangi minat bermain. Oleh karena itu game tersebut perlu dikembangkan dengan ditambahkan objek dan karakter lain sehingga lebih interaktif dengan lingkungan agar game lebih menarik. Menurut [10, 11], d ibutuhkan adanya AI (artificial intelligence)agar game leb ih menarik.AI didalam Gamedapat diterapkan pada NPC(non-playable character). NPC adalah karakter yang mampu berinteraksi dengan objek didalam dunia Game dan tindakannya tidak dapat dikendalikan oleh pemain. Tindakan NPC yang tidak dapat diprediksi salah satunya adalah pergerakannya dari suatu tempat ketempat lain.Dengan diterapkannyaAI pada NPC sehingga membuat NPC mampu mengotomasikan rute pergerakannya didalam game. NPC dapat mencari rute untuk bergerak dari posisi sekarang menuju posisi tujuannya dengan pathfinding. Beberapa metode pathfinding seperti Metode Breadth-first search dan Depth-first search adalah metode pencarian rute tanpa menghitung jarak yang harus ditempuh. Sedangkan A lgorit ma Dijkstra dan Algorit ma A-star sudah memperhitungkan jarak yang harus ditempuh dalam mencapai tujuan. Saat in i banyak game modern menggunakan algorit ma A-star karena Algorit ma A-star menjamin akan menemukan rute terpendek [12]. Untuk dapat melakukan pathfinding pada lingkungan pengembangan game, dibutuhkan suatu graf khusus pada peta game yang memiliki informasi costuntuk berpindah dari suatu titik ke t itik lain. Pada penelitian ini, penulis menggunakan model graf Navigation Mesh (Nav mesh) pada peta game agar dapat dikenali dan
dilakukan ko mputasi path oleh sistem game. Penelitian oleh [13] menyimpulkan bahwa metodepath findingmerupakanmetode yang sangatpentingdalam game 3D untukmenunjangcarabergerakobjek, terutamaobjek yang digerakkanoleh AI.Algorit ma A* danNavigation Mesh diperlukansupayadapatmelakukanarahpergerakankete mpattujuandengansangatcepat. Dilihat dari pernyataan-pernyataan diatas, maka penulis akan mengembangkan fitur NPC dengan AI yang mempunyai kemampuan yang secara otomatis mencari rute/pathfinding. Dengan adanya fitur ini, diharapkan game dapat lebih menarik minat pemain.
2
TeoriPendukung
A. Algorit ma A* Algorit ma A* adalah jenis algorit ma pencarian rute yang dapat mencari rute terpendek antara 2 tit ik pada weighted graph. Pada weighted graph,rute terpendek sama dengan rute dengan nilai (cost) terkecil[14].
Gambar1 Weighted Graph
Algorit ma A* menggunakanmetodeheuristikuntukmengurangi area pencariandimanahanya area yang menjanjikansaja yang akandiuji [15]. Fungsiheuristikh(n)adalahdasaralgoritma A* untukmengestimasicost min imu m darisuatutitikn ketitiktujuan. Pencarianrutedenganmempertimbangkansuatunilai/co sttertentudinamakandenganpathscoring.Pathscoringda patditulisdalamru musberikut: f= g +h
(1)
Berikut adalah pseudo code untuk algorit ma A*[13]. Tabel1 Pseudo Code Algoritma A*
function A*(start,goal) closedset := the empty set openset := {start} came_fro m := the empty map g[start] := 0 h[start] := heuristic_cost(start, goal) f[start] := g[start] + h[start]
bersebelahan.heuristic_costmerupakanfungsi yang menghasilkansuatunilai cost perkiraanberdasarkankriteriatertentu.
while openset is not empty x := the node in openset having the lowest f[] value
B. Unity3D
if x = goal
Unity 3D merupakanGame engine Multi-platform dengan IDE terintegrasi yang dikembangkanoleh Unity Technologies.Unity 3Dd igunakanuntukmengembangkan video games untuk plug-in web, plat form desktop, console, dan mobile devices, dantelahdigunakanolehjutaanpengembang.
return reconstruct_path(came_fro m, came_fro m[goal]) remove x fro m openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset
add y to openset
Unity 3Dadalahlingkunganpengembangangame: Sebuahaplikasirender yang terintegrasidengansejumlahtools yang dapatdigunakanuntukmenciptakan konten 3D yang interaktif, mensupporthasilpengerjaandalamberbagai format,sertaribuanAsset yang berkualitasdansiappakai yang tersediapadaAsset Storedankomunitaspengguna [16].
tentative_is_better := t rue
C. Navigation mesh (Nav mesh)
continue tentative_g_score dist_between(x,y)
:=
g[x]
+
if y not in openset
else if tentative_g_score
Navigation mesh (Nav mesh) adalah suatu bidang (mesh) tak terlihat yang memiliki informasi costyang dapat dilalui (walkable) pada suatu poligon . Un ity 3D memilikisuatucaraotomatisuntukmembuat (generate)navmesh yang efisien yang memilikibeberapa parameter nu merik. Proses inidisebutdenganbaking.Contohnavmeshterlihatpadag ambarberikut:
came_fro m[y] := x g[y] := tentative_g_score h[y] := heuristic_cost(y, goal) f[y] := g_score[y] + h_score[y] return failure function current_node)
reconstruct_path(came_fro m,
if came_fro m[current_node] is set p := reconstruct_path(came_fro m, came_fro m[current_node]) return (p + cu rrent_node) else return current_node closedsetmerupakantabel node yang telahditelusuri. opensetmerupakantabelprioritas node. came_frompath terbaikuntukmencapaisuatu node. g[]merupakannilaidarifungsi g(x).h[]merupakannilaidarifungsi h(x).f[]merupakan ju mlahdari g(x) dan h(x).dist_between merupakanfungsiyang menghasilkanjarakantara 2 node yang
Gambar2Petadengannavmeshdanrintangan (obstacle)
3
PerancangandanImplementasi
Pada penelitian in i, NPC akan mencari tit ik tujuannya secara acak dan akan mengulangi proses ini setelah sampai dit itik tujuan. Penulis merancang 3 karakter NPC menggunakan Unity 3D, yaitu tupai, kura-kura, dan siput. Rancangan titik tujuan (target) yang akan dituju oleh NPC berju mlah 15 t itik.
4
PengujiandanAnalisa
Pengujian dilakukan dengan menguji rute tempuh optimal menurut logika manusa dengan rute yang dipilih oleh NPC, dan waktu yang dibutuhkan oleh NPC untuk mencari rute ke t itik tujuan. Berikutadalahcontohgambarpengujian yang dilakukan NPC darit itikawalmenujusuatutitiktujuan (tit ik target 2).
Gambar3Contoh NPC Tupai
Gambar6 NPC dantitik target 2
Gambar4TitikTujuan NPC
Implementasi graf nav mesh yang dibuat pada game Funny English sebagai berikut:
Gambar7Rute O ptimal secaralogika
Gambar5Navmeshpadapeta game
Rata-rata waktu yang dibutuhkan (ms) 0.25 0.2
0.15 0.1 0.05 0 Tupai
5 Gambar8Rute yang akantempuholeh NPC
Total pengujianpencarianrutedilakukansebanyak 30 kali. Pencarianrutedilakukan 10 kali olehmasing-masing NPC.Pengujianwaktu yang dilakukanadalahwaktu yang dibutuhkanolehmasing-masing NPC untuktiappencarianrute.
Kura-kura
Siput
Kesimpulan
Dari seluruh pengujian yang telah d ilakukan, dapat diambil kesimpulan bahwa seluruh rute yang diamb il oleh NPC telah sesuai dengan rute optimal yang harus ditempuh secara logika manusia. Rata-rata waktu yang dibutuhkan untuk pengambilan rute juga terjadi dalam waktu yang singkat (≤0.2 detik).
Pustaka
Berikutadalahtabelhasilketepatanpengujianpencarianr uteolehNPCd ibandingdenganrutesesuailogikamanusia.
[1]
http://www.ethnologue.com/statistics/size, diaksespada 22:13, 18 Agustus 2014.
Tabel2Pencarianruteoleh NPC
[2]
English as Global language, Crystal David,Camridge University Press, Second Ed ition,2003, ISBN, 0521 530326, Paperback
Ketepatan Rute yang Diambil
[3] PP no 32 tahun 2013 tentang standard nasionalpendidikanperubahan no 19 tahun 2005.
12 10 8 6 4 2 0
[4] Cameron, Lynne. 2001. Teaching Language to Young Learners. Cambridge: Camb ridge University Press
Tupai
Kura-kura
Berikutadalahtabelwaktu dibutuhkanmasing-masing
rata-rata
Siput
yang NPC
untuktiappencarianrute. Tabel3Waktu rata-rata yang dibutuhkanuntukmencarirute
[5] Purnamasari, Hanna Rach mawat i. 2013. MeningkatkanKosakataBahasaInggrisAnak Taman Kanak-KanakMelalu iMetodeBerceritaDenganM enggunakan Media BonekaJari Dan KartuBergambar. S1 Thesis, UniversitasPendidikan Indonesia, http://repository.upi.edu/2937/, d iaksestanggal 11-Mei-2014 [6] Slattery, M ., & Willis, J. (2001). English for primary teachers: A handbook of activities and classroom language. Oxford: Oxford University Press. [7] Sutanto, Stefany. 2010. Pembangunan AplikasiPembelajaran BahasaInggrisbagiAnak TK Berbasis Multimedia. S1 thesis, UAJY, http://repository.upi.edu/2937/ [8] Riwinoto. 2013. PengembanganGame Ho me Sweet Ho me dalamPembelajaranKosakataBahasaInggrisuntuk AnakUsiaDinimenggunakanDiagramUnifiedMod elling Language, ScriptwritingdanStoryboard: StudiKasus TK-B AnandaBatam.
[9] Firmanda, Ardiman, &A lfian. 2012. Game EdukasiBahasaInggrisuntukAnak Indonesia Berbasis 3D. Paper TugasAkhir D3. PoliteknikNegeriBatam. [10] Mark Owen Riedl& Game Production,
AlexanderZook, AI for
[11] ChirstophSalge, Christian Lipski, Tobias Mahlamann, Brig itte mathiak. Using Genetically Optimized Artificial Intelligence to imp rove Gameplay ing Fun for Strategical Games [12] Patel, A mit. 2014. Introduction to A*, fro m Amit’s Thought on Pathfinding. http://theory.stanford.edu/% 7Eamitp/ GamePr ogramming/index.html,d iaksespada 21:19, 26 Juni 2014. [13] Yonathan, Freddi. Metode Pathfinding pada Game 3D Menggunakan Algoritma A* dengan Navigation Mesh. 2011 [14] T.H. Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms, Third Ed ition.The MIT Press, 2001. [15] I. M illington and J.Funge, Artificial Intelligence for Games Morgan Kaufmann, 2009. [16] https://unity3d.com/unity, d iaksespada 20:42, 14 Juni 2014.
