如果点之间没有有效路径，如何阻止 A* 无限循环

Question

因此，我正在为 2D 游戏进行寻路，并且遇到了一些问题，如果地图中的两点之间没有有效路径，A* 实现将无限循环。这是我当前使用的代码：

public static List<Vector2> getPath(EntityMob start, Vector2 end){
        List<Node> openList = new ArrayList<>();
        Set<Node> closedList = new HashSet<>();
        
        Vector2 bounds = new Vector2(start.floor.floor_width,start.floor.floor_height);
        openList.add(new Node(start.getX(),start.getZ()));
        while(!openList.isEmpty()) {
            openList.sort(Comparator.comparingInt(n->n.f));
            Node current = openList.get(0);
            
            if(current.x==end.x&&current.z==end.z) {
                return reconstructPath(current);
            }
            
            openList.remove(current);
            closedList.add(current);
            for(Node neighbor : getNeighbors(current,bounds)) {
                
                if(closedList.contains(neighbor)||!start.canIStepOn(neighbor.x, neighbor.z)) {
                    
                    continue;
                }
                
                int tentativeG = current.g+1;
                if(!openList.contains(neighbor)) {
                    openList.add(neighbor);
                }else if(tentativeG>=neighbor.g) {
                    continue;
                }
                neighbor.parent=current;
                neighbor.g=tentativeG;
                neighbor.h=manhattanDistance(neighbor.asVector(),end);
                neighbor.f=neighbor.g+neighbor.h;
            }
        }
        return Collections.emptyList();
    }
    
    private static List<Node> getNeighbors(Node node, Vector2 bounds){
        List<Node> neighbors = new ArrayList<>();
        if(node.x>0) neighbors.add(new Node(node.x-1,node.z));
        if(node.x<bounds.x-1) neighbors.add(new Node(node.x+1,node.z));
        if(node.z>0) neighbors.add(new Node(node.x,node.z-1));
        if(node.z<bounds.z-1) neighbors.add(new Node(node.x,node.z+1));
        
        return neighbors;
        
    }
    
    private static List<Vector2> reconstructPath(Node node){
        List<Vector2> path = new ArrayList<>();
        while(node!=null) {
            path.add(node.asVector());
            node=node.parent;
        }
        Collections.reverse(path);
        return path;
    }
    
    private static int manhattanDistance(Vector2 node, Vector2 target) {
        return Math.abs(node.x-target.x)+Math.abs(node.z-target.z);
    }

以及正在使用的 Node 类：

public class Node {
    
    public int x,z;
    
    public Node parent;
    public int g,h,f;

    public Node(int x, int z) {
        this.x = x;
        this.z = z;
        this.g = 0;
        this.h = 0;
        this.f = 0;
        this.parent=null;
    }
    
    public Vector2 asVector() {
        return new Vector2(this.x,this.z);
    }
    
    @Override
    public boolean equals(Object o) {
        Node noder = (Node) o;
        return x==noder.x&&z==noder.z;
    }
}

该系统在大多数地下城布局中都运行良好，但如果存在阻碍两点之间畅通路径的危险，该功能将无限循环，因为它不断尝试找到绕过危险的方法。

在点之间找到有效路径时的结果

如果点之间没有有效路径，该函数将重复循环通过红色图块，而不是在测试了所有选项后退出

对于一些额外的细节，函数 canIstepOn(x,z) 检查生物的移动类型，并检查位置 x,z 处的图块需要什么移动类型（普通怪物为固体地面，水生怪物为流体图块） ，两种类型的飞行瓷砖）

我试图让函数在函数到达地图边界时退出，这应该会打破循环并返回一个空列表，但我尝试这样做只会进一步破坏函数，影响怪物在缺乏危险的更平凡的地牢楼层中移动。

Answer 1

事实证明，算法本身已正确实现，但 Node 类仍然使用默认的 hashCode() 函数。

为了解决这个问题，我将以下代码添加到 Node.java

@Override
public int hashCode(){
    return Objects.hash(x,z);
}

这允许 HashSet 正确检查它是否已经包含具有相同坐标的 Node。