Abstract

Pathfinding is an important problem in video games. Good pathfinding strategy, for both player characters and non-player characters is one of the key differences between a good game and a less successful one. Finding the shortest path for one character unit in a given environment is a very well-known problem for which there exist many solutions. When a group of units wants to pass through the map, the problem becomes more complicated. This thesis introduces the Reduced Wait Time (RWT) algorithm which is a multi-unit path planning algorithm where units can take several paths instead of just the shortest one to reduce the overall waiting time of the units in queues along the path and therefore reduces the total time needed to pass all units through the map.
The main goal of this thesis is propose the pathfinding algorithm RWT to reduce the total time for a group of units to pass a route. The simulation results shows that the RWT algorithm not only reduces the time to pass by decreasing the waiting time, but also can reduce the number of collisions between units which reduces the CPU usage which is another important consideration for games. Using the RWT algorithm also gives an opportunity to the level designers to be able to implement strategic pathfinding in games. Different routes have different strategic advantages and disadvantages over each other; being able to send units through different paths enables designers to consider strategic path-planning.
The RWT algorithm was implemented using the Unity game engine and tested on a number of randomly generated example maps. The experimental results were compared with the results from other related algorithms such as Local Repair A* and Maximum Flow to show that the RWT algorithm works better than other studied algorithms.