A*寻路初探 GameDev.net

Fly_1101

想请教大家个问题：
[图六]下面：
注意，起始格下方格子的父节点已经和前面不同的。之前它的G值是28，并且指向右上方的格子。现在它的G值是20，指向它上方的格子。这在寻路过程中的某处发生，当应用新路径时，G值经过检查变得低了－于是父节点被重新指定，G和F值被重新计算。尽管这一变化在这个例子中并不重要，在很多场合，这种变化会导致寻路结果的巨大变化。

这里“G值经过检查变得低了”，怎么个检验法呢？如果按：

6.如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不做。
      另一方面，如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格（在上面的图表中，把箭头的方向改为指向这个方格）。最后，重新计算F和G的值。

进行检验，觉得不对呀，这里检验后启始点下面第2个点的父结点怎么就指向启始点的下面第1个结点了？！而当前父结点应该是启始点下面第2个点的右边那个点呀！

小小C

好难哩，要慢慢看下

a-John

说实话 文章写得还不全
里面还有很多问题没有提到，比如说当中间的墙再往下多一格他的寻路是怎样的呢？
还有及时战略游戏中每个单位的寻路是怎样的呢？
都没有提到，
哈哈~~~~~~这个并不是看一篇文章就OK了
还有我建议用终点搜索起点，比如在某些游戏中控制主角去往某点位置
用起点搜索终点的话       用于npc的移动，
但是并不是一开始就找出了路径了，而是每一个游戏循环中都在做哪些事情
这样的话，npc的路径不是最短路径了，很多游戏中可以看到这点




赫赫     

lijunjun

已阅,但本文出现了一些错误:
一,笔误
文中说:
其余3格，两个已经在开启列表中（起始格，和当前格上方的格子，在表格中蓝色高亮显示),于是我们略过它们。

应该是 "两个已经在关闭列表中",这个应该是笔误.

二,逻辑错误
在 起始位置 右上角的F=54 还是 右下角的F=54 的优先选择上.本文选择的是右下角的作为优选择,但如果这样的话,最后出来的红色搜索路径,便不是在示意图的下方,而是在示意图的上方.

本文作为学术性的文章,我认为应该审了又审,不然会误人子弟.虽然是翻译过来的,但也要仔细审阅.

我看了下原文
two are already on the closed list (the starting square, and the one just
-----------------------------------
                        -----------
above the current square, both highlighted in blue in the diagram), so we ignore them. And the last square, to the immediate left of the current square,
这确实是翻译者出的错。

CuriousZhen

讲得很明白，还有什么不好理解。

quanyy

同意楼上，说的很明白了，不知道哪不好理解

ljlees0830

虽然在其他地方看过一遍了，再看一遍，收获还是很大、、、

cwbcwb505

兄弟，你自己没有实现过这个算法？我实现了一个，可是效率还是不行，不知道还能不能从理论上改善一点呢？

轩辕崇正

不知道等高线算法和A*算法相比如何??

chunchongc

谢谢楼主的翻译，但是文中有一些错误需要指出一下，防止误导大家。

1.其余3格，两个已经在开启列表中（起始格，和当前格上方的格子，在表格中蓝色高亮显示),于是我们略过它们，这句话正确的翻译应该是 "两个已经在关闭列表中",英文原文写得也是在关闭列表中。
2.原文作者图示和计算是正确的，请同志们严格按照步骤来。

Anyway,谢谢作者,谢谢译者，虽然有些错误,但是作为一篇入门科普，却是很好了。