When using a pathfinding algorithm, you may want to treat map spaces as something other than clear and blocked. Often there is more information available, such as the difficulty of moving through that area. For example, swamps and mountains may be more difficult to pass than grasslands and desert. With some algorithms, like A*, you can put this encode this information into the cost function. Listed below are some ideas for movement costs that might be useful.
Altitude#
High altitudes (such as mountains) can have a higher movement cost than low altitudes. With this cost function, your units will try to stay in the lowlands whenever possible. For example, if the source and destination are both at high altitudes, the unit might move downhill, travel for a while, and then move back uphill.
Moving uphill#
Instead of high altitudes having a high cost, moving uphill can have a high cost. This avoids the odd situation described above. With this cost function, units try to avoid moving uphill. Faced with the same situation, the unit will try to avoid moving back uphill at the end; it can do this by staying at a high altitude throughout its travels. A cost function such as this one may be good for units such as soldiers, which can move downhill easily but have a hard time going uphill.
Moving up- or downhill#
Some units, such as tanks, have a hard time moving uphill or downhill. You can assign a high cost to moving downhill, and an even higher cost to moving uphill. The units will try to avoid changing altitudes.
Terrain#
You may want different types of terrain to have different movement costs.
Forests, mountains, and hills#
Instead of using altitudes, you may want to use terrain types, as in Civilization. Each terrain type can have a movement cost associated with it. This movement table might apply to all units, or different movement tables could be associated with each unit type. For example, soldiers might have no trouble moving through forests, but tanks might have a very hard time. The movement cost might correspond to the destination or the source or an average or max of both. Or the movement cost might correspond to changing terrain, such as grass to mountains being more expensive than mountains to mountains, or grass to grass.
Roads#
In many games, the primary purpose of roads is to make movement possible or easier. After choosing a movement cost function, you can add a road modifier to it. One possibility is to divide the cost by some constant (such as two); another is to assign a constant cost to movement along a road.
I strongly advise that you do not make road movement free (zero-cost). This confuses pathfinding algorithms such as A*, because it introduces the possibility that the shortest path from one point to another is along a winding road that seems to lead nowhere. The algorithm has to search a very wide area to make sure that no such roads exist. Note that in the game Civilization, railroads had zero-cost movement, but when using the “Auto Goto” function, railroads had a non-zero cost. This is evidence that a pathfinding algorithm was being used.
Walls or other barriers#
Instead of checking both movement costs and for obstacles in your pathfinding algorithm, you can use movement costs. Just assign a very high movement cost to any obstacle. When expanding nodes (in the A* algorithm), check if the cost is too high; if it is, then throw the node out.
Sloped Land#
Instead of using movement up and down hills, you might want to make movement on any hill expensive. To do this, compute the overall slope of the terrain (by looking at the maximum difference between the current tail and its neighbors), and use that as part of the movement cost. Land that is very steep will have a high cost and land that is shallow will have a low cost. This approach differs from the movement uphill/downhill cost in that it looks for land that is steep, while the previous approach looked for units that move in a steep direction. In particular, if you’re on a hill and can move left or right without going up or down, the uphill/downhill approach will consider it a low cost, while this approach will consider it a high cost (because the land is steep even if you aren’t going up or down).
Sloped land costs may not make sense for unit movement, but you can use pathfinding for more than finding paths for units. I use it for finding paths for roads, canals, bridges, and so on. If you want to build these items on flat land, you can take land slope into account when finding a path for a road or canal. See the section on applications for more ideas.
Enemies and friendly units#
Another modifier can help you avoid enemy units. Using influence maps[1], you can keep track of areas that are near enemy or friendly units, have recently killed soldiers, have been recently explored, are close to an escape route, or have been traversed recently. An influence map might have a positive value for friendly units and a negative value for enemy units. By increasing the movement cost whenever you are in negative territory, you can influence your units to stay away from the enemy.
Even more complicated (and perhaps not possible with influence maps) is to look at visibility: is your unit visible by an enemy unit? Is your unit detectable in some other way? Is it possible for that enemy unit to fire on you?
Marked beacons#
If your map is designed and not automatically generated, you can add extra information to it. For example, ancient trade routes often would pass particular points, which often became trading towns. These places are beacons, places that are known to be along good paths. The distance to a beacon would be added to the movement cost as a way to influence paths to favor beacons.
Good choices for beacons include lighthouses, cities, mountain passes, and bridges.
Fuel consumption#
In addition to looking at the time it takes to go somewhere, you may want to consider the fuel it takes. The fuel consumption may be given more weight when the unit’s fuel level is lower.
To track the fuel usage through the map, you need to use state space, as described in . The state would be the pair <location, fuel>. However, state space can become very large, so it may be worth looking at alternatives to using ordinary A*.
One alternative is A* with Bounded Costs (ABC). With ABC, you can assign a bound (“20 gallons”) to a cost (“fuel”).