When using a path-finding 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.
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.
UnitMovement
class.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.
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.
You may want different types of terrain to have different movement costs.
Instead of relying on altitude, you may want to use terrain types. (For example, Civilization does this.) 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. A fancier method is to assign movement costs to changing terrain. Going from grassland into mountains could be more expensive than going from hills to mountains, which could be more expensive than going from mountains to mountains.
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 fixed cost to movement along a road.
UnitMovement
class.I strongly advise that you do not make road movement free (zero-cost). This confuses path-finding 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 path-finding algorithm was being used.
Instead of checking both movement costs and for obstacles in your path-finding algorithm, you can just 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.
FlatCanalPath
class.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 path-finding 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.
Another modifier can help you avoid enemy units. Using influence maps, you can keep track of areas that are near enemy or friendly units. The influence map has 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?
If your map is designed and not automatically generated, you can add extra information to it. For example, you can mark certain positions as beacons, and pre-calculate good paths between beacons. The paths between beacons can have a lower movement cost than other paths; that way, the path finding algorithm could gravitate towards one of these predetermined paths. You can imagine a plateau (normal movement costs) with a canyon (paths between beacons); if the path-finding algorithm falls into the canyon, it's likely to stay in there. This could cut the time it takes to find a path (but find less optimal paths); however, I have not tried this technique so I am not sure it works.
Another way to think about this technique is that you need to make decisions about where to move next. With beacons, you do not need to make very many decisions---you simply decide which beacon to visit next, instead of where to turn at each step.
Good choices for beacons include lighthouses, cities, mountain passes, and bridges.
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").
Back: Heuristics | Up: Home | Next: User experience with shortest paths |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |