1 / 6
文档名称:

寻路算法的优化探讨.doc

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

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

分享

预览

寻路算法的优化探讨.doc

上传人:小雄 2021/9/4 文件大小:161 KB

下载得到文件列表

寻路算法的优化探讨.doc

文档介绍

文档介绍:游戏编程中寻路算法的优化探讨
1背景
近年来,游戏产业的快速发展带动了游戏中人工智能(Artificial Intelligence, AI)的发展,越来越多的游戏采用人工智能技术提高游戏的可玩性。
一个在市场上畅销的成功的游戏,必须既要有华丽的画面视觉效果和悦耳的 听觉感受,又要有高超逼真的人工智能控制系统。游戏开发者把AI应用在计算 机或者游戏机的游戏中,就会使广大玩家感到他们所面对的由电脑AI系统控制 的敌人(即NPC)跟现实中的敌人一样拥有人类智能,让玩家留下如临实境的体 验。如果一个游戏的人工智能做得一团糟的话,那么绝大多数游戏玩家宁愿在网 络上跟真人进行对战了,或者就转投向其他拥有更高智能的游戏去了,这将给游 戏制作公司带来承重的打击甚至破产。
在电子游戏中,玩家操控主要角色,而其他角色的行为逻辑由人工智能操纵, 这些角色我们称之为NPC (Non-Player Character,非玩家控制角色)。大部分游 戏在开发过程中都会遇到路径探索问题,快速、准确地计算出游戏角色从地图中 的A点到达B点的一条路径,一直是游戏开发者追求的目标,同时也是游戏人 工智能研究的一个重要方面。
一般游戏AI系统都是从搭建最基本的寻路系统开始,一步步修改和完善后 而成的。本文重点阐述了游戏AI开发中最基本寻路算法及其优化。
2游戏编程中的简单寻路算法

考虑以下图1-1:
图1-1
该单位的初始位置(start)在地图的下方,想要到达地图的目标位置(goal)。 如果物体所能侦测到的地方(粉色部分所示)并没有障碍,那么物体就会直接向 上走到它的目标位置。但在距离顶端较近的位置时,物体侦测到了障碍,因而改 变了方向。该物体将不得不行进一个“U”形的路径绕过障碍物(如红色路径所 示)o通过对比可知,寻路系统能够通过搜索一个更大的范围(如蓝色区域所示),
并寻找一个更短的路线(如蓝色路径所示),使物体避免绕这条由凹陷障碍物造 成的远路。
我们可以通过改进物体的移动算法解决上图所示的陷阱。即可以避免在地图 上创建有凹陷的物体,或者标记整个凹陷物体的整个凸包为危险区域(即除非目 标在该区域内,否则避免进入该区域),如下图1-2:
1
图1-2
寻路系统则会让路径的决定提前,而不是如上图一样,物体直到移动到最后 一刻才发现问题所在。对于“改进物体移动算法”和“使用寻路系统规划路径”两种 方式有以下的折中:规划路径一般来说更慢,但效果更好;改进移动算法则会快 一些,但有时候会卡住。如果游戏地图经常改变,那么路径规划的方式可能没有 较大意义。
A*寻路算法
将寻路问题简化在二维网格中。大部分在AI和算法领域的寻路算法都是针 对作为数学结构的“图”本身,而并非针对这种网格化游戏地图。我们希望寻找 一种能利用游戏地图自身特征的方法。其实有些在二维网格图中我们认为是常识 的事情,一些在普通图上使用的寻路算法本身可能并没有考虑到。例如如果两个 物体距离较远,那么可能从一个物体到另一个物体的移动的时间和路径会较长。 对于方向来说,如果方向是朝东,那么最优路径的路径也应当是大体往东走,而 不是向西去。在网格中还可以从对称中获取信息,即先向北再向西,大部分情况 下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。

最近更新

乘用车公司岗位分析培训 27页

高速离心泵飞溅润滑方式原理分析 3页

高性能LiFePO 4C正极材料制备及性能研究 3页

诺和力早期应用的益处 34页

面向多核处理器的共享cache优化研究进展 3页

高一学期个人总结(29篇) 32页

铁路行车组织安全双向闭环系统可靠性研究 3页

钇掺杂ZrO 2陶瓷的制备及性能研究 3页

绿色会展政策对行业发展的影响-全面剖析 28页

轧钢厂水处理系统电气及自动化技术改造 3页

超高层建筑结构施工测量控制方法 3页

超低噪声放大器及数据处理技术——高温超导Jc.. 3页

贫煤作为高炉喷吹煤时助燃剂配方优化研究 3页

谈我国房地产交易市场的现状与发展对策 3页

论变换域通信系统中的时间同步与方法实现 3页

行政事业单位预算编制及管理研究 3页

虚拟社区知识共享行为实证研究 3页

营改增对施工企业会计核算的影响及对策 3页

苏州市十年酸雨变化趋势分析研究 3页

节能与新能源驱动下商用车车架纵梁结构和工艺.. 3页

2025年度专业割双眼皮手术术前协议书范本 8页

2025年农村房屋赠与合同附宅基地使用权变更协.. 8页

自动变速器与ABS系统综合故障探密及研究 3页

股权集中度及性质与真实活动盈余管理关系研究.. 3页

职业情感承诺与职业成就感对社会工作者职业意.. 3页

美人蕉生态护坡对径流污染净化作用的初步研究.. 3页

2023年社会工作实务初级重点知识点汇总 18页

“十三五”全国眼健康规划(2016-2020)实施自评.. 3页

高处作业安全培训试卷 4页

砖厂应急预案11篇 27页