Applications

In addition to finding a path for a unit to move along, path-finding 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 path-finding 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 path-finder 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.

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 path-finding 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.


Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel