在这篇文章中,我会简单介绍一下 A* 算法以及该算法的一些改进点,我也会讲解一些常用的 A* 衍生算法以及 HPA 算法的一些实现要点....分帧寻路.如果你的游戏并不需要在一帧中就获取完整的寻路结果,那么我们就可以使用分帧寻路来优化 A* 算法.我们可以设置一个循环上限,如果 A* 算法在该循环限制内没能完成寻路,我们便暂停当前寻路,并在下一帧继续...(译注:原文的意思应该是分段寻路,方法是如果在设置的循环限制内不能完成寻路的话,下一帧就从最后一个搜索节点开始重新寻路,这种方法并不一定能正确得到寻路结果,译文调整为分帧寻路)
节点中保存 is_open...现在,我们来看个例子,我们想寻找一条从 S 到 G 的路径,我们首先在低层级地图上(各个簇之间)进行一次 A* 寻路,然后,我们可以根据预计算数据(簇之间的连通数据)快速的得到一条完整的路径....,算法仅需要扩展被其称为 跳跃点(jump point) 的节点,接下来我会解释 JPS 是如何找到这些跳跃点的.