我在 Java 中实现 A* 算法时遇到问题，为什么它是无限的？

问题描述 投票：0回答：1

背景 - 我目前正在尝试在我的游戏中实现 A* 算法。我之前已经在标准网格风格游戏中做到了这一点，并设法让它工作，但由于某种原因，我在这里只能获得部分成功。我正在尝试将其实现到等距 2D 游戏中。我已经将所有内容从笛卡尔坐标转换为网格坐标，因此它可以与网格系统一起使用。

行为 - 最初，它有效。您可以一次毫无问题地移开约 6-8 个方块。小动作接连奏效。然而，如果超过这个数量，一切都会冻结。我已经确定这绝对是导致崩溃的路径查找。我认为该算法出于某种原因会出错，并偏离轨道，确定正确的路径成本太高。这很奇怪，因为我只使用 4 个相邻点，并且计算成本应该非常小，并且不会导致冻结。这也不是一个小冻结，冻结>30秒（我还没有等足够长的时间来看看它是否真的完成，因为我认为它走错了方向，而且永远不会）

要考虑的事情 - 由于该游戏的本质是等距的，并且从笛卡尔到网格的转换（反之亦然），所有内容都是浮点数而不是整数。然而，例如，当检查角色移动后的位置时，它始终处于适当的整数网格参考中（因此不存在“im at 1.9，check at 2.9”行为。由于我进行舍入，它始终为 int。另外，节点不是预先定义的。当从当前节点创建子节点时，节点是“动态”定义的。这是因为这个系统与游戏无关，我只关心角色必须获得的坐标列表基本上以所需的路径返回。

这是 A* 算法：

public class PathFinder {

private Node nodeStart;
private Node nodeGoal;
private float cost = 10f;


Set<Node> open = new HashSet<>();
Set<Node> closed = new HashSet<>();

public PathFinder(Node start, Node goal){
    this.nodeStart = start;
    this.nodeGoal = goal;
    open.add(nodeStart);
}

public List<Node> findPath(){

    while (!open.isEmpty()){
        Node currentNode = open.stream().min(Comparator.comparing(Node::getF)).get();
        open.remove(currentNode);
        closed.add(currentNode);
        if(currentNode.equals(nodeGoal)){
            return reversePath(currentNode);
        }
        else{
            for(Node child : getAdjacents(currentNode)){
                if(!child.isBlock() && !closed.contains(child)) {
                    child.setNodeData(currentNode, cost);
                    open.add(child);
                }
                else{
                    boolean changed = child.checkBetterPath(currentNode, cost);
                    if (changed) {
                        // Remove and Add the changed node, so that the PriorityQueue can sort again its
                        // contents with the modified "finalCost" value of the modified node
                        open.remove(child);
                        open.add(child);
                    }
                }
            };
        }

    }
    return new ArrayList<>();
}

private List<Node> getAdjacents(Node currentNode){
    ArrayList<Node> children =  new ArrayList<>();

    children.add(new Node(currentNode.getX()+1, currentNode.getY(), currentNode, nodeGoal));
    children.add(new Node(currentNode.getX()-1, currentNode.getY(), currentNode, nodeGoal));
    children.add(new Node(currentNode.getX(), currentNode.getY() - 1, currentNode, nodeGoal));
    children.add(new Node(currentNode.getX(), currentNode.getY() + 1, currentNode, nodeGoal));

    return children;
}

public List<Node> reversePath(Node goal){
    List<Node> finalPath = new ArrayList<>();
    Node tmp;
    Node current;
    current = goal;
    while(current.getParent() != null){
        finalPath.add(0, current);
        current = current.getParent();
    }
    return finalPath;
}}

这是我的节点类：

public class Node {

private boolean isBlock;
private Node parent;
private float x;
private float y;

private float g;
private float f;
private float h;

Node finalNode;

public Node(float x, float y){
    this.x = x;
    this.y = y;
}
public Node(float x, float y, Node parent, Node finalNode){
    this.x = x;
    this.y = y;
    this.parent = parent;
    this.finalNode = finalNode;
    calculateHeuristic(finalNode);
}

public void calculateHeuristic(Node finalNode) {
    this.h = Math.abs(finalNode.getX() - getX()) + Math.abs(finalNode.getY() - getY());
}
public void setNodeData(Node currentNode, float cost) {
    float gCost = currentNode.getG() + cost;
    setParent(currentNode);
    setG(gCost);
    calculateFinalCost();
}

public boolean checkBetterPath(Node currentNode, float cost) {
    float gCost = currentNode.getG() + cost;
    if (gCost < getG()) {
        setNodeData(currentNode, cost);
        return true;
    }
    return false;
}

private void calculateFinalCost() {
    float finalCost = getG() + getH();
    setF(finalCost);
}

public float getX() {
    return x;
}

public float getY() {
    return y;
}

public Node getParent() {
    return parent;
}

public boolean isBlock() {
    return isBlock;
}

public void setBlock(boolean block) {
    isBlock = block;
}

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

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

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

public float getG() {
    return g;
}

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

public float getF() {
    return f;
}

public void setF(float f) {
    this.f = f;
}

public float getH() {
    return h;
}

public void setH(float h) {
    this.h = h;
}
@Override
public boolean equals(Object arg0) {
    Node other = (Node) arg0;
    return this.getX() == other.getX() && this.getY() == other.getY();
}

@Override
public String toString() {
    return "Node [row=" + x + ", col=" + y + "]";
}}

以下是导致崩溃的一些测试数据：

public class Main {
public static void main(String[] args) {
    PathFinder pathFinder = new PathFinder(new Node(1,1), new Node(14,1));

    List<Node> path = pathFinder.findPath();
    System.out.println(path);
}}
java libgdx game-development a-star isometric
1个回答
0
投票

您的解决方案有两个缺陷。

浮点值比较

这与您的问题没有直接关系，但可能会导致严重的副作用。 如here所述，由于精度问题，不应将浮点数与

==
进行比较。

没有实现 hashCode()

Java中的HashSet使用对象的HashCode方法来与值进行比较。由于您没有为 Node 覆盖它，因此即使您的 equals() 方法认为它们相等，它也会给出两个不同的值：

public static void main(String[] args) {
    final var a = new Node(1.0f, 1.0f);
    final var b = new Node(1.0f, 1.0f);

    System.out.println(a.equals(b));
    // true
    System.out.println(a.hashCode());
    // 918221580
    System.out.println(b.hashCode());
    // 2055281021
}

因此，只需为 Node 正确实现 hashCode() 即可解决问题：

    @Override
    public int hashCode() {
        return Objects.hash(this.getX(), this.getY());
    }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.