A-Star Pathfinding Not Giving Shortest Path

Question

I'm attempting to implement the A* pathfinding algorithm in Java. I thought it was working well, but then I found instances where it doesn't follow the shortest path

Green = start, red = target, black = walls (unwalkable), blue = path

Red # in top left is G value, green # in top right is H value, black # in middle is F value. Black lines show parents.

I have a Node class which has the following properties: Integers x, y == 0 Integers f, g== -1 Node parent

H is calculated using the diagonal shortcut method described here

int xDist = Math.abs(end.x - x);
int yDist = Math.abs(end.y - y);
//end == target node
if (xDist > yDist) {
    h = 14 * yDist + 10 * (xDist - yDist);
} else {
    h = 14 * xDist + 10 * (yDist - xDist);
}

G is calculated as follows:

public int getG(boolean force) { //force == true will recalculate G
    if (g == -1 || force) {
        if (equals(start) || parent == null) {
            g = 0; //If its the start, g = 0
        } else {
            g = parent.getG(force) + (parent.x != x && parent.y != y ? 14 : 10);
            //10 for orthogonal moves, 14 for diagonal
        }
    }
    return g;
}

The path is calculated using this findPath method:

public static boolean findPath(Node start, Node end) {
    if (start.block || end.block) {
        //start or target has a wall on it
        return false;
    }
    Node.start = start;
    Node.end = end;
    LinkedHashSet<Node> open = new LinkedHashSet<Node>();
    LinkedHashSet<Node> closed = new LinkedHashSet<Node>();
    //open and closed lists, respectively
    boolean found = false;
    open.add(start);
    //add the starting node to open list
    while (open.size() > 0) {
        //while there is something in open list
        int lowF = Integer.MAX_VALUE;
        int curF = 0;
        Node curN = null;
        for (Node node : open) {
            curF = node.getF();
            if (curF < lowF) {
                lowF = curF;
                curN = node;
            }
        }
        //curN == lowest F value in open list
        if (curN == end) {
            //target has been found
            found = true;
            break;
        }
        open.remove(curN);
        closed.add(curN);
        //switch the lowest F value Node to the closed list
        for (Node node : curN.getAdjacent()) {
            //iterate over non-wall adjacent nodes
            if (closed.contains(node)) {
                //already on closed list
                continue;
            }
            if (!open.contains(node) || node.getG() < curN.getG()) {
                //not on open list OR it has a lower G cost
                node.parent = curN;
                //set node's parent to the lowest F cost Node from before
                node.getF(true);
                //recalculates the F (and G) values
                open.add(node);
                //add to the open list.
                //will NOT be readded if already present
            }
        }
    }
    return found;
    //loop is over, return true
}

I lead myself to believe that the issue was in my heuristic, however I'm not sure that's the case anymore: shouldn't the shortest path still be found eventually?

The path begins by approaching the target the fastest way because of the heuristic, but then seems to "change it's mind." I've been baffled for days.

When I remove the H value (i.e. set it to 0) I get the expected result. When I remove diagonal movement I also get the expected result.

Answer 1

Here is the pseudo-code from wikipedia for A* with a consistent-heuristic:

1. while openset is not empty
2.     current := the node in openset having the lowest f_score[] value
3.     if current = goal
4.        return reconstruct_path(came_from, goal)
5. 
6.     remove current from openset
7.     add current to closedset
8.     for each neighbor in neighbor_nodes(current)
9.        tentative_g_score := g_score[current] + dist_between(current,neighbor)
10.       if neighbor in closedset and tentative_g_score >= g_score[neighbor]
11.          continue
12.
13.       if neighbor not in openset or tentative_g_score < g_score[neighbor] 
14.          came_from[neighbor] := current
15.          g_score[neighbor] := tentative_g_score
16.          f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
17.          if neighbor not in openset
18.             add neighbor to openset
19. 
20. return failure

The important lines are these:

9.        tentative_g_score := g_score[current] + dist_between(current,neighbor)
...
13.       if neighbor not in openset or tentative_g_score < g_score[neighbor] 

The purpose of tentative_g_score is that you may need to update the g-score of a node in the open-list if you find a closer neighbor to it. You are not doing that; you are instead comparing the g-score of the node to the g-score of its neighbor.

Answer 2

I agree about the G values. Note that all paths chosen are diagonal unless there is no other choice.

I suspect that the error may be in this line: if (!open.contains(node) || node.getG() < curN.getG())

The G comparison doesn't seem to compare apples with apples, you're comparing the G cost of the current node with the G cost of it's neighbour. Perhaps you should be comparing the G cost of the current node plus the distance to the neighbour with the G cost of the neighbour, or possibly comparing the F costs.

Answer 3

There is another bug beyond the neighbor-g confusion (described in BlueRaja's answer) and the incorrect computation of G (hinted at by poster's response).

Unlike optimal search algorithms like Dijkstra's algorithm, A* requires re-opening closed nodes, so this code is incorrect:

        if (closed.contains(node)) {
            //already on closed list
            continue;
        }

Conceptually, you can only avoid re-opening closed nodes if you're guaranteed to only close them when you've found the optimal path to them. Dijkstra's algorithm finds the optimal path to all nodes on the grid, and so has this optimal subsequence property that avoids the need to reopen. But A* uses H to bias the search and therefore does not guarantee that the first time a node is visited (closed) the optimal path to that interim node was actually found.

The internet appears to be full of incorrect descriptions and pseudocode for A* that avoid reopening closed nodes. The wikipedia page is correct, as its pseudocode includes:

        if neighbor in closedset and tentative_g_score >= g_score[neighbor]
           continue

Another link which shows this correctly (but is easy to misinterpret the g values): http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Astar_Search

On many A* searches, failing to do this will have no effect (the bug is invisible). But with some searches it can have significant effects.