-1

我正在用 Java 实现 A* 搜索算法，但它工作不正常。这是我的算法代码：

    public List<Tile> calculatePath(Tile start, Tile goal) {
    Node current = new Node(start, null, 0, getDistance(start, finish));
    openList.add(current);
    while (openList.size() > 0) {
        Collections.sort(openList, nodeSorter);
        current = openList.get(0);
        if (current.tile instanceof FinishTile) {
            List<Tile> path = new ArrayList<Tile>();
            while (current.parent != null) {
                path.add(current.tile);
                current = current.parent;
            }
            openList.clear();
            closedList.clear();
            return path;
        }
        openList.remove(current);
        closedList.add(current);
        for (int i = 0; i < 9; i++) {
            if (i == 4) continue;
            int x = current.tile.getX(Tile.TILE_PRECISION);
            int y = current.tile.getY(Tile.TILE_PRECISION);
            int xi = (i % 3) - 1;
            int yi = (i / 3) - 1;
            Tile at = getTile(x + xi, y + yi);
            if (at == null) continue;
            if (at instanceof WallTile || tileInList(closedList, at)) continue;
            if (!tileInList(openList, at)) openList.add(new Node(at, current, getDistance(start, at), getDistance(at, finish)));
        }
    }
    return null;
}

Node类如下：

public class Node {

public Tile tile;
public Node parent;
public final int fCost, gCost, hCost;

public Node(Tile tile, Node parent, int gCost, int hCost) {
    this.tile = tile;
    this.parent = parent;
    this.fCost = gCost + hCost;
    this.gCost = gCost;
    this.hCost = hCost;
}

}

这是它产生的路径：

一个明星

如您所见，它不会选择最佳路径（几乎会）。任何人都可以在我的代码中看到任何明显的错误，还是您认为错误存在于其他地方？谢谢你的帮助。:)

4

1 回答 1

0

显然，即使对角线移动与水平/垂直移动的成本相同，它也没有选择最好的方式。只需检查路径。对不起伙计

于 2013-07-31T19:56:30.307 回答