Extension for Pathfinding - the path of least turns
First, I want to thank someone for taking the time to look at this. Many of us are familiar with Dijkstra's algorithm and thus A *. I have used A * in many applications, but for this particular case I have a very difficult time coming up with an algorithm. This case involves finding the path with the least number of turns. In fact, I don't even care about the "shortest" path, only the one that has the smallest turns! I am working with an up-down-left-right grid, no diagonals, which means there are many possible solutions for the shortest path.For example, in a 5x5 grid with a starter at the bottom left and in the top right corner we can make a ladder case or go all the way right, then all the way (best for me!).
With A * you are using Cost = DistanceFromStart + Heuristic (Manhattan) and I tried to expand it by adding the cost of numTurns. This works fine until I move on to the next one:
| 0 0 0 0 0 * 0 0
| 0 0 1 '2' + 0 0 E
| 0 0 S 1 2 * 0 0
| 0 0 0 0 0 * 0 0
| 0 0 0 0 0 * 0 0
Please excuse the bad formatting, I hope you can see what I intended.
* - walls, 0 empty, S - start, and E - end. You will see that the path S-> 1-> 2 → + will give the same cost as s-> 1 '-> 2' → +. They both have one turn so far, the same distance from S, and the same Manhattan. However, from +, if we took route (), we don't need to turn. But if we took route 1 2, we must turn right (+1 cost). So, although we can get there first from 1 2, this is not the least twists and turns.
I've tried adjustments such as allowing several of the same square to be in the priority queue at once, so they both get a chance (if their values are minimal on the heap). I have tried other other "hacked" solutions but I keep getting cases where they arent closed. Does anyone know an intuitive way to do this? Again, I'll try to ask a question that I can:
Given a grid with up and down movement along the left edge and obstacles, how can I find the path of the smallest turns from A to B. I don't need the guarantee of the shortest distance. The app is a bot for a game that connects tiles and tiles can only be removed if they are less than three times. Thanks again for everyone who can help!
source to share
I think you need to include "direction" in your state. When you reach "+" with 1-> 2 → +, you are faced with “up”, and when you reach “+” with 1 '-> 2' → +, you are “on the right”.
You can then include the cost of changing direction in your cost. That is, the cost of a trip from one state to another. Now, going to 1-> 2 → +, when estimating movement to the right, the cost of changing direction will be taken into account, and 1 '-> 2' → + will not be.
When you go into the "generate children" phase of your A *, you are probably only increasing the "cost-so-far" by 1, the number of gridcells it took to go to the neighbor. You also need to add 1 if the direction of the neighbors to your current position is! = Current direction.
For starters, you can use some special directional direction, such as OMNIDIRECTIONAL, so there is no cost to jump to any square from the starting position.
source to share