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?

First Look at Choke Detection Visualization

These are the results of step 3 in the map analysis algorithm used by the Skynet bot. Regions have been identified, largest first, by spreading out from local maxima until choke points are detected. In these images generated with CIMG, each region is assigned a separate color. Terrain not part of any region (impassable) is black. Centers of chokes are white circles, while a line is drawn between the two sides of the choke. It seems that the sides of the chokes are found by increasing radius search from the center until an impassable tile is found. The vector is then traced to the opposite direction until it finds the far side.

First up is Orbital Relay. The center ring has been broken up into 4 separate regions, and the choke lines are slanted to the human eye, but this could be a trick of the tile geometry.

Lost Temple's center area is missing a southern choke. Perhaps it is too wide, though I had thought the north and south entrances identical in width.

On Tau Cross, there is a division that cuts the northwest 'sausage' in half. Many humans would not have marked it as a choke, but it's not a significant impact on gameplay. Why is the northern green part sectioned off, when the protrusions of the south are not? It can be seen in the southwest the little tiny colored dots assigned to minuscule regions. Perhaps these insignificant areas should be ignored.

Python is dominated by a large central region. The northwest and southeast have resource clusters, so it might be wise to create separate regions, but their 'chokes' are indefensible. In this case we see what appears to be a thresholding issue, where the NW has no choke, but one is detected in the SE.

Skynet's terrain analysis package has done an acceptable job on these maps. Next time it will be directly compared against BWTA.

BWAPI regions for map analysis

BWTA is trash as far as I'm concerned. It crashes on every other map, including single player maps, and takes forever to analyze new maps. Even loading data from analyzed maps takes more than a few seconds. Such slow and unreliable performance is unforgivable. Apparently it is not good enough for competitive starcraft AI, as both Skynet and UAlbertabot roll their own solutions to map analysis.

Before I take the time to develop a full-blown map analysis algorithm, I'm going to take a second look at BWAPI's regions to determine if it is possible to build it up to a reasonable mapping solution. Lets take a look at what a map analysis package should provide.

Map Feature Detection:

1. Connectivity - can I walk from point A to point B? Separate the map into islands, for pathing.
2. Base locations - find resource clusters and get good spots to place a resource building.
3. Choke points - ideal defensive locations.
4. Regions - choke points segment the map into these areas. Useless in maps such as Python with large central plains.

Of these features, BWAPI regions already handles connectivity via RegionGroupIDs. I am also not that interested in base locations as it clearly was a secondary add-on in BWTA. The meat of BWTA was its method of using CGAL to create a Voronoi Diagram from map data. It could then use some filtering to determine chokes, then segment the map into Regions. My first objective is to see if it is possible to use the region class built into BWAPI to detect choke points.

Choke Point Detection with BWAPI Regions

For the initial survey I am using the Orbital Relay map. I have written code that will display the outlines of regions as well as their ID and DefensePriority. The key to finding chokepoints is the DefensePriority property. This is determined by internal Starcraft logic that tries to find good spots to defend. Presumably the built-in Starcraft AI would send its units to guard regions with high DefensePriority.

For the following screenshots I have modified my code to only display regions with DefensePriority greater than 0.

This region is off-center of the chokepoint, and there are no other high DefensePriority regions around it. The problem here is that the bot has no way to know the region is off-center, so it will defend poorly against attacks coming from the south

These two pictures show more usable results. There is a small region that is centered on the bridges.

A rare DefensePriority of 3 indicates that Starcraft has detected a 3-way choke.

Another 3-way choke. Note the ring with 4 bridges in the center of the map. The region where the bridge touches the ring should be detected as a '3' in every case, but only 2 are shown as 3-way. A 50% detection rate isn't very good.

This is interesting. The algorithm seems to calculate the width of a passage and denotes choke points if the clearance is below a certain value. The ring in the middle of the map is narrow enough that all the regions along the ring are marked with '2'.

Why are these impassable space tiles marked? It could be that the algorithm didn't check to see if the entire region was passable. A simple check should filter these false positives out.

The real trouble seems to be here, with these false positives detected on platform corners. This may be because the impassable doodads fooled the algorithm by reducing clearance, or creating multiple narrow paths around the corner. Unless the computer is predicting an ideal landing point, these false positives are useless. They may be partially filtered out by checking for impassibility. 

With a bit of filtering, native BWAPI regions could be used to create a passable terrain analyzer. However, accuracy is poor at times and useless regions probably will slip through the filters to be classified as chokepoints. 

BWAPI Regions

The newer versions of BWAPI provide access to internal Broodwar map region information.
As the API reference states:
“The Region class provides access to some of Broodwar's pathing information and offers members that can assist in navigation, scouting, construction, and information for key areas such as chokepoints. Though not always accurate, it is a lightweight alternative to BWTA that beginners can start with.
These regions are not so advanced as to cover everything up to a choke point with accurate polygons, but instead are small clusters of tiles connected to each other, kind of like a honeycomb.”

This could provide a more stable alternative to BWTA, which crashes on maps like Lost Temple.
I wrote this code to draw boxes around and print information about each region.

set<Region*> allRegions = Broodwar->getAllRegions();
BOOST_FOREACH(Region* bwRegion, allRegions)
{
    Broodwar->drawBoxMap(bwRegion->getBoundsLeft(), bwRegion->getBoundsTop(),
        bwRegion->getBoundsRight(), bwRegion->getBoundsBottom(), Colors::Yellow);
    Broodwar->drawTextMap(bwRegion->getCenter().x(),bwRegion->getCenter().y(),
        "Region [%d,%d] %d", bwRegion->getRegionGroupID(), bwRegion->getID()
        ,bwRegion->getDefensePriority());
}

Region->getDefensePriority() seems to indicate if the region is a choke, and how many other regions it branches into.

A BWAPI Region will commonly be placed around clumps of minerals.

As shown in these screenshots, a DefensePriority value of 0 indicates a normal region that makes up a larger area.

This narrow intersection is divided into multiple Regions: one ‘3’ intersection and multiple 2’s.

 
A DefensePriority value of 2 indicates a bridge-type choke between two areas, and 3 is for a T-intersection choke. I have not seen any values of 4, but they may appear for a 4-way intersection.

This region just south of a mineral cluster is falsely identified as a chokepoint. BWAPI regions are usually created around any impassable doodads, and given their own Group IDs.

The two doodads on the right have been clumped together into an impassable region. The impassable space tiles are also partitioned into a region group.

Another look at a 3-way intersection

The downside of BWAPI regions is the large amount of nesting and overlap occurring. However, it is interesting that impassable space and water tiles get their own regions, unlike BWTA regions.
On the upside, it should be safe to assume that every tile is covered with at least one BWAPI region. In contrast, BWTA Regions do not include impassable groups or choke points between two adjacent regions, returning a NULL pointer for getRegion().