Original title: Multi-agentní pathfinding s leteckými transporty
Translated title: Multi-agent pathfinding with air transports
Authors: Kozma, Matouš ; Černý, Martin (advisor) ; Děchtěrenko, Filip (referee)
Document type: Bachelor's theses
Year: 2015
Language: eng
Abstract: [eng] [cze]
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. Ve většině realtimových strategiích (RTS) je často třeba řešit problém hledání nejkratší cesty pro skupinu jednotek. O tomto problému je známo, že je těžký, ale některé hry vyžadují řešení složitější verze tohoto problému. V této verzi se objevují kromě běžných pozemních jednotek i létající transporty, které se mohou dostat na jakékoliv pole na mapě, naložit jednotku na určitém místě a vyložit ji jinde. V této práci je představena nová rodina algoritmů založená na hladovém algoritmu, jehož primitivní verze je řešením nejčastěji používaným v dnešních hrách. Implementujeme tyto algoritmy v RTS hře Starcraft a změříme jejich výkon. Z těchto algoritmů vybereme ten s nejlepším výkonem jako řešení práce.
Keywords: multi-agent pathfinding; multimodal pathfinding; starcraft; multi-agentní pathfinding; multimodální pathfinding; starcraft

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/81915

Permalink: http://www.nusl.cz/ntk/nusl-351609


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses