A* График Поиск Хороший Эвристический

Question

Я реализую алгоритм поиска пути A* для простого лабиринта с несколькими выходами с различными расстояниями, однако я не могу найти подходящую эвристику, кажется, она выполняет поиск в ширину.

Стоимость изначально установлена ​​на 1

Вот моя попытка:

public void search(Node startNode, Node goalNode){
    System.out.println("Search Started");
    boolean found = false;
    boolean noPath = false;

    Queue<Node> open = new PriorityQueue<Node>(10,new Comparator<Node>(){

        @Override
        public int compare(Node t, Node t1) {
            return Double.compare(t.getCost(), t1.getCost());
        }
    });

    visited[startNode.getX()][startNode.getY()] = true;
    order[startNode.getX()][startNode.getY()] = 0;
    startNode.setCost(h(startNode, goalNode));
    open.add(startNode);

    while (found == false && noPath == false) {
        if (open.isEmpty()) {
            noPath = true;

        }else{

             Node current = open.remove();

            if(current.getX() == goalNode.getX() && current.getY() == goalNode.getY()){

                System.out.println("found Node");
                printOrder();
                found = true;
                break;


            }else{
                for (int i = 0; i < 4; i++){
                    Node nextNode = getAction(current.getX(),current.getY());
                    System.out.println("getting node:" + nextNode.getX() + " " + nextNode.getY());
                    int g2 = current.getCost()+cost+h(current, goalNode);
                    System.err.println(g2);
                    nextNode.setCost(g2);

                    if (nextNode.getX() != -1) {
                      count++;
                      visited[nextNode.getX()][nextNode.getY()] = true;
                      order[nextNode.getX()][nextNode.getY()] = count;
                      open.add(nextNode);

                    }
                }    
            }                
        }
    }
}

Эвристическая функция

public int h(Node current, Node goal){

    return (goal.getX() - current.getX()) + (goal.getY() - current.getY());

}

Помощь будет высоко ценится

Answer 1

Для типичного лабиринта - один выход, только один путь, ширина пути =1 - A* не имеет преимущества перед шириной в первую очередь. Эта разница видна только для карт, как вы могли бы видеть в стратегических играх, где есть преимущество в том, чтобы пытаться идти в воздушном направлении цели, и где ранее пройденное расстояние имеет значение. Если хотите, посмотрите на другие алгоритмы:

https://en.wikipedia.org/wiki/Maze_solving_algorithm