The meaning behind BWAPI region priority

It occurred to me after viewing this image how the Broodwar built-in region priority system works.

In this visualization, the yellow colored regions have a priority of 2, and the blue ones are priority 3. There are no dividing lines between the yellow regions, just note that the larger ones are actually made up of multiples.

Priority works just like the number in Minesweeper: it is the number of distinct impassable terrain areas that a region touches. That is why there are random yellow regions everywhere in this map, as there many little doodads scattered around that will make a region in the middle of a clear area have priority of 2. The built-in analysis system thinks that it is a choke.

Unfortunately this discovery means that the BWAPI regions are not very valuable for choke detection. They are still a good alternative to implementing a map-grid system, as they are approximately grid-like, but conform to impassable regions so you won't have a grid square which is split by a cliff.

La Mancha

Now I finally see why the map is named La Mancha.

That is clearly a windmill in the center of the map!

Worker Payoff Time

In Broodwar, you spend 50 minerals to train a worker. How long does it take the increased mining speed from that additional worker to pay back the investment.

We need to account for the build time of the worker, as well as the time required for it to mine 50 minerals.

Here is the equation


According to BWAPI, SCVs take 300 frames to make:


Workers in BW gather at ~1 mineral/second, so as on fastest there are 24 frames a second:


The cost of a worker is 50 minerals


Finally we get


So from this math it takes 1550 frames, or about 65 seconds on fastest for a worker to be built and then make back its cost. In a build order that is trying to reach a certain amount of minerals the fastest, it would be optimal to stop building workers about a minute before completion.

The following are simulation results for time to gather 1000 minerals starting with 1 worker, and controlling the number of workers built. The fastest time was with 10 workers built, 11 in total.

INFO: pred: 22223, cur: 0 work_time:22223
simulated 0 worker time: 22223
INFO: pred: 12373, cur: 1412 work_time:10961
simulated 1 worker time: 12373
INFO: pred: 9325, cur: 2118 work_time:7207
simulated 2 worker time: 9325
INFO: pred: 7919, cur: 2588 work_time:5331
simulated 3 worker time: 7919
INFO: pred: 7146, cur: 2941 work_time:4205
simulated 4 worker time: 7146
INFO: pred: 6680, cur: 3241 work_time:3439
simulated 5 worker time: 6680
INFO: pred: 6390, cur: 3541 work_time:2849
simulated 6 worker time: 6390
INFO: pred: 6211, cur: 3841 work_time:2370
simulated 7 worker time: 6211
INFO: pred: 6104, cur: 4141 work_time:1963
simulated 8 worker time: 6104
INFO: pred: 6049, cur: 4441 work_time:1608
simulated 9 worker time: 6049
INFO: pred: 6031, cur: 4741 work_time:1290
simulated 10 worker time: 6031

The final work time of 1290 frames, adding the 300 for train time, yields 1590, just above the cutoff for breakeven time to build a worker. Building another worker after that time resulted in a longer time to reach the mineral goal of 1000.

instanceof for C++: typeid

Always be certain that pointers are dereferenced when using typeid. It can be a common error, and the compiler won't give any warning.

Variations in SCV harvesting rate

SCVs harvest the slowest of all workers because they have the lowest acceleration. However, sometimes they don't need to accelerate and seem to jump to max speed. This happens on certain minerals, depending on how they are placed on the map in relation to the command center. 

I observed this effect when I was trying to  measure how many SCVs can mine a mineral for maximum efficiency. I defined idle time for each mineral as any frame an SCV is travelling and not harvesting from it. Dividing by the total time gives the idle ratio. As seen below, the ratios for 1 SCV per patch is about 0.5, so in theory 2 SCVs can mine from each patch at full efficiency. 

Take note of the top 2 mineral patches. They both have had only one SCV (the 10th extra SCV stays around the bottom) for a while, and have stabilized to different idle values. The top one spends 48% idle, while the one under it is 55% idle. The SCV that mines the top patch is consistently moving faster than the SCV directly below it.

If we assume the difference is from the top SCV not having to accelerate, and that it is possible to micro the SCVs to move faster in mining, then 2 SCVs per patch should achieve perfect efficiency.

Where do SCVs go inside refineries?

SCV just before it enters the refinery. Its order is 'MoveToGas'.

SCV inside refinery. Notice the info panel is still being drawn in the same place. Its order is now 'HarvestGas'.

The refinery info panel, with SCV inside. BWAPI does not return any units loaded inside the refinery, or else it would have shown up on the info panel.

SCV as it leaves the refinery. Its order is now 'ReturnGas'.

I now believe that the SCV simply turns invisible while it is harvesting gas. Maybe it is also invincible. BWAPI's Unit::getLoadedUnits() cannot be used here as it returns no loaded units. The only way to check for SCVs inside refineries seems to be to see if the Order status is 'HarvestGas'. BWAPI documentation notes that Game::getAllUnits() does not include units inside refineries so the pointer to the SCVs must be saved before they enter.

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.