Terrain Analysis in StarCraft 1 and 2 as Combinatorial Optimization

A Real-Time Strategy game, or RTS game, is a genre of video game where players must gather resources to develop an army, and must destroy the army or the buildings of other players to win. Unlike classic strategic board games such as Chess, players are not making moves alternatively, by simultaneously in real-time. The most popular way to play this kind of games involves two players in a 1 vs 1 game.

This study tackles terrain analysis on the two widely popular RTS games of the StarCraft series: the first one “StarCraft” together with its extension “StarCraft: Brood War”, denoted in this paper as StarCraft 1, and the second one “StarCraft II” under its last version named “Legacy of the Void”, denoted here as StarCraft 2. To explain something concerning both games, we will simply write StarCraft. Both games have a similar gameplay with some different features, such as unit characteristics and some map properties.

In StarCraft, players must gather two types of resources (minerals and gas) in order to construct buildings. Those buildings are required to produce units, to improve some unit characteristics or even to add new ones. All of these have a given cost to be paid in resources.

Games are played on a rectangular map, discretized into tiles called buildable tiles, upon which buildings can be constructed, and smaller tiles called walkable tiles, which are discrete in StarCraft 1 but continuous values in StarCraft 2 (so not tiles per se), on which units can walk. Indeed, some pixels on a map can be walkable without being buildable. This mostly happens at the edge of some natural borders such as cliffs or water.

Like most RTS games, the map is covered by a “fog of war” preventing players seeing enemy units that are not next to their own units. However, since each game on a given map will always start with the same initial properties (except the starting position of players), it is considered that the map topology and properties, such as the position and quantity of each resource, are known.

A bot playing StarCraft must know the terrain topology and the map properties to be able to do some spacial reasoning. Spacial reasoning is necessary to make good decisions such as where to expend for colonizing an unclaimed part of the map, where to attack the opponent in priority, and where defense must be reinforced.

Terrain analysis is gathering and processing data about the map topology and properties to have a qualitative spatial representation, required to make spatial reasoning. In StarCraft, map topology is characterized among other things by the terrain height (low, high and very high, to take StarCraft 1 terminology, and a rare fourth level in StarCraft 2) and the nature of each tile paving the map (walkable and/or buildable). Map properties include the height and width of the map, the position and the quantity of resources, the possible starting position of players, the presence, position and hit points of destructible obstacles, etc.

One of the main jobs done by a terrain analysis is splitting the map into regions, and spotting choke points that are easy to defend and make evident region delimiters.

Taunt offers the same features BWTA and BWTA2 provide: split the map into regions, mark choke points and base placements, compute contour polygons of regions and choke points, etc.

The new features compare to BWTA/BWTA2 are listed below. To the best of our knowledge, the two first ones have not been implemented by any other terrain analysis tools for StarCraft.

• •

  Proposing a unique terrain analysis library working with StarCraft 1 and StarCraft 2 maps, with the same library interface.

• •

  Offering different options of terrain analysis, to better fit different needs.

• •

  Allowing dynamic terrain analysis, such as recomputing regions after some dynamic event like the suppression of destructible obstacles (also implemented in by the StarCraft 1 terrain analysis library BWEM).

Taunt stands for “Terrain Analysis: UNiversal Tool”. Our goal is to propose a terrain analysis library which is universal because it can be used for both StarCraft games, but also universal because it is able to analyze the same map differently, aiming to provide an adapted analysis to various StarCraft bots.

Taunt roughly follows the same steps as BWTA2 until its fifth step, with a significant difference at Step 2. It also uses the boost::geometry library, then exploiting the R-Tree data structure for diverse queries. Its process is given in Alg. 3.

One problem with all existing terrain analysis libraries for StarCraft 1 or StarCraft 2 is that they tend to cut the map into numerous regions. Some of these regions do not contain any relevant strategic properties and would be probably not considered as an independent region by human players. This is due to the fact that all existing libraries are building regions by considering each slight narrowing of the ground, even large ones, as a choke point.

We wanted to counter-balance this with Taunt, and to propose a different way (actually, different ways) to cut the map. To be sure all regions have some strategical interest, we ensure that all of them must contain exactly one resource cluster, i.e., a pack of mineral patches, with or without gas geyser around, with some exceptions like islands, areas surrounded by walkable but unbuildable lands, and areas surrounded by areas of different heights but without any resource clusters (which is very rare in practice).

