Map Analysis - What Would Skynet Do?

In my last article, I wrote that BWTA and Skynet's map analysis methods are essentially the same. Both try to find the medial lines between obstructions. The clearance along the medial lines may then be used to detect choke points. Local minima tend to indicate chokes, while local maxima indicate the centers of large regions.

The first steps for each are very much the same: flood-fill the map to determine connectivity and find obstacles, then determine the medial lines between impassable areas. The execution of these concepts differs. BWTA vectorizes everything by turning connected regions into polygons, then using the CGAL library to calculate the Voronoi diagram between the obstacle polygons. The approach unfortunately is slow and crashes on too many maps. However BWTA does deliver excellent results when it works. The algorithm used in Skynet is discrete and performs its calculations directly on the map tiles. I am going to implement it and see how it compares to BWTA.

The flood-fill algorithm is easy to explain. Pick a tile, then assign it and all connected tiles a number. Repeat for any unvisited tiles, and you end up with every tile on the map labeled with its connectivity number. From any tile you can reach any other tile with the same number. I visualized this by assigning each number a separate color and by drawing an image where each pixel corresponds to a tile.

Next step is to generate a clearance map. Assign for each tile a number that represents the distance it is away from any obstacle. This can be done by setting each tile that borders an obstacle a distance of 1 tile, then propagating to adjacent tiles, adding 1 each iteration. Skynet's algorithm ignores all small obstacles from this calculation and counts distance in tenths of a tile, so two directly adjacent tiles would be 10 apart. This is so that diagonal tiles may be 14 apart. It also keeps track of where the nearest obstacle tile is from each tile, which will be important later on to find the medial lines.

I visually represent the clearance map using a heatmap. Blue indicates close proximity to obstacles, while tiles with greater clearance turn green, then red for the centers of regions. Blue shapes in the interior of regions are the small obstacles ignored in the clearance calculation.

I start by using the Orbital Relay map because its clean lines and symmetry make it easier to spot any anomalies. At the top is the connectivity map and the clearance heatmap is on the bottom. It is easy to understand why the built-in analysis accessed through BWAPI regions classifies all of the center ring as a large chokepoint.

This is Lost Temple from the ICCup map pack. The chokes from the main bases may be clearly seen as fine threads.

 Tau Cross is going to be a hard one for algorithms to get right. There may be false chokes detected along the 3 long narrow areas in the middle.

 Python is the only one I tested where it is difficult to pick out the ramps to the main bases that can clearly be seen on the top connectivity map. It may be that the extremely large central region shifted the rest of the map closer to blue. Python should be another challenge to map analysis algorithms. I only want to find 8 chokes on this map, 1 for each main and natural. The NW and SE areas are too wide to be called chokes. The mouths leading to each natural are about as wide as choke points can get.