Finding Base Locations

One very useful thing BWTA did was find the Baselocations on the map, places to build resource depots (hatchery, command center, nexus.) However, BWTA would sometimes place the baseloc on a suboptimal spot. The optimal spot to build a depot in every mineral cluster is the location that minimizes the distance to each mineral and vespene geyser. This problem is very easy for a human to solve, and seems to give BWTA-based bots some trouble.

I had a good idea how to solve this problem and I wondered if my solution would run into the same trouble, so I built a baselocation analyzer from scratch. The algorithm has 2 major steps. First I need to group the resources on the map into clusters. Then I can analyze each cluster in isolation and find the optimal spot to place a resource depot. The fact that this problem is trivial for a human to solve by inspection made it easy to   check accuracy by visualizing the data in graphical form.

Grouping resources into clusters

This was actually simple as I had already implemented the DBSCAN algorithm. I still needed to tweak the thresholds, as the previous incarnation was focused on clustering mobile units. I found it necessary to drastically raise the radius to 367 pixels due to a far away geyser in Tau Cross. The number of neighbors threshold I have at 3, and I reject all minerals with fewer than 250 remaining since the map Fortress has a few 249s that are only there to allow workers to pass through the gates into the expansions.

Once I had grouped the resources based on proximity, I had an issue to resolve. On Central Plains the two clusters at 6 o'clock were so close that they got merged into a single cluster. I separated such bridged clusters by ensuring that all resources in each cluster belonged to the same region. Thus it is important to tackle regions and choke points before base locations.

Finding Optimal Depot Positions

Now that the large set of resources has been segmented into smaller localized clusters, I am able to tackle each cluster in isolation. For each resource unit, I generated a potential field that decayed with distance. Resource depots cannot be built within 3 build tiles of resource units, so I generated a second field that wiped out the first within a radius of 3.

Now that I had the potential fields set up, all I had to do was sweep an area around each cluster and select the spot with highest potential, which would be where the summed field concentration is greatest. Since all resource depots are 4x3 build tiles in footprint, I checked the footprint to be sure that it was outside the 3-tile limit radius and also that it was on buildable terrain. For this case, walkability == buildabiliity. I initially tried to use BWAPI's isBuildable(x,y) function, but it seemed to take unexplored tiles as unbuildable, and I only wanted to work with static map data, so I ended up using isWalkable(x,y).

Results

The algorithm produced excellent results right away with no additional tuning required. Here are the images of detected base locations and the potential field overlaid onto the image of the map regions. I tested each map in the SSCAI 2012 tournament.

Benzene

Destination

Heartbreak Ridge

Neo Moon Glaive

Tau Cross

Andromeda

Circuit Breaker

Electric Circuit

Empire of the Sun

Icarus

Jade

Judgement Day

Python

Roadrunner

So far this algorithm has placed the base location in the optimal spot for each map that I have tested.

Choke Detection Tweaks

A statement I made earlier was incorrect: Skynet's algorithm does not find all regions first as BWTA does. Instead, it alternates, finding a region, then determining the limits of that region by closing it off with chokepoints. Thus the order of forming regions matters and will affect where the choke points are found. Skynet starts with the largest region and works its way down.

Two thresholds control the chokepoint detection process. The regionThreshold, originally set at 0.9, eliminates chokepoints that are too wide compared to the parent region. The tileThreshold controls how quickly the choke must widen out. It was originally 0.8, but changing it to 0.91 greatly improves accuracy over my map sample set.

 Orbital Relay is not shown since it remains identical.

 Python's top left resource area is now detected thanks to the bump to 0.91.

 Many changes in Tau Cross. The importance of the additional regions is that all resources are now partitioned into their own regions. I believe that this is important for strategic purposes.

Lost temple's center area is now cordoned off, which is the important part. It now looks similar to BWTA's output, but has extra regions. BWTA has an extra step in which it merges small regions together. I don't think it is necessary, since the AI should be able to deal with having extra regions. In any case, it is better to have too many divisions than too few.

