java - A星寻路|六角 handle

我是个新手，我面临着一个非常棘手的问题：
.
似乎算法已经吞下了一个额外的十六进制。
有人能指出我的错误吗？
下面是代码：
（1和2中出现的“ob”是一组“障碍物”）
1.寻路功能：

private static Node pathFinding(Vector2i startHex, Vector2i goalHex, HashSet<Vector2i> ob, int movesLeft) {
    start = new Node(startHex);
    goal = new Node(goalHex);

    if (distance(start, goal) > movesLeft) return null;

    TreeSet<Node> openSet = new TreeSet<>(new NodeComparator());
    HashSet<Node> closedSet = new HashSet<>();

    start.cameFrom = null;
    start.g = 0;
    start.h = distance(start, goal);
    start.f = start.g + start.h;
    openSet.add(start);

    float tentativeScore;

    while (!openSet.isEmpty()) {
        current = openSet.pollFirst();
        if (current.coords.equals(goal.coords)) {
            return current;
        }
        closedSet.add(current);
        for (Node node : getNeighbors(current, ob)) {
            node.g = distance(start, node);
            tentativeScore = current.g + distance(current, node);

            if (!closedSet.contains(node) || tentativeScore < node.g) {
                node.g = tentativeScore;
                node.h = distance(node, goal);
                node.f = node.g + node.h;
                node.cameFrom = current;
                openSet.add(node);
            }
        }
    }
    return null;
}

2.邻居：

private static final Vector2i[] directions2i = {
        new Vector2i(0,-1), new Vector2i(1,-1), new Vector2i(1,0),
        new Vector2i(0,1), new Vector2i(-1,1), new Vector2i(-1,0)
};

private static List<Node> getNeighbors(Node origin, HashSet<Vector2i> ob) {
    List<Node> list = new ArrayList<>();
    for (int i = 0; i < 6; i++) {
        Vector2i dir = new Vector2i(origin.coords.x + directions2i[i].x, origin.coords.y + directions2i[i].y);
        if (!ob.contains(dir))
            list.add(new Node(dir));
    }
    return list;
}

3.启发式：

static float distance(Node a, Node b) {
    return (Math.abs(a.coords.x - b.coords.x) + Math.abs(a.coords.y - b.coords.y) + Math.abs(a.coords.x +a.coords.y -b.coords.x -b.coords.y)) / 2;
}

4.如果这里是节点和比较器类：

public class Node {
public Node cameFrom;
public Vector2i coords;
float g, h, f;

@Override
public int hashCode() {
    return coords.x * 100000 + coords.y;
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (getClass() != o.getClass()) return false;
    Node oth = (Node) o;
    return this.coords.equals(oth.coords);
}

Node(Vector2i coords) {
    this.coords = new Vector2i(coords);
}
}

private static class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2) {
        return Float.compare(o1.f, o2.f);
    }
}

最佳答案

TreeSet不适合此用法。它是根据比较器定义的（忽略equals的实现），但是在开放集中有多个具有相同f分数的节点（确实需要存在）是可能的，也是常见的。这将导致本应存在的节点丢失，以及重复节点的无意义存在。
顺便说一句，在插入节点之前删除节点并不是一个真正的解决方案，只是一个快速的技巧（显然）让它在某些时候起作用。你不应该把这个建议当作一个可以接受的解决办法，应该进行根本性的改变。
通常提到的一种方法是维护链接的优先级队列和散列映射，其中优先级队列更新散列映射以跟踪具有给定坐标的节点在队列中的位置这使得可以快速查询打开的集合中的“contains”（hashmap），快速从队列中删除具有给定坐标的节点（hashmap，然后告诉队列删除位于给定索引处的节点），并且仍然可以快速访问f得分最低的节点（与通常一样）。
由于队列需要知道散列映射并对其进行更新，因此不能使用内置的有序容器进行这种安排。幸运的是，二进制堆并不难实现，而且它已经完成了，所以您可以借用现有的实现。

关于java - A星寻路|六角 handle ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45894845/