To answer your question, let's look at A*'s behaviour in terms of expanding nodes. Assuming an admissible heuristic and a monotonic cost function, then it is provable that A* will search(expand) all nodes within a given cost contour before expanding any nodes in a higher cost contour. Thus, adding the goal node to your open list does not mean that you have considered all nodes within the cost contour that contains the goal. However, assuming no variation to the algorithm, at the time you remove the goal from the OPEN list, you will have searched every possible node (given your discretisation of the state and action space) within the cost contour of the goal. Thus, the search can be ended and the path back through the ancestors of the goal can be obtained as the optimal solution.

Timkin

Yeah, I've made this mistake too :). You have to wait until the target is popped from the list. Otherwise, you could wind up in the case where there's a good-looking node at the top of the list with a long traversal to get to the target. If you accept that as your best path, you might miss a node that didn't look quite as good but has a shorter final traversal.

I used the psuedo-code from Game Programming Gems 1 and it worked great (once I figured out I'd missed that subtlety :) ).

The other problem that can be faced is that your heuristic can become inadmissible. That is, it may overestimate the cost. Let's say your heuristic is based on a function of straight line distance and average hex-edge traversal cost (since you obviously don't want to check every edge to the goal... which would just give you a modified brute force search). When you are far away from the goal, any particular straight line path to the goal will typcially have an actual cost close to the heuristic cost, since the sampling of different edge traversal costs on that path would be close to the global probability distribution and thus the mean of the path (a sample from the population) will be close to the population mean.

Close to the goal though sampling errors take over. You might find yourself only 3 hexes from the goal and expect 'average' traversal costs to the goal. Of course, there might be 3 bridges to the goal. The heuristic cannot account for that and so overestimates the cost to the goal. Thus, the A* algorithm will end up having to search all nodes within the cost contour corresponding to the overestimated cost, which means that it will no longer be optimally efficient. Given that the cost to search the tree grows exponentially with depth, even a small over-estimate of the true cost can cause a lot of extra computation.

How do you get around this? There's no easy way around it other than modifying your heuristic. I would suggest that you compute the discrete probability distribution for edge traversal costs (from a normalised histogram count of different costs, which can be obtained for static maps during offline pre-processing of the map) and use an underestimated heuristic cost corresponding to something like the lowest (first) quartile value of the distrbution.

Cheers,

Timkin

Just be aware that underestimating the heuristic by 'too much' is almost as bad as overestimating the heuristic. The larger the underestimate the more and more the search behaves like an uninformed greedy search, which means you expand more nodes than necessary to find the optimal path to the goal. Optimal efficiency for A* occurs when the heuristic equals the true cost to the goal for every node.

Timkin