Choke Detection Depends on Region Detection

I know why chokes are missing in Skynet's analysis. The algorithm finds regions first, then tries to narrow down where to choke should go between regions. The missing chokes are from missing regions - compared to BWTA's results.

These images are visualizations constructed by taking the number of adjacent tiles that have a different nearest obstacle. The colors start off deep blue for 0 and move up towards red. Pink circles are drawn at detected region centers. Compare these images with the chokes detected in my last post.

 You can see from the Orbital relay image that there are only 4 regions in the center ring, hence only 4 choke points dividing it, while BWTA must have found 8 regions.

 On Python it is apparent that the top left region has not been detected, explaining the lack of a choke there.

 On Tau Cross we see that there can be a choke point for every land path between two adjacent regions.

The lack of a bottom choke in the center area of Lost Temple is due to there only being one region center detected at the very bottom instead of in the middle intersection area. The algorithm decided to place the single choke a bit further south of the bottom entrance.

Adjusting the thresholds for what is considered a region will probably fix this issue. I am going to try to match BWTA's output.

Map Analysis - What Would Skynet Do?

In my last article, I wrote that BWTA and Skynet's map analysis methods are essentially the same. Both try to find the medial lines between obstructions. The clearance along the medial lines may then be used to detect choke points. Local minima tend to indicate chokes, while local maxima indicate the centers of large regions.

The first steps for each are very much the same: flood-fill the map to determine connectivity and find obstacles, then determine the medial lines between impassable areas. The execution of these concepts differs. BWTA vectorizes everything by turning connected regions into polygons, then using the CGAL library to calculate the Voronoi diagram between the obstacle polygons. The approach unfortunately is slow and crashes on too many maps. However BWTA does deliver excellent results when it works. The algorithm used in Skynet is discrete and performs its calculations directly on the map tiles. I am going to implement it and see how it compares to BWTA.

The flood-fill algorithm is easy to explain. Pick a tile, then assign it and all connected tiles a number. Repeat for any unvisited tiles, and you end up with every tile on the map labeled with its connectivity number. From any tile you can reach any other tile with the same number. I visualized this by assigning each number a separate color and by drawing an image where each pixel corresponds to a tile.

Next step is to generate a clearance map. Assign for each tile a number that represents the distance it is away from any obstacle. This can be done by setting each tile that borders an obstacle a distance of 1 tile, then propagating to adjacent tiles, adding 1 each iteration. Skynet's algorithm ignores all small obstacles from this calculation and counts distance in tenths of a tile, so two directly adjacent tiles would be 10 apart. This is so that diagonal tiles may be 14 apart. It also keeps track of where the nearest obstacle tile is from each tile, which will be important later on to find the medial lines.

I visually represent the clearance map using a heatmap. Blue indicates close proximity to obstacles, while tiles with greater clearance turn green, then red for the centers of regions. Blue shapes in the interior of regions are the small obstacles ignored in the clearance calculation.

I start by using the Orbital Relay map because its clean lines and symmetry make it easier to spot any anomalies. At the top is the connectivity map and the clearance heatmap is on the bottom. It is easy to understand why the built-in analysis accessed through BWAPI regions classifies all of the center ring as a large chokepoint.

This is Lost Temple from the ICCup map pack. The chokes from the main bases may be clearly seen as fine threads.

 Tau Cross is going to be a hard one for algorithms to get right. There may be false chokes detected along the 3 long narrow areas in the middle.

 Python is the only one I tested where it is difficult to pick out the ramps to the main bases that can clearly be seen on the top connectivity map. It may be that the extremely large central region shifted the rest of the map closer to blue. Python should be another challenge to map analysis algorithms. I only want to find 8 chokes on this map, 1 for each main and natural. The NW and SE areas are too wide to be called chokes. The mouths leading to each natural are about as wide as choke points can get.

Visualizing Map Information

