A-Star Pathfinding | Hexagonal Grip

Question

I'm a newbie and I'm facing such an awkward problem:

.

It seems like the algorithm has swallowed an extra hex. Could anybody point to my mistake?

So here is the code:

('ob' that appears in 1 and 2 is set of 'obstacles')

1.Pathfinding func:

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.Neighbors:

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.Heuristic:

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.And just in case here is Node and Comparator classes:

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);
    }
}

Answer 1

TreeSet is not suitable for this usage. It is defined in terms of the comparator (ignoring the implementation of equals), but it is both possible and common to have multiple nodes (that really need to be there) with the same F score in the Open set. This will cause both the loss of nodes that should have been there, and the pointless presence of duplicates.

Removing a node before inserting it is not a real solution by the way, just a quick hack that (apparently) makes it work some of the time. You should not regard that suggestion as an acceptable solution, fundamental changes should be applied.

A commonly mentioned approach is maintaining a linked priority queue and hash map, where the priority queue updates the hash map to keep track of where a node with given coordinates occurs in the queue. This enables querying the Open set for "contains" quickly (hashmap), removing a node-with-given-coordinates from the queue quickly (hashmap, then tell the queue to remove the node at the given index), and still gives quick access to the node with lowest F score (as usual).

This arrangement can not be made with built-in ordered containers, since the queue needs to know about the hash map and update it. Fortunately a binary heap is not that hard to implement, and it has already been done too so you may be able to borrow an existing implementation.