java - A* 寻路问题

Question

我查阅了大量有关 A* 寻路的文章，在查看了伪代码之后，我尝试编写自己的代码。

我有一个 Node 类:

private int x, y;

//The cost of movement (g) and the heuristic (h)
private int g;

private Node parent;

public Node(int x, int y) {
    this.x = x;
    this.y = y;
}

public Node(int x, int y, Node parent) {
    this.x = x;
    this.y = y;
    this.parent = parent;
    this.g = parent.getG() + 1;
}

public boolean equals(Node node) {
    return (this.x == node.getX() && this.y == node.getY() && this.parent.equals(node.getParent()));
}

public int getX() {
    return x;
}

public void setX(int x) {
    this.x = x;
}

public int getY() {
    return y;
}

public void setY(int y) {
    this.y = y;
}

public Node getParent() {
    return parent;
}

public void setParent(Node parent) {
    this.parent = parent;
}

public int getF(Node goal) {
    return g + getH(goal);
}

public int getG() {
    return g;
}

public void setG(int g) {
    this.g = g;
}

public int getH(Node goal) {
    int dx = Math.abs(this.x - goal.getX());
    int dy = Math.abs(this.y - goal.getY());
    return (dx + dy);
}

}

寻路:

public Path getPath(Node start, Node goal) {
    ArrayList<Node> openset = new ArrayList<Node>();
    ArrayList<Node> closedset = new ArrayList<Node>();

    //Add current position to open set
    openset.add(start);

    while(!openset.isEmpty()) {
        //Current node = node with lowest F score
        Node current = getNodeWithLowestScore(openset, goal);
        closedset.add(current);
        openset.remove(current);

        if(closedset.contains(goal)) {
            System.out.println("PATH FOUND.");
            break;
        }

        ArrayList<Node> adjacentNodes = getAdjacentNodes(current, closedset);

        for(Node n : adjacentNodes) {
            if(closedset.contains(n)) {
                continue;
            }

            if(!openset.contains(n)) {
                n.setParent(current);
                openset.add(n);
            }else{
                if(n.getF(goal) > (current.getG() + n.getH(goal))) {
                    n.setParent(current);
                }
            }
        }
    }
    return null;
}

public Node getNodeWithLowestScore(ArrayList<Node> openset, Node goal) {
    Node lowest = openset.get(0);

    for(int i = 0; i < openset.size(); i++) {

        Node n = openset.get(i);
        int nscore = n.getF(goal);

        if(nscore < lowest.getF(goal)) {
            lowest = n;
        }
    }
    return lowest;
}

public ArrayList<Node> getAdjacentNodes(Node node, ArrayList<Node> closedset) {
    ArrayList<Node> nodes = new ArrayList<Node>();

    nodes.add(new Node(node.getX() + 1, node.getY(), node));
    nodes.add(new Node(node.getX() - 1, node.getY(), node));
    nodes.add(new Node(node.getX(), node.getY() + 1, node));
    nodes.add(new Node(node.getX(), node.getY() - 1, node));

    for(int i = 0; i < nodes.size(); i++) {
        if(nodes.get(i) == null || closedset.contains(nodes.get(i))) {
            nodes.remove(i);
        }
    }
    return nodes;
}

}

它不起作用，如果我打印出开集或闭集的大小，数字就会飙升得很高。我使用 30x30 2D 网格进行了测试，从 10, 10(开始)到 30, 30(目标)。

到目前为止我所做的更改:

getAdjacentNodes 方法 ->

    ArrayList<Node> nodes = new ArrayList<Node>();

    nodes.add(new Node(node.getX() + 1, node.getY(), node));
    nodes.add(new Node(node.getX() - 1, node.getY(), node));
    nodes.add(new Node(node.getX(), node.getY() + 1, node));
    nodes.add(new Node(node.getX(), node.getY() - 1, node));

    for(int i = 0; i < nodes.size(); i++) {
        int x = nodes.get(i).getX();
        int y = nodes.get(i).getY();
        if(!((x > 0 && x < 30) && (y > 0 && y < 30))) {
            nodes.remove(i);
        }
    }
    return nodes;
}

getPath 方法 -> (在 while(openset is notempty) 方法内)

        Node current = getNodeWithLowestScore(openset, goal);
        openset.remove(current);

        if(current.equals(goal)) {
            System.out.println("PATH FOUND.");
            break;
        }else{
            closedset.add(current);
            ArrayList<Node> adjacentNodes = getAdjacentNodes(current, closedset);

            for(Node n : adjacentNodes) {
                if(closedset.contains(n) && (n.getG() > current.getG())) {
                    n.setG(current.getG());
                    n.setParent(current);
                }else if(openset.contains(n) && (n.getG() > current.getG())) {
                    n.setG(current.getG());
                    n.setParent(current);
                }else{
                    openset.add(n);
                }
            }
        }
    }

Answer 1

您的主要问题是一个小细节

public boolean equals(Node node) {
    return (this.x == node.getX() && this.y == node.getY() 
         && this.parent.equals(node.getParent()));
}

结合

if(!openset.contains(n)) {
    n.setParent(current);
    openset.add(n);
}

这很难发现，我花了一段时间才弄清楚。

ArrayList<>().contains(Object o) 内部使用(在 indexOf 的帮助下)方法 Object().equals(Object o) ，需要 Object作为参数。

您的Node().equals(Node n)方法使用 Node参数，因此不会覆盖 Object().equals(Object o)您想要覆盖的方法。

要解决此问题，您应该将方法更改为:

public boolean equals(Object o) {
    if(!(o instanceof Node)) return false;
    return (this.x == node.getX() && this.y == node.getY() 
         && this.parent.equals(node.getParent()));
}

我不知道你的代码是否还有更多问题，因为我不知道你如何调用它以及你的 Path 类是什么样子等等。我尝试从 (0, 0) 到 (3, 2)，至少它终止了，并且修复后大小似乎更小。

我调用 Node().getParent() 时发生了一些 NullPointerExceptions不过，也许你应该看看。例如在您的equals(Object o)中this.parent可能为空，您应该事先检查一下。

祝你好运!