ANALYSIS AND IMPLEMENTATION OF ALGORITHMS FOR FINDING THE OPTIMAL PATH FOR PROGRAMMABLE OBJECTS IN DIGITAL GAME SPACES
Abstract
The study is devoted to developing methods for finding the optimal path for programmable objects in a virtual game environment. Algorithmic approaches to determining the shortest path are considered, and the application of the A* algorithm in the Unity engine is investigated for implementing an effective search for the shortest distances between the initial and target points of movement of a game character. Particular attention is paid to the analysis of the key parameters of the algorithm – gCost, hCost, and fCost, which determine the heuristic estimate of the cost of movement and ensure the optimality of routes in the context of the complex structure of the game space. The study also considers the features of the virtual environment, such as the presence of obstacles, variable environmental conditions, and the dynamics of the game process, which affect decision-making by the navigation system.In the process of software implementation of the A* algorithm, special attention is paid to the mechanism of dynamic updating of the set of neighboring nodes for each vertex of the navigation graph. This approach provides flexibility for the algorithm in a changing environment, allowing it to quickly respond to the appearance of new obstacles or changes in the topology of the game scene. This allowed us to increase the adaptability of the pathfinding system to real-time conditions, which is critically important for modern gaming applications.The results of the study confirm the high efficiency of the A* algorithm in solving the problems of finding the optimal path, which makes it relevant for a wide range of applications in the field of computer technology, in particular in game design, virtual simulations, and autonomous navigation systems in robotics. The integration of the algorithm into the Unity development environment not only expands the functionality of this engine but also creates the prerequisites for further improvement of the intelligent components of gaming and simulation systems. The presented study emphasizes the importance of implementing adaptive navigation algorithms and their role in the development of innovative technologies. The results can be used to increase the adaptability and performance of navigation systems in computer games.
References
2. Фесенко А.Р. Комп’ютерна реалізація аналізу пошуку шляху в програмованих об’єктах гри. URL: https://surl.li/kgipri
3. Гарт, П., Нільсен, Н., Раппапорт, Б. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics. 1968. ol. 4, No. 2. С. 100–107.
4. Introduction to the A* Algorithm. URL: https://www.redblobgames.com/pathfinding/a-star/introduction.html.
5. Dijkstra’s Algorithm – Shortest Path. URL: https://surl.li/ysngqd.
6. Алгоритм Дейкстри. URL: https://www.wikiwand.com/uk/articles/Алгоритм_Дейкстри.
7. Рассел, С., Норвіг, П. Штучний інтелект: сучасний підхід. Київ: Діалектика, 2020. 1168 с.
8. LaValle, S. M. Planning Algorithms. Cambridge: Cambridge University Press, 2006. 826 p.
9. Millington, I., Funge, J. Artificial Intelligence for Games. 2nd ed.
10. Koenig, S., Likhachev, M. D* Lite // Proceedings of the AAAI Conference on Artificial Intelligence. 2002. Vol. 15, No. 1. С. 476–483.
11. Unity AI Navigation Docs, 2023.
12. A* Search: Concept, Algorithm, Implementation, Advantages, Disadvantages. URL: https://surl.li/zazxtd.
13. Krianto S. Bellman Ford algorithm – in Routing Information Protocol. Journal of Physics Conference Series, Volume 1007(1), 2018. 10 р.
14. Iterative Deepening A* Algorithm (IDA*). URL: https://www.tpointtech.com/iterative-deepening-a-algorithm.
15. D*, D* Lite & LPA*. URL: https://surl.li/psneqo