文档章节

AStar寻路1-实现基本功能

梦想游戏人
 梦想游戏人
发布于 2017/06/08 20:02
字数 470
阅读 42
收藏 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-性能优化

© 著作权归作者所有

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

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

xhload3d
2015/11/17
0
0
基于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*寻路算法在Unity中的简单应用

前言 在使用Unity开发游戏项目时,经常会遇到一些角色的导航需求,然而Unity提供给我们的NavMesh+NavMeshAgent并不能很好帮我们实现,且寻路网格的烘焙,以及在导航过程中寻路网格的检测,都...

欣羽馨予
2016/06/23
0
0
考研复试系列——第十一节 map的使用

考研复试系列——第十一节 map的使用 前言 map基础 #pragma warning(disable:4786)//消除4786警告 include include include using namespace std; int main(){string str = "wangcan";rever......

cassiepython
2017/03/12
0
0
Silverlight游戏设计(Game Design):(四)从零开始搭建游戏主体框架

思路已俨然清晰,接下来要做的是从零开始搭建游戏的主体框架。Silverlight作为RIA界的新宠儿,不仅在游戏开发方面性能优越,在企业开发领域的优异表现同样日益显著。像我们这些长期从事.NET开...

晨曦之光
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSX | SafariBookmarksSyncAgent意外退出解决方法

1. 启动系统, 按住⌘-R不松手2. 在实用工具(Utilities)下打开终端,输入csrutil disable, 然后回车; 你就看到提示系统完整性保护(SIP: System Integrity Protection)已禁用3. 输入reboot回车...

云迹
今天
4
0
面向对象类之间的关系

面向对象类之间的关系:is-a、has-a、use-a is-a关系也叫继承或泛化,比如大雁和鸟类之间的关系就是继承。 has-a关系称为关联关系,例如企鹅在气候寒冷的地方生活,“企鹅”和“气候”就是关...

gackey
今天
4
0
读书(附电子书)|小狗钱钱之白色的拉布拉多

关注公众号,在公众号中回复“小狗钱钱”可免费获得电子书。 一、背景 之前写了一篇文章 《小狗钱钱》 理财小白应该读的一本书,那时候我才看那本书,现在看了一大半了,发现这本书确实不错,...

tiankonguse
今天
4
0
Permissions 0777 for ‘***’ are too open

异常显示: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: UNPROTECTED PRIVATE KEY FILE! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ......

李玉长
今天
5
0
区块链10年了,还未落地,它失败了吗?

导读 几乎每个人,甚至是对通证持怀疑态度的人,都对区块链的技术有积极的看法,因为它有可能改变世界。然而,区块链技术问世已经10年了,我们仍然没有真正的用上区块链技术。 几乎每个人,甚...

问题终结者
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部