LAPORAN TUGAS REVIEW LITERATUR TUGAS METODOLOGI PENELITIAN. Disusun oleh. Rd.Muh.Jodi Indra.S Kelas Metlit-4

LAPORAN TUGAS REVIEW LITERATUR

TUGAS METODOLOGI PENELITIAN

Disusun oleh

Rd.Muh.Jodi Indra.S 10112258

Kelas Metlit-4

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNIK DAN ILMU KOMPUTER UNIVERSITAS KOMPUTER INDONESIA 2013

Jurnal 1 Judul Jurnal/Proceeding & tahun penerbitan

Penulis

TURN BASED STRATEGY GAME MENGGUNAKAN ALGORITMA RESOURCE ASSIGNMENT PADA PERANGKAT MOBILE BERBASIS ANDROID/ Vol. 2, No. 2, Oktober 2013 sumberhttp://komputa.if.unikom.ac.id/jurnal/turn-basedstrategy-game.18 akses: Minggu,19 oktober 2014 Riandanu Madi Utomo & Nelly Indriani Widiastuti

Masalah utama yang diangkat 1.Penjelasan cara tentang bermain game Turn Based Strategy 2.Penjelasan tentang desain game Kontribusi Penulis Saran dari penulis adalah Resource Assigment Algorithm (RAA) dipilih untuk menyelesaikan masalah tersebut, karena algoritma RAA mempunyai kemampuan untuk menghasilkan sebuah nilai berdasarkan beberapa nilai yang ada dengan diurutkan menggunakan skala prioritas. At Hasil penelitian, Berdasarkan hasil pengujian, maka kesimpulan pada Kesimpulan, & saran penelitian ini adalah : 1. Penggunaan algoritma resource assignment dapat memunculkan kemampuan berfikir dan berstrategi pada AI yang terdapat di game turnbased strategy. 2. Game turn-based strategy cocok diimplementasikan pada platform mobile sehingga dapat dimainkan kapan saja dan dimana saja.

Jurnal 2 Judul Jurnal/Proceeding & tahun penerbitan

Penulis

Masalah utama yang diangkat

A*-based Pathfinding in Modern Computer Games / VOL.11 No.1, January 2011 Sumber: http://paper.ijcsns.org/07_book/201101/20110119.pdf Akses: Minggu 19 oktober 2014 Xiao Cui and Hao Shi

Masalah yang paling umum dari pathfinding dalam video game adalah bagaimana untuk menghindari rintangan cerdik dan mencari keluar jalur yang paling efisien di medan yang berbeda.

Kontribusi Penulis

metode, mengoptimalkan representasi peta, memperkenalkan struktur data baru dan mengurangi kebutuhan memori. Bagian berikutnya memberikan gambaran A teknik * yang secara luas digunakan dalam industri game saat ini.

Hasil penelitian, Kesimpulan, & saran

Sebuah penelitian yang potensial adalah untuk terus mengoptimalkan A * algoritma dari perspektif ini atau untuk menggabungkan beberapa teknik optimasi menjadi satu solusi tunggal. lain cara untuk membuat beberapa kontribusi ke permainan AI masyarakat adalah untuk menerapkan teknik ini dijelaskan diatas untuk permainan komputer yang sebenarnya karena tidak semua teknik yang dijelaskan dalam makalah ini telah banyak digunakan di industri game saat ini.

Dekripsi Ilmiah literature menggunakan Contrast

Peneletian yang dilakukan oleh Riandanu Madi Utomo&Nelly Indriani Widiastuti pada tahun 2013 yang berjudul “TURN BASED STRATEGY GAME MENGGUNAKAN ALGRORITMA RESOURCE ASSIGNMENT PADA PERANGKAT MOBILE BERBASIS ANDROID”. Peneletian ini membahas tentang Turn-based strategy(TBS)game yaitu turunan dari game dengan genre strategi dimana pemainnya saling bergiliran pada pengambilan keputusannya dalam bermain yang hanya bisa di lakukan dengan satu pemain (singleplayer) sedangkan lawannya adalah komputer atau istilah lainnya disebut Non Playable Character(NPC),maka perlu di terapkan NPC atau program yang memiliki Arificial Intelegence (AI). Game ini player harus memerlukan kemampuan berfikir dan berstrategi secara logis,karena game ini tidak memerlukan kecepatan dan keakuratan dalam bermain tetapi memerlukan pengambilan keputusan yang tepat. Solusi untuk memunculkan kemampuan berfikir dan berstrategi secara logis pada AI adalah menggunakan Resource Assignment Algoritma(RAA). RAA mempunyai kemampuan untuk menghasilkan sebuah nilai berdasarkan beberapa nilai yang ada dengan skala prioritas. Sedangkan Penelitian yang dilakukan oleh Xiao Cui and Hao Shi pada tahun 2011, yang berjudul “A*-based Pathfinding in Modern Computer Games”. Penelitian ini membahas tentang pembuatan game dengan menggunakan algoritma sebagai pembuatan dari game tersebut,terdapat game yang menggunakan tampilan 3D dan banyak yang frustasi kecerdasan buatan (AI) masalah dalam industry. A * berbasis algoritma dan teknik dari perspektif yang berbeda. Hal ini bertujuan untuk mengeksplorasi hubungan antara berbagai A * algoritma berbasis. Pada bagian pertama bagian, ikhtisar pathfinding disajikan. Kemudian, Rincian dari algoritma A * ditangani sebagai dasar penyampaian sejumlah teknik optimasi dari sudut yang berbeda.. dikirim pada misi dari saat mereka lokasi untuk yang telah ditetapkan atau pemutar ditentukan tujuan. Masalah yang paling umum dari pathfinding dalam video game adalah bagaimana untuk menghindari rintangan cerdik dan mencari keluar jalur yang paling efisien di medan yang berbeda. Jadi, dari kedua literature diatas dapat di tarik kesimpulan bahwa pada jurnal pertama dijelaskan tentang pembuatan game strategy dari turunan game genre yang memerlukan kemampuan berfikir dan berstrategi. Sedangkan pada jurnal kedua dijelaskan bahwa memerlukan kemampuan berfikir dan berstrategi karena kebanyakan game tidak perlu memerlukan kemampuan yang berakurat dan kecepatan.

Jurnal Riandanu Madi Utomo & Nelly Indriani Widiastuti (2013)

“TURN BASED STRATEGY GAME MENGGUNAKAN ALGORITMA RESOURCE ASSIGNMENT PADAPERANGKAT MOBILE BERBASIS ANDROID”

Xiao Cui and Hao Shi (2011)

“ A*-based Pathfinding in Modern Computer Games ”

Tujuan

Perbedaan

Persamaan

Kesimpulan

Dengan dibuatnya Captcha berbasiskan video dapat digunakan untuk mencegah serangan dan meningkatkan keamanan dari suatu website.

Membuat game dengan tampilan sederhana dengan mudah di mengerti oleh user

Membuat game adventure dan strategy

Masalah yang paling umum dari pathfinding dalam video game adalah bagaimana untuk menghindari rintangan cerdik dan mencari keluar jalur yang paling efisien di medan yang berbeda.

Membuat tampilan game menjadi lebih seperti hidup atau yg di sebut 3D

Membuat game adventure dan strategy.

Berdasarkan hasil pengujian, maka kesimpulan pada penelitian ini adalah : 1. Penggunaan algoritma resource assignment dapat memunculkan kemampuan berfikir dan berstrategi pada AI yang terdapat di game turnbased strategy. 2. Game turnbased strategy cocok Sebuah penelitian yang potensial adalah untuk terus mengoptimalkan A * algoritma dari perspektif ini atau untuk menggabungkan beberapa teknik optimasi menjadi satu solusi tunggal. lain cara untuk membuat beberapa kontribusi ke permainan AI masyarakat adalah untuk menerapkan teknik ini dijelaskan diatas untuk permainan komputer yang sebenarnya

karena tidak semua teknik yang dijelaskan dalam makalah ini telah banyak digunakan di industri game saat ini.

TURN BASED STRATEGY GAME MENGGUNAKAN ALGORITMA RESOURCE ASSIGNMENT PADA PERANGKAT MOBILE BERBASIS ANDROID Riandanu Madi Utomo, Nelly Indriani Widiastuti Universitas Komputer Indonesia Jl. Dipati Ukur 112 - 116 Telp. (022)2504119 Bandung 40132 Email : [email protected], [email protected] ABSTRAK Turn-based strategy (TBS) game adalah turunan dari game dengan genre strategi dimana pemainnya saling bergiliran pada pengambilan keputusannya dalam bermain. Pada game jenis ini, player dapat memainkan oleh satu pemain saja (single player) sedangkan lawannya adalah komputer atau istilah lainnya disebut Non Playable Character (NPC). Berdasarkan kebutuhan tersebut, maka perlu diterapkan NPC atau program yang memiliki Artificial Intelegence (AI). Peran NPC tersebut berfungsi untuk menggantikan peran manusia dalam menjadi teman atau musuh dari pemain pada sebuah game. NPC tersebut pada game TBS harus memiliki kemampuan berfikir dan berstrategi secara logis. Untuk memunculkan kemampuan tersebut, NPC harus dapat memperhitungkan kondisi yang dialaminya sebagai dasar keputusan yang akan diambil. Resource Assigment Algorithm (RAA) dipilih untuk menyelesaikan masalah tersebut, karena algoritma RAA mempunyai kemampuan untuk menghasilkan sebuah nilai berdasarkan beberapa nilai yang ada dengan diurutkan menggunakan skala prioritas [2]. Game TBS pada perangkat mobile masih jarang, sehingga penempatan game ini pada perangkat mobile dipilih agar game ini dapat dimainkan dimana saja dan kapan saja. Kata Kunci: Turn-Based Strategy, Game, Algoritma Resource Assignment, Perangkat Mobile

1. PENDAHULUAN Turn-based strategy (TBS) game adalah turunan dari game dengan genre strategi dimana pemainnya saling bergiliran pada pengambilan keputusannya dalam bermain. Contohnya adalah permainan catur kuno yang merupakan cikal bakal game TBS moderen dimana bidak putih dapat dijalankan oleh pemainnya ketika pemain yang mengendalikan bidak hitam telah menjalankan bidaknya. Untuk

menguasai game TBS, player memerlukan kemampuan berfikir dan berstrategi secara logis. Game ini tidak memerlukan kecepatan dan keakuratan dalam bermain tetapi memerlukan pengambilan keputusan yang tepat yang dapat membawa pemain pada kemenangan [1]. Varian game TBS semakin berkembang, tidak hanya dalam bentuk catur namun ada pula yang berbentuk simulasi peperangan dengan aturan yang lebih kompleks, pemainnya masih bergiliran dalam mengambil keputusan. Game TBS dapat dimainkan oleh hanya satu pemain saja (single player), sebagai lawan diperankan oleh Non Playable Character (NPC). Peran NPC adalah sebagai teman atau musuh dari pemain pada sebuah game. NPC pada game TBS memerlukan kemampuan berfikir dan berstrategi secara logis yaitu dengan memasukan kondisi yang sedang dialaminya pada penentuan keputusan. Berdasarkan masalah yang telah dijelaskan, maka NPC pada game TBS pun harus memiliki kemampuan yang sama agar pemain merasa lebih tertantang dan merasa seakan-akan bermain dengan pemain manusia. Solusi untuk memunculkan kemampuan berfikir dan berstrategi secara logis pada AI adalah menggunakan Resource Assignment Algorithm (RAA). RAA mempunyai kemampuan untuk menghasilkan sebuah nilai berdasarkan beberapa nilai yang ada dengan diurutkan menggunakan skala prioritas [2]. Dalam penerapannya pada game TBS maka nilai yang akan dihasilkan adalah nilai untuk mengeksekusi sebuah keputusan, dan beberapa nilai yang diurutkan dengan menggunakan skala prioritas adalah berbagai kemungkinan kondisi yang dihadapi sehingga AI akan terlihat memiliki kemampuan berfikir dan berstrategi secara logis karena faktorfaktor kondisi yang sedang dihadapi oleh AI ikut dimasukan dalam perhitungan. Game TBS dapat ditempatkan pada berbagai platform, baik desktop, mobile, ataupun konsol. Game TBS tidak memerlukan banyak tombol kontrol pada perangkat yang menjalankannya, bahkan dapat dilakukan hanya dengan menggunakan

touch screen. Game TBS pada mobile platform dipilih agar game ini dapat dimainkan dimana saja dan kapan saja. Perkembangan game TBS pada platform mobile juga masih dinilai lambat. Menurut data dari www.metacritic.com, hanya terdapat 28 game TBS pada platform mobile untuk Android. Berdasarkan hal tersebut, maka peluang untuk mengembangkan game TBS pada platform mobile terutama Android masih sangat besar.

to task doers seperti yang ditunjukan pada Gambar 2.1. 1. Gather Task Gather Task adalah proses pertama dari Algoritma Resource Assignment yang mana pada tahap ini adalah menentukan banyaknya objects yang terlibat.

RUMUSAN MASALAH Berdasarkan pendahuluan yang telah dijelaskan, maka rumusan masalah adalah bagaimana membuat NPC pada game TBS mobile yang memiliki kemampuan yang dapat memperhitungkan kondisi yang dialaminya sebagai dasar keputusan yang akan diambil menggunakan Resource Assigment Algorithm.

