文档章节

AStar寻路1-实现基本功能

梦想游戏人
 梦想游戏人
发布于 2017/06/08 20:02
字数 470
阅读 46
收藏 0

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-性能优化

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 36
博文 438
码字总数 124281
作品 0
成都
私信 提问
基于HTML5的WebGL呈现A星算法的3D可视化

最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A算法的WebGL 3D呈现,算法基于开源 https://github.com/bgrins/javascript-astar 的javascript实现,其实作者也有个...

xhload3d
2015/11/17
0
0
百度2010年 Astar程序设计大赛启动

5月18日午间消息,由中文搜索引擎百度举办的“2010 Astar百度之星程序设计大赛”正式面向全国高校学生和广大编程爱好者启动,本届“Astar大赛”主题为“乐CODE乐CODE”。 除延续往届的赛程及...

红薯
2010/05/18
972
5
2011 Astar 百度之星程序设计大赛开幕

5月20日消息,由中文搜索引擎百度举办的“2011 Astar百度之星程序设计大赛”正式面向全国高校学生和广大编程爱好者正式拉开帷幕。 百度技术副总裁王劲出席启动仪式,与北大、清华、北邮等国内...

红薯
2011/05/20
2.5K
14
基于HT for Web的3D呈现A* Search Algorithm

最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A算法的WebGL 3D呈现,算法基于开源 https://github.com/bgrins/javascript-astar 的javascript实现,其实作者也有个...

xhload3d
2014/11/24
0
0
安卓智能室内导航系统设计与实现,毕设

结合电子地图工具设计室内导航系统。设计开发地图栅格化工具,实现地图的电子化标注(如标注障碍区和可通行区),基于A Star算法设计智能导航路径生成,设计智能APP路径导航系统,实现导航路...

zb1489050274113
2017/03/09
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Temp-Memo

Recommended Ref : SQL High CPU troubleshooting checklist -- Top 50 SQL highly consuming cpuSELECT TOP 50[Avg. MultiCore/CPU time(sec)] = qs.total_worker_time / 1000000 / qs......

Goopand
22分钟前
1
0
dotConnect for Oracle入门指南(七):存储过程

【下载dotConnect for Oracle最新版本】 dotConnect for Oracle(原名OraDirect.NET)建立在ADO.NET技术上,为基于Oracle数据库的应用程序提供完整的解决方案。它为设计应用程序结构带来了新的...

电池盒
24分钟前
2
0
如何使用阿里云ARMS轻松重现用户浏览器问题

客户投诉不断,本地却无法重现? 页面加载较慢是用户经常会反馈的问题,也是前端非常关注的问题之一。但定位、排查解决这类问题就通常会花费非常多的时间,主要原因如下: 页面是在用户端的浏...

阿里云官方博客
28分钟前
1
0
因资源用尽导致服务宕机

1. 事故的发生 服务调用场景和发生的事件如下图所示,红色表示服务不可用. 服务A和服务B都是内部服务,服务C_*为不同运营商提供的服务,遵循一样的协议。 某一天,突然发现所有服务A调用服务...

北风刮的不认真了
32分钟前
3
0
锤子科技"临死前"被"接盘" ,内部人士爆料已改签今日头条母公司

就在昨天,据据锤子科技内部人士透露,部分锤子科技员工在昨天已经接到了相关的临时通知,要求改签劳动合同至今日头条的母公司——字节跳动。至于这是锤子科技真正再度复活还是借尸还魂都不重...

终端研发部
42分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部