Ответы пользователя по тегу Алгоритмы
  • Как реализовать A star на Java для лабиринта в виде текста из ASCII-символов?

    Julegg
    @Julegg Автор вопроса
    Сам задал вопрос, сам ответил.
    ошибки у меня были глупые, я просто нарушил часть алгоритма:
    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>



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