Pathfinding with Hard Constraints : Mobile Systems and Real Time Strategy Games Combined

Abstract: There is an abundance of pathfinding solutions, but are any of those solutions suitable for usage in a real time strategy (RTS) game designed for mobile systems with limited processing and storage capabilities (such as the Nintendo DS, PSP, cellular phones, etc.)? The RTS domain puts great requirements on the pathfinding mechanics used in the game; in the form of de- mands on responsiveness and path optimality. Furthermore, the Nintendo DS, and its portable, distant relatives, bring hard con- straints on the processing- and memory resources available to said mechanics. This master thesis aims to find a pathfinding solution well suited to function within the above mentioned, narrow domain. From a broad selection of candidate solutions, a few promising subjects are treated to an investigative empirical study; with the goal of finding the best “fitting” solution, considering the domain. The empirical study shows that the triangle-based TRA' solution and the hierarchical-abstraction influenced Minimal Memory so- lution are both very promising candidates. Depending on how one exactly defines the domain, either one of the solutions could be considered the ‘best’ choice. Since the overall performance of TRA' showed a slight advantage, this solution was further inves- tigated by running an implementation on one of the intended domain platforms; the Nintendo DS. This paper is structured to serve as a guide, of sorts, to some very interesting, and diverse, pathfinding solutions. In the spirit of this effort, all of the more important aspects of these solu- tions, and the pathfinding domain as a whole, are thoroughly explained.