2. LANDASAN TEORI 2.1 Turn-based Strategy Game Turn-based strategy (TBS) game adalah turunan dari game dengan genre strategi dimana pemainnya bergantian dalam bermain. Hal ini sangat bertolak belakang dengan game-game lain dimana para pemainnya bermain bersama secara simultan. Game TBS berawal dari permainan catur kuno dimana player saling bergiliran menjalankan bidak caturnya.Game TBS mempunyai gameplay yang menawarkan pemainnya memilih satu dari berbagai macam keputusan yang disediakan pada game.Saat ini game TBS banyak dijumpai dalam video game.Berbagai jenis gameplay turunan game TBS ini pun bermunculan seperti menghabisi musuh (annihilate), menguasai wilayah (dominate), bahkan dengan misi-misi lebih spesifik lagi [3]. Pemain dalam game TBS tidak bergantung pada kecepatan, refleks, dan akurasi ketika bermain game lainnya karena sifat gameplay yang saling bergiliran dalam bertindak membuat pemainnya cenderung lebih mengandalkan logika dan intuisi dalam mengambil tindakan. Game ini pertama kali muncul dalam video game pada tahun 1977 dan sampai sekarang masih terus dikembangkan. 2.2 Resource Assigment Algorithm Algoritma resource assignment (RAA) adalah sebuah algoritma yang dapat menentukan sebuah nilai untuk sebuah objek yang memiliki resource berdasarkan nilai resource yang berasal dari objek lain maupun objek itu sendiri. Dengan kata lain, RAA adalah algoritma yang bergantung pada nilai resource yang dimiliki oleh objek-objek dalam menentukan sebuah nilai untuk sebuah objek [4]. Algoritma ini memiliki tiga parameter utama yaitu objects, resource dan modifier. Secara keseluruhan algoritma ini terbagi menjadi empat bagian yaitu gather task, generate all possible assignments, sort possible assignment according to score dan assign

Gambar 2.1 Elemen Algoritma Resource Assignment [1] 2. Generate All Possible Assignments Proses ini untuk penentuan nilai modifier yang mana nilai modifier ini akan digunakan untuk mengambil keputusan terhadap objects. Proses penentuan nilai modifier disini akan melibatkan resource yang terdapat pada objects. Nilai modifier terdapat pada setiap keputusan. Setiap keputusan tersebut akan diujikan pada setiap objects. Pengujian dilakukan berdasarkan aturan yang akan diterapkan pada sistem. Setiap terdapat aturan yang terpenuhi, maka nilai modifier untuk keputusan pada aturan tersebut akan ditambahkan. 3. Sort Assignments According to Score Proses ini adalah proses pengurutan setiap nilai modifier pada objects. Proses pengurutan ini bertujuan menentukan nilai modifier terbesar. 4. Assign to Task Doers Proses untuk menjalankan keputusan dengan memperhatikan nilai modifier terbesar yang didapatkan dari tahap Sort Assignments According to Score.

3. ANALISIS 3.1 Analisis Game Analisis game yang akan dikembangkan merupakan bagian yang mendeskripsikan game yang akan dikembangkan. Pada bagian ini terdiri dari story line, tingkat kesulitan, gameplay dan scoring. 1. Storyline Dengan tema perang moderen dan mengambil setting tahun 2106, diceritakan ketika tahun 2087, planet bumi ada pada kondisi yang sangat mengkawatirkan dikarenakan efek pemanasan global berada pada puncaknya. Karena dikhawatirkan akan mengancam kelangsungan hidup umat manusia,

maka dibawah Perserikatan Bangsa Bangsa (PBB) umat manusia memulai proyek terbesar sepanjang sejarah yaitu membuat alat yang akan mendinginkan bumi dengan memperkuat medan magnetik pada kutub bumi. PBB kemudian membagi negara-negara kepada dua fraksi yaitu Northern Alliance yang dipimpin oleh Amerika Serikat dan Southern Alliance yang dipimpin oleh Russia.Tugas masingmasing fraksi adalah membuat alat pada masingmasing kutub magnetik di bumi untuk mengurangi efek pemanasan global pada bumi. Pada game ini, player akan menjadi komandan pasukan GER yang akan bertempur dengan mengontrol Combat Gadget Droid yang merupakan unit pada game. Berdasarkan cerita diatas maka game ini diberi judul “The Icycle War - 2106”. Jenis misi yang terdapat pada game ini adalah mendominasi wilayah pada map yang terdapat pada setiap stage. Sistem pendominasian terletak pada jumlah node yang dikusai, semakin banyak node yang dikusai maka semakin besar dominasi pada map. Player yang menguasai seluruh node pada map adalah pemenangnya. 2.

Gameplay Analisis gameplay dilakukan untuk menggambarkan aturan-aturan dalam game. Analisis gameplay terdiri dari deskripsi alur permainan, deskripsi aturan game dan deskripsi kondisi pada game. a. Deskripsi Alur Permainan Pada game ini alur permainan sangat bergantung pada keputusan player sehingga alur permainan tidak dapat dipastikan. Player harus mengalahkan musuhnya dengan menguasai node yang ada pada permainan. Node dapat dikuasai oleh player dengan cara menempatkan pasukan pada node tersebut. Player akan diberi sejumlah pasukan pada awal permainan. Untuk memperbanyak pasukannya, player harus memproduksi pasukan sehingga dapat digunakan untuk mengusai node.Dalam memproduksi pasukan player harus menggunakan resource point untuk memproduksi pasukan.Resource point didapat dari setiap node yang dikuasai. b. Deskripsi Aturan Game Aturan (rule) pada game dibuat untuk menjaga keseimbangan permainan sehingga permainan tidak memberatkan atau meringankan player. Berikut adalah aturan utama yang akan diterapkan pada game ini : 1) Player membuat keputusan terhadap sumber daya yang dimilikinya yang berupa unit ,resource, dan node. 2) Kondisi untuk memenangkan pertempuran adalah ketika seluruh node pada map berhasil dikuasai. Dalam game ini, player harus mengambil keputusan yang dapat diambil pada setiap turn. Berikut adalah aturan pengambilan keputusan untuk setiap unit :

1)

Jenis keputusan yang dapat diambil adalah pass, build unit, attack, assign unit. 2) Pass adalah keputusan player untuk tidak melakukan apa-apa pada turn-nya. 3) Build unit adalah keputusan untuk membuat unit, unit dapat dibuat dengan uang yang dimiliki player. 4) Attack adalah keputusan menyerang node netral atau node milik musuh dengan mengirimkan beberapa unit yang ada ke node tersebut. 5) Assign unit adalah keputusan menempatkan unit pada node yang dimiliki player dengan tujuan mempertahankan node tersebut dari serangan musuh. Turn-based strategy game mempunyai sistem turn pada gameplay-nya.Turn adalah kondisi dimana suatu keputusan harus diambil.Turn dimulai dari player dan dilanjutkan dengan musuhnya (AI), lalu kembali dilanjutkan oleh player dan seterusnya hingga permainan berakhir ketika seluuh node dikuasai oleh salah satu pihak. Unit pada game ini dibagi menjadi tiga kelas yaitu infantry, tank dan artillery. Sistem pembagian kelas ini memungkinkan timbulnya faktor keuntungan dan kerugian ketika suatu kelas unit berhadapan dengan kelas unit yang lain.Perbedaan kelas pada unit terdapat pada kekuatannya, dimana infantry lebih lemahdari artillery dan tank, tank lebih kuat dari infantry dan lebih lemah dari artillery, sedangkan artillery lebih kuat tank dan infantry. c. Deskripsi Kondisi Pada Game Kondisi pada game adalah keadaan yang mungkin terjadi dalam game. Berikut adalah kondisi tersebut. 1) Keadaan awal (starting condition) Pada saat memulai game, player dan AI diberikan kondisi sebagai berikut : (a) Terdapat 1 node yang telah dikuasai. (b) Diberikan sejumlah resource untuk memproduksi unit. (c) Diberikan sejumlah unit untuk mengusai atau mempertahankan node. 2) Keadaan dalam game (in-game condition) Pada saat bermain, player harus melakukan tugas-tugas sebagai berikut : (a) Mempertahankan node yang dimiliki. (b) Menyerang dan mengambil alih node musuh atau node netral. (c) Memproduksi unit. (d) Tidak melakukan apa-apa (skip turn) 3) Keadaan akhir (final condition) Game akan berakhir dengan kondisi menang (victory) jika seluruh node berhasil dikuasai oleh player. Game akan berakhir dengan kondisi kalah (lose) jika seluruh node dikuasai oleh musuh (AI) atau player keluar dari game.

