Irawan, Fathony Teguh (2018) Implementasi Multi-Agent Path Finding Menggunakan Algoritma Conflict-Based Search Pada Game Bergenre Adventure-Puzzle. Sarjana thesis, Universitas Brawijaya.
Abstract
Kebutuhan akan video game terus meningkat, hal ini dapat dilihat dari semakin banyaknya pemain video game. Dengan meningkatnya pemain, sebuah video game harus teroptimasi agar dapat menjangkau lebih banyak pasar. Penggunaan artificial intelligence pada video game bukanlah merupakan hal baru lagi. Pada umumnya, kebanyakan video game sekarang memanfaatkan artificial intelligence pada entitas di video game-nya. Permasalahan yang terjadi adalah pengaruh dari implementasi artificial intelligence terhadap performa dari suatu video game. Permasalahan dari multi-agent pathfinding adalah untuk mencari jalur untuk lebih dari satu agen. Constraint yang dimiliki oleh multi-agent pathfinding adalah tidak boleh ada lebih dari satu agen yang menempati tempat yang sama pada waktu yang sama. Pada penelitian ini, peneliti mengajuan untuk menggunakan algoritma conflict-based search dalam menyelesaikan multi-agent pathfinding. Perancangan multi-agent pathfinding adalah dengan merancang algoritma Conflict-based search pada high-level searching, dan A* search pada low-level search. Implementasi multi-agent pathfinding berdasarkan perancangan yang sudah didefinisikan, diimplementasikan pada game engine Unity3D dengan menggunakan bahasa pemrograman C#. Proses pengujian dilakukan setelah implementasi selesai dan didapati hasil dimana tidak ada lebih dari satu agen yang menempati tempat yang sama pada waktu yang sama. Penggunaan resource dari conflict-based search menunjukkan bahwa penggunaan resource yang stabil dengan nilai CPU pada nilai 35% dan RAM pada nilai 7%. FPS yang didapatkan pada multi-agent pathfinding adalah berkisar 52 hingga 59 frame per seconds dan masih dapat dikatakan playable. Namun, waktu cycle yang dihasilkan terus bertambah seiring bertambahnya jumlah agen. Dengan implementasi ini diharapkan pengembang game tidak kesulitan dalam membangun multi-agent pathfinding pada video game-nya.
English Abstract
The need for video game continues to increase, this can be seen from the increasing number of video game players. With increasing player, a video game must be optimized to be able to reach more markets. Artificial intelligence usage in video games is not new thing anymore. In general, most of video games now take advantage of artificial intelligence on entities in their video games. The problem that occurs is the impact of the implementation of artificial intelligence on the performance of video game. Multi-agent pathfinding is there to try to find path for the agents registered. Multi-agent pathfinding has some constraint that doesn’t let more than one agent occupying same place at the same time. In this study, researcher propose to use conflict-based search algorithm to solve multiagent pathfinding constraint. The design of multi-agent pathfinding is by designing conflict-based search for high-level search and A* search for low-level search. Implementation of multi-agent pathfinding is based on the design that has been defined, implemented on Unity3D game engine using C# programming language. Testing process is conducted after the implementation is completed and found the result is there is no condition where more than one agent occupy same place at the same time. Resource usage of conflict-based search also shown to be at stable rate with 35% CPU utilization and 7% RAM usage. FPS that obtained from multi-agent pathfinding is at 52 to 59 frame per seconds and still considered as playable. However, cycle time that generated while running conflict-based search continuous to growth as the number of agents increases. With this implementation is expected to help game developer to implement multi-agent pathfinding in their video game.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/FTIK/2018/127/051801114 |
| Uncontrolled Keywords: | Video Game, Artificial Intelligence, Multi-Agent Pathfinding, Conflictbased Search |
| Subjects: | 000 Computer science, information and general works > 006 Special computer methods > 006.3 Artificial intelligence |
| Divisions: | Fakultas Ilmu Komputer > Teknik Informatika |
| Depositing User: | Yusuf Dwi N. |
| Date Deposited: | 02 Jul 2018 07:08 |
| Last Modified: | 26 Oct 2021 07:40 |
| URI: | http://repository.ub.ac.id/id/eprint/11814 |
Preview |
Text
BAB VI.pdf Download (415kB) | Preview |
Preview |
Text
BAB VII.pdf Download (36kB) | Preview |
Preview |
Text
Bagian Depan.pdf Download (135kB) | Preview |
Preview |
Text
Daftar Pustaka.pdf Download (28kB) | Preview |
Preview |
Text
BAB I.pdf Download (57kB) | Preview |
Preview |
Text
BAB II.pdf Download (115kB) | Preview |
Preview |
Text
BAB III.pdf Download (63kB) | Preview |
Preview |
Text
BAB IV.pdf Download (281kB) | Preview |
Preview |
Text
BAB V.pdf Download (1MB) | Preview |
Actions (login required)
 |
View Item |