A *算法當前節點向外擴展而不是單向

Question

黃色圓圈表示起始節點，紅色圓圈表示目標節點。我不明白爲什麼我的當前節點向外擴展，而不是下面的節點剛剛直接進入目標的圖像。

我這個指南目前以下http://www.policyalmanac.org/games/aStarTutorial.htm

我不能讓這部分進入我的頭我應該如何以G選擇一個更好的路徑。它表示，較低的G成本意味着更好的路徑。但是我應該比較哪個節點與較低的G成本？

如果它已經在打開的列表中，請檢查該方向的路徑是否更好，並使用G成本作爲度量值。較低的G成本意味着這是一條更好的路徑。如果是這樣，請將正方形的父母更改爲當前正方形，然後重新計算正方形的G和F分數。

我的期望輸出應該是這樣的。

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

我認爲你有問題獲得最低成本：

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 e lowestCost = 0但fCost總是大於0，所以這個函數並不是真正的工作。它從最初的lowestCost獲得最低成本，而不是從fCost開放清單中獲得。嘗試在開放列表中以大數字或首位值啓動lowestCost。