3.

Sistem Penilaian Sistem pemberian skor (scoring) pada game ini terjadi ketika player telah menyelesaikan game pada suatu stage. Pemberian skor pada player tidak hanya ketika player memenangkan permainan tetapi ketika player kalah pada permainan. Skor yang diberikan berupa jumlah resource yang telah player habiskan selama permainan. 3.2 Analisis Kebutuhan Games Pada game ini terdapat objek-objek dan resource yang akan berperan dalam jalannya permainan ini. Objek dan resource dapat dilihat pada Tabel 3.1.

Gambar 3.2 Map Stage 1 dan Stage 2

Tabel 3.1. Objek dan Resource Permainan Nama Node Infantry Tank Artillery Modifier

Map

Keterangan Merupakan objek yang menampung resource pada game. Merupakan salah satu resource pada game. Merupakan salah satu resource pada game. Merupakan salah satu resource pada game. Merupakan nilai yang terdapat pada setiap keputusan yang akan dijalankan oleh AI. Semakin besar nilai ini, semakin diprioritaskan pula sebuah keputusan akan dijalankan oleh AI. Merupakan arena pada permainan di setiap stage yang direpresentasikan menggunakan Graph dengan node sebagai simpulnya.

Selain objek dan resource, permainan ini juga membutuhkan map yang dibentuk yang direpresentasikan dalam bentuk graph tertutup dan tidak berarah. Di dalam map terdapat node, yaitu simpul-simpul yang harus dikuasai oleh player. Pada bagian perancangan ini, node digambarkan dengan bulatan berwarna. Angka dalam node merepresentasikan urutan node. Warna pada node merepresentasikan status kepemilikan node tersebut. Warna merah untuk node milik musuh (AI), warna biru untuk node milik player dan warna putih untuk node netral. Setiap node dihubungkan dengan menggunakan garis penghubung yang merepresentasikan hubungan tetangga dari sebuah node, contohnya adalah node 1 memiliki dua tetangga yaitu node 2 dan node 6 pada Gambar 3.2. Penggambaran inisialisasi map pada permainan ini dapat ini dapat dilihat pada Gambar 3.2 dan Gambar 3.3.

Gambar 3.3 Map Stage 3 Pada stage 1 dan 2, map tersusun dari 6 node yang mana pada awal permainan dimiliki node 1 dimiliki oleh player dan node 4 dimiliki oleh AI. Kepemilikan node dibedakan dengan warna yang mana apabila node berwarna biru, merupakan kepemilikan player dan merah merupakan kepemilkan AI. Pada Gambar 3.2 terlihat bahwa setiap node memiliki tetangga yang ditunjukan pada tabel berikut. Tabel 3.2 Daftar Tetangga Untuk Setiap Node Pada Map Stage 1 dan Stage 2 Node 1 2 3 4 5 6

Tetangga 1 2 1 2 3 4 5

Tetangga 2 6 3 4 5 6 1

Pada Stage 3, map tersusun dari 8 node yang mana pada awal permainan dimiliki node 1 dimiliki oleh player dan node 5 dimiliki oleh AI. Kepemilikan node dibedakan dengan warna yang mana apabila node berwarna biru, merupakan kepemilikan player dan merah merupakan kepemilkan AI, sama seperti pada stage 1 dan 2. Pada Gambar .33 terlihat bahwa setiap node memiliki tetangga yang ditunjukan pada tabel berikut.

Tabel 3.3 Daftar Tetangga Untuk Setiap Node Pada Map Stage 1 Node 1 2 3 4 5 6

Tetangga 1 2 1 2 3 4 5

Tetangga 2 6 3 4 5 6 1

3.3 Analisis Algoritma Algoritma resource assignment (RAA) adalah sebuah algoritma yang dapat menentukan sebuah nilai untuk sebuah objek yang memiliki resource berdasarkan nilai resource yang berasal dari objek lain maupun objek itu sendiri. Cara kerja algoritma resource assignment adalah dengan memeriksa status kepemilikan node dan menghitung nilai modifier pada setiap keputusan. Keputusan dengan nilai modifier terbesar adalah keputusan yang dipilih dan ditempatkan pada node tersebut. Setelah seluruh node diperiksa, maka nilai modifier pada setiap node diurutkan dan dipilih node dengan nilai modifier terbesar. Node tersebut adalah node yang keputusannya akan dijalankan oleh AI. Secara keseluruhan algoritma ini terbagi menjadi empat bagian yaitu gather task, generate all possible assignments, sort possible assignment according to score dan assign to task doers. Penerapan bagian-bagian tersebut pada proses pengambilan keputusan pada game ini adalah sebagai berikut: 1. Gather Task Proses dimana menentukan banyaknya node pada map serta penentuan tetangga untuk setiap node. 2. Generate All Possible Assignments Proses penentuan nilai modifier yang dihitung berdasarkan semua resource (infantry, tank, artillery) yang kemudian setelah memperhitungkan nilai modifiernya akan diambil keputusan apakah akan menyerang, bertahan, memproduksi unit, melewatkan giliran dan tidak memiliki keputusan sama sekali. Langkah-langkah dalam menentukan nilai modifier pada setiap node ditentukan dari aturan pada permainan. Langkah-langkah tersebut adalah sebagai berikut : a. Periksa status kepemilikan setiap node, jika status kepemilikan node adalah milik player atau netral, maka nilai modifier untuk node tersebut adalah 0 dan node tersebut tidak mempunyai keputusan (nilai keputusan = -1). b. Jika status kepemilikan node adalah milik AI maka dilakukan perhitungan nilai modifier untuk setiap keputusan berikut :

1) Keputusan menyerang Pada keputusan ini, dilakukan pemeriksaan kondisi pada node sebagai berikut : (a) Apakah status node tetangga dari node yang sedang diperiksa adalah milik player atau netral atau milik musuh (AI). Bila status kepemilikannya adalah milik player atau netral, maka nilai modifier pada keputusan ini ditambah 1. Bila status kepemilikan adalah milik musuh (AI), maka nilai modifier tidak bertambah. (b) Bandingkan kekuatan node yang sedang diperiksa dengan kekuatan node tetangganya. Apabila kekuatan node yang sedang diperiksa lebih besar kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini ditambah 1. Jika kekuatan node yang sedang diperiksa lebih kecil kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini tidak ditambahkan. (c) Bandingkan stok unit AI dengan jumlah unit pada node tetangga. Apabila stok unit AI lebih banyak jumlahnya debandingkan dengan stok unit pada node tetangga, maka nilai modifier pada keputusan ini ditambah 1. stok unit AI lebih banyak jumlahnya debandingkan dengan stok unit pada node tetangga, maka nilai modifier pada keputusan ini tidak ditambahkan. (d) Nilai modifier akhir untuk keputusan ini adalah jumlah dari nilai modifier pada kondisi yang cocok dibagi dengan jumlah seluruh kondisi yaitu 6. 2) Keputusan bertahan Pada keputusan ini, dilakukan langkah sebagai berikut : (a) Apakah status node tetangga dari node yang sedang diperiksa adalah milik player atau netral atau milik musuh (AI). Bila status kepemilikannya adalah milik player atau netral, maka nilai modifier pada keputusan ini ditambah 1. Bila status kepemilikan adalah milik musuh (AI), maka nilai modifier tidak bertambah. (b) Bandingkan kekuatan node yang sedang diperiksa dengan kekuatan node tetangganya. Apabila kekuatan node yang sedang diperiksa lebih kecil kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini ditambah 1. Jika

Jurnal Ilmiah Komputer dan Informatika Vol. 2, No. 2, Oktober 2013, ISSN : kekuatan node yang sedang diperiksa lebih besar kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini tidak ditambahkan. (c) Periksa stok unit milik AI, jika AI memiliki stok unit, maka nilai modifier pada keputusan ini ditambah 1. Jika AI tidak memiliki stok unit, maka nilai modifier pada keputusan ini tidak ditambahkan. (d) Nilai modifier akhir untuk keputusan ini adalah jumlah dari nilai modifier pada kondisi yang cocok dibagi dengan jumlah seluruh kondisi yaitu 5. 3) Keputusan memproduksi unit Pada keputusan ini, dilakukan langkah sebagai berikut : (a) Apakah status node tetangga dari node yang sedang diperiksa adalah milik player atau netral atau milik musuh (AI). Bila status kepemilikannya adalah milik musuh (AI) atau netral, maka nilai modifier pada keputusan ini ditambah 1. Bila status kepemilikan adalah milik player, maka nilai modifier tidak bertambah. (b) Bandingkan kekuatan node yang sedang diperiksa dengan kekuatan node tetangganya. Apabila kekuatan node yang sedang diperiksa lebih besar kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini ditambah 1. Jika kekuatan node yang sedang diperiksa lebih kecil kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini tidak ditambahkan. (c) Periksa stok unit milik AI, jika AI tidak memiliki stok unit, maka nilai modifier pada keputusan ini ditambah 1. Jika AI memiliki stok unit, maka nilai modifier pada keputusan ini tidak ditambahkan. (d) Periksa jumlah resource (julah dana untuk memproduksi unit) milik AI. Jika resource yang dimiliki lebih dari 30 maka nilai modifier pada keputusan ini ditambah 1. Jika resource yang dimiliki kurang dari 30 maka nilai modifier pada keputusan ini tidak ditambahkan. (e) Nilai modifier akhir untuk keputusan ini adalah jumlah dari nilai modifier pada kondisi yang cocok dibagi dengan jumlah seluruh kondisi yaitu 6.

4)

Keputusan melewatkan giliran Pada keputusan ini, dilakukan langkah sebagai berikut : (a) Apakah status node tetangga dari node yang sedang diperiksa adalah milik player atau netral atau milik musuh (AI). Bila status kepemilikannya adalah milik musuh (AI) atau netral, maka nilai modifier pada keputusan ini ditambah 1. Bila status kepemilikan adalah milik player, maka nilai modifier tidak bertambah. (b) Bandingkan kekuatan node yang sedang diperiksa dengan kekuatan node tetangganya. Apabila kekuatan node yang sedang diperiksa lebih besar kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini ditambah 1. Jika kekuatan node yang sedang diperiksa lebih kecil kekuatannya dibandingkan dengan node tetangganya maka nilai modifier pada keputusan ini tidak ditambahkan. (c) Periksa stok unit milik AI, jika AI tidak memiliki stok unit, maka nilai modifier pada keputusan ini ditambah 1. Jika AI memiliki stok unit, maka nilai modifier pada keputusan ini tidak ditambahkan. (d) Periksa jumlah resource (julah dana untuk memproduksi unit) milik AI. Jika resource yang dimiliki kurang dari 30 maka nilai modifier pada keputusan ini ditambah 1. Jika resource yang dimiliki lebih dari 30 maka nilai modifier pada keputusan ini tidak ditambahkan. (e) Nilai modifier akhir untuk keputusan ini adalah jumlah dari nilai modifier pada kondisi yang cocok dibagi dengan jumlah seluruh kondisi yaitu 6.

3.

Sort Assignments According to Score Proses yang merupakan tahap mengurutkan nilai modifier yang didapatkan dari tahap Generate All Possible Assignments sehingga didapat nilai modifier yang terbesar. Proses ini terjadi pada pengurutan nilai modifier pada setiap keputusan untuk menentukan nilai modifier untuk sebuah node, serta pada proses pengurutan nilai modifier pada seluruh node sehingga didapat node dengan nilai modifier terbesar.

4.

Assign to Task Doers Proses menjalankan keputusan yang didapatkan berdasarkan hasil pengurutan nilai modifier pada tahap Sort Assignments According to Score dengan menyeleksi nilai keputusan yang terdapat pada sebuah node. Jika nilai keputusan adalah 1, maka keputusan yang diambil adalah

Jurnal Ilmiah Komputer dan Informatika Vol. 2, No. 2, Oktober 2013, ISSN : menyerang. Jika nilai keputusan adalah 2, maka keputusan yang diambil adalah bertahan. Jika nilai keputusan adalah 3, maka keputusan yang diambil adalah memproduksi unit. Jika nilai keputusan adalah 4, maka keputusan yang diambil adalah melewatkan giliran.

4. IMPLEMENTASI & PENGUJIAN 4.1 Implementasi Sistem Game ini dibuat menggunakan Construct 2 R95 sehingga game ini merupakan game berbasiskan HTML 5. Implementasi game kedalam smartphone berbasiskan android menggunakan PhoneGap sebagai tool-nya. Perangkat keras yang digunakan untuk mengimplimentasikan dan menguji game ini memiliki spesifikasi sebagai berikut : 1. Processor dengan kecepatan 2,3GHz 2. Memori 2GB 3. Harddisk 250GB 4. Video Card dengan memori 256MB 5. Monitor 6. Mouse dan Keyboard 7. Speaker 4.2 Implementasi Antar Muka Implementasi antar muka adalah bagian yang menunjukan bentuk tampilan setiap antarmuka pada aplikasi yang sudah dibangun. Implementasi antar muka pada game ini disesuaikan dengan kebutuhan sistem. Berikut adalah salah satu antar muka pada stage 1 ditunjukan pada Gambar 4.1

