IMPLEMENTASI HIERARCHICAL PATHFINDING A STAR ALGORITHM PADA GAME FINDYOURLETTERS MENGGUNAKAN PHONEGAP

22094797, Ignatius David Markal (2013) IMPLEMENTASI HIERARCHICAL PATHFINDING A STAR ALGORITHM PADA GAME FINDYOURLETTERS MENGGUNAKAN PHONEGAP. Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22094797_bab1_bab5_daftarpustaka.pdf Download (1MB)
	Text (Skripsi Informatika) 22094797_bab2-sd-bab4_lampiran.pdf Restricted to Registered users only Download (6MB) | Request a copy

Abstract

Seiring meningkatnya perkembangan game di gadget maka tingkat kompleksitas game juga semakin meningkat. Khusus game-game yang membutuhkan kecerdasan buatan maka diperlukan adanya algoritma kecerdasan buatan yang lebih baik dari algoritma-algoritma yang ada sebelumnya. Pathfinding adalah proses pencarian jalur yang sering digunakan di game. Adapun contoh algoritma yang dapat digunakan untuk pathfinding antara lain Djikstra dan A Star. Akan tetapi algoritma tersebut masih perlu untuk ditingkatkan dalam hal kecepatan dan penghematan resource CPU dan memory untuk diterapkan pada gadget yang memiliki resource CPU dan memory terbatas. Algoritma Hierarchical Pathfinding A Star (HPA*) merupakan salah satu dari pengembangan dari Algoritma A Star (A*) dengan melakukan abstraksi terhadap papan permainan (map abstraction) dengan membagi papan permainan ke dalam beberapa klaster yang saling berhubungan (linked local clusters), sehingga proses pathfinding dapat dipercepat dan kebutuhan memori dapat dikurangi. Untuk membuktikan kelebihan Algoritma Hierarchical Pathfinding A Star maka penulis merancang game dengan nama FindYourLetters. Game ini merupakan game bergenre puzzle, dimana tokoh utama diharuskan untuk menyusun huruf-huruf dari sebuah kata yang diberikan. Setiap tokoh utama mengambil salah satu dari huruf tersebut maka aka nada musuh-musuh yang mengejar tokoh utama dengan menerapkan Algoritma HPA* selama 5 detik. Setelah dilakukan analisis dan pengujian, disimpulkan bahwa Algoritma HPA* dapat menghasilkan pencarian jalur yang lebih cepat daripada Algoritma A* biasa. Sedangkan dari hasil pengujian dari Game FindYourLetters secara langsung di Gadget memanfaatkan PhoneGap (free cross-platform framework untuk membangun aplikasi mobile) dengan cara merata-rata kebutuhan CPU dan memori saat game dimainkan selama 20 kali, diperoleh kesimpulan bahwa penggunaan resource CPU dan memori pada Algoritma HPA* memiliki perbedaan selisih efisiensi relatif kecil dengan Algoritma A* biasa.

Actions (login required)

View Item