<source lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class AStarMazeSolver {
private static final int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
public List<Coordinate> solve(Maze maze) {
LinkedList<Coordinate> frontier = new LinkedList<>();
Coordinate start = maze.getEntry();
Coordinate exit = maze.getExit();
frontier.add(start);
while (!frontier.isEmpty()) {
/*Считаю, что ошибка в следующей строчке, т.е. очередь у меня никогда не пустеет. */
Coordinate cur = BestHeuristic(frontier, exit);
if (!maze.isValidLocation(cur.getX(), cur.getY()) || maze.isExplored(cur.getX(), cur.getY())) {
continue;
}
if (cur.getParent() != null) {
if (maze.isPortal(cur.getX(), cur.getY())
&& !maze.isPortal(cur.getParent().getX(), cur.getParent().getY())) {
Coordinate pexit = maze.searchPortalExit(cur.getX(), cur.getY());
Coordinate coordinate = new Coordinate(pexit.getX(), pexit.getY(), cur);
frontier.add(coordinate);
maze.setVisited(cur.getX(), cur.getY(), true);
continue;
}
}
if (maze.isWall(cur.getX(), cur.getY())) {
maze.setVisited(cur.getX(), cur.getY(), true);
continue;
}
else if (maze.isExit(cur.getX(), cur.getY())) {
return backtrackPath(cur);
}
for (int[] direction : DIRECTIONS) {
Coordinate coordinate = new Coordinate(cur.getX() + direction[0], cur.getY() + direction[1], cur);
frontier.add(coordinate);
maze.setVisited(cur.getX(), cur.getY(), true);
}
}
return Collections.emptyList();
}
/**
* здесь я просто вычисляю эвристику
*
* @param c1
* Актуальная координата
* @param exit
* Координата выхода
* @return
*/
private int calculateAbsolutHeuristic(Coordinate c1, Coordinate exit) {
return backtrackPath(c1).size() + c1.getHeuristic();
}
/**
* А здесь я вычисляю пройденный путь, просто прохожу по всем родителям до старта.
*
* @param cur
* Актуальная координата
* @return
*/
private List<Coordinate> backtrackPath(Coordinate cur) {
List<Coordinate> path = new ArrayList<>();
Coordinate iter = cur;
while (iter != null) {
path.add(iter);
iter = iter.parent;
}
return path;
}
/**
* В этом методе я получаю очередь клеток, для которых буду рассматривать следующий ход, и координаты выхода, после чего я возвращаю куда надо двигаться.
*/
private Coordinate BestHeuristic (List<Coordinate> frontier, Coordinate exit){
Coordinate NextToGo = frontier.get(0);
for (int i=1; i<frontier.size(); i++) {
if (calculateAbsolutHeuristic(NextToGo, exit) > calculateAbsolutHeuristic(frontier.get(i), exit)) {
NextToGo = frontier.get(i);
}
}
return NextToGo;
}
}
</source>
Простой
