Starcraft AI blog

Here are details of how zones and chokes are calculated.

Map partitions. This is old work, but I want to mention it for completeness. The partitions data structure is a grid of 8x8 walk tiles that divides the map into connected partitions—you can walk from any point in a partition to any other, while you can’t walk to another partition. The partitions are not used to calculate zones and chokes, but they are related map information.

Inset. The inset is the Manhattan distance of each walkable 8x8 walk tile from the nearest unwalkable walk tile. It’s calculated by a straightforward breadth-first search. The distance is measured in walk tiles. In code, you access inset values with the.inset.at(). The inset is directly useful for a variety of micro decisions, and indirectly useful because you can calculate other information from it.

The inset values take immobile static units into account, such as mineral patches and neutral buildings. There are advantages and disadvantages to the decision.

One idea I have considered: I could calculate negative inset values for distances away from walkable terrain. Then air units would be able to easily find places safe from ground units, such as overlord watch posts. Another idea: I could change the scale of the inset values (the values in the inset grid) from walk tiles (8 pixels across) to pixels. Walk tiles are the least often used scale, and I suppose it’s a cognitive burden to remember that insets are in an unusual scale.

vWalkRoom gives an estimate, for each walk tile, of the room around the tile: How big a thing could fit there, measured in walk tiles. It is calculated from the insets and used to calculate the tile room. The v stands for “vertical” because of the simplified algorithm: It scans down each column of the grid of insets (because of the data structure, it’s more cache-friendly that way), and fills in stretches of walk tiles with the maximum inset in that stretch. A stretch starts at the first walkable walk tile, or after the previous stretch ends. A stretch ends before the last walkable walk tile, or after the inset has been decreasing and starts to increase again. Note that scanning horizontally would often give different numbers! This is a fast and simple algorithm, not an exact one. To get the vWalkRoom, use the.vWalkRoom.at().

tileRoom is nothing more than the vWalkRoom scaled to tiles. Each 32x32 tile is filled in with the maximum vWalkRoom value of the 16 8x8 walk tiles that make it up. The purpose is to reduce the data volume so that zone calculations are fast; zones don’t need higher resolution than this. A disadvantage of scaling to tile size is that connectivity information is lost. Two adjacent tiles A and B might both have positive tile room, even though you can’t walk from one to the other (it does happen sometimes). To find connectivity, use partitions. The tile room is useful for tactical decisions, and for getting an idea of whether a unit or army will fit into a space. Get it with the.tileRoom.at().

Zones are calculated using the tile room. There is no separate data structure for chokes; a choke is simply a zone where isChoke() returns true. The data describing zones consists of a grid of tiles so you can look up the zone ID of any location, and a vector of Zone data structures indexed by the ID. (Keeping IDs in the grid instead of pointers means I can use inheritance of grid classes without needing a template class.)

Zones are calculated from the tile room values with an iterated flood-fill algorithm. The borders of a zone are the tiles at the edge of a walkable area, points where the ground height changes, and points that change from non-choke to choke or vice versa. A tile is (initially) in a choke if its tile room is less than a constant—I use 12 for now, which includes narrow bridges but not wide bridges. This creates a certain number of nonsense zones that then need to be cleaned up: Tiny isolated zones are deleted, tiny zones with only one neighboring zone are merged into the larger zone, and “choke” zones which have only one neighbor are not real chokes and are also merged into the neighbor. That’s about it; all done save minor details.

Here is the public interface of a Zone. Every method and every returned reference is const; once the zone is initialized, nobody is allowed to change it.

	int id() const;
	bool isValid() const;
	bool isChoke() const;
	int groundHeight() const;
	const std::vector<BWAPI::TilePosition> & tiles() const;
	const std::set<Zone *> & neighbors() const;

The id() is a small integer. isValid() is false for zones which were deleted or merged into another zone; the data structure itself is empty but is not deleted, because the zones are indexed by ID (this could be cleaned up if it ever starts to matter). groundHeight() is -1 if the zone has more than one ground height, which can happen after zones are merged, or is the zone’s constant ground height otherwise (actually the low bit is cleared, so that the “doodad” heights are lost). There is a vector of tiles so you can know what’s in the zone without scanning the grid (also used to delete and merge zones), and a set of neighbors so you can work with the map topology.

Overall, Steamhammer’s map analysis is not as polished or complete as BWEM. There are points I want to clean up, and a lot of features are on my list to add—and as I mentioned a couple days ago, I may yet restructure it entirely. As one example of an awkward point, some choke zones are not shaped as you might expect. On Benzene, to illustrate, the down ramp from each main base is next to the geyser and mineral line in the natural, tiles which are also low in tile room. So the choke zone extends down the ramp and then along the resources in the natural. Steamhammer as it stands has no trouble coping with the oddly shaped choke or the oddly truncated natural zone, but I will have to take it into account in new code; it constitutes technical debt.