In addition to finding a path for a unit to move along, pathfinding can be used for several other purposes.
Exploration#
If part of your cost function penalizes paths that are on known territory, paths are more likely to go through unexplored territory. These paths are good for scout units.
Spying#
If part of the cost function penalizes paths near the enemy’s watchtowers and other units, your unit will tend to stay in hiding. Note however that to work well, you may have to update the path periodically to take into account enemy unit movements.
Road building#
Historically, roads have been built along paths that are often used. As the paths are used more and more often, vegetation is removed and replaced with dirt, and later with stone or other material. One application of pathfinding is to find roads. Given places that people want to go (cities, lakes, springs, sources of minerals, and so on), find paths randomly between these important locations. After finding hundreds or perhaps thousands of paths, determine which spaces on the map most often occur on paths. Turn those spaces into roads. Repeat the experiment, with the pathfinder preferring roads, and you will find more roads to build. This technique can work for multiple types of roads as well (highways, roads, dirt paths): the most commonly used spaces would become highways and less commonly used spaces would become roads or dirt paths.
Pathfinding is also used for building roads over mountains that avoid extreme slopes. This article[1] shows how setting the movement cost to the square of the slope makes A* find a “natural” looking path up and over a mountain pass.
Terrain analysis#
Combining influence maps, pathfinding, and line of sight can give you interesting ways to analyze terrain.
Using the same approach as road building, we can use pathfinding to determine what areas are the most likely to be traversed given some set of source and destination points. These points, and areas near them, tend to be strategically important. Clash of Civilizations uses this for their Map AI[2].
By further analysing the common paths we find, we can find ambush sites—locations along a path that do not have line-of-sight access to the location N steps further along the path. Placing an ambush at one of these points means the enemy will not see you until they are within distance N, so you can ambush with a large force.
City building#
Cities often form around natural resources such as farmland or sources of mineral wealth. As people from these cities trade with each other, they need trading routes. Use pathfinding to find their trading routes, and then mark a day’s worth of travel on these routes. After a caravan travels for a day, it will need a place to stop: a perfect place for a city! Cities that lie along more than one travel route are great places for trading villages, which eventually grow into cities.
A combination of the road building and city building may be useful for producing realistic maps, either for scenarios or for randomized maps.