a星算法

问题描述

精选答案

a星算法一般指A*搜寻算法，A*算法是比较流行的启发式搜索算法之一，被广泛应用于路径优化领域。

它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价该节点处于最短路线上的可能性的量度。A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。A*算法进行下一步将要走的节点的搜索的时候，每次都是选择F值最小的节点，因此找到的是最优路径。但是正因为如此A*算法每次都要扩展当前节点的全部后继节点，运用启发函数计算它们的F值，然后选择F值最小的节点作为下一步走的节点。在这个过程中，OPEN表需要保存大量的节点信息，不仅存储量大是一个问题，而且在查找F值最小的节点时，需要查询的节点也非常多，当然就非常耗时，这个问题就非常严重了。再加上如果游戏地图庞大，路径比较复杂，路径搜索过程则可能要计算成千上万的节点，计算量非常巨大。因此，搜索一条路径需要一定的时间，这就意味着游戏运行速度降低。