A *経路探索アルゴリズム。移動コストとヒューリスティックが不正です

Question

私の問題は、ノードとヒューリスティックの移動コスト（Gコスト）が不正確で、画像と一致しないことです。

私はここに3つのラベルがあり、移動コストは左下に、ヒューリスティックは右下に表示されています。左上のラベルは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

あなたの問題はTileMap map変数のisWalkableメソッドにあるようです。

あなたの画像は、あなたのアルゴリズムが行っている壁の横に斜めに通過することはできません。

スコアが14で追加されるため、14 + 14 = 28と表示されます。14 + 10（最初に下がる）+ 10（右に行く）= 34です。

私はあなたの問題をはっきりと説明したいと思います。私はあなたの実装がisWalkableであるかどうかわからないので、完全な解決策を提供することはできませんが、私はあなたに正しい方向を指摘して欲しいと思います。