Pathfinding for Autonomous Swarm Systems with A Star and Flocking Algorithms

Year 2023, , 251 - 261, 31.10.2023

Mehmet Albayrak , Ali Murat Sümen

https://doi.org/10.17671/gazibtd.1236552

Abstract

In computer games with the theme of war and artificial life, the systems of artificial intelligence characters to move in flocks according to the rules of the raid movement algorithm by finding a way to a common goal as a team have been studied. Among the pathfinding algorithms used by these systems, Dijkstra, Best-First Search and A* have been examined. The results have shown that the A* pathfinding algorithm was the fastest and most efficient. By using this algorithm and a swarm movement model, an artificial intelligence system has been developed that can find its own way while moving as a team. It has been observed that teams formed by artificial intelligence characters using the A* algorithm achieve more successful results against in-game situations.
Within the scope of this study, a team-based artificial intelligence module was developed for a war-themed game. This module was created using the Unity 3D game engine. Using the flag grabbing scenario mode, the behavior of the leader user team and the enemy team was examined. As a result of this study, it has been revealed that important features of games such as playability and realism can be taken to the next level through dynamic game characters by using A* and raid movement algorithms.

Keywords

A*, flocking, swarm, team-based artificial intelligence, pathfinding algorithm

A Yıldız ve Akın Algoritmaları ile Otonom Sürü Sistemleri için Yol Bulma

Abstract

Savaş ve yapay yaşam temalı bilgisayar oyunlarında, yapay zekâlı karakterlerin, ortak bir hedefe takım halinde yol bularak akın hareketi algoritması kurallarına göre sürü halinde hareket etme sistemleri üzerinde çalışılmıştır. Bu sistemlerin kullandığı yol bulma algoritmaları arasında Dijkstra, Best-First Search (en iyi ilk arama) ve A* (A yıldız) incelenmiştir. Sonuçlar, A* yol bulma algoritmasının en hızlı ve etkili olduğunu göstermiştir. Bu algoritma ve sürü hareketi modeli kullanarak, takım halinde hareket ederken kendi yolunu bulabilen yapay zekâ sistemi geliştirilmiştir. A* algoritmasını kullanan yapay zekâlı karakterlerin oluşturduğu takımların, oyun içi durumlara karşı daha başarılı sonuçlar elde ettiği görülmüştür.
Bu çalışma kapsamında, savaş temalı bir oyun için takım tabanlı yapay zekâ modülü geliştirilmiştir. Bu modül, Unity 3D oyun motoru kullanılarak oluşturulmuştur. Bayrak kapma senaryosu modunda kullanılarak, lider kullanıcılı takım ile düşman takımı arasındaki karşılaşmanın sergilediği davranışlar incelenmiştir. Bu çalışma sonucunda, A* ve akın hareketi algoritmalarının kullanılması ile oyunların oynanabilirlik ve gerçekçilik gibi önemli özelliklerinin, dinamik oyun karakterleri aracılığıyla bir üst seviyeye taşınabileceği ortaya çıkmıştır.

Keywords

A*, Akın, Sürü, Takım Tabanlı Yapay Zekâ, Yol Bulma Algoritmaları

References

• Kocabaş, Ş. ve Öztemel, E., “AISim: An Intelligent Agent for Distributed Interactive Simulation". Seventh Computer Generated Forces and Behavioral Representation, 12-15 May 1998, Orlando, Florida, USA.
• Kent, S., “The Ultimate History of Video Games”, Prima Publishing, USA, 608p., 2001.
• Foeada, D., vd., “A Systematic Literature Review of A* Pathfinding”, Procedia Computer Sciences, c. 179, ss. 507-514, Oca. 2021, doi: 10.1016/j.procs.2021.01.034.
• Patel, A., “Heuristics” “http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html”, Erişim Tarihi:10.05.2021.
• Patel, A., “Heuristics” “http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html”, Erişim Tarihi:10.05.2021.
• Delling, D., Sanders, P., Schultes, D., ve Wagner, D., “Engineering Route Planning Algorithms”, Algorithmics of Large and Complex Networks - Design, Analysis and Simulation, 2009, ss. 117–139, doi: 10.1007/978-3-642-02094-0_7.
• Zafar, Z., ve Kant, K, “Novel Optimization using Hierarchical Path Finding A* (HPA*) Algorithm for Strategic Gaming Setup”, International Journal of Engineering & Technology, c. 7, ss. 54-57, Mar. 2018, doi: 10.14419/ijet.v7i2.6.10067.
• Gunda, R., A* Search Algorithm. “https://ramahanishagunda.medium.com/a-search-algorithm-8233683c5d60”, Erişim Tarihi: 28.05.2021.
• Rafiq, A., Kadir, T., ve Normaziah, I., “Pathfinding Algorithms in Game Development”, IOP Conf. Ser.: Mater. Sci. Eng., ss. 769, Oca. 2021, doi: 10.1088/1757-899X/769/1/012021.
• Jiang, Wenrong., “Analysis of Iterative Deepening A* Algorithm”, IOP Conference Series. Earth and Environmental Science, 2021, Vol. 693, Iss. 1, doi: 10.1088/1755-1315/693/1/012028.
• Lovinger, Justin and Xiaoqin Zhang. “Enhanced Simplified Memory-bounded A Star (SMA*+).” GCAI (2017).
• Rodler, P., “RBF-HS: Recursive Best-First Hitting Set Search”, Artificial Intelligence, Elsevier, 2022, doi: 10.48550/arXiv.2010.04282.
• Reynolds, C., Boids. “http://www.red3d.com/cwr/boids/”, Erişim Tarihi: 08.06.2021.
• H. Fathy, O. A. Raouf ve H. Abdelkader, “Flocking Behaviour of Group Movement in Real Strategy Games”, 9th International Conference on Informatics and Systems, ss. PDC-64-PDC-67, 2014, doi: 10.1109/INFOS.2014.7036679.
• Reynolds, C., Steering Behaviors For Autonomous Characters. “http://www.red3d.com/cwr/steer/gdc99/”, Erişim Tarihi: 12.11.2022.
• D. Sigurdson, V. Bulitko, W. Yeoh, C. Hernández ve S. Koenig, “Multi-Agent Pathfinding with Real-Time Heuristic Search”, IEEE Conference on Computational Intelligence and Games (CIG), 2018, ss. 1-8, doi: 10.1109/CIG.2018.8490436.
• Lee-Urban S., Vasta, M., Munoz-Avila, H., “RETALIATE: Learning Winning Policies in First-Person Shooter Games”, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Tem. 2007.