How to find the shortest path with a minimum number of turns (turns in priority)?

Question

Algorithms

How to find the shortest path with the minimum number of turns?

In this example, 1 is an orange wall and 0 is a black void:


The red line is how the path should be laid. And white as it is laid.

The code can be taken from https://github.com/StanislavPetrovV/Python-Dijkstr... file bfs_pygame_control.py

Answer 1

To solve the problem, I used the Lee algorithm to build a displacement map, then I used graphs to find all paths, and then I found all paths with a minimum number of turns. I got everything in 300 lines of code.

Answer 2

You need to start by finding the angle between the start and end points.
Here: L-shaped corner of the (lower left) square 9x9 (not along the edge of the red line, but one closer to the center!).
And already from it - to finish building to the starting and ending points.

Answer 3

Having found the path with the algorithm that successfully finds it now (if it is really capable of finding obstacle avoidance, for example), you can apply simple simplifications to it - replace two knees with their mapping so that at least one of them becomes a continuation of the previous knee, and the number of bends decreases . Unless, of course, obstacles do not interfere with this. On this map, you will come to the same three bends.

Answer 4

Non-optimized algorithm (to understand the essence): We
sort through all possible ways to achieve the goal. We count the number of steps. Since we need the fastest path, we are looking for the minimum number of steps. Now, among the set of found "imaginary" paths, we choose those paths that have the minimum number of turns. The answer will be any of those found in the end.
Can be slightly modified by counting immediately (steps + turns). Naturally, the turn will have a weight greater than the weight of 1 step. For example, 10 times more to emphasize the importance of turns, that they are in priority. Then the distance will be calculated according to the formula:
S = steps + 10 * turns
Obviously, with such a scheme, any extra turn will dramatically increase the distance. This will be the criterion for rejecting an unsuccessful path.
This idea can be integrated into an existing algorithm that you use, but depending on the type of algorithm you have, there may be nuances.

Answer 5

Looks like it's called Manhattan Distance.
As a pedestrian walks through the blocks.
By the way, the author is a bit cunning. There are two more paths with the same number of turns.
Should I search for everything? And how long does the author want to search until the problem has become purely combinatorial?

Answer 6

You need to build a tricky graph.
Firstly, all distances in the graph will not be one number, but a pair - in fact, the length of the path and the number of turns. When summing two lengths, add them component by component, when comparing, first compare the lengths, and then the number of turns. Theoretically, you can collapse everything back into a single number if you count 100000*<length> + <number of turns>. But there may be special effects if the paths are very complex and have more than 100,000 turns. Also, beware of overflow.
For each cell, make 4 vertices, which will mean that you are in this cell and "look" in one of the 4 sides.
Create 4 edges between adjacent directions with length {0, 1} (length 0 but 1 turn). From each vertex, also create an edge of length {1, 0} (length - 1, 0 turns) to the vertex in the adjacent cell with the same direction (from the "top" of the 4 vertices, make an edge to the "top" same vertex in the cell above .Similarly in the other three directions).
Now the shortest path in this graph will be what you need. There is still a question with initial final direction. You can add a "central" vertex to the initial and final cells, to which it is connected by edges of length {0, 1} (It is important to make 1 turn, otherwise it will be possible to spin in place through this central vertex). Think of this peak as "looking at the floor". You start in one cell, looking at the floor, and you need to end up in another cell, again looking at the floor. You can turn around in the cage, or move to the cage ahead of you.
Since there are already different edge lengths, breadth-first traversal will no longer search for the shortest distance. But you can use dijkstra/A*.
The implementation does not even need to store all the vertices and edges. It's just that now the vertex instead of {x, y} will be described by {x, y, d}. Instead of iterating over 4 directions [-1,0],[0,-1],[0,1],[1,0] - you make the transition {x+dx[d],y+dy[d], d} or change d to (d+1)%d and (d+3)%4. And in the queues you store not one number, but a pair of {length, turns}. For A*, you still need to figure out the remaining length - well, you take what you already have in length, and take 1 in terms of the number of turns if there are different directions at the beginning and end.
Playing with edge lengths and their comparisons, you can, for example, allow slightly longer paths if they have significantly fewer turns. (for example, you can go around the maze around the perimeter than a little shorter but zigzag walk inside). To do this, the length of the edge can be length*K+turns.
Since there are 4-5 times more vertices, this will run 4-5 times slower.