When working with terrain analysis it is important to be able to verify what the algorithm is doing. I have found the best way to do so is by presenting data visually. Using the CIMG library, it is easy to render map information to a bitmap file and then save the image to disk.

CIMG is a header only library and requires only a single include:

#include "CImg.h"

using namespace cimg_library;

To create an image, instantiate the CImg class:

CImg<unsigned char> img(mMapWidth, mMapHeight, 1, 3); 

 The first two parameters in the constructor are the width and height of the image. 1 and 3 are for z-buffer and number of color channels.

Next, to fill the image, iterate over the map data and call the draw_point method:

img.draw_point(x,y,pointColor,1);

The last 1 there is for opacity. Color is represented by an array of unsigned chars as so:

unsigned char pointColor[3];

unsigned char black[] = {0,0,0};

unsigned char white[] = {255,255,255};

When finished, simply call the output function to save:

img.save_bmp(bmp_name.c_str());

Here bmp_name is a string value containing the filename. Don't forget to add '.bmp' extension. Note that it only takes c-style strings. It isn't possible to specify a directory to save the file under, so for a BWAPI-module the image files will appear in your Starcraft root directory.

This is an image I generated using walkability data from the Orbital Relay map.

A Method for Terrain Analysis

Since BWTA is abandoned and BWAPI regions are too inaccurate, there's no choice but to roll my own map analysis algorithm, or is there?

On a google search, map analysis techniques are few and far between. I eventually stumbled across this thread. The OP, Laccolith, asks for help detecting choke points. He comes up with this solution in the end:

"Step 1: Flood fill from the tiles to their neightbours that have the same walk-ability as it, assigning a shared value, such that comparing the value of 2 tiles will tell whether they are connected. Also count the number of tiles for each connected unwalkable set and if the total is low, I used 172, designate that "region" a small obstacle.

Step 2: Same as your first step, calculate the 8-connected tiles. Though having a cost of 14 when it moves diagonally and 10 otherwise. It also doesn't assign an initial value to those tiles marked as small obstacles in the previous step.

Step 3: Then in a loop, continue until there are no unvisited tiles remaining:

Find the tile with the largest clearance(distance to obstacle) that hasn't been visited yet. Propagate from it tile to it's neighbours in the same way as step 2, though only travel to the 4-connected tiles, using aBrushfire Algorithm to travel through the tiles with a larger clearance first, skipping those already marked as chokepoints. While traveling, store the last tile that had the lowest clearance along the current path.

At each step compare the clearance of the start tile, the clearance of the current tile and the clearance of the lowest clearance tile so far. If certain conditions are met the lowest clearance tile will be marked as a choke point. The check I have so far is if the lowest value is less that 85% of the start tile or 75% of the current tile, then it is a chokepoint. The tiles between the obstacles that form the chokepoint are then marked off in a straight line, and all tiles on the other side of the chokepoint are removed from the current brushfire search. Then the burshfire algorithm continues until it cannot spread to any more tiles due to unwalkable tiles or chokepoint tiles.
The loop then continues, giving you after each step all the tiles that form this Region, the "center" of this region(the original tile) and the chokepoints connected to this region." 

The name Laccolith rings some bells, as I remember a video on youtube with some Protoss armies beating up on Terran. I head over to Skynet's google code page and browse through the source code there. Sure enough, it looks like the same algorithm. His description however, isn't the most understandable. I could grasp more easily what Emergent posted, that we need to find the medial transform of the map. If we could find the lines where tiles are equidistant from impassable tiles, they would form the edges of a graph with vertexes in the center of each region. Of course we would also get a bunch of useless lines going off into corners and even walls, so thresholding is required.

I'll call this approach that was used in Skynet the Medial Line method. The diagram it generates is strikingly similar to BWTA's approach described in Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition. BWTA's method identifies the impassable areas first, then computes a Voronoi diagram between the obstacles. The Voronoi algorithm tries to partition space into cells will walls equidistant to the nearest two objects.  Basically both methods are accomplishing the same thing.

