Как реализовать A star на Java для лабиринта в виде текста из ASCII-символов?

Question

[Sergei Zhilinski]

Добрый день. Я пытаюсь сделать реализацию поиска пути A-Star на Java для лабиринта, который подаётся как txt-Файл. На текущий момент у меня получилось реализовать DFS и BFS, а вот с A-Star я встрял.
Теоретически - я понимаю, я где-то накосячил с репрезентацией алгоритма, и спрашиваю помощи.
Код под спойлером.

spoiler

<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>

Answer 1

[Sergei Zhilinski]

Сам задал вопрос, сам ответил.
ошибки у меня были глупые, я просто нарушил часть алгоритма:
1.

spoiler

<source lang="java">
      /*Считаю, что ошибка в следующей строчке, т.е. очередь у меня никогда не пустеет. */
			Coordinate cur = BestHeuristic(frontier, exit);
</source>

должно быть как и в BFS:

spoiler

<source lang="java">
			Coordinate cur = frontier.remove();
</source>

2. А вот цикл for очень отличается. Было:

spoiler

<source lang="java">
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);
			}
</source>

Стало:

spoiler

<source lang="java">
for (int[] direction : DIRECTIONS) {
				Coordinate coordinate = new Coordinate(cur.getX() + direction[0], cur.getY() + direction[1], cur);

				if (frontier.indexOf(coordinate) >= 0 || closed.indexOf(coordinate) >= 0 && backtrackPath(coordinate).size()<backtrackPath(cur).size()) {
				//diesen Fall machen wir nix
				}
				else {
					coordinate.parent = cur;
				if (closed.indexOf(coordinate) >= 0) {
					closed.remove(coordinate);
				}
				if (frontier.indexOf(coordinate) < 0 ) {
					frontier.add(coordinate);
				}
				}
				//BestHeuristic(frontier, exit)
				frontier.add(coordinate);
				maze.setVisited(cur.getX(), cur.getY(), true);
			
</source>

Был бы внимательней сразу, то и сам бы заметил.