Stack Overflow community!
I'm working on a pathfinding problem within a 3x3 grid, where each cell has a variable cost based on its coordinates, and there are additional costs for making 90-degree turns. The goal is to find the shortest path between two points in this grid, considering both cell costs and turn penalties.
Here are the specific rules I'm working with:
Cell Cost: If (x+y)%2==0, the cell cost is 2; otherwise, it's 1. Turn Cost: If the path takes a 90-degree turn, the cost of the turn is equal to the cost of the cell where the turn occurs.
Obstacles: Some cells are obstacles and cannot be part of the path.
To tackle this, I've attempted to use Dijkstra's algorithm. I've also defined a function to detect turns in the path. This function tracks the parent of the current cell, the current cell itself, and the next cell to determine if a turn is made.
Despite this setup, I'm finding that the algorithm does not always return the optimal path. It seems like my approach to incorporating turn costs might be flawed, or perhaps there's a better way to structure this problem for Dijkstra's algorithm.
Questions:
How can I accurately incorporate the cost of 90-degree turns into the pathfinding algorithm?
Are there any improvements or adjustments I can make to my current implementation to ensure it finds the optimal path? I would greatly appreciate any guidance, suggestions, or insights on how to tackle this challenge. Thank you in advance for your help!
To incorporate the concept of turning costs, you could make a duplicate of all the cells (nodes). We could call these sets two planes, as if we have a three-dimensional representation. Both planes correspond to an axis of traversal (north-south, versus east-west), and the corresponding plane only has the connecting edges along the respective axis. As long as you walk "north", you remain on the "north-south plane" of the graph. If you want to make a turn, you cannot do that on that plane as there is no such edge. But instead every cell is connected with an edge to its "copy" on the other plane. That edge represents a turn. On the arrival plane you can now go east or west, as the corresponding edges are available there.
So in essence you build a new graph that has twice the number of nodes, and has its edges split over them. Extra edges are created to represent turns.
This graph has no special rules anymore: it is a standard weighted graph, and you can apply a standard Dijkstra search on it. Just keep in mind that the target now consists of two nodes: if you reach any of these two, the goal is achieved. The same can be true for the starting node: you can actually start at two nodes now, assuming that the choice to make your first move horizontally or vertically is not considered a "turn". But also that is not an issue: with Dijkstra's you can put those two nodes in the queue at the start of the loop.
Also, when you get the solution path from this search, you'd want to translate that back to the original grid, meaning that you reduce node pairs that represent a plane-switch to just one node, making the corresponding "turn" implicit.