1 / 5
文档名称:

游戏自动寻路a算法.doc

格式:doc   大小:103KB   页数:5页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

游戏自动寻路a算法.doc

上传人:iris028 2020/2/3 文件大小:103 KB

下载得到文件列表

游戏自动寻路a算法.doc

文档介绍

文档介绍:浅谈游戏自动寻路A*算法  寻路是游戏中非常重要的一个元素,如何找到一条最短的路径是程序需要设计的算法,现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。状态空间搜索,就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程,通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多,这就产生了多条求解的路径,这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中找个一个路径可以从开始到结束,这个过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先,广度优先是从初始状态一层一层的向下找,知道找到结果目标为止,深度优先是按照一定的顺序先查找完一个分支再查找另一个分支,知道找到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法,但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成,所以要用到另一种算法---启发式搜索。启发式搜索就是在状态空间中对每一个搜索为止进行评估,指导找到最好的为止,再从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的,采用不同的估价可能有不同的结果。启发式搜索中的估价函数表示为:f(n)=g(n)+h(n)其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始点到n节点的实际代价,h(n)是从n节点到目标节点最佳路径的估价代价。这个里主要是h(n)体现了搜索的启发信息,因为g(n)是己知的。换个说法就是g(n)代表了索索的广度优先趋势但是当h(n)>>g(n)时,可以省略g(n),从而提高效率。启发式搜索其实也有很多算法,比如局部择优搜索,最好优先搜索等。A*也是如此,这些算法都启用了启发函数,但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点,父亲节点并且一直搜索下去。这种搜索结果很明显,由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点,除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点,这样防止了最佳节点的丢失。A*算法也是一种最好优先的算法,只是加上了一些特定的约束条件,由于在一些问题求解时,希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题,A*算法的目的就是这样。其估价的函数可以表示为:f'(n)=g'(n)+h'(n)这里的f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最短路径的启发值。由于f'(n)是无法提前预先知道的,因此用前面的估价函数f(n)做近似g(n)代表g'(n),但是g(n)≥g'(n)才可以通常都是大于所以不要考虑,但是h(n)代替h'(n)时候需要h(n)≤h'(n)才可以。可以证明应用这样的评估函数是可以找到最短路径的,因此应用这种评估函数的最好的优先算法就是A*算法。至于h(n)的启发函数的信息性,就是在估计一个节点值的约束条件,如果信息越多或者约束条件越多则排除节点就越多,估价函数就越好或者说这个算法就越好。这就是为什么广度优先

最近更新

人大科学发展观发言提纲与人大行风建设动员大.. 10页

云南省2020版保育员四级业务水平考试试题试卷.. 11页

云南省2018版保育员三级业务水平考试试题试题.. 10页

乡镇财政所2018年工作安排与乡镇财政所2018年.. 5页

“一二九”艺术节上的讲话与“一双手-一世界”.. 4页

2025年度委托招聘客服人才合作协议书 9页

2025年度委托书合同范文:跨区域项目合作协议.. 9页

2025年度女方离婚协议书模板与子女抚养权分配.. 7页

2025年度夫妻婚内财产保护及共同财产投资协议.. 7页

2025年度夫妻共同子女抚养及教育经费分配协议.. 8页

2025年度太阳能光伏发电项目环保监测合同 9页

2025年度天然气入户安装与居民用户安全知识培.. 9页

2025年度大蒜种植专用地租赁合同 8页

2025年度大棚种植项目土地整治与复垦合作协议.. 9页

2025年度大数据分析公司数据分析师劳动合同 7页

2025年度大学生就业实习基地合作协议范本 9页

2025年度大型餐饮企业厨师雇佣合同范本 8页

2025年度大型活动临时设施搭建与拆除工程合同.. 9页

2025年度大型地下停车场使用权转让协议范本 9页

2025年度多子女共同赡养高龄父母养老协议书 8页

2025年度外资企业股权代持税收筹划合同 8页

2025年度外聘演员网络电影合作合同 9页

2025年度外墙保温工程劳务清包及后期维护合同.. 9页

2025年度外卖行业数据共享与分析协议 9页

工程质量控制中试验检测的重要性 24页

2级经销商分销协议 5页

2024年高中生情绪调控心得体会(热门24篇) 36页

【2023年】福建省龙岩市辅警协警笔试笔试真题.. 16页

村后备干部笔试试题A及答案(最新版) 12页

物理学英文论文 4页