Starcraft AI blog

UAlbertaBot comes with distance maps: Give a destination tile position, get back a grid with the approximate ground distance from each tile on the map to the destination, or -1 if you can’t get there from here. Since forking Steamhammer from UAlbertaBot, I’ve added to and refined the subsystem, and used it for more purposes. For example, Steamhammer uses the ground distance to decide when to transfer workers to a new base so that they arrive just after it finishes. Pathfinding is an obvious use of distance maps, so maybe it’s surprising that I didn’t implement it until now.

the implementation

The low-level implementation is simple. The move command the.micro.Move() accepts an optional distance map. If provided, it calls on a simple algorithm that searches the distance map and finds a shortest-distance path segment 8 to 12 tiles ahead of the moving unit. MoveNear() and MoveSafely() also accept the optional distance map and pass it on to Move(), which does the work.

Plumbing the distance map through the abstraction hierarchy is the hard part. I chose to allow the squad’s order (class SquadOrder) to optionally keep a distance map. Basically, at any given time a squad may either have a distance map to its target, or not. If it has a map, then it is passed along on every movement order for the squad’s units. CombatCommander decides on the squad orders and generally gives a distance map to ground squads, and none to air squads which can fly straight to their destinations. Most squad targets are bases, and it happens that Steamhammer precalculates a distance map for each base. So a squad order to target a base uses the base’s distance map for free, while a squad order to target an arbitrary location calculates a new distance map which belongs directly to the squad order. I’ve been planning that detail of the implementation for years.

Pathfinding is used for squads with ground units, for the scouting worker, and for sending a worker to construct a new base. It is not used for constructing other buildings (which are usually nearby though not always) or for transferring workers between bases.

If the debug flag to draw squad information is turned on, a squad which has a distance map is listed with a “#” symbol before its name. The “#” represents the grid of distances.

results

Pathfinding works well in test games, though not perfectly. The paths are not true shortest paths (see “disadvantages” below), but close enough for now. In test games on Medusa, units of the Ground, Recon, and Watch squads navigate well, no longer getting stuck in the dead end back doors of the bases. On the other hand, I commonly saw a small number of transferred drones stuck there. One oversight is that some units still tend to get stuck behind the neutral buildings on Benzene. Benzene is not in the AIST S4 map pool, so I didn’t notice.

I also need to update the precalculated maps when map obstacles are destroyed. I’m sure I’ll iron out the details in time. It didn’t seem vital for now.

advantages

Once a distance map is calculated, it’s cheap to follow not only a shortest path for one unit, but any shortest path for all units. If you like one shortest path better than another for any reason, you can choose it on the fly.

A distance map need not be calculated from a single destination tile. It can start from any set of destination tiles, so that you can do things like find the shortest path to enter a region, or choose the closest of 2 equal goals. A distance map need not record literal distance; it can pretend that a dangerous tile is larger than others so that you tend to path around it when you can. Distance maps of different kinds have many potential uses.

• Ground unit pathing through terrain, the implemented feature.
• Ground or air unit safe paths, to avoid all known risk for scouting, or to discover containments.
• Ground or air unit least-danger paths, to reach a defended target with minimal damage.
• Ground or air paths which are out of sight range of known enemies, for sneaking around.
• Paths to safe firing zones, so we can attack a defended target from outside its defences.
• Maintaining a contant distance from an objective, such as the convex hull of a group of enemy units, for arcs and surrounds.

disadvantages

As implemented, the distances mapped are not true unit movement distances, but Manhattan distances. Units moving diagonally, say from bottom right to top left, tend to move not diagonally, but first to the left and then upward. I intend to correct it, but haven’t decided on a plan yet.

Distance maps are a bit bulky and slow, and usually involve calculating a lot of paths that you won’t go anywhere near, so you don’t want to calculate too many maps each frame. It’s better to reuse them as much as possible, which adds complexity. UAlbertaBot comes with a distance map cache, but its replacement policy is “periodically throw out all entries in case some may be unused.” Something a little more sophisticated is called for, especially if you want to store different kinds of distance maps in the same cache.

If you want to map something that changes frequently, like detailed enemy firing zones, you can either recalculate the map frequently—which is fine up to a point—or accept that it will often be a little outdated—also usually fine.

The disadvantages don’t seem severe to me. Distance maps gain their flexibility by doing more calculation than is necessary for any one use case—guess what, work harder, earn more. It does call for a little attention to efficiency.

Next: Combat sim smoothing.