java - A*寻路算法。运动成本和启发式不准确

Question

我的问题是我的节点和启发式的移动成本(G 成本)不准确，它与图片不符。

这是我正在关注的图像。这里有三个标签，移动成本标签在左下角，启发式标签在右下角。左上角的标签是 F = H + G

这是我的输出。如您所见，移动成本与所需输出不同。红圈为目标节点。

我的启发式成本也一样。

public class AStarPathFinder implements PathFinder {

private List<Node> open = new ArrayList<Node>();
private List<Node> close = new ArrayList<Node>();
private Node[][] nodes;

private TileMap map;
private Heuristic heuristic;

public AStarPathFinder(TiledMapStage mapStage, Heuristic heuristic) {
    this.heuristic = heuristic;
    nodes = mapStage.getNodes();
    map = mapStage.getMap();
}

@Override
public Path findPath(int startX, int startY, int goalX, int goalY) {
    clearNodes();

    Node goal = nodes[goalX][goalY];
    Node current = nodes[startX][startY];

    open.add(current);
    while (!open.isEmpty()) {

        current = getLowestFcost(open);
        open.remove(current);
        close.add(current);

        if (current == goal) {
            Path path = new Path();
            while (current != null) {
                path.add(current);
                current = current.parent;
            }
            return path;
        }
        // neighbors of current
        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 (map.isValidLocation(dx, dy)) {
                    if (!map.isWalkable(nodes[dx][dy], x, y) || close.contains(nodes[dx][dy]))
                        continue;

                    float newScore = movementCost(current.g, isDiagonal(x, y));
                    if (!open.contains(nodes[dx][dy])) {
                        open.add(nodes[dx][dy]);
                    } else if (newScore >= nodes[dx][dy].g) continue;

                    nodes[dx][dy].g = newScore;
                    nodes[dx][dy].h = heuristic.estimate(nodes[dx][dy], goal);
                    nodes[dx][dy].f = nodes[dx][dy].g + nodes[dx][dy].h;
                    nodes[dx][dy].parent = current;
                    nodes[dx][dy].label.setText((int) nodes[dx][dy].g + "");
                }
            }
        }
    }
    return null;
}

private Node getLowestFcost(List<Node> open) {
    Node lowestNode = open.get(0);
    for (int i = 0; i < open.size(); i++) {
        if (open.get(i).f <= lowestNode.f && open.get(i).h < lowestNode.h) {
            lowestNode = open.get(i);
        }
    }
    return lowestNode;
}

private boolean isDiagonal(int x, int y) {
    return (x == -1 && y == 1 ||
            x == 1 && y == 1 ||
            x == 1 && y == -1 ||
            x == -1 && y == -1);
}

private float movementCost(float cost, boolean diagonal) {
    return diagonal ? cost + 14 : cost + 10;
}

@Override
public void clearNodes() {
    for (int i = 0; i < map.getTileWidth(); i++) {
        for (int j = 0; j < map.getTileHeight(); j++) {
            if (nodes[i][j].cell != null) {
                nodes[i][j].label.setText("");
                nodes[i][j].f = 0;
                nodes[i][j].h = 0;
                nodes[i][j].g = 0;
                nodes[i][j].arrow.setDrawable("cursor");
                nodes[i][j].arrow.setVisible(false);
                nodes[i][j].parent = null;
            }
        }
    }
    close.clear();
    open.clear();
}
 }

这是 pseudocode我正在关注。我的启发式也是 diagonal distance

Answer 1

看起来您的问题出在 TileMap map 变量的 isWalkable 方法中。

您所关注的图像不允许沿墙对角线通过，而您的算法却可以。

您可以看到这一点，因为分数加上 14，如下所示:14 + 14 = 28。而您预期的结果如下:14 + 10(先下)+ 10(向右)= 34。

希望我能清楚地解释您的问题。我不知道您对 isWalkable 的实现，所以我无法提供完整的解决方案，但我希望我已经为您指明了正确的方向。