A *アルゴリズム現在のノードが一方向ではなく外側に広がる

Question

黄色の円は開始ノードを示し、赤色の円は目標ノードを示しています。なぜ私の現在のノードが、ノードがちょうど目標に向かっているところの下の画像の代わりに外側に広がっているのか理解できません。

私は現在、このガイドにhttp://www.policyalmanac.org/games/aStarTutorial.htm

を以下のよ、私はちょうど私がGのコストを使用して、より良い道を選ぶべきかに私の頭の中にこの部分を取得することはできません。 Gコストが低いことは、より良い道を意味すると言われています。その低Gコストとどのノードを比較すればよいですか？

既にオープンリストにある場合は、このコストが対策としてGコストを使用しているかどうかを確認してください。 Gのコストが低いことは、これがより良い経路であることを意味します。その場合は、正方形の親を現在の正方形に変更し、正方形のGとFのスコアを再計算します。

私の所望の出力は次のようにする必要があります。

private Node getLowestFCost(List<Node> open) { 
    int lowestCost = 0; 
    int index = 0; 
    for (int i = 0; i < open.size(); i++) { 
     if (open.get(i).fCost <= lowestCost) { 
      lowestCost = open.get(i).fCost; 
      index = i; 
     } 
    } 
    return open.get(index); 
} 

あなたはinitiat：私はあなたがlowestcostを得るために問題を抱えていると思います

public class AStar { 

private List<Node> open = new ArrayList<Node>(); 
private List<Node> close = new ArrayList<Node>(); 
private Node[][] nodes; 
private GIS gis; 
private MapListener mapListener; 
private Arrow arrow; 

public AStar(GIS gis) { 
    this.gis = gis; 
    mapListener = new MapListener(this); 
    createMapNodes(); 
} 

private void createMapNodes() { 
    nodes = new Node[gis.getUslMap().getTileWidth()][gis.getUslMap().getTileHeight()]; 
    for (int x = 0; x < gis.getUslMap().getTileWidth(); x++) { 
     for (int y = 0; y < gis.getUslMap().getTileHeight(); y++) { 
      TiledMapTileLayer.Cell cell = gis.getUslMap().getPathLayer().getCell(x, y); 

      arrow = new Arrow(); 
      nodes[x][y] = new Node(cell, arrow, x, y); 

      if (cell != null) { 
       nodes[x][y].setBounds(x * Map.TILE.getSize(), y * Map.TILE.getSize(), Map.TILE.getSize(), Map.TILE.getSize()); 
       nodes[x][y].getLabel().setBounds(x * Map.TILE.getSize(), y * Map.TILE.getSize(), Map.TILE.getSize(), Map.TILE.getSize()); 
       nodes[x][y].getArrow().getImage().setBounds(x * Map.TILE.getSize(), y * Map.TILE.getSize(), Map.TILE.getSize(), Map.TILE.getSize()); 

       mapListener = new MapListener(this); 
       nodes[x][y].addListener(mapListener); 

       gis.getUslMap().getStage().getActors().add(nodes[x][y].getLabel()); 
       gis.getUslMap().getStage().getActors().add(nodes[x][y].getArrow().getImage()); 
       gis.getUslMap().getStage().addActor(nodes[x][y]); 
       nodes[x][y].debug(); 
      } 
     } 
    } 
} 

private void clearNodes() { 
    for (int x = 0; x < gis.getUslMap().getTileWidth(); x++) { 
     for (int y = 0; y < gis.getUslMap().getTileHeight(); y++) { 
      nodes[x][y].gCost = 0; 
      nodes[x][y].hCost = 0; 
      nodes[x][y].fCost = 0; 
      nodes[x][y].getLabel().setText(""); 
      nodes[x][y].getArrow().setDrawable("blank"); 
     } 
    } 
    close.clear(); 
    open.clear(); 
} 

public void search(Vector2 start, Node goal) { 
    clearNodes(); 
    Node current = nodes[(int) start.x][(int) start.y]; 
    open.add(current); 

    while (!open.isEmpty()) { 
     current = getLowestFCost(open); 

     if (current == goal) 
      return; 
     open.remove(current); 
     close.add(current); 
     // Prints the Fcost. 
     current.getLabel().setText(current.fCost + ""); 

     // Detect the adjacent tiles or nodes of the current node 
     // and calculate the G, H and F cost 
     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 (isValidLocation(dx, dy)) { 
        if (isWalkable(x, y, nodes[dx][dy])) 
         continue; 

        if (!open.contains(nodes[dx][dy])) { 
         open.add(nodes[dx][dy]); 
         nodes[dx][dy].parent = current; 
         if (isDiagonal(x, y)) 
          nodes[dx][dy].gCost = current.gCost + 14; 
         else 
          nodes[dx][dy].gCost = current.gCost + 10; 

         nodes[dx][dy].fCost = nodes[dx][dy].gCost + heuristic(nodes[dx][dy], goal); 

        } else if (open.contains(nodes[dx][dy])&&) { 

        } 
       } 
      } 
     } 
    } 
} 

private boolean isWalkable(int x, int y, Node node) { 
    return x == 0 && y == 0 || node.getCell() == null || close.contains(node); 
} 

private boolean isValidLocation(int dx, int dy) { 
    return dx > 0 && dx < gis.getUslMap().getTileWidth() && 
      dy > 0 && dy < gis.getUslMap().getTileHeight(); 
} 

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

private Node getLowestFCost(List<Node> open) { 
    int lowestCost = 0; 
    int index = 0; 
    for (int i = 0; i < open.size(); i++) { 
     if (open.get(i).fCost <= lowestCost) { 
      lowestCost = open.get(i).fCost; 
      index = i; 
     } 
    } 
    return open.get(index); 
} 

private int heuristic(Node start, Node goal) { 
    int dx = Math.abs(start.x - goal.x); 
    int dy = Math.abs(start.y - goal.y); 
    start.hCost = 10 * (dx + dy); 
    return start.hCost; 
} 

}

マイnode.class

private TiledMapTileLayer.Cell cell; 
private Label label; 
private Arrow arrow; 
boolean diagonal; 
Node parent; 
int x; 
int y; 
int hCost; 
int gCost; 
int fCost; 

public Node(TiledMapTileLayer.Cell cell, Arrow arrow, int x, int y) { 
    this.cell = cell; 
    this.x = x; 
    this.y = y; 
    this.arrow = arrow; 
    label = new Label("", Assets.getInstance().getMapAsset().getAssetSkin(), "default"); 
    label.setPosition(this.getX(), this.getY()); 
} 


TiledMapTileLayer.Cell getCell() { 
    return cell; 
} 

Label getLabel() { 
    return label; 
} 

public Arrow getArrow() { 
    return arrow; 
} 

Answer 1

e lowestCost = 0しかし、fCostは常に0より大きいので、この関数は実際には機能しません。それはfCostオープンリストからではなく、最初のlowestCostから得られる最も低いコストを作ります。開いているリストで大きい番号または最初の値を持つlowestCostを開始しようとします。