How can I calculate all nodes inside X?

Question

I am trying to implement a path-finding algorithm, but I think I'm having problems with the terminology, because I'm not quite sure how to explain what I need to execute the algorithm.

I have a regular grid of nodes, and I'm trying to find all nodes within a specific "Manhattan distance."

Finding nodes inside, say, 5, is quite simple.

But I'm interested in "Weighted Manhattan Distance", where certain squares "stand" twice as much (or more) to enter. For example, if orange squares cost 2 to enter, and purple squares cost 10, the graph that interests me is as follows:

First, is there a term for this? It is difficult to find information about things when you are not quite sure what they are called in the first place.

Secondly, how can I calculate which nodes fall into my parameters? I am not looking for a complete solution, certainly, only some hints to get started; when I realized that my implementation would require three Dictionary s, I began to think that there might be an easier way to handle things.

Answer 1

For terminology, you basically request all the points at a certain distance on an arbitrary (positive) weighted graph. Using different weights means that it no longer matches a specific metric, such as Manhattan distance.

Regarding algorithms, Dijkstra's algorithm is probably what you want. The main idea is to keep the minimum cost of each square that you have found so far, and the priority queue of the best squares for further study.

Unlike the traditional Dijkstra, where you keep going until you find the minimum path to each square, you will want to stop adding nodes to the queue if the distance to them is too large. As soon as you finish, you will have a list of all the squares whose shortest path from the starting square is no more than x , which sounds the way you want.

Answer 2

Probably your best bet is to go with a weighted chart Dijkstra algorithm as described here: http://www.csl.mtu.edu/cs2321/www/newLectures/29_Weighted_Graphs_and_Dijkstra's_Algorithm.html (There is a description of the algorithm near the middle of the page.)

The Manhattan distance in your case probably means that you do not need diagonal paths on the graph.

Answer 3

Eric Lippert offers an excellent blog series on writing the A- * search algorithm in C # here:

Part 1: http://blogs.msdn.com/b/ericlippert/archive/2007/10/02/path-finding-using-a-in-c-3-0.aspx

Part 2: http://blogs.msdn.com/b/ericlippert/archive/2007/10/04/path-finding-using-a-in-c-3-0-part-two.aspx

Part 3: http://blogs.msdn.com/b/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx

Part 4: http://blogs.msdn.com/b/ericlippert/archive/2007/10/10/path-finding-using-a-in-c-3-0-part-four.aspx