It is far easier to follow BWTA's method as it is well-documented in a paper, but its reliance on CGAL leads to a lot of crashes. Perhaps a re-implementation would be able to handle all maps without crashing. Notice that fig 3A of the BWTA paper showing the raw Voronoi diagram has many useless branches reaching into corners. It occurred to me that the Voronoi algorithm could be modified to account only for comparing the nearest point of each subset, instead of allowing it to find two equidistant points of the same subset. This would solve the branching problem, but needs testing to determine if it would work with concave obstacles.

DBSCAN Drawbacks

After testing, it appears that the DBSCAN algorithm has a number of disadvantages that must be overcome in order for it to be used as a group detector for a BWAPI bot. These are what I consider to be the four major drawbacks in no particular order:


1. Instability

The assigned group IDs will often jump around, when groups merge and split, following no particular pattern. Grouping results depend entirely on unit traversal order, so when a small group splits off from a larger one,  sometimes the algorithm counter-intuitively assigns the original ID to the smaller group, rather than keeping it with the larger one. 

This instability means that we cannot simply store a groupID somewhere and come back later to check on our group. The ID could refer to the same group, but it might also point somewhere else, or become unused.

2. Performance
As I mentioned earlier, DBSCAN is too slow to run in debug mode, forcing testing to take place in release mode. The only solution appears to be running it in its own thread, which complicates matters with synchronization. It won't be easy to divide the workload among several frames, as the algorithm wants to be run all in one shot. Speed also degrades rapidly with the number of units in the game, even if most of them are not moving.

3. Inaccuracy
Uses a single radius value for all units; but not all units are equal. Longer-range units should have a larger associative area around them representing the ability to project power, while melee units would have a reduced radius. Unfortunately, the algorithm uses a single radius for all units, and this must be modified to fix the issue.

4. Association
Assume I grab the nearest unit and find out it belongs to group 5. How then can I access all units of group 5? I must iterate through entire set of units. This is probably the most minor of flaws, but creating additional associative sets for faster access is difficult due to ID instability.

Another Approach: Associative Network Clustering
If each unit were to have its own radius of influence, and keep track of the other units within, this would form a graph. We then have the option of using existing graph algorithms on the data. Also, the graph can be updated locally, no need to recompute the whole thing if a single vertex changes; just update its links. This approach allows easy association, higher accuracy, and greater performance, but I have yet to figure out how to get stable IDs.

A Look at DBSCAN Clustering

Finished implementing unit clustering based on the DBSCAN algorithm with parameters set:
threshold=3, and radius=6. Units with more than 3 neighbors in a radius of 6 tiles will be considered a cluster. The following screenshots will illustrate the mechanics of this algorithm.

Probe scout left, encounters clustered SCVS among mineral field.

An example of an early game scouting action. The scout is assigned to group 0, no cluster, since it is alone. The SCVs are in sufficient density to be assigned group 2.

Two SCVs and a Marine guard this ramp.

I have the parameters set so that it takes three units in close proximity to form a cluster. These units at the ramp are assigned group 15; separate from the mining cluster back at the Command Center.

A Protoss army on the move.

All the units in the army manage to get clustered into the same group, along with the Probe that is just passing through. The algorithm reacts instantaneously to unit movement since I have it run every frame. This unfortunately slows debug mode down to a crawl on a quad core AMD Phenom II 955 @ 3.4GHz, but performance is fine compiled in release mode. I have an idea to speed performance, but if continuous processing is required, this algorithm should be run in a separate thread.

A group of stragglers behind the army.

Catching up to the rest of the army.

This sequence shows the proximity needed to be considered part of the same cluster, 6 tiles as configured.

A construction SCV forms bridge between tanks left and workers right.

One shortcoming of the DBSCAN algorithm is that it sometimes allows a single unit to form a bridge, linking two clusters together. In the above shot, the tanks on the left should have their own group, but thanks to the SCV bridge in the center, are considered part of the same cluster as the mining SCVs on the right.

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.