## 再译《A *路径搜索入门》之四 原

如比如比

A *方法总结

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:

a） 找开启列表上最小F方块。我将此作当前方

1. Look for the lowest F cost square on the open list. We refer to this as the current square

b） 到关列表。

1. Switch it to the closed list.

c）  当前方块的8个方块的...

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）当你停止：

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.

Small Rant

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.

（待续）

### 如比如比

《鸡啄米C++编程入门系列》系列技术文章整理收藏

《鸡啄米C++编程入门系列》系列技术文章整理收藏 收藏整理鸡啄米C++编程入门系列文章，供个人和网友学习C++时参考 1鸡啄米：C++编程入门系列之前言 2鸡啄米：C++编程入门系列之一（进制数） ...

2015/05/26
132
0
《鸡啄米C++编程入门系列》系列技术文章整理收藏

2015/06/27
0
0
《鸡啄米VS2010/MFC编程入门》系列技术文章整理收藏

《鸡啄米VS2010/MFC编程入门》系列技术文章整理收藏 1VS2010/MFC编程入门之前言 http://www.lai18.com/content/410337.html 2VS2010/MFC编程入门之二（利用MFC向导生成单文档应用程序框架） ...

2015/06/27
267
0
VS2010/MFC编程入门教程之目录和总结（鸡啄米）

weixin_40647819
2018/05/23
0
0

■实施上的注意事项 Notes on Implementation 现在您了解了基本的方法，当你编写自己的程序时，有一些额外的事情要考虑。下面给出我用C ++和Blitz Basic编写的程序，用其他语言也同样有效。 ...

2015/06/11
0
0

Amino——框架层

10分钟前
0
0
k8s-dashboard

Kubernetes Dashboard 是一个管理Kubernetes集群的全功能Web界面，旨在以UI的方式完全替代命令行工具（kubectl 等） kubectl apply -f http://mirror.faasx.com/kubernetes/dashboard/master...

ZH-JSON
16分钟前
0
0
python如何安装库命令

python3 -m pip install 库名称

17分钟前
0
0

//举个例子 //Student类 public class Student { public String name; public String age; public Student(String name, String age) {this.name = name;this.age = age; } public S......

21分钟前
0
0

go4it
22分钟前
0
0