The optimal algorithm to solve this maze?
I am now stuck in a challenge that our lecturer gave us at our university. We looked at the most popular pathfinding algorithms like Dijkstra and A *. Although, I think this exercise requires something different, and it puzzles me.
A visual representation of the maze that needs a solution:
Color Legend
Blue = start node
Gray = path
Green = destination node
The way it has to be solved is that when a movement is done, it has to be done until it hits the edge of the maze or an obstacle (black borders). This would also need to be solved in the least possible line moves (in this case 7)
My question is, could someone nudge me in the right direction on which algorithm to look at? I think that Dijkstra / A * cannot go, given that the shortest path is not always the correct path when asked.
source to share
It is still resolved with Dijkstra / A *, what needs to be changed is the neighbors config.
A little background, first:
Dijkstra and A * are general pathfinding algorithms formulated in graphs. When instead of a graph we have a symbol moving on a grid, it may not be so obvious when the graph is. But it still exists, and one way to plot the graph would be this:
- graph nodes correspond to grid cells
- there are edges between nodes corresponding to neighboring cells.
Actually, in most tasks related to some configurations and transitions between them, you can build an appropriate graph and apply Dijkstra / A *. In this way, problems like sliding puzzle , rubik cube , etc., which seem to be significantly different from the character moving on the grid , can also be solved . But they have states and transitions between states, so you can try graph search methods (these methods, especially uninformed ones, such as Dijkstra's algorithm, may not always be possible due to the large search space, but in principle it is possible to apply them).
In the problem you mentioned, the chart will not differ much from the one that has characteristic symbol movements:
- nodes can still be grid cells
- now there will be faces from node to nodes corresponding to actual motions (ending near a border or obstacle), which in this case will not always coincide with the four spatial immediate neighbors of the mesh cell.
As Tamas Hegedus pointed out in the comment section, it is not clear which heuristic should be selected if A * is used.
Standard heuristics based on Manhattan or Euclidean distance are not valid here as they may overestimate target distance.
One valid heuristic would be id (row! = Destination_row) + id (col! = Destination_col), where id is the identity function, with id (false) = 0 and id (true) = 1.
source to share
Dijkstra / A * are accurate. You need to think carefully about what you think of as graphs and graphs.
In the blue box (let's call it 5,5
) you have three valid moves:
-
move one cell to the right (before
6,5
) -
move four cells to the left (before
1,5
) -
move five cells up (up
5,1
)
Please note that you cannot switch from 5,5
to 4,5
or 5,4
. Apply the same reasoning to new nodes (for example, from 5,1
you can go to 1,1
, 10,1
and 5,5
) and you have a graph where you run your Dijkstra / A *.
source to share
You need to evaluate every possible move and make a move that is minimal. Something like the following:
int minDistance(int x, int y, int prevX, int prevY, int distance) {
if (CollionWithBorder(x, y) // can't take this path
return int.MAX_VALUE;
if (NoCollionWithBorder(x, y) // it OK to take this path
{
// update the distance only when there is a long change in direction
if (LongDirectionChange(x, y, prevX, prevY))
distance = distance + 1;
)
if (ReachedDestination(x, y) // we're done
return distance;
// find the path with the minimum distance
return min(minDistance(x, y + 1, x, y, distance), // go right
minDistance(x + 1, y, x, y, distance), // go up
minDistance(x - 1, y, x, y, distance), // go down
minDistance(x, y - 1, x, y, distance)); // go left
}
bool LongDirectionChange(x, y, prevX, prevY) {
if (y-2 == prevY && x == prevX) ||(y == prevY && x-2 == prevX)
return true;
return false;
}
This assumes that no diagonal movements are allowed. If they are, add them to the min () call:
minDistance(x + 1, y + 1, distance), // go up diagonally to right
minDistance(x - 1, y - 1, distance), // go down diagonally to left
minDistance(x + 1, y - 1, distance), // go up diagonally to left
minDistance(x - 1, y + 1, distance), // go down diagonally to right
source to share