java - Android A *路径查找无限循环？

我迈出了大胆的一步，试图学习这个算法，并在我的游戏中实现它，“理解”它是很容易的一部分。在尝试实现它的过程中，我不断得到一个不退出的无限循环我一遍又一遍地浏览我的代码，但我一定是遗漏了一些东西，或者是不理解其中的一部分。任何帮助都将不胜感激。

public class PathFinder {
private LinkedList<Node> openList;
private LinkedList<Node> closedList;

public PathFinder() {
    openList = new LinkedList<Node>();
    closedList = new LinkedList<Node>();
}

private List<Node> buildPath(Node node) {
    LinkedList<Node> path = new LinkedList<Node>();
    while (node.parentNode != null) {
        path.addFirst(node);
        node = node.parentNode;
    }
    return path;
}

public List<Node> findPath(int sx, int sy, int dx, int dy) {
    Node startNode = new Node(sx, sy);
    Node endNode = new Node(dx, dy);
    startNode.costG = 0;
    startNode.costH = startNode.getManhattanCost(endNode);
    startNode.parentNode = null;
    openList.add(startNode);

    while (!openList.isEmpty()) {
        Node currentNode = (Node) openList.removeFirst();
        if (currentNode == endNode) {
            Log.d("android", "found path");
            return buildPath(endNode);
        } else {
            currentNode.createNeighbors();
            List<Node> neighbors = currentNode.getNeighbors();
            for (int i = 0; i < neighbors.size(); i++) {
                Node neighborNode = neighbors.get(i);
                neighborNode.costG += currentNode.costG;
                neighborNode.costH = neighborNode.getManhattanCost(endNode);
                neighborNode.costF = neighborNode.costG + neighborNode.costH;
                boolean isInOpen = openList.contains(neighborNode);
                boolean isInClosed = closedList.contains(neighborNode);

                if ((!isInOpen && !isInClosed) || neighborNode.costG < currentNode.costG) {
                    neighborNode.parentNode = currentNode;
                    neighborNode.costG += currentNode.costG;
                    neighborNode.costF = neighborNode.costG + neighborNode.costH;
                    if (isInClosed) {
                        closedList.remove(neighborNode);
                    }
                    if (!isInOpen) {
                        openList.add(neighborNode);
                    }
                }
            }
            closedList.add(currentNode);
        }
    }
    openList.clear();
    closedList.clear();
    return null;
}

}

public class Node {
public Node parentNode;
public List<Node> neighbors;
public int x;
public int y;
public int costG;
public int costH;
public int costF;

public Node(int x, int y) {
    this.x = x;
    this.y = y;
    neighbors = new ArrayList<Node>();
    costG = 10;
}

public void createNeighbors() {
    neighbors.add(new Node(x + 1, y));
    neighbors.add(new Node(x, y + 1));
    neighbors.add(new Node(x - 1, y));
    neighbors.add(new Node(x, y - 1));
}

public int getManhattanCost(Node node) {
    int i = (int) Math.abs(x - node.x);
    int j = (int) Math.abs(y - node.y);
    costH = i + j;
    return costH;
}

public int getTotalCost() {
    return costG + costH;
}

public List<Node> getNeighbors() {
    return neighbors;
}

}
sx、sy、dx和dy是2d数组中的起始位置和目标位置。
为了测试目的，我通过了int固定数sx=1，sy=1，dx=5，dy=5。换句话说，字符在（1，1）处，接触点在（5，5）处。

最佳答案

你遗漏了一件事，那就是你的openlist是由costf订购的。
另外，您要将2个节点对象与==进行比较，此时您应该与等于进行比较。也许这就是为什么你永远达不到目标…