Navigace skupiny jednotek v RTS hrách za pomoci toků v sítích nad flow field oblastmi

Abstract

This thesis explores the challenges of implementing effective navigation for groups of units in real-time strategy computer games, specifically focusing on the movement of large numbers of homogeneous units across a two-dimensional grid-based map. The thesis presents a pathfinding algorithm that could be used in RTS games. The algorithm enables the units to utilize multiple paths effectively by modeling the unit navigation as a flow network problem. The units use precomputed flow fields during the navigation. This allows for faster pathfinding times by offloading part of the computation to the preprocessing. The algorithm's performance is evaluated against a baseline solution using the A* algorithm and other existing solutions. Comparative analysis will be conducted utilizing maps from the Moving AI 2D Pathfinding Benchmark dataset to assess the efficacy of the proposed solution. 1

Tato diplomová práce zkoumá problém implementace efektivní navigace pro skupiny jednotek v real-time strategických počítačových hrách, konkrétně na pohych velkého množství stejnorodých jednotek na dvou-dimenzionální mapě. Práce navrhuje navigační algoritmus, který by bylo možné použít v RTS hrách. Algo- ritmus umožňuje jednotkám efektivně využit alternativní cesty díky modelování navigace jednotek pomocí toků v síti. Jednotky během své navigace používají předpočítaná vek- torová pole. To umožňuje dosažení rychlejšího nalezení cesty díky přesunutí části výpočtu do fáze preprocessingu. Efektivita algoritmu je porovnána proti základním řešenim využívajícím A*, nebo a jiné běžné navigační algoritmy. K posouzení účinnosti navrhovaného algorimu bude prove- dena srovnávací analýza s využitím map z datového souboru Moving AI 2D Pathfinding Benchmark. 1