Grouping Units

“It is the rule in war, if our forces are ten to the enemy’s one, to surround him; if five to one, to attack him...
If equally matched, we can offer battle; if slightly inferior in numbers, we can avoid the enemy; if unequal in every way, we can flee from him.” – Sun Tzu

Suppose that you have a squad of units engage the enemy. What are the relative strengths involved? In situations involving ranged units, Lanchester’s Square Law is in effect, magnifying imbalances.

1. Your squad is much stronger than the enemy. You win, taking small losses.
2. Your squad is much weaker than the enemy. You lose the squad, dealing minor damage in return.
3. The squads are closely matched. One side wins, while the other takes heavy losses.

Clearly the first situation is most desirable, and we want to avoid the second. In many bot matches, I’ve seen small groups of units thrown away by attacking a plainly superior force. If the bot can detect such a situation, it can eliminate these obvious mistakes. Now the problem is, how do we detect these relative strengths?

Naïve solutions:

I. Evaluate the strengths of enemy units within a certain radius of the centroid of our squad.

Suggested by the method getUnitsInRadius(), this works well in some cases, mostly when there are few units that all have similar range and small collision areas. Problems occur when long range units such as Seige Tanks are considered. If we don’t extend detection radius, then our squad members further away from squad center can be attacked without detecting the Seige Tank. If we extend detection radius however, incorporating a squad bounding circle radius for example, the algorithm will often over-estimate enemy strength, due to shorter range enemy troops being counted.

II. Evaluate the strengths of enemy units currently engaged with our squad, defined as attacking or being attacked.

This solution is suggested by getTarget() and getOrderTarget(), but we would like to identify an ugly situation before getting stuck in combat.

Neither of these methods can deal with the “tip of the iceberg” scenario, where our squad encounters one end of a large army that sprawls past the detection radius. We want to recognize concentrations of enemy troops that are usually controlled by bot and human players alike as squads. If one part of a squad is under attack, the rest are likely to assist them.

Now we need an algorithm that can assign enemy units to groups by proximity.

Enter Clustering


There exists a category of clustering algorithms, which are designed to assign a set of data points into groups. These often are designed to work with 2D data, such as unit positions on a map.

Density-based clustering is what we want. Points in areas of high density are assigned to clusters, while objects in sparse areas are considered outliers.

The most popular density-based clustering method is DBSCAN. The algorithm requires two parameters to be defined: a search radius, and the minimum number (threshold) of units needed to form a group.

The algorithm chooses a unit that hasn’t been visited. If there are not enough units in the search radius, label the unit as not part of a group.

If there are enough units in the search radius, start a group and add all the other units in the radius to that group, then visit each unvisited unit in the radius.

When there are no more unvisited units in the group, start over with an unvisited unit. This repeats until all units have been visited.

Now the only difficult part is deciding on values for radius and threshold.

To find suitable values, I am going to load up some replays using different values to experiment and see which combination will be the most effective at identifying groups, compared to human intuition.

BWAPI Regions

The newer versions of BWAPI provide access to internal Broodwar map region information.
As the API reference states:
“The Region class provides access to some of Broodwar's pathing information and offers members that can assist in navigation, scouting, construction, and information for key areas such as chokepoints. Though not always accurate, it is a lightweight alternative to BWTA that beginners can start with.
These regions are not so advanced as to cover everything up to a choke point with accurate polygons, but instead are small clusters of tiles connected to each other, kind of like a honeycomb.”

This could provide a more stable alternative to BWTA, which crashes on maps like Lost Temple.
I wrote this code to draw boxes around and print information about each region.

set<Region*> allRegions = Broodwar->getAllRegions();
BOOST_FOREACH(Region* bwRegion, allRegions)
{
    Broodwar->drawBoxMap(bwRegion->getBoundsLeft(), bwRegion->getBoundsTop(),
        bwRegion->getBoundsRight(), bwRegion->getBoundsBottom(), Colors::Yellow);
    Broodwar->drawTextMap(bwRegion->getCenter().x(),bwRegion->getCenter().y(),
        "Region [%d,%d] %d", bwRegion->getRegionGroupID(), bwRegion->getID()
        ,bwRegion->getDefensePriority());
}

Region->getDefensePriority() seems to indicate if the region is a choke, and how many other regions it branches into.

A BWAPI Region will commonly be placed around clumps of minerals.

As shown in these screenshots, a DefensePriority value of 0 indicates a normal region that makes up a larger area.

This narrow intersection is divided into multiple Regions: one ‘3’ intersection and multiple 2’s.

 
A DefensePriority value of 2 indicates a bridge-type choke between two areas, and 3 is for a T-intersection choke. I have not seen any values of 4, but they may appear for a 4-way intersection.

This region just south of a mineral cluster is falsely identified as a chokepoint. BWAPI regions are usually created around any impassable doodads, and given their own Group IDs.

The two doodads on the right have been clumped together into an impassable region. The impassable space tiles are also partitioned into a region group.

Another look at a 3-way intersection

The downside of BWAPI regions is the large amount of nesting and overlap occurring. However, it is interesting that impassable space and water tiles get their own regions, unlike BWTA regions.
On the upside, it should be safe to assume that every tile is covered with at least one BWAPI region. In contrast, BWTA Regions do not include impassable groups or choke points between two adjacent regions, returning a NULL pointer for getRegion().