Implementasi Multi-Agent Path Finding Menggunakan Algoritma Conflict-Based Search Pada Game Bergenre Adventure-Puzzle

Abstrak

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. FPS yang didapatkan pada multi-agent pathfinding 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.