Pathfinding with weighted routes

Question

Hi,

I'm working on a project where I need to perform pathfinding to find the route which costs the least. I don't really care if it's the shortest route possible. So far it seems A* is out of the question and I honestly do not understand Prim's algorithm.

Let me explain the kind of maps that I need to find routes on. This is an example map:

+------|-*----
+------|----|-
+--|--------|-
+@-|----------

The "*" is the start location, the "@" is the destination. The "+" signs in a line indicate a direct route which a) costs the same as a single step, and b) halves the cost of the entire route.

This means there are 10 "steps" from the start position to the destination via the "+" route, which ends up with a cost of 5. There are 15 steps to use the left-most "|" route ("|" is a lower cost than "-", but worse than "+"), which ends up with a cost of 15. Obviously, the route with a cost of 5 is the route to use.

Now I'm having trouble implementing this in C#. I currently have a "step" function which moves and returns if the way was blocked or the cost of the step, and the new position. This works well, but at the moment it is extremely naive in that it'll go down a "|" if it finds one before a "+" (which means the entire trip costs significantly more, as it hasn't found the faster route).

I was thinking of marking each location as "visited", but it's completely plausible that the lowest-cost route will loop back on itself. There are also many different paths, each of which is unique, and each of which may use different path segments (that may have already been visited by a previous run). Obviously each path needs to be traversed in order to find the cheapest path, but I can't figure out how to do that without ending up searching the same routes over and over again.

If it makes it simpler, I can limit any movement to only move towards the destination (ie, can't go back up again after going down).

If anyone could provide some insight, that'd be great!

Answer 1

From what I understand, the '-' fields in your map are graph nodes. Each '-' node has at most 8 edges to neighboring '-' fields. 8 if you allow diagonal movement, otherwise only 4 neighboring '-' nodes are valid. There is no edge between a '-' node and a '|' node.

This is enough to implement a simple depth-first search / breadth-first-search in which you keep a queue of unvisted nodes (LIFO for depth-first, FIFO for breadth-first) and a list of visited nodes (to avoid cycling). Both algorithms will be relatively inefficient, but can be easily improved upon.

I'm not sure what the meaning of your '+' nodes is. Is moving from one '+' to the next '+' mode a free move? If so, you can model this using edge costs. A move from or to a '-' node has cost 1, a move from '+' to '+' node has cost 0.

The breadth-first-search algorithm can be extended to Dijkstra's algorithm that calculates the shortest path between your source and destination as long as all graph edges are non-negative:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

The Dijkstra algorithm can be further improved with the addition of a simple heuristic, making it the A* algorithm. If you have the coordinates of your goal in 2D coordinates, you could use the euclidian distance between a node and the goal as a rough estimate of which node is best to follow. If the '+' fields are something of a tunnel through your map with zero cost to move, the A* algorithm may not help that much because heuristically moving towards your destination will often be wrong if you should have moved towards the tunnel. If there are multiple tunnels or tunnels not leading to your destination, there may not be an heuristic better than the naive Dijkstra algorithm.

Please note that it is impossible for the lowest-cost route to contain a loop: If the lowest-cost route contained a loop, stripping the loop would still yield a valid route to the goal with lower cost contradicting the assumption that we started from a route with lowest-cost.

Have a look at Cormen's Introduction to Algorithms, or the relevant Wikipedia pages:

http://en.wikipedia.org/wiki/Shortest_path

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/A*_search_algorithm