游戏地图寻路及其真实性研究

发布时间：2016-11-23 02:08

  本文关键词：游戏地图寻路及其真实性研究，，由笔耕文化传播整理发布。

《西南大学》 2013年

游戏地图寻路及其真实性研究

韩玮  

【摘要】：随着社会的发展,人们物质水平的不断提高,同时得益于计算机的普及和软件技术的快速发展,游戏产业得到了快速的发展,尤其是在进入21世纪后,游戏产业迅速成为了朝阳产业。 游戏中路径搜索系统是游戏系统中非常重要的一部分,好的路径搜索算法对于游戏的重要性不可言喻。常见的路径搜索算法主要有深度优先搜索,广度优先搜索,Dijkstra, Floyd算法,A*算法等,其中A*算法是当前游戏开发中使用最为广泛的算法,也是游戏人工智能路径搜索中的研究重点。A*算法作为一种启发式搜索算法,在路径搜索时,相对其它搜索算法相当高效,它的评估函数是：F(n)=G(n)+H(n),其中G(n)表示从起始节点到当前节点的实际距离,H(n)表示从当前节点到下一步节点的估价值。A*算法总是寻找估价值最小的节点,因此能够找到最短路径,但是由于在游戏地图中,算法是基于节点搜索,所以在生成最终路径的时候,虽然是最优解,但是最终路径经常出现不符合现实情形,如何解决路径真实性问题,是一个非常重要的问题。 本文首先对A*算法进行深入研究,分析其产生问题的原因,然后针对A*寻路存在的问题,提出以了一种基于Floyd算法和Bezier曲线的改进A*算法,去掉了A*算法寻路中存在的拐点和多余的共线节点,避免了存在直线可走情况下走蛇型线路的问题,同时平滑了绕过障碍物时的生硬路径,较好的解决了A*算法路径真实性问题。最后,通过仿真实验对传统A*算法,基于二叉堆的A*算法和改进算法进行最终线路效果和时间效率的对比。实验中采用30*30的矩形方格来模拟地图,生成了固定地图和随机地图,固定地图主要是对比算法的时间效率方面,也比较最终的路径效果,随机地图主要观察在复杂的环境中,算法的路径效果。通过多次实验对比,得出的实验数据验证了改进算法的有效性,改进算法在时间消耗上优于传统A*算法,略低于二叉堆优化的A*算法,寻路效果更符合现实。

【关键词】：
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP301.6
【目录】：

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【参考文献】

中国期刊全文数据库 前10条

1 李擎,宋顶立,张双江,李哲,刘建光,王志良;两种改进的最优路径规划算法[J];北京科技大学学报;2005年03期

2 单伟;孟正大;;基于改进A~*算法的平滑路径设计[J];东南大学学报(自然科学版);2010年S1期

3 王海梅;周献中;;直线优化A~*算法在最短路径问题中的改进与实现[J];工程图学学报;2009年06期

4 李艳;陈彩;李铁松;苏兰明;;游戏地图中的分层动态路径搜索算法[J];计算机工程;2012年02期

5 王士同;启发式图搜索算法RA~*的改进算法IRA~*及IRA′[J];计算机学报;1991年03期

6 陈刚;付少锋;周利华;;A~*算法在游戏地图寻径中的几种改进策略研究[J];科学技术与工程;2007年15期

7 申麟;何明耘;陈雷霆;;基于灰度图像边缘检测的3D游戏路径搜索[J];计算机应用研究;2009年06期

8 刘娜;王玉芳;;A*寻路算法在游戏中的应用[J];数字技术与应用;2012年06期

9 张海涛;程荫杭;;基于A*算法的全局路径搜索[J];微计算机信息;2007年17期

10 邱磊;;基于A~*算法的游戏地图寻路实现及性能比较[J];陕西科技大学学报(自然科学版);2011年06期

中国重要会议论文全文数据库 前1条

1 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

【共引文献】

中国期刊全文数据库 前10条

1 单方,陈璞;注塑机锁模机构CAD的研究与开发[J];工程塑料应用;2001年09期

2 田晓艳;;计算智能主要算法研究[J];安防科技;2009年12期

3 陈帅,廖晓纬,王永礼,王霞,郑哓东,朱士永;多功能智能监测插座研究[J];安庆师范学院学报(自然科学版);2002年02期

4 樊孝忠,柳林,任锋;汉字智能输入刍议[J];兵工自动化;1995年04期

5 高恒振;靳肖闪;李军;郭玉华;景宁;;多星成像任务规划的决策支持技术[J];兵工自动化;2006年12期

