Shortest path 2D
Shortest Path 2D
Computer program ' Shortest Path 2D ' is upgraded version of program.
Improvement is reflected in implemented algorithm for path correction, and changed GUI.
Free program can be downloaded by click on picture below or link at the end of page.
For the proper work of the program it is necessary to have .Net framework 4.0 installed ( ^ ) !
Shortest path 2D
Computer program " Shortest path 2D " is designed for finding the shortest walkable path between two points belonging to the same two-dimensional plane. A plane has precisely defined dimensions, where all points have the same distance from the neighboring points and specific value for characteristic of points - 'Walkability of points', which can have two values: walkable or impassable.
Walkable path is a set of interconnected passable points from baseline to end point.
There are many different algorithms for solving such problems, see the text on the following link (^).
Algorithm that was applied to solve this problem consists of two parts :
- The first part is to determine the value for the distance of each walkable point on the plane from the starting point.
- The second part is choosing the shortest walkable path.
The first part of the algorithm is easily understood through the following textual and graphical presentation. We can show plane as a two-dimensional matrix.
example :
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
