网站开发定制方案,网站专题特点,网站开发大作业报告,简历模板免费可编辑本文目的是对A*寻路算法所生成的路径进行一些人性化的调整#xff0c;使其看起来不至于太机械化。关于A*算法的原理与实现#xff0c;读者可以阅读其他资料#xff0c;这里不再详细阐述。
如何写估价函数A*寻路算法本质上是一个有方向性的广度优先搜索算法#xff0c;它使用… 本文目的是对A*寻路算法所生成的路径进行一些人性化的调整使其看起来不至于太机械化。关于A*算法的原理与实现读者可以阅读其他资料这里不再详细阐述。
如何写估价函数A*寻路算法本质上是一个有方向性的广度优先搜索算法它使用一个估价函数来估测可能的最短路径在每一次搜索迭代完成后选取其邻接点中最优的一个即距离终点最近的一个点作为下一次迭代的起点。如此反复直到找到终点。下面先列出估价函数的常规写法设i点到起点的价值为S到终点的估价为Ei点的总估价G等于SE。S的值是确定的[cpp] view plain copyS parent.S 1i点是其父节点的水平或垂直方向上的邻接点 或 S parent.S sqrt(2)i点是其父节点斜方向上的邻接点 E点的值需要估算。精确一点的写法[cpp] view plain copy水平距离dx abs(ix - ex) 垂直距离dy abs(iy - ey) 需要斜着走过的距离v1 min(dx, dy) * sqrt(2) 需要直线走过的距离v2 max(dx, dy) - min(dx, dy) E v1 v2 粗略的写法[cpp] view plain copyE abs(ix - ex) abs(iy - ey) 如何避免转向抖动A*寻路得到的结果是最优的但不是唯一的这源于两点之间最近的路线可能不只一条。那么问题就产生了两条最佳路线距离都相等的情况下哪一条会更好红色是障碍白色可通行黑色是搜索路径如上图所示是A* 8方向搜索得到的两条距离相等的路线但是左图的路线在中间位置发生了“拐弯”要比右图的路线多一个“拐弯”。如果路线上拐弯太多人物行走的过程中会出现频繁转向从而出现“抖动”现象。所以我们判定右图路线优于左图路线。针对这一问题我们可以通过修改估价函数来选择“拐弯”更少的路线。拐弯的问题可以简化成先尽可能的向一个方向走然后再考虑转向。进一步简化成点越接近起点或是终点越优先考虑。我们给E加上一个干扰值factor,[cpp] view plain copyfactor min(abs(ix - sx), abs(ix - ex)) min(abs(iy - sy), abs(iy - ey)) factor * 0.01 factor的值不能过大否则会造成搜索结果不是最短距离因此适当的给factor乘上一个缩放系数。
如何远离障碍物A*寻路的效果是抄近道走捷径。但对于游戏体验来说这并不完全是件好事放着宽阔的马路不走非得走悬崖峭壁一不小心就跌落万丈深渊或者卡在岩石边上。那么我们该如何避免这些现象呢同样我们可以通过修改估计函数做到。我们给每一块可走区域都加上一个干扰值越靠近障碍的可走区域其干扰值越大。干扰值计算方法[cpp] view plain copyfactor 0 for(x -n; x n; x) { for(y -n; y n; y) { if(isObstacle(ix x, iy y)) { factor n - min(abs(x), abs(y)) } } } 我们甚至可以根据地表的材质来增加干扰值比如山路和沼泽地带明显比马路的干扰值大。
后记总之我们可以调节估价函数来达到不同的效果。但是也不能随意修改不良的估价函数会增加搜索成本。
