Terrain Analysis in StarCraft 1 and 2 as Combinatorial Optimization
This provides a flexible tool for StarCraft bot developers, allowing adaptive AI with varied spatial needs, though it is incremental as it builds on existing analysis methods.
The paper tackles terrain analysis in StarCraft games by framing it as a combinatorial optimization problem, enabling customizable spatial representations through adjustable constraints and objective functions, and introduces a universal library, Taunt, that works for both StarCraft 1 and 2.
Terrain analysis in Real-Time Strategy games is a necessary step to allow spacial reasoning. The goal of terrain analysis is to gather and process data about the map topology and properties to have a qualitative spatial representation. On StarCraft games, all previous works on terrain analysis propose a crisp analysis based on connected component detection, Voronoi diagram computation and pruning, and region merging. Those methods have been implemented as game-specific libraries, and they can only offer the same kind of analysis for all maps and all users. In this paper, we propose a way to consider terrain analysis as a combinatorial optimization problem. Our method allows different kinds of analysis by changing constraints or the objective function in the problem model. We also present a library, Taunt, implementing our method and able to handle both StarCraft 1 and StarCraft 2 maps. This makes our library a universal tool for StarCraft bots with different spatial representation needs. We believe our library unlocks the possibility to have real adaptive AIs playing StarCraft, and can be the starting point of a new wave of bots.