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

Я думаю, что у вас есть проблемы, чтобы получить lowestcost:

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 с большим числом или первым значением в открытом списке.