我正在用 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;
}
}
这是它产生的路径:
如您所见,它不会选择最佳路径(几乎会)。任何人都可以在我的代码中看到任何明显的错误,还是您认为错误存在于其他地方?谢谢你的帮助。:)