Алгоритм поиска пути *. Стоимость движения и эвристика неточны

Question

Моя проблема в том, что стоимость движения (стоимость G) моего узла и эвристика неточна, она не соответствует изображению.

Вот изображение того, что я следую. Здесь есть три ярлыка, а стоимость движения обозначена в левом нижнем углу, а эвристика внизу справа. Ярлык в левом верхнем углу: F = H + G

Вот мой вывод. Поскольку вы можете видеть, что стоимость движения не совпадает с желаемой производительностью. Красный круг является узлом цели.

Кроме того, то же самое с моими Эвристическими стоимостями.

public class AStarPathFinder implements PathFinder { 

private List<Node> open = new ArrayList<Node>(); 
private List<Node> close = new ArrayList<Node>(); 
private Node[][] nodes; 

private TileMap map; 
private Heuristic heuristic; 

public AStarPathFinder(TiledMapStage mapStage, Heuristic heuristic) { 
    this.heuristic = heuristic; 
    nodes = mapStage.getNodes(); 
    map = mapStage.getMap(); 
} 

@Override 
public Path findPath(int startX, int startY, int goalX, int goalY) { 
    clearNodes(); 

    Node goal = nodes[goalX][goalY]; 
    Node current = nodes[startX][startY]; 

    open.add(current); 
    while (!open.isEmpty()) { 

     current = getLowestFcost(open); 
     open.remove(current); 
     close.add(current); 

     if (current == goal) { 
      Path path = new Path(); 
      while (current != null) { 
       path.add(current); 
       current = current.parent; 
      } 
      return path; 
     } 
     // neighbors of current 
     for (int x = -1; x < 2; x++) { 
      for (int y = -1; y < 2; y++) { 
       int dx = current.x + x; 
       int dy = current.y + y; 

       if (map.isValidLocation(dx, dy)) { 
        if (!map.isWalkable(nodes[dx][dy], x, y) || close.contains(nodes[dx][dy])) 
         continue; 

        float newScore = movementCost(current.g, isDiagonal(x, y)); 
        if (!open.contains(nodes[dx][dy])) { 
         open.add(nodes[dx][dy]); 
        } else if (newScore >= nodes[dx][dy].g) continue; 

        nodes[dx][dy].g = newScore; 
        nodes[dx][dy].h = heuristic.estimate(nodes[dx][dy], goal); 
        nodes[dx][dy].f = nodes[dx][dy].g + nodes[dx][dy].h; 
        nodes[dx][dy].parent = current; 
        nodes[dx][dy].label.setText((int) nodes[dx][dy].g + ""); 
       } 
      } 
     } 
    } 
    return null; 
} 

private Node getLowestFcost(List<Node> open) { 
    Node lowestNode = open.get(0); 
    for (int i = 0; i < open.size(); i++) { 
     if (open.get(i).f <= lowestNode.f && open.get(i).h < lowestNode.h) { 
      lowestNode = open.get(i); 
     } 
    } 
    return lowestNode; 
} 

private boolean isDiagonal(int x, int y) { 
    return (x == -1 && y == 1 || 
      x == 1 && y == 1 || 
      x == 1 && y == -1 || 
      x == -1 && y == -1); 
} 

private float movementCost(float cost, boolean diagonal) { 
    return diagonal ? cost + 14 : cost + 10; 
} 

@Override 
public void clearNodes() { 
    for (int i = 0; i < map.getTileWidth(); i++) { 
     for (int j = 0; j < map.getTileHeight(); j++) { 
      if (nodes[i][j].cell != null) { 
       nodes[i][j].label.setText(""); 
       nodes[i][j].f = 0; 
       nodes[i][j].h = 0; 
       nodes[i][j].g = 0; 
       nodes[i][j].arrow.setDrawable("cursor"); 
       nodes[i][j].arrow.setVisible(false); 
       nodes[i][j].parent = null; 
      } 
     } 
    } 
    close.clear(); 
    open.clear(); 
} 
} 

Вот pseudocode, что я следую. Также моя эвристика - diagonal distance

Answer 1

Похоже, ваша проблема в методе isWalkable вашей переменной TileMap map.

Изображение, за которым вы следуете, не позволяет проходить по диагонали вдоль стены, где работает ваш алгоритм.

Вы можете видеть это, потому что оценка добавляется с 14 следующим образом: 14 + 14 = 28. Пока вы ожидали, что она будет идти следующим образом: 14 + 10 (спускается сначала) + 10 (идет вправо) = 34.

Надеюсь, я четко объяснил вашу проблему. Я не знаю вашей реализации isWalkable, поэтому я не могу предоставить полное решение, но надеюсь, что я указал вам в правильном направлении.