0
$\begingroup$

Say I have a $10\times10$ plane and I am given two points on the plane, suppose $(0,0)$ and $(10,10)$. What formula or algorithm could be used to trace all the possible paths between these two points? I would like to apply it to a plane of variable area and to any two points within that plane.

Here is a photo that will hopefully clarify

Photo

If the algorithm were to draw the route's lines they should be something like this. You could see that there are many other possible routes with an increase in 'turns' but these 4 'main'routes are the ones that span the whole plane to your target

$\endgroup$
4
  • 1
    $\begingroup$ I'm guessing there must be some constraint on what is meant by a valid path, otherwise there are clearly unlimited possibilities. Is the path confined to the integer grid? Or to line segments joining integer lattice points? Is there some restriction on directions? On revisiting points already part of the path? $\endgroup$
    – Joffan
    Commented May 11, 2015 at 22:15
  • $\begingroup$ You seems to implicitly assume that the path is indeed confined to the integer grid lines (despite your mention of "diagonally"). In your example, there are far more than 3 possible paths from x to y, unless there are more constraints you haven't yet explained. For example, starting from x, go down 1, right 2, up 1, left 1, up 1, right 1 to end at y. Is this one of the 3 paths? $\endgroup$
    – Joffan
    Commented May 11, 2015 at 22:37
  • $\begingroup$ If you are allowed to visit a location more than once, than the number of paths is unlimited. On the other hand of you can visit a location only once, it is easy to get trapped between your own path and the walls of your area. For example in your picture, go $RDDDLUU$ and you are stuck. $\endgroup$
    – M. Wind
    Commented May 11, 2015 at 23:22
  • $\begingroup$ Say once you take a step down, you cant go up, or versa vise. Also you cannot cross your own path twice $\endgroup$
    – AlanZ2223
    Commented May 12, 2015 at 1:42

1 Answer 1

Reset to default
0
$\begingroup$

Suppose $(x_1,y_1)$ and $(x_2,y_2)$ represent the two points on a plane of size $m\times n$. You didn't specify restrictions on the paths, but I'll assume they must fall on gridlines.

Any path connecting these two points must have a net offset of $(x_2-x_1,y_2-y_1)$, so to find all the shortest paths you would just have to arrange $h=x_2-x_1$ horizontal and $v=y_2-y_1$ vertical steps starting from the first point. For example, with R = right and U = up, the move RRRRRUUURRUUUUUUURRR will take you from (0,0) to (10,10).

Now to find all possible paths (including those that overlap and cross earlier parts of the path), you could also insert backwards movements to create offsets like this: $(h+1)-1$, $(h+2)-2$,...,$(h+(m-h))-(m-h)$. Doing the same procedure for vertical motion, you can generate all possible paths by creating random sequences of left, right, up, and down motions in which the number of each motion is on that list.

In your example, you could not only move 10 right and 10 up, but also 11 right, 1 left, 12 up, and 2 down. For instance, RRRUUUUDLURRRDUUUUURRRRRUU is a valid path that would be generated by this algorithm.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .