Find the shortest path with least turns

[imwithye]

Sometimes, the shortest path is not enough. It requires a shortest path with less turns. It is quite normal in the robot and maze problem. For example, the graph below is the shortest path found by A* algorithm with Manhattan distance.

If we consider turning is an issue here, the actual shortest path is that go down then turn left and go to the goal directly. This path is the same weight with the shortest path found above but with less turns.

PathFinding.js is a great searching library but I notice that PathFinding.js does not provide this feature directly. Is there anyway to add the feature in and is there any plan to support this feature by default?

[imor]

Hi @imwithye
You can take a look at #32. This PR was not merged because the changes were done in the wrong file. If you happen to make it work please consider opening a pull request.

[cuixiping]

Neither #32 nor #150 can find the best path with least turns. For example:

In this case, the result (yellow) is not the best path (red).

[Nixon-Joseph]

Neither #32 nor #150 can find the best path with least turns. For example: In this case, the result (yellow) is not the best path (red).

Running into a similar requirement. Have you found a solution @cuixiping?

Another note, technically, if the initial direction matters (it does in my case), both the yellow and red solutions in your screenshot have the same number of turns, if the initial direction is to the right.

I'm gonna try both #32 and #150 personally and see if they work for my particular use case. If not, I'd love to know if you found a solution for what you needed.

[cuixiping]

@Nixon-Joseph
I wrote my own search of BFS algorithm instead of using pathfinding.js.

[cuixiping]

I added a demo based on the visual demo of PathFinding.js.
It works as my expect.

1. Select Breadth-First-Search
2. Uncheck other options, check Less Stairs

demo