'Shortest path maze solving algorithm
I have this method that solves the first possible path in a 2D maze matrix (works fine)
public boolean findFirstPath() {
boolean found = false;
path = new ArrayList<Coordinate>(); // restarts the path in case the algorithm has been solved previously
Coordinate coor = new Coordinate();
coor.i = startI; coor.j = startJ; coor.direction = 0; // instance of the first Coordinate object
path.add(coor); // the first coordinate is added to the path
while (!found && path.size() > 0) {
path.get(path.size()-1).direction++; // accesses the last element and increments the direction by 1
if (path.get(path.size()-1).direction <= 4) {
Coordinate coor_next = setNextCell(path.get(path.size()-1)); // we assign the last element of the path
if (isValidSpot(coor_next)) {
path.add(coor_next); // add to the path the valid cell
if (coor_next.i == endI && coor_next.j == endJ) { // if it reaches the end
found = true;
}
}
} else { // if it has checked all 4 directions go back
path.remove(path.size()-1); // deletes the last position in backtracking
}
}
return found;
}
I need to make modifications to find the shortest possible path and I can't find an optimal solution, I've tried something like this:
public boolean findShortestPath() {
boolean found = false;
int steps = 0;
path = new ArrayList<Coordinate>();
ArrayList<Coordinate> shortest = new ArrayList<Coordinate>(); // arrayList where the shortest path will be stored
Coordinate coor = new Coordinate();
coor.i = startI; coor.j = startJ; coor.direction = 0;
path.add(coor);
while (!found && path.size() > 0) {
path.get(path.size()-1).direction++;
if (path.get(path.size()-1).direction <= 4) {
Coordinate coor_next = setNextCell(path.get(path.size()-1));
if (isValidSpot(coor_next)) {
steps++;
if (steps < path.size()) {
shortest.add(path.get(path.size()-1));
} else {
path.add(coor_next);
}
if (coor_next.i == endI && coor_next.j == endJ) {
found = true;
}
}
} else {
path.remove(path.size()-1);
}
}
return found;
}
but it does not even enter the if (steps < path.size()) comprobation, any suggestions? Thanks.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
