# A* with differing path costs

This topic is 4335 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites
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

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 11
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633722
• Total Posts
3013540
×