Gambar 4.1 Antarmuka Stage 1 Beberapa antarmuka selama permainan seperti menyerang, mempertahankan node dan produksi unit.

Gambar 4.2 Antarmuka Menyerang

Gambar 4.3Produksi unit

Gambar 4.4 Mempertahankan Node 4.3 Pengujian Sistem Rencana pengujian perangkat lunak ini dibagi menjadi 2 bagian yaitu pengujian black box dan pengujian white box. Pengujian white box dilakukan untuk menguji kesalahan logik dan asumsi yang tidak tepat pada kemungkinan eksekusi. Pengembangan kode-kode program selalu memungkinkan terjadinya alur program yang tidak dan tereksekusi dan kesalahan typography yang sulit ditemukan kalau tidak dijalankan. Pada umumnya pengujian ini dilakukan hanya pada lingkungan developer. Pengujian black box dilakukan untuk mencari fungsi-fungsi program yang tidak benar atau hilang. Kesalahan lain yang mungkin terjadi dalam pembuatan program adalah kesalahan dalam struktur data, kesalahan antar muka, inisialisasi dan akhir program dan kesalahan performansi. Strategi pengujian akan dilakukan dengan menggunakan pengujian Beta. Pengujian beta adalah pengujian pada lingkungan pengguna. Pengujian ini dilakukan dengan menggunakan metode pengumpulan data melalui kuesioner. Pengguna akan mencoba game ini, kemudian pengguna akan memberikan feedback pada kuesioner yang telah disediakan . Deskripsi rencana pengujian dapat dilihat dalam Tabel 4.1.

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January an

Black tombol

Kelas Tabel 4.1 Rencana Pengujian Uji pada

Black tombol White

Black

nilai pada Uji Menu

Uji Black

Black tombol

tombol Black

Black tombol

petunjuk

Uji Menu

Black

Black

tombol

tombol Black

tombol

Black Black

tombol Black

Uji

Black tombol

Petunjuk

Black tombol Black

Uji

Black

Black tombol Black tombol Memilih

Black

Memilih

Black

Memilih

Black

Pengujian dengan kuesioner juga dilakukan untuk mengetahui penilaian kualitatif pada game ini.

5. PENUTUP Bagian ini merupakan kesimpulan dari keseluruhan penelitian yang dilakukan. Berdasarkan hasil pengujian, maka kesimpulan pada penelitian ini adalah : 1. Penggunaan algoritma resource assignment dapat memunculkan kemampuan berfikir dan berstrategi pada AI yang terdapat di game turn- based strategy. 2. Game turn-based strategy cocok diimplementasikan pada platform mobile sehingga dapat dimainkan kapan saja dan dimana saja.

DAFTAR PUSTAKA Black

Uji tombol

Black tombol

Black tombol Black

Uji

Black tombol

[1] Ed Welch. (2007, July) GAMASUTRA. [Online]. http://www.gamasutra.com/view/feature/1535/ designing_ai_algorithms_for_.php [2] Amnon Meisels and Ella Ovadia, "Assigning Resource to Constrained Activities". [3] Scott Rigby and Richard M Ryan, GLUED TO GAMES, How Video Games Draw Us In and Hold Us Spellbound. California, United States of America: Greenwood, 2011. [4] Rajendra Akerkar and Priti Sajja, KnowledgeBased System. United States of America: Jones and Barlett, 2010

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January

A*-based Pathfinding in Modern Computer Games Xiao Cui and Hao Shi School of Engineering and Science, Victoria University, Melbourne, Australia game. Considerable effort has been made to optimize this Pathfinding in computer games has been investigated for many algorithm over the past decades and dozens of revised years. It is probably the most popular but frustrating game algorithms have been introduced successfully. Examples artificial intelligence (AI) problem in game industry. Various of such optimizations include improving heuristic search algorithms, such as Dijkstra’s algorithm, bread first methods, optimizing map representations, introducing search algorithm and depth first search algorithm, were created new data structures and reducing memory requirements. to solve the shortest path problem until the emergence of A* The next section provides an overview of A* techniques algorithm as a provably optimal solution for pathfinding. Since which are widely used in current game industry. it was created, it has successfully attracted attention of Summary

thousands of researchers to put effort into it. A long list of A*-based algorithms and techniques were generated. This paper reviews a number of popular A*-based algorithms and techniques from different perspectives. It aims to explore the relationship between various A*-based algorithms. In the first section, an overview of pathfinding is presented. Then, the details of A* algorithm are addressed as a basis of delivering a number of optimization techniques from different angles. Finally, a number of real examples of how the pathfinding techniques are used in real games are given and a conclusion is drawn. Key words: Pathfinding, A*, A* optimization, Computer game

1. Introduction Pathfinding generally refers to find the shortest route between two end points. Examples of such problems include transit planning, telephone traffic routing, maze navigation and robot path planning. As the importance of game industry increases, pathfinding has become a popular and frustrating problem in game industry. Games like role-playing games and real-time strategy games often have characters sent on missions from their current location to a predetermined or player determined destination. The most common issue of pathfinding in a video game is how to avoid obstacles cleverly and seek out the most efficient path over different terrain. Early solutions to the problem of pathfinding in computer games, such as depth first search, iterative deepening, breadth first search, Dijkstra’s algorithm, best first search, A* algorithm, and iterative deepening A*, were soon overwhelmed by the sheer exponential growth in the complexity of the game. More efficient solutions are required so as to be able to solve pathfinding problems on a more complex environment with limited time and resources. Because of the huge success of A* algorithm in path finding [1], many researchers are pinning their hopes on speeding up A* so as to satisfy the changing needs of the Manuscript received January 5, 2011 Manuscript revised January 20, 2011

2. A* algorithm A* is a generic search algorithm that can be used to find solutions for many problems, pathfinding just being one of them. For pathfinding, A* algorithm repeatedly examines the most promising unexplored location it has seen. When a location is explored, the algorithm is finished if that location is the goal; otherwise, it makes note of all that location’s neighbors for further exploration. A* is probably the most popular path finding algorithm in game AI (Artificial Intelligence) [2]. 1. 2.

3.

Add the starting node to the open list. Repeat the following steps: a. Look for the node which has the lowest f on the open list. Refer to this node as the current node. b. Switch it to the closed list. c. For each reachable node from the current node i. If it is on the closed list, ignore it. ii. If it isn’t on the open list, add it to the open list. Make the current node the parent of this node. Record the f, g, and h value of this node. iii. If it is on the open list already, check to see if this is a better path. If so, change its parent to the current node, and recalculate the f and g value. d. Stop when i. Add the target node to the closed list. ii. Fail to find the target node, and the open list is empty. Tracing backwards from the target node to the starting node. That is your path. Fig. 1 Pseudocode of A* [3].

In the standard terminology used when talking about A*, g(n) represents the exact cost from starting point to any

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January

