A Method for Terrain Analysis

Since BWTA is abandoned and BWAPI regions are too inaccurate, there's no choice but to roll my own map analysis algorithm, or is there?

On a google search, map analysis techniques are few and far between. I eventually stumbled across this thread. The OP, Laccolith, asks for help detecting choke points. He comes up with this solution in the end:

"Step 1: Flood fill from the tiles to their neightbours that have the same walk-ability as it, assigning a shared value, such that comparing the value of 2 tiles will tell whether they are connected. Also count the number of tiles for each connected unwalkable set and if the total is low, I used 172, designate that "region" a small obstacle.

Step 2: Same as your first step, calculate the 8-connected tiles. Though having a cost of 14 when it moves diagonally and 10 otherwise. It also doesn't assign an initial value to those tiles marked as small obstacles in the previous step.

Step 3: Then in a loop, continue until there are no unvisited tiles remaining:

Find the tile with the largest clearance(distance to obstacle) that hasn't been visited yet. Propagate from it tile to it's neighbours in the same way as step 2, though only travel to the 4-connected tiles, using aBrushfire Algorithm to travel through the tiles with a larger clearance first, skipping those already marked as chokepoints. While traveling, store the last tile that had the lowest clearance along the current path.

At each step compare the clearance of the start tile, the clearance of the current tile and the clearance of the lowest clearance tile so far. If certain conditions are met the lowest clearance tile will be marked as a choke point. The check I have so far is if the lowest value is less that 85% of the start tile or 75% of the current tile, then it is a chokepoint. The tiles between the obstacles that form the chokepoint are then marked off in a straight line, and all tiles on the other side of the chokepoint are removed from the current brushfire search. Then the burshfire algorithm continues until it cannot spread to any more tiles due to unwalkable tiles or chokepoint tiles.
The loop then continues, giving you after each step all the tiles that form this Region, the "center" of this region(the original tile) and the chokepoints connected to this region." 

The name Laccolith rings some bells, as I remember a video on youtube with some Protoss armies beating up on Terran. I head over to Skynet's google code page and browse through the source code there. Sure enough, it looks like the same algorithm. His description however, isn't the most understandable. I could grasp more easily what Emergent posted, that we need to find the medial transform of the map. If we could find the lines where tiles are equidistant from impassable tiles, they would form the edges of a graph with vertexes in the center of each region. Of course we would also get a bunch of useless lines going off into corners and even walls, so thresholding is required.

I'll call this approach that was used in Skynet the Medial Line method. The diagram it generates is strikingly similar to BWTA's approach described in Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition. BWTA's method identifies the impassable areas first, then computes a Voronoi diagram between the obstacles. The Voronoi algorithm tries to partition space into cells will walls equidistant to the nearest two objects.  Basically both methods are accomplishing the same thing.

It is far easier to follow BWTA's method as it is well-documented in a paper, but its reliance on CGAL leads to a lot of crashes. Perhaps a re-implementation would be able to handle all maps without crashing. Notice that fig 3A of the BWTA paper showing the raw Voronoi diagram has many useless branches reaching into corners. It occurred to me that the Voronoi algorithm could be modified to account only for comparing the nearest point of each subset, instead of allowing it to find two equidistant points of the same subset. This would solve the branching problem, but needs testing to determine if it would work with concave obstacles.