Multi-agent pathfinding with air transports

In most real-time strategy (RTS) games the problem of finding the shortest path for multiple units in real-time has to be solved many times during one match. That problem is known to be difficult, but some games require solving an even more complicated version of the problem where, in addition to land-based units, there are aerial transports, which are able to move everywhere around the map and to load a unit at one place and unload it somewhere else. In this thesis we introduce a new family of algorithms based on a greedy algorithm, which also serves as a basis for the primitive solutions used in games today. We implement these algorithms in the RTS game Starcraft and evaluate their effectiveness. From these tests we choose the one with the best performance as the solution of this thesis