Home Work Resume

Bachelor Thesis

Flow Fields

for motion control of large NPC groups in Real-Time Strategy games

Computer Science - Game Engineering
University of Applied Sciences Kempten

Pathfinding algorithms are a particularly important component of real-time strategy games. In order to solve the dependency of the required computing time on the number of troops flow fields can be used to solve the dependency of the required computing time on the number of troops on a field. The goal of this work is to answer the question whether flow fields are a reasonable alternative to the widely used A*-algorithm and to what extent it can be used in real-time strategy games. is possible. For this purpose, an application was developed with the help of the Unity Engine, which allows to test both pathfinding methods in detail and to measure the performance in benchmarks. It can be seen that flow fields are significantly faster above a certain number of units, but some of the functions provided by the A* algorithm are lost, are lost. A solution which is based on both methods and dynamically switches between the algorithms turns out to be the preferred method.


Flow Fields
Implementation of Flow Fields on a 2D Grid which allows any number of NPCs to find their best path to the target.
The A* algorithm is the most used method for pathfinding in games and allows for an easy comparison in the application.
Dynamic Switch
Dynamic Switching between Flow Fields and the A* algorithm is one of the solutions to solve some of the problems.
To compare Flow Fields and A* Pathfinding there is a Benchmarking-Tool implemented using graphs and .csv export.


Short demonstration of the finished application.