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.

Analysis Results for SSCAI 2012 Maps

Results from my modified algorithm (based off Skynet). Details here and here. This is the set of maps to be used in the SSCAI competition. I am very happy with the results.

Benzene

Destination

Heartbreak Ridge

Neo Moon Glaive

Tau Cross

Andromeda

Circuit Breaker

Electric Circuit

Empire of the Sun

Icarus

Jade

Judgement Day

La Mancha 1.1

Python

Roadrunner

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.

A Comparison of BWTA and Skynet Map Analysis Algorithms

The pictures are laid out with Skynet's result on the left and BWTA on the right. BWTA has its resolution limited to build tiles instead of walk tiles. It's interface getRegion() function is the cause of this limit by only accepting build tile coordinates.

Orbital Relay
BWTA ignores the useless regions in the center and provides a more consistent division of the inner ring into 3-way intersections and elbows.

Python
BWTA again repeats its more consistent results by partitioning off the top left corner resource area, which Skynet missed.

Tau Cross
Again BWTA's partition of the regions is more logical. Though there is a useless 'appendix' on the bottom right. Importantly, all the resource clusters get their own region. I earlier said that the 3 sausage shaped regions have no defensible places to be split into regions, but creating individual regions around resources is sensible.

Lost Temple
Just as with Skynet, BWTA forgoes the bottom entrance to the center resource point. The results are nearly identical but for the wide choke closing off the bottom of the center resource area and a short passage. I think that BWTA's solution is closer to optimal since the center region does need to be closed off somehow.

BWTA has superior results in this short comparison. It appears that Skynet has missed a few chokes, perhaps the threshold is set too aggressively?