AStar寻路1-实现基本功能
AStar寻路1-实现基本功能
梦想游戏人 发表于7个月前
AStar寻路1-实现基本功能
  • 发表于 7个月前
  • 阅读 25
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: A星,Astar,寻路

A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。

基本思想是有2个列表,open和close,

open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。

启发式函数f=g+h;

f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的估计值越接近当前点到终点的最短路径的实际值那么A星搜索出来的路径就越接近实际的最短路径,从这点来看A星是时间和精度的一个权衡改进的广度搜索算法。h值始终为0的话,那退化为广度搜索了(没有了估值,f的计算都是实际值,因此变为了暴力的广度搜索)。

进过以下测试,大约牺牲了10%的精度换来了10倍的速度。

上图为h值为0,退化为广度搜索。

上图为曼哈顿估值法(即横向和纵向距离之和),

上图为距离估值法。

上图为随机化地图遮挡的结果,

每次搜索都从open表中找出代价最小的节点进行搜索,在搜索当前点时,如果周围点已经存在于open列表中,那么就要重新计算f和g值,表示进过当前点到达 周围点会不会更近,重新计算后open列表将会重新排序,下个轮回再次从f值最小的开始广度搜索。

下篇主要是优化性能    AStar寻路2-性能优化

共有 人打赏支持
粉丝 32
博文 383
码字总数 110289
×
梦想游戏人
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: