How to implement A star in Java for maze as text from ASCII characters?

S

Sergei Zhilinski2018-11-16 20:14:26

Java

Sergei Zhilinski, 2018-11-16 20:14:26

Good afternoon. I'm trying to make an A-Star pathfinding implementation in Java for a maze that is served as a txt file. At the moment, I managed to implement DFS and BFS, but I stuck with A-Star.
Theoretically - I understand, I screwed up somewhere with the representation of the algorithm, and I ask for help.
Spoiler code.

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>

Reply

Answer the question

In order to leave comments, you need to log in

1 answer(s)

S

Sergei Zhilinski, 2018-11-16
@Julegg

Asked the question, answered it myself.
I made stupid mistakes, I just broke part of the algorithm:
1.

spoiler

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

should be like in BFS:

spoiler

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

2. But the for loop is very different. It was:

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>

It became:

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>

If I had been more careful, I would have noticed.