Shortest path 2D

1 2 3 4 5 6 7

1 # # # # # # #

2 # A # . . . # A - starting point

3 # . # . # . # B - ending point

4 # . . . . . # . - walkable point

5 # . # . # . # # - impassable point

6 # . . . . B #

7 # # # # # # #

At the first step, set the value for the distance for starting point at one.

1 2 3 4 5 6 7

1 # # # # # # #

2 # 1 # . . . # 1 - starting point

3 # . # . # . # B - ending point

4 # . . . . . # . - walkable point

5 # . # . # . # # - impassable point

6 # . . . . B #

7 # # # # # # #

At the second step, for each walkable point for wich a value for distance from starting point is not determined,

we set that value by finding the neighboring point which has the lowest value for the distance and that value we increase by one.

In the first case it is the point at coordinates (2,3) with the assigned value of two, for the distance from starting point,

because in its neighborhood there is only a starting point with a value for the distance set at one.

1 2 3 4 5 6 7

1 # # # # # # #

2 # 1 # . . . # 1 - starting point

3 # 2 # . # . # B - ending point

4 # . . . . . # . - walkable point

5 # . # . # . # # - impassable point

6 # . . . . B # 2 - new point with determined distance

7 # # # # # # #

We repeat the second step while new walkable points that gets value for distance appears.

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

1 # # # # # # # 1 # # # # # # # 1 # # # # # # # 1 # # # # # # #

2 # 1 # . . . # 2 # 1 # . . . # 2 # 1 # 5 5 . # 2 # 1 # 5 5 6 #

3 # 2 # . # . # 3 # 2 # 4 # . # 3 # 2 # 4 # . # 3 # 2 # 4 # 6 #

4 # 3 3 . . . # 4 # 3 3 4 . . # 4 # 3 3 4 5 . # 4 # 3 3 4 5 6 #

5 # . # . # . # 5 # 4 # 4 # . # 5 # 4 # 4 # . # 5 # 4 # 4 # 6 #

6 # . . . . B # 6 # . . . . B # 6 # 5 5 5 5 B # 6 # 5 5 5 5 B #

7 # # # # # # # 7 # # # # # # # 7 # # # # # # # 7 # # # # # # #

The second part of the algorithm is to select the shortest path from the starting to the ending point, provided that one exists.

1 - Position the pointer at the coordinates of the end point.

2 - Check all of the neighboring points and pick the one that has the lowest value for the distance.

3 - If there are more points in the same environment with the lowest value, we choose one at random principle.

This step can also be different, in the example program is implemented function that determines which point

will be selected based on the value for distance and the proximity of point to the imaginary straight line that passes

through the starting and ending point.

4 - We set the pointer to the selected point and repeat steps 2, 3 and 4 until we get to the starting point.

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

1 # # # # # # # 1 # # # # # # # 1 # # # # # # # 1 # # # # # # #

2 # A # 5 5 6 # 2 # A # 5 5 6 # 2 # A # 5 5 6 # 2 # A # 5 5 6 #

3 # 2 # 4 # 6 # 3 # 2 # 4 # 6 # 3 # 2 # 4 # 6 # 3 # o # 4 # 6 #

4 # 3 3 4 5 6 # 4 # 3 3 4 5 6 # 4 # 3 o 4 5 6 # 4 # 3 o 4 5 6 #

5 # 4 # 4 # 6 # 5 # 4 # o # 6 # 5 # 4 # o # 6 # 5 # 4 # o # 6 #

6 # 5 5 5 o B # 6 # 5 5 5 o B # 6 # 5 5 5 o B # 6 # 5 5 5 o B #

7 # # # # # # # 7 # # # # # # # 7 # # # # # # # 7 # # # # # # #

1 2 3 4 5 6 7

1 # # # # # # #

2 # A # . . . # A - starting point

3 # o # . # . # B - ending point

4 # . o . . . # . - walkable point

5 # . # o # . # # - impassable point

6 # . . . o B # o - selected shortest path point

7 # # # # # # #

The illustration above shows one of many possible traversable path from the starting to the ending point which is also the shortest.

The term 'Walkable Path' is deliberately emphasized because of the possibility that the passability of path was characterized in a different way.In the program, walkable path is defined so that it is not possible to move diagonally if in the neighborhood, in the direction of movement, areimpassable points, and in that case the text-graphical representation of matrix with determined distances of points from the starting pointlooks like this:

1 2 3 4 5 6 7

1 # # # # # # #

2 # 1 # 7 8 9 # 1 - starting point

3 # 2 # 6 # 8 # B - ending point

4 # 3 4 5 6 7 # . - walkable point

5 # 4 # 6 # 8 # # - impassable point

6 # 5 6 7 8 B #

7 # # # # # # #

And illustration of matrix with selected shortest path like this :

1 2 3 4 5 6 7

1 # # # # # # #

2 # A # 7 8 9 # A - starting point

3 # o # 6 # 8 # B - ending point

4 # o o o o o # . - walkable point

5 # 4 # 6 # o # # - impassable point

6 # 5 6 7 8 B # o - selected shortest path point

7 # # # # # # #

The difference in the length of paths is noticeable immediately, four walkable points in the first in the relation to seven in the second case.

Implemented as a console application in C# programming language, the program is one of the many solutions to this type of problem.

At the link below or by clicking on the image of the program, you can download an executable version of the program or complete

program code. For the proper work of the program it is necessary to have .Net framework 4.0 installed ( ^ ) !

All the best,

Author