java - A*算法当前节点向外扩散而不是一个方向

Question

黄色圆圈表示起始节点，红色圆圈表示目标节点。我不明白为什么我当前的节点向外扩散，而不是下面的节点直接进入目标的图像。

我目前正在遵循本指南 Link

关于如何使用 G 成本选择更好的路径，我只是无法理解这一部分。它说较低的 G 成本意味着更好的路径。但是我应该将哪个节点与较低的 G 成本进行比较？

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square.

我想要的输出应该是这样的。

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;
}

我的节点类

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);
}

你启动了lowestCost = 0但是fCost总是大于0，所以这个函数并没有真正起作用。它使最低成本从初始lowestCost 中获得，而不是从fCost open 列表中获得。尝试用大数字或开放列表中的第一个值启动 lowestCost。