阅读数:59 评论数:0

0、这里假设有人要从A点去往B点。

1、找到与起始点相邻的所有可到达方块，将这些点加入到“候选列表”。

2、从“候选列表”中将A方块删除，并将其加入到“排除列表”，表明在此列表中的方块不需要再去关注。

3、路径评估 F=G+H

（1）G= 表示从A点到当前点的所经过的路径长度

（2）H=从当前点到目标点B的估计路径长度。这经常被描述为“启发式”，有时这样会引起歧义。之所以这么叫是因为这仅仅是一种猜测。事实上在找到路径之前我们并不知道实际路径长度，因为会有如墙，水等东西阻挡。这里给出一种计算H的方法，同时在网上有许多其他计算H值的方法。

4、不断的遍历“候选列表”并选择最小F值的点。

5、将其从“候选列表”中删除加入到“排除列表”

6、检查其领域内方块，排除不可通过方块，并且将没有在“候选列表”中的方块加入到“候选列表”。是当前选中方块成为父方块。

7、如果领域内存在方块在“候选列表中”中，那么就检查是否从当前点经由那个候选方块是一条更好路径。换句话说，检查那个方块的G值是否会因为我们使用了当前点到达那里而变小，如果不是，什么都不做，另一方面，如果新的路径G值变小了，就将那个候选方块的父节点改为当前点。最后重新计算那个候选节点的F和G值。

8、目标方块被加入到“排除类表”，这种情况下路径被找到

9、在“候选列表”中的点全部被放到了“排除列表中”，此时路径查找失败，没有通路。