Let’s use the StarCraft 2 map Oxide LE in Fig. 1 to illustrate the different steps of Alg. 3.

At Step 1, Taunt gathers information about the map via the right API, i.e., BWAPI⁴⁴4github.com/bwapi/bwapi for StarCraft 1 maps and CPP-SC2⁵⁵5github.com/cpp-sc2/cpp-sc2 for StarCraft 2 maps. Step 2 uses the same contour tracing algorithm from Chang et al [4], but to compute connected components of walkable lands rather than obstacles like in BWTA2. Although this algorithm is from 2004, a recent survey from He et al [10] indicates that it is still state-of-the-art for computing connected components together with contours.

After Step 3 and 4, we obtain labeled connected components and their contour. The result gives what we can observe in Fig. 2, where green parts are connected components (only one in this map) together with their contour in black.

Step 5 consists in splitting each component of walkable land into separated areas regarding their height and if they are unbuildable or not. In StarCraft 2, unbuildable parts are usually slopes, bridges and woods, and are therefore natural choke points. In StarCraft 1, in addition to slopes and bridges, we can also have large chunks of unbuildable areas, usually located in the central part of the map (see for instance Fig 7(g)). Step 6 computes the contour polygons of these unbuildable areas.

The result of Steps 5 and 6 can be seen in Fig. 3. Blue parts are unbuildable areas. Low, high and very high areas are respectively in yellow, khaki and green.

Since we aim to have exactly one resource cluster per region (with some exceptions listed at the beginning of this section), we need to locate and count clusters on each walkable area. This is done with Step 7, and areas with more than one resource cluster will be handled by Step 8. Only buildable areas are concerned by these steps: since, by definition, players cannot build bases upon unbuildable tiles, there are never resource clusters on unbuildable areas.

In Fig. 4, we can see resource clusters in blue or red boxes. Red dots are the centroid of a cluster, and orange lines connect this centroid to all tiles upon which there is a resource of the cluster.

If there is only one cluster in an area, it is framed by a blue box on the figure. Otherwise, if they are two or more clusters, they are framed by a red box. In that case, if $n$ resource clusters exist on the same area, we need to find $n-1$ separations to make regions containing exactly one cluster each. To do this, we solve a combinatorial optimization problem (Step 8) to find separations satisfying some mandatory constraints and optimizing a giving objective function. We show separations found by solving two combinatorial optimization problems while trying to minimize the total length of separations (Fig. 5), corresponding to choke points, and while trying to minimize the least squares difference of region surfaces (Fig. 6). Separations are represented by red lines.

Once regions have been computed, it is trivial to merge two separated regions by an obstacle if the latter is destroyed, and to run Step 8 on this merged region if making a new separation is required. The way Taunt decides separations area by area, allows us to reanalyze a map locally, without the need to reconsider it as a whole.

We modeled the problem of placing $n-1$ separations in an area containing $n$ resource clusters to make $n$ regions with exactly one resource cluster each, with $n\geq 2$, in a Constraint Programming formalism called Error Function Optimization Problem, or EFOP [11].

An EFOP model is actually an Error Function Satisfaction Problem model, or EFSP, together with an objective function we aim to maximize or minimize. An EFSP model is defined by a set of variables, a set of domains, i.e., the possible values each variable can take, and a set of constraints determining which combinations of variable values are possible or forbidden. Our EFSP model is defined as follows:

• Variables: All possible separations, i.e., all possible pairs of points on the contour polygon of an area,
  Domains: Each variable has the domain $\{0,1\}$, indicating if its corresponding separation is selected or not,
  Constraints:

  1. 1.

     NoCrossings: No separations crossing each other,

  2. 2.

     MaxOneClusterPerRegion: Separations must split the terrain into regions such that each region exactly contains one resource cluster.

In EFSP and EFOP models, constraints are represented as error functions. For the two constraints in our model, their error function is expressed as follows:

• •

  NoCrossings: Number of separations crossing each other.

• •

  MaxOneClusterPerRegion: The highest number of resource clusters on the same region minus 1, added to the number of regions without any clusters.

Having models as small as possible, i.e., with few variables, small domains and few constraints, is important to solve them faster. We have the following tricks to reduce the model size:

• •

  Ill-formed separations, i.e., crossing resources or unwalkable/unbuildable tiles, are filtered out from the set of variables before running the constraint solver.