6 陈永科;王树坤;刘俊友;凌用银;李鹏辉;鲍忠宝;;基于动漫技术的炮兵模拟训练系统[J];兵工自动化;2011年10期

7 杨志刚;马云鹏;胡春梅;;一个智力游戏的计算机求解方法与讨论[J];北京机械工业学院学报;2006年01期

8 李国和,赵沁平;信息系统的一种分块特征选取方法[J];北京航空航天大学学报;2003年03期

9 李国和,赵沁平,王喜;一种频繁复合项目集的混合求解方法[J];北京航空航天大学学报;2004年08期

10 宁文如,申海军;飞行员导航专家系统[J];北京航空航天大学学报;1997年06期

中国重要会议论文全文数据库 前10条

1 李萍;薛克敏;刘小旦;;人工智能技术在汽车覆盖件成形过程的应用[A];2004“安徽制造业发展”博士科技论坛论文集[C];2004年

2 姜帆;潘方胜;李红云;;一个基于FCR算法的推理机的设计[A];第三届全国软件测试会议与移动计算、栅格、智能化高级论坛论文集[C];2009年

3 刘忠菁;霍小江;黄训诚;陈学广;;节能电力调度中分布式仿生优化策略发生器的研究[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

4 孙兆豪;李昂;刘坤起;解建军;;论代数、逻辑和智能系统之间的对应关系[A];逻辑学及其应用研究——第四届全国逻辑系统、智能科学与信息科学学术会议论文集[C];2008年

5 孙涌;詹云;;停车诱导系统中最短路径的探索[A];江苏省系统工程学会第十一届学术年会论文集[C];2009年

6 刘奇;唐金国;李荣新;黄传毅;;基于框架的CGF实体行为建模研究[A];'2008系统仿真技术及其应用学术会议论文集[C];2008年

7 蒋序平;;一种面向网络管理的语义网络模型[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

8 尚文倩;王永滨;黄厚宽;;本科阶段《人工智能》课程教学改革初探[A];2008年中国高校通信类院系学术研讨会论文集（上册）[C];2009年

9 王应;;基于时间属性的多源日志因果关联算法[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

10 陈立鹏;;基于Win32的单机游戏架构设计[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

中国博士学位论文全文数据库 前10条

1 陈飞;基于Agent船载危险品应急管理资源协同分配机制研究[D];大连海事大学;2010年

2 赵进慧;膜计算仿生优化算法及应用研究[D];浙江大学;2010年

3 迟雷;基于过程控制优化的重组大肠杆菌高密度发酵研究[D];西北大学;2011年

4 马驰;松辽平原土地盐碱化监测机理及方法研究[D];吉林大学;2011年

5 田瑞;应急交通保障辅助决策支持系统相关模型与方法研究[D];吉林大学;2011年

6 冯启高;农业机械化系统分析及智能决策支持系统研究[D];江苏大学;2011年

7 刘慧;基于PLS-SEM的中国高等教育学生满意度测评研究[D];江苏大学;2011年

8 冯肖维;基于多传感器信息融合的移动机器人位姿计算方法研究[D];上海大学;2011年

9 赵明;组织因素对核电厂人因可靠性的影响研究[D];南华大学;2011年

10 俞斌;不确定条件下散装液体化学品船安全评价方法及应用研究[D];上海海事大学;2011年

中国硕士学位论文全文数据库 前10条

1 崔静怡;基于车载导航系统的大区域路径规划算法的设计与实现[D];山东科技大学;2010年

2 常春艳;矿山土地复垦方案论证管理系统研究[D];山东农业大学;2010年

3 梁永生;坦克战场景模拟仿真研究[D];哈尔滨工程大学;2010年

4 王涛;社保审计专家系统关键技术研究[D];哈尔滨工程大学;2010年

5 柴红霞;移动机器人在SLAM中数据关联方法的研究[D];大连理工大学;2010年

6 杨克强;LVQ神经网络在齿轮箱故障诊断中的研究[D];安徽农业大学;2010年

7 金璐钰;基于框架的事件抽取关键技术研究[D];苏州大学;2010年

8 苏瑞;基于多代理技术的多功能IED在数字化变电站中的应用[D];中国电力科学研究院;2010年

9 陈政;一种改进的遗传算法优化BP网络的研究及应用[D];暨南大学;2011年

10 徐衡;汽车性能检测线及其故障自动诊断系统[D];南昌大学;2010年

【二级参考文献】

中国期刊全文数据库 前10条

1 王海梅;周献中;;网络系统中的最短路径分析及其应用研究[J];兵工学报;2006年03期

2 彭飞,柳重堪,张其善;车辆定位与导航系统中的快速路径规划算法[J];北京航空航天大学学报;2002年01期

3 王同喜;孙淑霞;;基于A~*和Bresenham相结合的网络游戏寻路算法设计与实现[J];成都理工大学学报(自然科学版);2007年04期

4 陆锋;最短路径算法:分类体系与研究进展[J];测绘学报;2001年03期

5 王海霞;王春莲;;浅析计算机人工智能启发式搜索函数[J];电脑知识与技术;2008年08期

6 苏永云,晏克非,黄翔,朱培康;车辆导航系统的动态最优路径搜索方法研究[J];系统工程;2000年04期

7 高博;徐德民;张福斌;;动态目标的Field D~*算法及路径的提取计算[J];火力与指挥控制;2010年08期

8 赵伟华,章复嘉,梁红兵;车辆导航系统最优路径规划的研究与实现[J];杭州电子工业学院学报;2003年01期

9 段莉琼,朱建军,王庆社,马玲;改进的最短路径搜索A*算法的高效实现[J];海洋测绘;2004年05期

10 周艳霞;唐新春;;基于A~*算法的海底地形等深线模型构建方法研究[J];海洋测绘;2010年03期

中国硕士学位论文全文数据库 前2条

1 靳旭栋;游戏领域中启发式寻径算法的运用和优化[D];华东师范大学;2007年

2 张颖;基于D~*思想的ASON动态均衡恢复策略研究[D];江苏大学;2007年

【相似文献】

中国期刊全文数据库 前10条

1 冯玉翔,唐韶华;利用证书路径搜索实现交叉认证[J];计算机工程与应用;2003年36期

2 李得伟;韩宝明;韩宇;;一种逆向改进型A*路径搜索算法[J];系统仿真学报;2007年22期

3 李艳军;李智勇;陈思远;;一种面向3D场景的实时自动路径搜索方法[J];计算机应用;2010年01期

4 王天顺;张莉;;一种基于导航网格的路径搜索技术[J];电脑知识与技术;2010年12期

5 柯健;李帅;郝沅君;张倩倩;;虚拟场景中路径搜索技术的研究[J];苏州市职业大学学报;2012年02期

6 符光梅;王红;;基于节点可达度的公交多路径搜索算法[J];计算机应用研究;2012年12期

7 何国辉;陈家琪;;游戏开发中智能路径搜索算法的研究[J];计算机工程与设计;2006年13期

8 缪成;吴启迪;许维胜;;突发灾害下可靠路径搜索模型与算法[J];计算机工程与应用;2007年28期

9 陆悠;华泽;张妮;;基于二维有向集合扩散的公交网路径搜索算法研究[J];计算机与现代化;2009年12期

10 夏云龙;王正武;王杰;;考虑可靠性的降级路网最优路径搜索方法[J];交通科学与工程;2013年04期

中国重要会议论文全文数据库 前3条

1 陈思远;史广顺;李刚;;实时3D游戏中的智能体路径搜索与动作控制[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

2 文聪;徐红兵;邓罡;;任意多边形排样和最短切割路径搜索的算法及实现[A];2006中国控制与决策学术年会论文集[C];2006年

3 徐萍;马齐爽;;复杂供电系统的一种潜通路分析方法[A];第六届全国信息获取与处理学术会议论文集（1）[C];2008年

中国博士学位论文全文数据库 前1条

1 马尧;在线社会网络的信任网络发现与信任融合研究[D];华中科技大学;2014年

中国硕士学位论文全文数据库 前10条

1 陈彩;游戏地图中的分层和动态路径搜索[D];河北大学;2012年

2 李文亮;基于决策树划分的分层路径搜索[D];河北大学;2011年

3 左振华;基于ArcGIS API for Flex的人性化路径搜索算法研究及实现[D];内蒙古师范大学;2010年

4 徐菲云;3D游戏场景中路径搜索的研究与实现[D];电子科技大学;2007年

5 武玥;矿山巷道路径搜索及可视化[D];西安科技大学;2014年

6 靳旭栋;游戏领域中启发式寻径算法的运用和优化[D];华东师范大学;2007年

7 杨春晓;基于MapX的最优路径搜索理论与实施技术研究[D];吉林大学;2004年

8 李楠;信任网络中路径搜索的优化研究[D];河北科技大学;2012年

9 李铁松;游戏地图中分层路径搜索与地图复杂性度量研究[D];河北大学;2012年

10 史娟;基于地形分析的路径搜索算法研究[D];华中科技大学;2005年

  本文关键词：游戏地图寻路及其真实性研究，由笔耕文化传播整理发布。

本文编号：187180