| NIM | H1D022023 |
|---|
| Namamhs | ZIA KHUSNUL FAUZI AKHMAD |
|---|
| Judul Artikel | OPTIMALISASI ALGORITMA PATHFINDING A* DENGAN JUMP POINT SEARCH PADA GAME BERBASIS GRID MOVEMENT
|
|---|
| Abstrak (Bhs. Indonesia) | Perkembangan teknologi digital, khususnya dalam industri video game, mendorong pemanfaatan kecerdasan buatan (Artificial Intelligence/AI) untuk meningkatkan kualitas gameplay, salah satunya melalui sistem pathfinding pada game. Algoritma A* banyak digunakan karena mampu menghasilkan jalur optimal, namun memiliki kelemahan pada eksplorasi node yang tinggi sehingga memengaruhi waktu komputasi dan penggunaan memori. Penelitian ini bertujuan untuk mengoptimalkan algoritma A* menggunakan Jump Point Search (JPS) serta membandingkan efektivitas dan efisiensi keduanya. Metode yang digunakan adalah eksperimen kualitatif dengan pendekatan Game Development Life Cycle (GDLC). Game dikembangkan menggunakan Unity sebagai studi kasus implementasi algoritma, kemudian diuji menggunakan dataset benchmark Sturtevant dengan lebih dari 1,35 juta skenario. Evaluasi dilakukan berdasarkan completeness, optimality, time complexity, dan space complexity. Hasil penelitian menunjukkan bahwa kedua algoritma memiliki tingkat completeness dan optimality sebesar 100%. Namun, JPS lebih unggul dalam efisiensi dengan rata-rata waktu eksekusi 5,92 ms dibandingkan A* sebesar 17,10 ms serta penggunaan memori 7,79 MB dibandingkan 9,09 MB. Dari sisi eksplorasi node, A* memiliki rata-rata open node sebesar 1.764 dan closed node sebesar 45.569, sedangkan JPS hanya 83 open node dan 3.395 closed node. Uji ANOVA menunjukkan perbedaan yang signifikan secara statistik antara kedua algoritma. Dengan demikian, JPS terbukti mampu meningkatkan efisiensi A* tanpa mengurangi optimalitas solusi. |
|---|
| Abtrak (Bhs. Inggris) | Advances in digital technology, particularly in the video game industry, have driven the use of artificial intelligence (AI) to enhance gameplay quality, including through pathfinding systems in games. The A* algorithm is widely used because it can generate optimal paths, but it has a weakness in high-node exploration, which affects computation time and memory usage. This study aims to optimize the A* algorithm using Jump Point Search (JPS) and to compare the effectiveness and efficiency of both. The method used is a qualitative experiment employing the Game Development Life Cycle (GDLC) approach. The game was developed using Unity as a case study for algorithm implementation and then tested using the Sturtevant benchmark dataset with over 1.35 million scenarios. Evaluation was based on completeness, optimality, time complexity, and space complexity. The results show that both algorithms have a completeness and optimality rate of 100%. However, JPS is superior in efficiency with an average execution time of 5.92 ms compared to A*’s 17.10 ms, and memory usage of 7.79 MB compared to 9.09 MB. In terms of node exploration, A* had an average of 1,764 open nodes and 45,569 closed nodes, while JPS had only 83 open nodes and 3,395 closed nodes. The ANOVA test revealed statistically significant differences between the two algorithms. Thus, JPS has been proven capable of enhancing A*’s efficiency without compromising solution optimality. |
|---|
| Kata kunci | A*, game, Jump Point Search, optimalisasi algoritma, pathfinding |
|---|
| Pembimbing 1 | Dr. M. Agus Syamsul Ariffin S.St., M.Kom. |
|---|
| Pembimbing 2 | Ir.Nur Alfi Ekowati, S.Kom., M.Sc |
|---|
| Pembimbing 3 | |
|---|
| Tahun | 2026 |
|---|
| Jumlah Halaman | 160 |
|---|
| Tgl. Entri | 2026-04-28 17:29:32.25548 |
|---|