  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.
