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.