Implementation of a method for finding a shortest path with dynamic obstacles in computer games

V domeni računalniških iger problem iskanja poti in izogibanja dinamičnim oviram predstavlja enega izmed osrednjih izzivov. Potrebno ga je razrešiti na način, ki opazovalcu ustvarja vtis inteligence. V sklopu tega magistrskega dela smo razvili metodo za iskanje najkrajše poti, ki omogoča predvidevanje položaja ovir. Najprej smo preučili in predstavili najpogostejše pristope k iskanju najkrajše poti in izogibanju oviram v računalniških igrah. Na tej osnovi smo zasnovali in opisali razvoj lastne metode, ki združuje principe napovedovanja poti in sodelovalnega iskanja. Z našo metodo smo v izbranih scenarijih dosegli boljše potovalne čase agentov do njihovega cilja, kot so jih imeli z uporabo tradicionalnega pristopa k izogibanju oviram.Finding the shortest path, while avoiding dynamic obstacles, is one of the most important challenges in the domain of computer games, as it is crucial for creating the illusion of an intelligent agent. In this master’s thesis, we describe a method for finding the shortest path by considering the future positions of dynamic obstacles. For this purpose, we first describe traditional approaches to finding the shortest path around dynamic obstacles in computer games and discuss in detail the development of our own method. This combines the principles of cooperative pathfinding with path prediction. Results showed that our method improves travel times in comparison to the traditional approaches