How can I calculate all nodes within X?

Question

I am trying to implement a pathfinding algorithm, but I think I'm running into terminology issues, in that I'm not quite sure how to explain what I need the algorithm to do.

I have a regular grid of nodes, and I am trying to find all nodes within a certain "Manhattan Distance".

Finding the nodes within, say, 5, is simple enough.

But I am interested in a "Weighted Manhattan Distance", where certain squares "cost" twice as much (or more) to enter. For instance, if orange squares cost 2 to enter, and purple squares cost 10, the graph I'm interested in looks like this:

Firstly, is there a term for this? It's hard to look up info on things when you're not entirely sure what they're called in the first place.

Secondly, how can I calculate which nodes fall within my parameters? I'm not looking for a full solution, necessarily, just some hints to get started; when I realized my implementation would require three Dictionarys, I began to think there might be an easier way of handling things.

Answer 1

For terminology, you're basically asking for all points within a certain distance on an arbitrary (positive) weighted graph. The use of differing weights means it no longer corresponds to a specific metric such as Manhattan distance.

As for algorithms, Dijkstra's algorithm is probably what you want. The basic idea is to maintain the minimum cost to each square that you've found so far, and a priority queue of the best squares to explore next.

Unlike traditional Dijkstra's where you keep going until you find the minimal path to every square, you'll want to stop adding nodes to the queue if the distance to them is too long. Once you're done, you'll have a list of all squares whose shortest path from the starting square is at most x, which sounds like what you want.