# Find a proper path between two nodes in a grid

This question is about finding a proper path (route) between two nodes (P,Q) in a grid (i.e., graph, network, ...). In our concept, we define a path proper (nice) if it is the most similar* to the straight line connecting the two nodes, as shown in the following figure. So, from 10 possible short paths (all are 5 segments in length,) between green and red nodes, number 5 is chosen the best one.

most similar: the similarity between two polylines (here a polyline and a line) can be defined in various ways (see this) for example. So vertices of a polyline can be evaluated with regards to the line.

Suppose we have locations as grid nodes, (1) we are looking for implementations of the method explained above in any programming languages. Source code, coding hints, ideas etc are more than welcome. We prefer not to use existing graph libraries but are interested in digesting the solution with examples.

The method needs to be flexible to (2) adding some conditions such as "not visiting a node" as shown in the following figure (yellow node). That is, the best choice from above needs to be slightly adapted to satisfy the required condition.

-
You will need to quantify what you mean by "most similar" or "nicest" in order to make this a well-posed question. BTW, the generalized version of the question (2) is much more difficult than the first version; it's not a matter of a "slight adaptation"! – whuber Nov 8 '12 at 13:53
@whuber an explanation with a link was added. – Developer Nov 9 '12 at 4:38
Just curious, why is it important for the path to approximate a straight line connecting the two nodes? Why is it considered 'nice'? – R.K. Nov 9 '12 at 7:15
You will be interested in Bresenham's algorithm: it offers one (very well known and extensively used) solution to the first part of this question. It is a minimax (not least-squares) solution. The second part is potentially difficult. Genetic algorithms look especially suitable for obtaining near-optimal solutions. – whuber Nov 9 '12 at 15:25
It's not strictly a graph-theoretic problem: the criterion for "nicest" depends on the embedding of the graph in the plane. Bresenham's algorithm is a good candidate for constructing partial solutions, depending on exactly how you quantify "nicest". You will get different solutions depending on whether "nice" is meant in an L^1 or L^2 sense, for instance. So, rather than teasing us about what the real problem is, please state the problem that you actually want solved. – whuber Nov 11 '12 at 15:14

