java - A* 寻路在某些情况下永远运行

Question

我已经使用这个伪代码在 Java 中编写了一个 A* 寻路算法。对于某些情况，它工作正常，但对于某些情况，它会永远挂起并向打开列表添加无限数量的节点。这是我执行伪代码的问题，还是伪代码本身的问题？我已经尝试了一堆用于调试的打印语句，但我什至无法确定问题所在。这是我的 A* 代码:

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;

public class AStar {

    Point[] adjacents = {new Point(0,1),new Point(1,1), new Point(1,0), new Point(1,-1), new Point(0,-1), new Point(-1,-1), new Point(-1,0), new Point(-1,1)};

    public Node[] calculatePH(Node startNode, Node endNode, int[][] map) {
        // Initialize both open and closed list
        ArrayList<Node> open = new ArrayList<Node>();
        ArrayList<Node> closed = new ArrayList<Node>();
        // Add the start node
        open.add(startNode);
        // Loop until you find the end
        while(!open.isEmpty()) {
            // Get the current node
            Node currentNode = open.get(0);
            for(Node n : open) {
                if(n.f<currentNode.f) {
                    currentNode = n;
                }
            }

            open.remove(currentNode);
            closed.add(currentNode);

            // Found the goal
            if(currentNode.equals(endNode)) {
                ArrayList<Node> path = new ArrayList<Node>();
                Node current = currentNode;
                while(current!=null) {
                    path.add(current);
                    current = current.parent;
                }
                Collections.reverse(path);
                return path.toArray(new Node[path.size()]);
            }

            // Generate children

            ArrayList<Node> children = new ArrayList<Node>();
            for(Point p : adjacents) {
                Point childpos = currentNode.getLocation();
                childpos.translate(p.x, p.y);

                //Checks to ensure that the node is on the actual field, so we don't ram into a field tech lol
                if((childpos.y>(map.length-1)) || (childpos.y<0) || (childpos.x>(map[0].length-1)) || (childpos.x<0)) {
                    continue;
                }

                //Checks to ensure that the node is "walkable", or basically just not inside a wall or object.
                if(map[childpos.y][childpos.x] != 0) {
                    continue;
                }

                Node child = new Node(currentNode,childpos);
                children.add(child);
            }

            for(Node n : children) {
                // Child is on the closedList
                if(closed.indexOf(n)>-1) {
                    continue;
                }

                n.g = currentNode.g + currentNode.distance(n);
                n.h = n.distance(endNode);
                n.f = n.g+n.h;
                boolean inFlag = false;
                for(Node m : open) {
                    if((n==m) && (n.g>m.g)) {
                        inFlag = true;
                    }
                }

                if(!inFlag) {
                    open.add(n);
                }
            }
        }

        return new Node[0];
    }
}

还有 Node 类，它是 java.awt.Point 的子类，带有一些额外的东西。

import java.awt.Point;
import java.util.ArrayList;

public class Node extends Point { //Extends Point for conveinince and 
    //neatness. Maybe just use a has-a relationship if this breaks.

    public Node(Node Parent, Point loc) {
        super(loc);
        this.parent = Parent;
    }

    public Node(Point loc) {
        super(loc);

    }

    void translate(Point p){
        translate(p.x,p.y);
    }

    public Node parent;

    public double f;
    public double g;
    public double h;

    public String toString() {

        return "("+x+","+y+")";
    }
}

我正在使用一个高 27 宽 54 的迷宫，起点在 (0,0)，终点在 (24,24)，目前有两个障碍。在这种情况下它工作正常:

但在这种情况下它会永远挂起。唯一的区别是第二个障碍物向下延伸了 1 行。

任何帮助都将不胜感激，如果我应该更改问题或添加更多信息，请告诉我。

编辑:它不是很漂亮，但这里是包含非功能版本的 map 数据的 int[][]。

int[][] map ={
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
       };

Answer 1

刚刚弄明白了，感谢 bracco23 为我指出了正确的代码部分。事实证明我犯了一个新手 java 错误并使用 == 而不是 .equals 进行了比较。换掉它解决了这个问题。