Starcraft AI blog

Suppose you want to place static defense, or immobile defense like sieged tanks or burrowed lurkers, to guard your natural. Or maybe you want to place spider mines, or other scout units, in a picket line to spot movement. Where should you put your stuff? Well, it depends on the terrain and on what you are guarding against. To protect against ground attacks on the natural base, you normally want defenses which cover the choke. Many bots do it directly: Here is the base, there is the choke, set defenses in between.

In the general case, you want to analyze the paths your opponent must take, or is likely to take. If you can place defenses to cover every approach (out to beyond the enemy’s range of fire), then an attack must engage the defenses before it can reach the defended place—stand and fight, or siege them down from range, or run by while taking damage, no matter what there will be shooting.

This is true even against air units. If a pro terran suspects a drop early in the game, they may build 2 turrets widely spaced across the main (leaving most of the army in the natural for all contingencies). The turrets don’t close down every path, and the drop can still happen, but they make life difficult for the shuttle. The drop might come in at any angle and protoss may try to be tricky, but protoss has to find the turrets and either try to thread through (risky) or stop to take one out (slow). Bots are not sharp enough at defense to get by with so few turrets, but can still obey the principle that follows from path analysis: To defend against a drop with a small number of transports, widely spaced turrets do the most to limit the enemy freedom of action.

Compare late game defense against arbiter recall. The arbiter cannot come in at just any angle—there’s a big terran army in position to catch it! And at this stage in the game terran has the minerals to afford fences of turrets across any vulnerable approaches to a mineral line—covering the direct paths. In addition, depending on the terrain, many terrans will build turrets right up against the edge of the map to guard against the arbiter sliding in along the edge where the army won’t see it. That is an example of covering the likely path.

Path analysis can also tell where it may make sense to place pylon walls. I would love to be able to automatically discover the possibility of pylon walls to protect the mineral line at the mineral only bases on Circuit Breaker. Pylons there between the nexus and cliff can keep vultures far enough away that the probes can evade some of their fire.

The advantage of path analysis over choke analysis is that it is more general. It automatically covers all cases. You don’t need special case code to figure out how to defend your natural on Moon Glaive, which has 2 entrances, or to defend a mineral only on Python, which is not behind a choke at all. You don’t have to calculate separately whether a photon cannon’s range is enough to cover a wide choke, or leaves a path open; the analysis tells you. If there is a backdoor entrance, you don’t have to go looking for it, a thorough path analysis will remind you. But how do you do the analysis?

shortest path method

Steamhammer inherited distance maps from UAlbertaBot (originally DistanceMap, more recently renamed GridDistances). UAlbertaBot may have borrowed the idea from Skynet—nothing new here, and I’m sure many bots use this idea. Anyway, the algorithm is trivial: Specify a tile as the start, and give it distance 0. Tiles adjacent to 0 get distance 1, tiles adjacent to 1 (and not already marked) get distance 2, and so on. If you only mark walkable tiles, then you get something reasonably close to a map saying how far away everything is by ground from the start tile.

You can use the distance map to effortlessly find shortest ground paths either to or from the start tile. It’s efficient if you find many paths to or from a specific place (such as a base you want to defend or attack). In fact, it’s more general: In principle, you can specify any subset of tiles as start tiles, even tiles that are far away from each other. Specify the set of tiles where your workers are, and you find shortest paths to any part of your mineral line, for example. You can also use tricks like adding fake extra distance to tiles which are under fire, to route around dangerous places as much as possible.

If you’re only worried about shortest paths, there’s an easy algorithm to find the set of all tiles that are on a shortest path to a given place, your origin (which might be a tile or an area). First, make a distance map starting from the origin. Then pick a point outside—say, the center of the map if it’s reachable—and look up its distance. Let’s pretend it’s 100. Mark all tiles that have distance 100, or perhaps all tiles with distance 100 which are not in a base you control (since the enemy won’t start out from there). Then walk inward along the distance map: Mark all adjacent tiles with distance 99, then 98, and so on. When you’re done, you know all the tiles that are on a shortest path from anywhere at distance 100 to your origin.

The analysis only includes shortest paths, but it is thorough. It counts shortest paths in every direction, including through back doors.

region and choke method

BWTA and BWEM both calculate chokes and regions, creating a graph of the overall map structure. BWEM does pathfinding on this graph, rather than directly on the map, and if you use BWTA it’s easy enough to implement something similar yourself. You can enumerate high-level paths through the graph, then work out low-level path details inside each region using the distance map method above (make distance maps from each choke).

random method

Instead of calculating all short paths, you might prefer to take a random sample from a larger set of paths. Start with a random point outside (not in a base you control), and create a path using a distance map toward your origin—but don’t always choose a direction that decreases the distance. If the distance decreases on average, the path will eventually lead to the origin. You can also generate random paths with the region and choke method.

To make sure the random paths are diverse enough, you could use a multi-scale method. Start with a coarse path whose steps are far apart. It can be done directly using a distance map; pick random angles and find the tile in that direction at a given Euclidean distance (of, say, a randomly chosen 10 plus or minus 5 tiles), and accept it if it has a ground distance that is not too great (this choice can be random too). Once you have a coarse path, you can fill in the detailed path between the coarse path tiles using the same distance map.