You want to favor edges that are "close" to the line segment joining the endpoints of the path (its "axis," let's say). One direct way to do this is to weight the edges accordingly. How you weight them will determine what kind of path is "nicest." Just make sure that edges further from the axis get proportionately greater weight.

As an illustration, I have removed three points from the lattice shown in the question:

To obtain a "nicest" path from, say, (1,2) to (6,6), let's transform the coordinates to stretch the points quadratically relative to their distance to the axis:

(The quadratic stretching ensures that edge weights increase linearly with distance from the axis. Stronger transformations, such as exponential stretching, could be used if this does not appear sufficient to achieve the intended "niceness" of the ensuing solutions.)

Using the new distances for the edge weights, find the shortest path (using any efficient algorithm; Dijkstra's will do fine):

Although in the original lattice metric (where all edges have unit length) there are many shortest paths between (1,2) and (6,6)--such as the one going from (1,2) east to (6,2) and thence north to (6,6)--the quadratic distortion causes edges closer to the axis to be favored.

Note, please, that the lattice points themselves do not need to be changed: once the "nicest" path is found based on the reweighted edges, draw it in the original lattice (using the original vertex coordinates).

Evidently, each new origin-destination pair will require a reweighting of the edges. Although this may seem inefficient for large lattices, its signal advantage is that it automatically handles the second (more difficult) part of the question, where constraints (in the form of vertices to be avoided) are included: no special new algorithm is needed.

For completeness, here is the Mathematica code used to generate examples like this: it shows how to carry out the metric distortion.

``````m = 30; n = 20; (* Lattice dimensions *)
s = {m - 1, 7}; t = {2, n - 2}; (* Path endpoints *)
v = s - t;
v = {-v[[2]], v[[1]]} / Norm[v];
a = {{v[[2]], -v[[1]]}, v};
o = v.t;
vertices = Flatten[Table[{i, j}, {i, 1, m}, {j, 1, n}], 1];
vertices = Sort[RandomSample[vertices,
Length[vertices] - 5 Floor[Sqrt[Length[vertices]]]]];

With[{\[Epsilon] = 10/(m + n)}, coords = Transpose[a] . {#[[1]], (#[[2]] +
Sign[#[[2]] - o] \[Epsilon] (#[[2]] - o)^2)} & /@ (a.# & /@ vertices);
f[i_Integer, j_Integer] :=
If[Total[Abs[vertices[[i]] - vertices[[j]]]] != 1, Infinity, Norm[coords[[i]] - coords[[j]]]];
Show[ContourPlot[(#[[2]] - o + Sign[#[[2]] - o] \[Epsilon] (#[[2]] - o)^2) & @ (a.{x, y}),
{x, 1, m}, {y, 1, n}, AspectRatio -> n/m],
ListPlot[vertices, PlotStyle -> White], Epilog -> {Red, PointSize[0.015], Point[{s, t}]}]]

adj = Outer[f, Range[Length[vertices]], Range[Length[vertices]], 1];

{v1, v2} = Flatten[Position[vertices, #] & /@ {s, t}];
Show[HighlightGraph[g, PathGraph[FindShortestPath[g, v1, v2]], GraphHighlightStyle -> "Thick"],
Graphics[{Gray, Dashed, Line[{coords[[v1]], coords[[v2]]}]}]]
``````

Another example of its output, showing the grid and the solution in weighted and original coordinates:

-
Good answer, although translating Mathematica code to Python will take sometime ;) Also I appreciate both Aragon and R.K. ideas given below. – Developer Nov 16 '12 at 13:29

For the first problem, you might want to check out line rasterization algorithms. Bresenham's algorithm , which @whuber mentioned, is one of them. This is so because your nodes, with their von Neuman neighborhoods, can be treated as the center of a raster cell. Your "nice" path requirement is also similar to the raster approximation of a line.

Below is an overview of how a few line rasterization algorithms work.

In Bresenham's algorithm, you basically select a pixel vertically closest to segment.

Another algorithm is the naive line rasterization algorithm. It simply computes y as a function of x and then moves a vertical scan line from x1 to x2.

Yet another algorithm is the scan line rasterization algorithm which handles all the segments together pixel row by pixel row.

For the second part, maybe you can combine it with something like the A* pathfinding algorithm with obstacles? For example, it will keep on following the line rasterization path until such time that it encounters an obstacle, in which case, it will switch to a pathfinding algorithm to get back to the original "nice path." I'm thinking of something like the following:

1. Apply line rasterization algorithm on nodes without considering the conditions. This would result in a nice path that doesn't take into account the nodes that shouldn't be visited.
2. Apply conditions.
3. Trace the path in step 1. If it encounters a node that shouldn't be visited, use A* or some other pathfinding algorithm to get to the next allowable node in the step 1 path. Once it gets to the path, resume tracing the path.
4. Repeat step 3 until done.

What do you think?

Disclaimer: Illustrations were taken from lecture slides of an MIT graphics class.

-
Indeed for the problem of our interest, the case is the second one i.e., incorporating conditions. We provided the first part as background to the problem. That is, the method should be extendable for such flexibility. Anyway, we thank you for your nice demonstrations of rasterization techniques. – Developer Nov 11 '12 at 2:54
Updated my answer. What do you think? – R.K. Nov 11 '12 at 3:08
Your answer and Aragon's indeed seem promising if work together. We upvoted both already for their constructive ideas. Do you think your idea may work considering the recent comments above for the post? – Developer Nov 11 '12 at 3:30
Theoretically, it should work for complex routes as well. It would be a multistep process. Rasterize routes. Then trace them. Then switch to the pathfinding algorithms if it encounters gaps or obstacles. Then resume to tracing the routes once it gets back to the original path. I think this is more of a pathfinding problem instead of a shortest route one. – R.K. Nov 11 '12 at 3:34

i know that you want to find proper path but i think you need to check out Shortest path algorithm for your problem. as Dijkstra's shortest path algorithm, it is not only check shortest path also suitable path for your problem. my suggestion is that Dijkstra's algorithm is the most using algorithm in this area that you should check out it with some examples. in addition to using a wide range of scientific studies, ArcGIS is using it for solving network problems too. check out this page, you will find lots of good examples.

From Wikipedia:

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

From Wikipedia Dijkstra's Algorithm:

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

the other algorithms:

``````* Dijkstra's algorithm solves the single-source shortest path problems.
* Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
* A* search algorithm solves for single pair shortest path using heuristics to try to
speed up the search.
* Floyd–Warshall algorithm solves all pairs shortest paths.
* Johnson's algorithm solves all pairs shortest paths, and may be faster than
Floyd–Warshall on sparse graphs.
* Perturbation theory finds (at worst) the locally shortest path.
``````

i hope it helps you...

-
This is all correct, but will be of little help in solving the problem, because between any two nodes of a regular grid there are usually an enormous number of shortest-length paths. The question concerns finding one that deviates from a given line segment as little as possible (in some undefined sense). – whuber Nov 8 '12 at 13:52
We agree that there are some benefits of using graph theory concept. Thanks. – Developer Nov 11 '12 at 3:21