Summary of the A* Method
Okay, now that you have gone through the explanation, let's lay out the step-by-step method all in one place:
Add the starting square (or node) to the open list.
Repeat the following:
Look for the lowest F cost square on the open list. We refer to this as the current square
Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
d) Stop when you:
Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path.
Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list. Doing this will be faster and it will almost always give you the shortest path, but not always. Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example.
请原谅我的题外话，但值得指出的是，当你在网上阅读的A *路径搜索，并在各类论坛上的各种讨论时，你偶尔会看到有人提到某些代码不是A *。对于A *使用方法，你需要包含上面讨论到的元素 -- 特别是开放列表和关闭列表和路径采用F值，G值和H值。有很多其他的路径搜索算法，但是其它的通常被认为是最好的方法不是A *。在这篇文章的末尾有布莱恩斯托特讨论，包括他们的一些利弊引用的文章很多。有时替代品在某些情况下更好，但你应该明白你正在进入。好了，爽了。回到话题。
Forgive me for digressing, but it is worth pointing out that when you read various discussions of A* pathfinding on the web and in assorted forums, you will occasionally see someone refer to certain code as A* when it isn't. For the A* method to be used, you need to include the elements just discussed above -- specifically open and closed lists and path scoring using F, G, and H. There are lots of other pathfinding algorithms, but those other methods are not A*, which is generally considered to be the best of the lot. Bryan Stout discusses many of them in the article referenced at the end of this article, including some of their pros and cons. Sometimes alternatives are better under certain circumstances, but you should understand what you are getting into. Okay, enough ranting. Back to the article.