++++++#对相邻的 3 格中的每一个?
++++++++++如果它不可通过或者已经在关闭列表中,略过它。反之如下。
++++++++++如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一
格的 //和 - 值。
++++++++++如果它已经在开启列表中,用 值为参考检查新的路径是否更好。更低的 值意味
着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的
和 值。如果你保持你的开启列表按 值排序,改变之后你可能需要重新对开启列表排序。
++++++#停止,当你
++++++++++把目标格添加进了开启列表,这时候路径被找到,或者
++++++++++没有找到目标格,开启列表已经空了。这时候,路径不存在。
++ 保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。
题外话
离题一下,见谅,值得一提的是,当你在网上或者相关论坛看到关于 的不同的探讨,
你有时会看到一些被当作 算法的代码而实际上他们不是。要使用 ,你必须包含上面
讨论的所有元素--特定的开启和关闭列表,用 / 和 - 作路径评价。有很多其他的寻路
算法,但他们并不是 ,被认为是他们当中最好的。&56" 在这篇文章后面的参
考文档中论述了一部分,包括他们的一些优点和缺点。有时候特定的场合其他算法会更好
但你必须很明确你在作什么。好了,够多的了。回到文章。
实现的注解
现在你已经明白了基本原理,写你的程序的时候还得考虑一些额外的东西。下面这些材料
中的一些引用了我用 $%%和 &'& 写的程序,但对其他语言写的代码同样有效。
),维护开启列表:这是 寻路算法最重要的组成部分。每次你访问开启列表,你都需要
寻找 值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意 保存,当需
要寻找 值最低的元素的时候,遍历开启列表。这很简单,但是太慢了,尤其是对长路径
来说。这可以通过维护一格排好序的列表来改善,每次寻找 值最低的方格只需要选取列
表的首元素。当我自己实现的时候,这种方法是我的首选。
在小地图。这种方法工作的很好,但它并不是最快的解决方 案。更苛求速度的 程序员
使用叫做“57的方法,这也是我在代码中使用的方法。凭我的经验,这种方法在大
多数场合会快 ~ 倍,并且在长路经上速度呈几何级数提升!) 倍以上速度#。如果你想了
解更多关于 5 的内容,查阅我的文章,8&5-9。
,其他单位:如果你恰好看了我的例子代码,你会发现它完全忽略了其他单位。我的寻
路者事实上可以相互穿越。取决于具体的游戏,这也许可以,也许不行。如果你 打算考虑
其他单位,希望他们能互相绕过,我建议在寻路算法中忽略其他单位,写一些新的代码作
碰撞检测。当碰撞发生,你可以生成一条新路径或者使用一些标准的移动规则!比如总是
向右,等等#直到路上没有了障碍,然后再生成新路径。为什么在最初的路径计算中不考虑
其他单位呢?那是因为其他单位会移动,当你到达他们原来的位置的时候,他们可能已经