Ramadhan, Akbar (2019) Penerapan Theta* Pathfinding Untuk Navigasi Non-Player Character Pada Gim Maze. Sarjana thesis, Universitas Brawijaya.
Abstract
Perkembangan Video Game semakin maju seiring berkembangnya zaman, dengan seperti contoh Computer Graphic yang menghasilkan produk yang hampir setara dengan kenyataan, dan banyaknya game engine yang tersedia untuk pengembang, membantu perkembangan game development dan industri gim. Salah satu aspek dari game development yang turut berkembang adalah Artificial Intelligence (AI). AI dapat membuat gim terasa nyata dengan membuat kecerdasan yang dapat mendekati pola pikir manusia. Salah satu penerapan dari AI yang sering dipakai adalah pathfinding. Pathfinding merupakan metode pencarian jalur dari suatu titik ke titik tertentu yang akan dijalankan oleh AI. Metode pathfinding yang paling sering digunakan adalah A*, karena A* pathfinding dipastikan dapat memberikan hasil pencarian yang paling optimal. Namun, jalur yang dihasilkan belum tentu jalur terdekat, karena jalur alternatif lainnya yang dilewati masih dapat dioptimalkan dengan post-processing technique. Banyak metode alternatif selain A*, salah satunya adalah Theta* Pathfinding, yang merupakan algoritme yang dikembangkan lebih lanjut dari A* Pathfinding. Penelitian ini membahas Theta* Pathfinding dan performanya dibandingkan A* Pathfinding dalam gim maze. Komponen yang digunakan untuk menelusuri maze adalah Non-Player Character (NPC) yang diimplementasi AI. Hasil dari pengujian menunjukkan bahwa Theta* Pathfinding menghasilkan pencarian jalur yang lebih optimal dengan waktu yang lebih singkat dibandingkan A* Pathfinding.
English Abstract
Video Game development has grown as time passes, with an example of Computer Graphic which resulted in a product that is almost on par with reality, and with varieties of game engine available for developers, helps the growth of game development and game industries. One aspect of game development which has also grown is Artificial Intelligence, or AI for short. AI has the ability to give the game a feeling of reality, with its intelligence that is almost like that of a human. One use of AI that is frequently used is Pathfinding. Pathfinding is a path searching method from one point to another driven by AI. A* is the most frequently used pathfinding, because A* is guaranteed to give the optimal path. However, the generated path is not always the closest path, as there are other omitted paths which can optimized further with post-processing technique. There are a lot of alternatives beside A*, one example is Theta* Pathfinding, which is an algorithm that was developed further from A*. This research discusses Theta* Pathfinding and its performance compared to the basic A* Pathfinding in a maze game. The component used to search for the path in the maze is AI-implemented Non-Player Character (NPC). The result of this research shows that Theta* Pathfinding generates a shorter, more optimal route and with a shorter time compared to that of A* Pathfinding.
Other obstract
-
Item Type: | Thesis (Sarjana) |
---|---|
Identification Number: | SKR/FILKOM/2019/591/051907783 |
Uncontrolled Keywords: | artificial intelligence, pathfinding, a*(a star), theta*(theta star), maze, non-player character(npc) |
Subjects: | 000 Computer science, information and general works > 006 Special computer methods > 006.6 Computer graphics |
Divisions: | Fakultas Ilmu Komputer > Teknik Informatika |
Depositing User: | Budi Wahyono Wahyono |
Date Deposited: | 24 Aug 2020 07:25 |
Last Modified: | 19 Oct 2021 05:40 |
URI: | http://repository.ub.ac.id/id/eprint/173934 |
Preview |
Text
Akbar Ramadhan .pdf Download (1MB) | Preview |
Actions (login required)
View Item |