Visualizing the algorithm for finding the shortest path "PathFinding.js"

Many people are taking care of the service which instantly finds the shortest route to the destination, such as a car navigation application or a smartphone map application, but most people who know how that mechanism is There should not be. For that process, an algorithm dedicated to route searching is used, but the site that shows the behavior of such algorithm and the site that shows the change of the result due to the difference in type is "PathFinding.js"is.

PathFinding.js
http://qiao.github.io/PathFinding.js/visual/

On this site, you can interactively experience various algorithms to discover the shortest route from the start point to the goal point, while changing settings on your own. It is also possible to place an obstacle between the two points and in the following movie search the route from the green point on the lower left of the screen to the red point on the upper right while avoiding gray obstacles and display it as a yellow line You can see how it is done.

I tried searching the route from the start to the goal in "PathFinding.js" with "A *" algorithm - YouTube


When opening the site, the grid screen is displayed, and one green and red squares are displayed one by one. The interesting thing about this site is to select various route search algorithms displayed on the right side of the page and see how each algorithm looks for the shortest route from green mass to red mass.


In the initial state, "A *A solution called "Manhattan" is selected as an algorithm called "A Star". When you click "Research Start" in this state, the search started and the shortest route of yellow was displayed. Of course it became a straight route, but as I saw in the lower left, I understood that the length of the route became "10".


Next time I tried searching with a slight layout change, a diagonal route was searched in this way. It seems that it is set to pass through a slanted line of 45 degrees whenever passing through a square diagonally. The interesting thing is the total distance of the calculated route and the distance is as long as "12.49", although the actual number of squares that are going through is the same as above, and it is not the actual number of masses It shows that it shows. In this case, the straight squareFour(Distance = 1), the mass that crossed obliquely8 pieces(Distance = √ 2 ≈ 1.414), "4 × 1 + 8 × 1.414 = 12.484 →12.49It seems that it is becoming the numerical value of.


Changing the solution to "Euclidean (Euclidean)" at the same A *, a slightly different route was searched. However, even in this case the total distance is 12.49, which shows that it is the same as Manhattan.


When it is "Octile (octile)" it changes to a different route again. Still the total distance did not change.


"Chebychev (Chebyshev) "It will be. After all the distance is 12.49.


Next time, when I unchecked "Allow Diagonal", only the route that proceeded at all right angles was searched even with the same "Manhattan" solution, and the distance also increased to "16" I understood that.


When "Bi-directional" is checked, route search was started from both green and red cells. The time required for the search has also been shortened.


If you check "Do not Cross Corners" and place "Weight (weighted weight)" more than 1, we have searched for routes that do not pass through the corners as much as possible. The algorithm around this seems to be incorporated in car navigation systems of cars.


In this way, PathFinding.js can experience various route search algorithms. In each algorithm, a search based on a specific mathematical expression is performed, but it is an interesting place of this site that you can witness each difference without worrying about such a thing.

It is also possible to place obstacles between two points and search for routes. When clicking on the square with the mouse, the mass turned gray and became an obstacle as follows. When we search the route by placing an obstacle wall between two points like this ...


Such a route was searched. Looking at the state of the search, the shortest straight route is drawn from both the green and red points first, and when it hits the wall, it seems as if to seek the idea to search for the shortest route along the wall as much as possible I will.


Now arrange complex obstacles. I tried digging that the route can not be searched unless it goes away from each destination once.


Looking at the route searching in this state is like this. As expected, the obstacles of the one aiming at the shortest in the shortest were obstructed, and it became very interesting how to find a solution in a fumbling state.

In "PathFinding.js", I tried to search the route in the state of obstacles being trapped - YouTube


The result was like this.


In addition, checking the diagonal line · bidirectional check and searching with straight line emphasis is here. I am surprised that the results are so different even on the same ring. The total distance is greatly reduced from "32" and "41.94" earlier, due to turning off bidirectional search. At the beginning, the distance increased by bidirectional off, but this time the distance will be shortened. It was quite interesting to see the result change dramatically depending on the parameter's condition.


In this way, although it was "PathFinding.js" which is likely to be quite hungry even with the "A *" algorithm alone, it is possible to select more algorithms from the right side of the screen. As the results change depending on the algorithm chosen or the time required for the search changes dramatically, it seems interesting to visit the site first and try out all kinds of patterns.