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

In this example, 1 is the orange wall and 0 is the black void:
5fa044698a457815018169.png


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

The code can be taken from https://github.com/StanislavPetrovV/Python-Dijkstr... bfs_pygame_control.py file
by
By directed brute force. By the way, the problem does not always have a single solution. Your example is an example of multiple possible solutions.

6 Answers

0 votes
by
 
Best answer
To solve the problem, I used the Lie algorithm to build a movement map, then used graphs to find all the paths, and then found all the paths with the minimum number of turns. I ended up with 300 lines of code.
0 votes
by
It seems to be called Manhattan Distance.
As a pedestrian walks the blocks.

By the way, the author is a bit tricky. There are two more paths with the same number of turns.

Is it necessary to search for everything? And how long does the author want to search before the problem becomes purely combinatorial?
by
There are two more tracks with the same number of turns.

I counted twelve path options with three turns.
Maybe I missed some.
0 votes
by
You have to build a dodgy graph.

First, all distances in the graph will not be one number, but a pair - the actual path length and the number of turns. When summing the two lengths, add them one by one, and when comparing them, compare the lengths first, and then the number of turns. Theoretically, you can collapse everything back into one number if you count 100000* + . But there can be special effects if the paths are very complex and have more than 100000 turns. Also, beware of overflow.

For each cell, make 4 vertices, which will mean that you are in that cell and "looking" to 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 neighboring cell with the same direction (from the "top" of 4 vertices make an edge to the "top" vertex in the top cell. Similarly for the other three directions).

Now the shortest path in this graph will be what you need. There is also an issue with the initial endpoints. You can add a "central" vertex to the start and end cells, which is connected by edges of length {0, 1} (it is important to make 1 turn, otherwise you can twist in place through this central vertex). Think of this vertex as "looking at the floor." You start in some 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 in front of you.

Since there are already different edge lengths here, traversing the width will no longer look for the shortest distance. But you can use dextra/A*.

The implementation doesn't even need to store all vertices and edges. You just have a vertex described by {x, y, d} instead of {x, y, d}. Instead of trying 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 you don't keep a single number in the queues, but a pair of {length, turns}. For A* you still need to estimate the remaining length - well you take the length you already have, and take 1 for the number of turns if the beginning and end have different directions.

By playing with the lengths of the edges and their comparisons you can, for example, allow slightly longer paths if they have a lot fewer turns. (e.g. you can go around the perimeter of the maze than a slightly shorter but zig-zag path inside). To do this, the length of the edge can be length*K+turns.

Since there are 4-5 times as many vertices here, it will be 4-5 times slower.
0 votes
by
Unoptimized algorithm (to understand the point):
We go through all the possible ways to achieve the goal. Count the number of steps. Since we need the fastest way, we are looking for the minimum number of steps. Now among the set of found "minimal" paths choose those paths that have the minimum number of turns. The answer will be any of those found in the end.

You can modify it a bit by counting at once (steps + turns). Naturally, the turn will have more weight than the weight of 1 step. For example, 10 times more, to emphasize the importance of turns, that they are a priority. Then the distance will be counted by the formula:
S = steps + 10 * turns
Obviously, with this layout, any extra turn will dramatically increase the distance. This will be the criterion for culling the unsuccessful path.

This idea can be integrated into the existing algorithm you use, but it depends on the type of your algorithm, there may be nuances.
by
We go through all kinds of ways to achieve the goal.


Do you know how many there are? The number of combinations of W+H by H, where W,H are map sizes. And this is only the shortest paths. And you can also zigzag... In short, it is VERY much.

Bad idea. This is the task of finding the shortest path. It has been solved a thousand times in computer science. Only when you read "shortest path" you should immediately think of graph theory. And you don't have to build a bicycle, you just have to know the theory.
by
If the number of turns is more important than the length of the path, it is not certain that the shortest path with the minimum number of turns will have the minimum length.
0 votes
by
Having found the path with the algorithm that finds it successfully now (if it is really capable of finding a way around obstacles, for example), we 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 prevent this. On this map, you will arrive at the same three bends.
0 votes
by
Start by finding the angle between the start point and the end point.
Here: the L-shaped corner (bottom left) of the 9x9 square (not along the edge of the red line, but one closer to the center!)
And already from it - to build up to the starting and ending point.
...