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

My implementation of A* finds the shortest path until I start adding hexside effects - that was the point of my post but perhaps I didn't say so explicitly.

"His way will generate a usually good path, but it doesn't take into account the weight of the neighbor->target link, which can be extensive."

I think this is the crux of the issue - if you don't have hexside effects, but just per-hex movement costs, then every neighbor->target cost will be identical, i.e. just the cost of stepping into the target hex.

Thanks for all the feedback - I will see if I can adjust the alg to meet your suggestions, but if not I will probably be pleased with the current behavior.

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

Hmm, my heuristic at the moment is just the manhattan distance times the minimum movement cost (i.e. road/bridge movement).

After a very small amount of experiementation, I found that sometime it will find optimal paths even when I add a large scaling factor to the heuristic, but if there's more interesting terrain between start and finish, even 1.5x the above formula starts to find non-optimal paths.

Which sort of points to the question of how vital it is that the very best path is found. I'm not modeling the AI of supergeniuses that are going to actually do cost-benefit analysis on different routes from A to B, rather they're gonna use their best guess or their captain's stubborn hunch. However, since as mentioned my game does all of it's pathfinding non-interactively, efficiency isn't such a concern that I'm looking for ways to compromise on it right now.

I have a question about influence maps now and how to integrate them into A* but I'll make that a new thread.

Happy Flightless Bird Day!

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