point n, h(n) represents the estimated cost from point n to the destination, and f(n)=g(n)+h(n). Fig. 1 lays out the algorithm step-by-step. A* has several useful properties which have been proved by Hart, Nilsson and Raphael in 1968 [4]. First, A* is guaranteed to find a path from the start to the goal if there exists a path. And it is optimal if h(n) is an admissible heuristic, which means h(n) is always less than or equal to the actual cheapest path cost from n to the goal. The third property of A* is that it makes the most efficient use of the heuristic. That is, no search method which uses the same heuristic function to find an optimal path examines fewer nodes than A*. Although A* is the most popular choice for pathfinding in computer games, how to apply it in a computer game depends on the nature of the game and its internal representation of the world. For example, in a rectangular grid of 1000×1000 squares, there are 1 million possible squares to search. To find a path in that kind of map simply takes a lot of work. Thus, reducing the search space may significantly speed up A*. Several optimizations are discussed in Section 3.

roadmap of North America, showing all roads annotated with driving distances, an A* implementation can compute the optimal travel route but this might be an expensive computation because of the sheer size of the roadmap. However, a hierarchical path finding would never work at such a low level of detail. Using abstraction can quickly find a route. The problem described above might be solved more efficiently by planning a large-scale route at the city level first and then planning the inter routes at each city passing through.

3. A* Optimizations Fig. 2 Five ways to represent search space [5].

The following sub-sections discuss several potential optimizations of A* from four different perspectives and reviews some popular A*-based algorithms.

3.1 Search Space In any game environment, AI characters need to use an underlying data structure – a search space representation – to plan a path to any given destination. Finding the most appropriate data structure to represent the search space for the game world is absolutely critical to achieving realistic-looking movement and acceptable pathfinding performance. As you can see in the above example, a simpler search space will mean that A* has less work to do, and less work will allow the algorithm to run faster. Examples of such representations include rectangular grid (Fig. 2a), quadtree (Fig. 2c), convex polygons (Fig. 2d), points of visibility (Fig. 2e), and generalized cylinders (Fig. 2f). The following sub-sections review two popular A*-based algorithms which optimize A* algorithm by reducing the search space.

3.1.1 Hierarchical Pathfinding A* (HPA*) Hierarchical pathfinding is an extremely powerful technique that speeds up the pathfinding process. The complexity of the problem can be reduced by breaking up the world hierarchically. Consider the problem of travelling from Los Angeles to Toronto. Given a detailed

A much faster A*-based search algorithm giving nearly solutions named HPA* is described in [6]. This is a domain-independent approach. The hierarchy can be extended to more than two levels, making it more scalable for large problem spaces. A three-step process is applied. The first step is to travel to the border of the neighborhood that contains the start location. Then, the second step is to search for a path from the border of the start neighborhood to the border of the goal neighborhood. This step is done at an abstract level, where search is simpler and faster. The last step is to complete the path by travelling from the border of the goal neighborhood to the goal position. HPA* has been proved that it is 10 times faster than a low-level A* in [6]. The potential problem of this technique is that the cost increases significantly when adding a new abstraction layer.

3.1.2 Navigation Mesh (NavMesh) NavMesh is another popular technique for AI pathfinding in 3D worlds. A NavMesh is a set of convex polygons that describe the “walkable” surface of a 3D environment. It is a simple, highly intuitive floor plan that AI characters can use for navigation and pathfinding in the game world. Fig. 3b shows an example of NavMesh. A character moves from the starting point in pol2 to the desired destination in pol4. In this case, the starting point is not

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January

in the same polygon as the desired point. Thus, the character needs to determine the next polygon it will go to. Repeat this step until both the character and the goal are located in the same polygon. Then, the character can move to the destination in a straight line. Compared with a waypoint graph as shown in Fig. 3a, NavMesh approach is guaranteed to find a near optimal path by searching much less data. And the pathfinding behavior in a NavMesh is superior to that in a waypoint graph [7].

search using various heuristic costs while trying to overcome a large obstacle. When the heuristic equals to zero (shown in Fig. 4a), A* algorithm turns to Dijkstra’s algorithm. All the neighboring nodes are expanded. When the heuristic uses the Euclidean distance to the goal (shown in Fig. 4b), only the nodes that look like better options are examined. When the heuristic is overestimated a little (shown in Fig. 4c), the search pushes hard on the closest nodes to the goal. Thus, overestimating the heuristic cost a little may result in exploring much fewer nodes than non-overestimation heuristic approaches. However, how much should the cost be overestimated is a tricky problem. No general solution exists at present.

3.3 Memory Although A* is about as good a search algorithm as you can find so far, it must be used wisely; otherwise, it might be wasteful of resources. A* algorithm requires a huge amount of memory to track the progress of each search especially when searching on large and complex environments. Reducing the required memory for pathfinding is a tricky problem in game AI. There has been a lot of work on this area. Fig. 3 Different representations of waypoint graph and NavMesh [7]

Creating navigation meshes that are highly simplified and easy for pathfinding is critical to achieving a good pathfinding. Tozour [9] describes how to construct a good navigation mesh and proposes a number of optimization techniques for navigation mesh.

3.2 Heuristic Function The secret to the success of A* is that it extends Dijkstra’s algorithm by introducing heuristic approach. Dijkstra’s algorithm is guaranteed to find a shortest path in a connected weighted graph as long as none of the edges has a negative value but it is not efficient enough because all the possible states must be examined. However, A* algorithm improves the computational efficiency significantly by introducing a heuristic approach. Using a heuristic approach means, rather than an exhaustive expansion, only the states that look like better options are examined. The heuristic function used in A* algorithm is to estimate the cost from any nodes on the graph to the desired destination. If the estimated cost is exactly equal to the real cost, then only the nodes on the best path are selected and nothing else is expanded. Thus, a good heuristic function which can accurately estimate the cost may make the algorithm much quicker. On the other hand, using a heuristic that overestimates the true cost a little usually results in a faster search with a reasonable path [10]. Fig. 4 shows the growth of the

Fig. 4 Comparison between different heuristics [10].

The most popular way to avoid memory waste is to pre-allocate a minimum amount of memory [10]. The general idea is to dedicate a piece of memory (Node Bank) before A* starts execution. During the execution, if all the memory gets exhausted, create a new buffer to progress the search. The size of this buffer is allowed to change so that less memory is wasted. The size of the

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January

minimum memory mainly depends on the complexity of the environment. Thus, tuning is required before this strategy is applied to a particular application. Another alternative to reduce space requirements in A* is to compute the whole path in small pieces. This is the core concept behind IDA* (Iterative Deepening A*), which is a very popular variant of A* algorithm. In IDA*, a path is cut off when its total cost f(n) exceeds a maximum cost threshold. IDA* starts with a threshold equal to f(start_node), in this case, the threshold is equal to h(start_node) because g(start_node)=0. Then, neighboring nodes are expanded until either a solution is found that scores below the threshold or no solution is found. In this case, the threshold is increased by one, and another search is triggered. The main advantage of IDA* over A* is that memory usage is significantly reduced.

group of units goes around forest to get to another position, half of them get stuck in the trees as shown in Fig. 5. Such situations always happen especially when the density of forest increases.