• •

  Since we know how many separations we must have to get $n$ regions, we randomly select $n-1$ initial separations and ask the solver to handle the problem as a permutation problem. This allows us not to consider a constraint checking the correct number of selected separations.

In order to allow better separations, we enrich the set of variables by adding some points in the contour polygon to break long lines (typically, when the contour contains an edge of the map). Although this increases the model size by adding variables, it may allow nicer separations improving the objective function.

After these variable reduction tricks and this enrichment, we obtain models from some hundreds to 2,000 variables, regarding the map and their areas. The mean numbers of variables among areas within the same maps are given in Table I.

We use this EFSP model for the experiments in this paper. When Taunt will be released, we plan to propose other models with other constraints to offer more diverse analysis possibilities to StarCraft bot authors. For instance, we could add a constraint to force regions to have a minimal surface, or to get perfectly symmetric separations on symmetrical maps.

We get an EFOP model upon this EFSP model by adding an objective function. We have tested two different ones:

• Objective functions:

  1. 1.

     MinSeparationLength: Minimize the sum of separation length.

  2. 2.

     LeastSquaresAreas: Least squares area difference, i.e., minimize the difference of region areas.

The different region-making we got with these two objective functions can be observed in Fig 5 and 6, respectively.

These models have been implemented using the framework GHOST [9], which contains a local search solver to find a solution of the problem within a given timeout. For our experiments presented in Section V, we set a timeout of $n\times 100$ms to find separations in each area containing $n$ resource clusters, with $n\geq 2$. Taunt contains a mechanism that double timeouts and relaunch this solving step if no solutions have been found in its previous run.

Tests have been conducted using a bot under development able to play both at StarCraft 1 and StarCraft 2, on a machine equipped with a Core i9 9900 CPU and 32 GB of RAM, running on Windows 10. Taunt is written in C++ and has been compiled with the Visual Studio 2022 compiler with the /02 optimization option.

The terrain analysis results, namely the region-making and the computation of their contour polygon, are good on all tested maps: Taunt shows its ability to split a map into regions with the desired properties. In order to have a point of comparison with existing libraries and an objective metric for the evaluation of Taunt’s performance, we compare runtimes of BWTA2 and Taunt on StarCraft 1 maps. We choose BWTA2 rather than a more modern library like BWEM, since the latter does not propose features like the computation of contours. BWTA2 is actually the more modern terrain analysis library for StarCraft 1 offering equivalent features as Taunt.

Runtime comparisons are shown in Table II. BWTA2 and Taunt have been run on the same machine through the same bot, under the same conditions. The full run of BWTA2 and Taunt algorithms is measured in milliseconds, including fetching data from APIs and preparing data structures. The reader can observe that the map Destination is not on this table. We have taken out this map from comparisons because it would be completely at the advantage of Taunt, being an unfair comparison with BWTA2. Indeed, Destination is a map such that all walkable areas contain one resource cluster only, so there is nothing to compute for Taunt at Step 8 in Alg. 3, which is the more complex and computation heavy step. This is why we have 0 variables in Table I, and why there are no red separation lines in Fig 7(b). As a result, Destination is processed in 15ms by Taunt, against 843ms by BWTA2.

Results from Table II allow us to conclude that Taunt runs faster over most maps than BWTA2, and has a significant lower median and mean runtime. The standard deviation is almost 4 times higher, though: this is due to the runtime of Step 8 in Alg. 3 that depends on the number of areas to handle and the number of separations to found.

Since there are no terrain analysis library for StarCraft 2 with equivalent features as Taunt, we could not make any runtime comparison on StarCraft 2 maps. Thus, Table III shows runtimes for Taunt only. Like for Table II, runtimes take into account the full run of Taunt’s algorithm, including building inputs and initializing data structures. Looking at medians in Tables II and III, we can conclude that runtimes over StarCraft 1 and StarCraft 2 maps are equivalent. The StarCraft 2 map Romanticide is an exception: it contains 2 areas with 2 separations required for each, and 1 area requiring 5 separations, which is significantly more than the average map. This is the only map where Taunt needed to use its inner mechanism that doubles the timeout and relaunch the solver, since no satisfying separations have been found during the first run of the solver. This explains the difference of runtimes between Romanticide and other StarCraft 2 maps.