I'm having some trouble implementing A* based on this: A* Pathfinding for Beginners I Googled a ton and found this: Path Finding Tutorial They are different in that the first tutorial tells you to ignore the closed list when iterating trough adjacent nodes, looking for a better path than the existing one. The second tutorial tells you to check both for open and closed nodes. That's news to me, but it makes more sense. However, I'm starting to wonder if I'm missing something. Any advice would be appreciated. Thanks guys.

The wikipedia entry is really good:

http://en.wikipedia.org/wiki/A*_search_algorithm

One thing it says is that you can "omit searching the closed list if a solution is guaranteed to exist". In the case of many games that probably isn't the case.

You might try both ways and see what the implications are are in terms of nodes searched to find the goal. It is a small difference in code.

Thank you, Fippy. (++)

Actually the wikipedia article is referring to something entirely different than the difference between the articles. The wikipedia article is about A* in general, where nodes can be generated as the tree is searched. In that situation, you wouldn't be able to tell if a newly generated node was equivalent to one that was already visited unless you maintained a closed list, so if there was no solution then the algorithm could become stuck in a cycle even if the search space is not infinite.

The A* tutorial algorithms are talking about what to do with nodes that are scanned (that are the successor to the node that was just expanded) that are already on the closed list. Both articles do use a closed list.

The difference is that in one of them nodes are never placed back on the open list after they are closed. A closed node stays closed forever. The other article says to check if the path just found to the closed node is better than the previously found path, and if so then the node is removed from the closed list and placed back onto the open list.

If I recall correctly, if the heuristic is monotonic then when a node is placed on the closed list it never needs to be opened again because the shortest path to that node has already been found. Monotonicity means that for any two nodes n1 and n2, h(n1) - h(n2) <= the length of the shortest path from n1 to n2. For example: if h(n1) is 5, and the shortest path from n1 to n2 is of length 2, h(n2) must be at least 3 for the heuristic to be monotonic.

Any admissible (guaranteed to find the shortest path, in A* by underestimating distance to the goal) and non-monotonic heuristic can be transformed into a monotonic heuristic by using as the new heuristic h-new(n2) = max(h(n1)-cost,h(n2)) when n1 is expanded and n2 is its successor.

As usual, discussion is complicated by confusion of locations, nodes, and states. If your nodes are spatial graph nodes - ie. locations - then you potentially have to be able to 'reopen' a node when you discover a quicker route to it. If your nodes are state tree nodes - ie. 'route taken so far' - then you never need to reopen a closed node, but representing the state becomes far less practical.

The act of moving a closed node back onto the open list is essentially that of finding that 2 branches of the search tree yield a result where the future state is identical, so that they can effectively be merged into one branch that takes on the characteristics of the most favourable approach to it. You know that one of these 2 branches will always be worse than the other, so you just overwrite the poor one with the good one and carry on.

It makes a lot more sense when you remember that A* is not fundamentally about finding paths, it's about finding plans, and that using it to find a path allows for some very specific optimisations, such as usually being able to treat the prior route to a location as having no effect on the future state.