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.