6
\$\begingroup\$

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.

screenshot

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Just looking at your G numbers, the red numbers, something already looks wrong. Look at the first few squares in the top row. The G numbers are 0, 10, 28, 38, etc. but they should be 0, 10, 20, 30, etc. I haven't looked at your code, but it smells like a bug in how the predecessors are being updated. (BTW, that's a nice debug vis! You might want to draw the predecessor arrows too.) \$\endgroup\$ Commented Oct 4, 2013 at 0:29
  • \$\begingroup\$ @NathanReed Thank you, thank you. I've updated the image to display parents. The issue is definitely more clear now, but I don't understand what's wrong with my implementation. It appears to me that I've matched the steps described here: policyalmanac.org/games/aStarTutorial.htm \$\endgroup\$ Commented Oct 4, 2013 at 0:43
  • 1
    \$\begingroup\$ Have you tried always recalculating G? You have stepped through in the debugger, haven't you? \$\endgroup\$ Commented Oct 4, 2013 at 10:09
  • \$\begingroup\$ @JackAidley Part of the problem was that I wasn't recalculating correctly, so thank you \$\endgroup\$ Commented Oct 4, 2013 at 12:27

3 Answers 3

Reset to default
7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Great answer. The pseudo-code really helped, I wish I would've seen it before. I obviously wasn't doing that correctly. Afterwards I found that I wasn't even recalculating correctly! Oops! Now I can move on to making this more efficient. Many thanks \$\endgroup\$ Commented Oct 4, 2013 at 12:29
  • 1
    \$\begingroup\$ @DrAgonmoray: Re more efficient: The biggest thing would be using a priority queue for the open-list, rather than a "LinkedHashSet". I believe Java has one built-in \$\endgroup\$ Commented Oct 4, 2013 at 16:01
  • 1
    \$\begingroup\$ Neat, I've never heard of those before. Thanks for the information - you've been a great help to me \$\endgroup\$ Commented Oct 4, 2013 at 23:26
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This answer is incorrect. When using a consistent heuristic (like OP's), closed nodes are guaranteed to never be reopened. \$\endgroup\$ Commented Oct 4, 2013 at 21:25
  • \$\begingroup\$ In what case would I use a non consistent heuristic? \$\endgroup\$ Commented Oct 4, 2013 at 23:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.