Shortest path algorithms in video games

Problem wyszukiwania najkrótszej ścieżki jest jednym z głównych obszarów badań w grach wideo od wielu lat. Jest to prawdopodobnie jeden z najbardziej popularnych, lecz jednocześnie najtrudniejszych problemów sztucznej inteligencji spotykanych w branży gier wideo. Celem pracy jest przedstawienie problemu wyszukiwania najkrótszej ścieżki, przegląd algorytmów rozwiązujących ten problem, w szczególności skupiając się na algorytmie A* oraz różnych jego modyfikacjach, a także stworzenie działającego algorytmu rozwiązującego problem w środowisku gry wideo . Implementacja algorytmu została wykonana w języku C# przy użyciu środowiska programistycznego Visual Studio oraz silnika Unity.Shortest path problem is one of the main areas of research in video games. It is probably one of the most popular, but, at the same time, one of the most difficult problems of artificial intelligence in video game industry. Purpose of this thesis is to present the shortest path problem, make an overview of the shortest path algorithms, in particular on the A* algorithm and its modifications, as well as implement algorithm that solves the shortest path problem in video game environment. Algorithm implementation was created in C# using Visual Studio and Unity