3.4 Data Structure Once a node has been initialized from the Node Bank (see Section 3.3), it needs to be put somewhere for fast retrieval. A hash table might be the best choice because it allows constant time storing and looking up of data. This hash table allows us to find out if a particular node is on the CLOSED list or the OPEN list instantaneously. A priority queue is the best way to maintain an OPEN list. It can be implemented by a binary heap. There is little work on introducing new data structures to maintain OPEN list and CLOSED list more efficiently. Probably introducing a new data structure to store the data can help speed up A* significantly.

Fig. 5 A screenshot of Age of Empires II. [11]

Another strategy game Civilization V uses hexagonal tiles to represent map locations as shown in Fig. 6. A pathfinding algorithm is applied to control the military unit moving to the desired location through a group of “walkable” hexagonal tiles. Similar to Age of Empires, Civilization V still suffers with bad pathfinding although it is the latest game of Civilization series which was released in November 2010.

4. Relevant Applications in Computer Games As a popular pathfinding algorithm in game industry, A* algorithm has been applied to a wide range of computer games. Although the algorithm itself is easy to understand, implementation in a real computer game is non-trivial. This section discusses several popular computer games in terms of pathfinding and uses a popular online game as an example to show how the different map representations can impact on the performance of pathfinding.

4.1 Pathfinding Challenge in Game Industry Age of Empires is a classic real-time strategy game. It uses grids to represent map locations. A 256×256 grid yields 65,536 possible locations. The movement of the military unit can be simplified as if moving an object through a maze. A* algorithm is applied to Age of Empires. Although it looks perfect theoretically, many Age of Empires players are annoyed by the terrible pathfinding. An example of such problems is that when a

Fig. 6 A screenshot of Civilization V. [12]

However, compared with strategy games which involve hundreds and thousands of units simultaneously, A* works much better in first-person shooter games like Counter-Strike which only involves a few units moving around at the same time. An explanation might be that the exponential growth in the number of units moving around at the same time makes the game environment much more dynamic and it is hard to provide optimal paths for hundreds and thousands of units in real time using limited CPU and memory resources. Massively

IJCSNS InternationalIJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January

multiplayer online is another example which involves real-time pathfinding intensively, like World of WardCraft.

4.2 Comparison between Map Representations Waypoint graph is a popular technique to represent map locations. Waypoints are a set of points that refer to the coordinates in the physic space. It is designed for navigation purpose and has been applied to a wide range of areas. Most game engines support pathfinding on a waypoint graph. Although it works well for most 2D games, it requires tons of waypoints to achieve an adequate movement in a 3D game because of the complexity of the environment. Thus, a new technique called NavMesh is created. As mentioned in Section 3.1.2, NavMesh only requires a couple of polygons to represent the map. It results in a much more quickly pathfinding because less data is examined. Five reasons why NavMesh works better than waypoint approaches in 3D games using World of WarCraft as an example are addressed by Tozour in 2008 [8]. It shows the difference between waypoints approaches and NavMesh when representing a complex 3D environment. It uses the town of Halaa in World of WarCraft as an example as shown in Fig. 7. In Fig. 7a, it uses 28 waypoints to represent the possible locations while on the other hand, as shown in Fig. 7b, only 14 convex polygons are used. The movement in Fig. 7b also acts much more like an actual human than the movement in Fig. 7a.

techniques described in this paper have been widely used in current game industry. The reason why they are reviewed in this paper is that they are the hottest topics in the academic domain of pathfinding and many researchers are struggling to bring them into real games. It is expected that this research help game industry has a basic understanding about the future research direction in pathfinding.

(a) Navigating from A to B using waypoint graph.

5. Conclusion This paper systematically reviews several popular A*-based algorithms and techniques according to the optimization of A*. It shows a clearly relational map between A* algorithm and its variants. The core of pathfinding algorithm is only a small piece of the puzzle in game AI. The most challenge is how to use the algorithm to solve tricky problems. A* algorithm is the most popular algorithm in pathfinding. It is hard-pressed to find a better algorithm since A* is provably optimal. A lot of effort has been put into speeding it up by optimizing it from different perspectives. The ways to improve the performance of A* search include optimizing the underlying search space, reducing the memory usage, improving heuristic functions and introducing new data structures. A potential research is to continue optimizing A* algorithm from these perspectives or to combine multiple optimization techniques into one single solution. Another way to make some contribution to the game AI community is to apply these techniques described above to the real computer games because not all of the

B. Stout, “The basics of A* for path planning,” in Game Programming GEMS, pp.254-262, Charles River Meida, America, 2000. [6] A.Botea, M.Mueller, and J.Schaeffer, “Near optimal hierarchical path-finding,” J. GD, vol.1, no.1, pp.7-28, [5]

(b) Navigating from A to B on NavMesh. Fig. 7 Comparison between wapoing graph and NavMesh [8].

References [1] B. Stout, “Smart moves: intelligent path-finding,” in Game Developer Magazine, pp.28-35, 1996. [2] Stanford Theory Group, “Amit’s A* page”, http://theory.stanford.edu/~amitp/GameProgramming/ASta rComparison.html, accessed October 12, 2010. [3] N.Nilsson, Artificial Intelligence: A New Synthesis, Morgan Kaufmann Publishers, San Francisco, 1998. [4] P. Hart, N. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans.Syst.Sci.Cybernet., vol.4, no.2, pp.100-107, 1968

2004. IJCSNS International IJCSNS JournalInternational of ComputerJournal Scienceofand Computer NetworkScience Security, andVOL.11 NetworkNo.1, Security, January VOL.11 No.1, January [7] Unreal Developer Network, “Navigation mesh reference”, http://udn.epicgames.com/Three/Navigation MeshReferenc e.html, accessed Jan.13, 2011. [8] Game/AI, “Fixing pathfinding once and for all”, http://www.aiblog.net/archives/000152.html, accessed September 23, 2010. [9] P. Tozour, “Building a near-optimal navigation mesh,” in AI Game Programming Wisdom, pp.171-185, Charles River Media, America, 2002. [10] S. Rabin, “A* speed optimizations,” in Programming GEMS, pp.264-271, Charles River Media, America, 2000. [11] Microsoft Games, “Microsoft Age of Empires”, http://www.microsoft.com/games/empires, accessed October 24, 2010. [12] Firaxis Games, “Sid Meier’s Civilization V”, http://www.civilization5.com, accessed October 24, 2010.

Game

Xiao Cui is a Ph.D student in School of Engineering and Science at Victoria University, Australia. He completed his master degree in the area of Software Engineering at Australian National University and obtained his Bachelor of Computer Science degree at Victoria University. His research interests include Object-Oriented Software Engineering, Pathfinding Algorithms, Database Management and Game Programming.

Hao Shi is an Associate Professor in School of Engineering and Science at Victoria University, Australia. She completed her PhD in the area of Computer Engineering at University of Wollongong and obtained her Bachelor of Engineering degree at Shanghai Jiao Tong University, China. She has been actively engaged in R&D and external consultancy activities. Her research interests include p2p Network, Location-Based Services, Web Services, Computer/Robotics Vision, Visual Communications, Internet and Multimedia Technologies.