Starcraft AI blog

Or rather, what should we want pathfinding to be? The term “pathfinding” prejudices the issue: It means finding a path from here to a given goal. The term presupposes that selecting the goal and figuring out how to get there can be separated. Picking the goal depends on the game situation and on what the enemy might do. Choosing how to get there also depends on the game situation and on what the enemy might do. The goal you want may depend on which paths the enemy is likely to block or to have vision over, so goal finding and path finding ought to feed into each other. Maybe we should use the word “movement” instead.

Following a static path to move blindly to a goal is a way to make terrible mistakes.

Consider some use cases:

• Scouting. The scout doesn’t mind being seen, as long as it gets to see too, but it wants to live as long as possible to see more. Later in the game you may see the most by reconnaissance in force, that is, scouting with the army. The most interesting targets to scout can change with new information: “There’s an expansion here, there shouldn’t be one over there too.” Or: “These units are screening a base that used to be empty; is it still empty?” The best scouting takes into account possible enemy intentions and tells you actual enemy intentions.

• Defending against an ongoing attack. It’s not enough to arrive at the goal, you have to arrive in position to help. It’s a tactical calculation about how reinforcements can best coordinate with existing defenders. Do I need to retreat until I can gather enough units to hold the attack? Can I hold long enough for the reinforcements to make a sandwich?

• Reinforcing an army with new production. Sometimes you can send new units to the front and it’s a pathfinding operation. Sometimes the enemy intercepts your reinforcements and it becomes a tactical calculation.

• Targets of opportunity. When a squad spots a target it can attack with little risk, it has to decide whether the original goal or the new target is better. Maybe other units should be rerouted to join in.

• Air units. Air units can fly anywhere and don’t need pathfinding to reach a goal, but they still prefer some paths over others. If the enemy is near, air units often want an escape route: A nearby obstacle or friendly force to retreat behind when in danger. Mutalisks, corsairs, and wraiths can rely on their speed to escape, but they still want to watch enemy movements to make sure they don’t get cut off and trapped. Overlords want to be close enough to see and detect as necessary, but safe and ideally unseen themselves.

• Dropping. The transports would like to stay unobserved until as late as possible, to reduce the enemy’s reaction time: Plan a path over friendly territory, above cliffs, at the extreme edge of the map, and so on. If there is no good path, then the drop target may be a poor one. After being seen, the transports have to circle around or thread through static defenses and moving defenders. If the defense is too strong, the drop should turn back, maybe unloading some units early to save what can be saved. It’s a matter of weighing risk and benefit, both of which are uncertain and depend on the overall game situation and on what the transports see immediately around them.

I’m beating a dead horse by now. Whether the goal is good depends on whether the path is good, and you have to reevaluate the goal when new information comes up en route. Tactical analysis and path analysis have to be integrated one way or another. And the enemy gets a vote, so A* is not a natural fit; A* thinks it is the only agent in the world. If you plan movement by search, it’s natural to use some kind of adversary search.

MaasCraft’s tactical search is one way of integrating tactical analysis and path planning. It’s too coarse-grained to catch all the nuances, but I think it’s an excellent start.

Another consideration is information. You do sometimes have to plan long paths, even if you don’t always follow them to the end. You have good information about the start of the path, because you can see it. You have less information about the end of the path, because a lot may have changed by then. It may make sense to plan the near segment of the path in detail (if you don’t handle details with a reactive algorithm), and distant segments only coarsely.

Next: The Pathfinder Almighty, one last post to wrap up the pathing series.