A *搜索算法無限循環

Question

就像標題所說，這個A *搜索算法從不停止搜索。我正在嘗試創建一個工作的A *搜索算法，用於在基於2D瓦片的遊戲中進行點擊步行，某些瓦片可以步行，而且某些瓦片是可靠的。

PathFinder.java：

public class PathFinder { 

public static List<Node> findPath(Map map, int sx, int sy, int dx, int dy) { 
    if(map.getTile(dx, dy).isSolid()) return null; 
    Node startNode = new Node(new Vector2i(sx, sy), null, 0, 0); 
    Vector2i goal = new Vector2i(dx, dy); 

    List<Node> open = new ArrayList<>(); 
    HashSet<Node> closed = new HashSet<>(); 
    open.add(startNode); 

    while(open.size() > 0) { 
     Node currentNode = open.get(0); 

     for(int i = 1; i < open.size(); i++) { 
      if(open.get(i).fCost < currentNode.fCost || 
        open.get(i).fCost == currentNode.fCost && open.get(i).hCost < currentNode.hCost) { 
       currentNode = open.get(i); 
      } 
     } 
     open.remove(currentNode); 
     closed.add(currentNode); 

     if(currentNode.tile == goal){ 
      System.out.println("returning path!"); 
      return retracePath(startNode, currentNode); 
     } 
     for(Tile tile : map.getNeighbors(currentNode)) { 
      Vector2i neighbor = new Vector2i(tile.getTileX(), tile.getTileY()); 
      if(tile.isSolid() || getNodeInHashSetForPosition(neighbor, closed) != null) { 
       continue; 
      } 

      double gCost = currentNode.gCost + getNodeDistance(currentNode.tile, neighbor); 

      if(currentNode.gCost < gCost || !vecInList(neighbor, open)) { 
       double hCost = getNodeDistance(neighbor, goal); 
       Node node = new Node(neighbor, currentNode, gCost, hCost); 
       if(!open.contains(node)) { 
        open.add(node); 
       } 
      } 
     } 
    } 
    return null; 
} 

private static List<Node> retracePath(Node startNode, Node endNode) { 
    List<Node> path = new ArrayList<>(); 
    Node currentNode = endNode; 

    while(currentNode != startNode) { 
     path.add(currentNode); 
     currentNode = currentNode.parent; 
    } 

    List<Node> finalPath = new ArrayList<>(); 

    for(int i = path.size() - 1; i > 0; i--) { 
     finalPath.add(path.get(i)); 
    } 

    return finalPath; 
} 

private static boolean vecInList(Vector2i vec, List<Node> list) { 
    for(Node n : list) { 
     if(n.tile.equals(vec)) return true; 
    } 
    return false; 
} 

private static boolean vecInList(Vector2i vec, HashSet<Node> list) { 
    for(Node n : list) { 
     if(n.tile.equals(vec)) return true; 
    } 
    return false; 
} 

private static Node getNodeInHashSetForPosition(Vector2i position, HashSet<Node> hashSet) { 
    for(Node n : hashSet) { 
     if(n.tile.equals(position)) return n; 
    } 
    return null; 
} 

private static double getNodeDistance(Vector2i nodeA, Vector2i nodeB) { 
    int dstX = Math.abs(nodeA.x - nodeB.x); 
    int dstY = Math.abs(nodeA.y - nodeB.y); 

    if(dstX > dstY) return 14 * dstY + 10 * (dstX - dstY); 
    return (14 * dstX) + (10 * (dstY - dstX)); 
} 
} 

Node.java

public class Node { 

public Vector2i tile; 
public Node parent; 
public double fCost, gCost, hCost; //a cost is like the distance it takes to get to that point. these are used to find the lowest cost way to get from start point A to end point B. 
//gCost is the sum of all of our node to node, or tile to tile, distances. 
//hCost is the direct distance from the start node to the end node. 
//fCost is the total cost for all the ways we calculate to get to the end node/tile. 

public Node(Vector2i tile, Node parent, double gCost, double hCost) { //NODE CONSTRUCTOR STARt 
    this.tile = tile; 
    this.parent = parent; 
    this.gCost = gCost; 
    this.hCost = hCost; 
    this.fCost = this.gCost + this.hCost; 
}//NODE CONSTRUCTOR END 
} 

Answer 1

變化如下：

  if(!open.contains(node)) { 

到：

  if(!veckInList(neighbor, open) {