Compulsive Research: 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.