A* with differing path costs
Author
How would I need to modify A* for use in terrain which allows multiple costs, for example, I could get on a train and travel by train, or I could get on a ship and travel partway on a ship, or go by foot. In either case, there is a cost to enter/exit the vehicle, and a cost to traverse the square. Is there an easy way to figure the minimum cost path?
Thanks,
Ralph
Pretty much what you need to do is just add a movement type to your planner node. Start it at whatever the unit currently is. If he's on foot start it that way, same for if he's in a vehicle, ship, etc. Then basically this movement type is going to effect how you expand further nodes. If your in a boat you wont be able to expand to a ground node without changing movement modes, which might incur an additional cost. If you want to restrict vehicles to roads that will also be a case within the expansion if your in a vehicle. The movement mode will likely also determine how you set up the costs of each node. Traditionally the cost in A* has meant distance, you can tweak it a bit with a multiplier up or down so it can double as speed. An example might be for every node you expand with a vehicle move mode you only add 0.75 of the given cost or something. It basically gives your A* another dimension, which can effect the speed of the search. Consider if a vehicle can only follow roads, and your pathfinding across country part ways. Each step along the road you kinda need to expand a node with your search that says, get out of the vehicle and try the rest on foot. This kind of thing can increase the expansion quite a bit.
Actually the cost function in A* has never been limited to representing distance. A* is a graph search algorithm. It can be used to find the least cost path between nodes in any graph (as long as there are no negative edge weights).
Games often modify A* for the special case of the graph nodes corresponding to tiles in a map and the edges being movement between those tiles.
In the case of different modes of transportation, there need to be edges to represent changes to different vehicles, and the nodes need to include information about what transportation is being used. For a train or a boat where you can only enter or leave at certain places and times, the nodes would correspond to those places. The edges connect those nodes, and the edge weights are the time it would take to wait for a train and then ride the train to the destination. There would also be edges to represent getting on and getting off a train.
These changes could also mean that you'll need to change your heuristic if you still want to guarantee that optimal solutions are found.
Games often modify A* for the special case of the graph nodes corresponding to tiles in a map and the edges being movement between those tiles.
In the case of different modes of transportation, there need to be edges to represent changes to different vehicles, and the nodes need to include information about what transportation is being used. For a train or a boat where you can only enter or leave at certain places and times, the nodes would correspond to those places. The edges connect those nodes, and the edge weights are the time it would take to wait for a train and then ride the train to the destination. There would also be edges to represent getting on and getting off a train.
These changes could also mean that you'll need to change your heuristic if you still want to guarantee that optimal solutions are found.
As Vorpy and DrEvil both mentioned, having different path costs between nodes is merely equivalent to including additional arcs in your graph. Think of the search tree generated from a given starting node in the graph. If the tree expands a node that has two (or more) viable traversal modes to another node, then there are simply two (or more) copies of the destination node as children of that node and each branch of the tree represents a mode of traversal. Subsequently, each copy of the destination node will have its own cost.
The heuristic won't be a problem provided you take into account the fastest mode of arc traversal for all nodes so that you never overestimate the actual cost. The difficulty will arise from the fact that the heuristic may be a large underestimate for some nodes, thus adding some inefficiency to your search.
One problem you might face (and I've faced this one myself), is that there may be several distinct paths with the same cost that are minima for the graph. For example, you might be able to walk forward to the goal for a given cost, or walk away from the goal and then get on a train that travels to the goal such that this trip has the same cost as walking. Both are optimal solutions. The problem with A* is that it will expand both solutions during its search and the one that is returned by the algorithm will be the one that is popped from the open list first, which will probably be based on which direction you first stepped in from the start node... so be careful with your problem set up and don't just assume that the solution returned is the only optimal solution.
Cheers,
Timkin
The heuristic won't be a problem provided you take into account the fastest mode of arc traversal for all nodes so that you never overestimate the actual cost. The difficulty will arise from the fact that the heuristic may be a large underestimate for some nodes, thus adding some inefficiency to your search.
One problem you might face (and I've faced this one myself), is that there may be several distinct paths with the same cost that are minima for the graph. For example, you might be able to walk forward to the goal for a given cost, or walk away from the goal and then get on a train that travels to the goal such that this trip has the same cost as walking. Both are optimal solutions. The problem with A* is that it will expand both solutions during its search and the one that is returned by the algorithm will be the one that is popped from the open list first, which will probably be based on which direction you first stepped in from the start node... so be careful with your problem set up and don't just assume that the solution returned is the only optimal solution.
Cheers,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
