A*搜索算法死循环

Question

正如标题所说，这个 A* 搜索算法永远不会停止搜索。我正在尝试为 point-click 在 2D tile-based 游戏中行走创建一个有效的 A* 搜索算法，一些方块是 walk-able 而一些方块是实心的。

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) {

A*搜索算法死循环

A* search algorithm infinite loop

algorithm

search

2d

a-star