Path finding for groups

OData support
Rajacsics Tamás
Department of Automation and Applied Informatics

Path finding has a great role in Real-Time Strategy (RTS) games. The player commands several units on a map, and most of these commands require the unit to go from point A to point B without colliding with any other objects on the map, including other units as well. Therefore a path finding algorithm is needed, which can find a collision free path from a start point to a destination, and another algorithm is needed, which makes the unit walk through the given path. These algorithms should be calculated in real-time, so efficiency is a key aspect in this problem. Unfortunately, the solution is not that simple, because multiple units might search path and move along them at the same time. In this case, this so called naïve approach has some performance and behavioral issues, so other algorithms should be taken into consideration throughout the planning.

In this paper we show the possible subtasks of the problem, and how others tried to solve them. Then with the help of these sources we present a method, which plans the paths of the units as a set of groups in our virtual world. Thereafter we define rules for the units to how to use the generated path to reach their goals. Solving the problem is not just the only issue, which needs to be solved, but it is essential that all used algorithms should produce their results in real-time. This means that time-consuming calculations should be done offline.

In the end, we will determine some metrics to measure the efficiency of the developed algorithm. Using those metrics will allow us to compare the algorithm with the naïve implementation, which will be presented to be worse than the group based path finding algorithm.


Please sign in to download the files of this thesis.