共查询到19条相似文献,搜索用时 140 毫秒
1.
2.
游戏开发中智能路径搜索算法的研究 总被引:11,自引:3,他引:8
路径搜索是许多游戏特别是即时战略游戏的核心组成部分,首先介绍了游戏中路径搜索的相关概念。路径搜索的算法有很多,不同的搜索算法有其不同的搜索策略、时间效率、空间消耗与应用场合。分析对比了多种路径搜索算法的运行数据之后,详细讨论了A^*算法。由于游戏中的路径搜索有其自身的特点,针对游戏中路径搜索的具体要求从搜索效率、路径的真实平滑性和动态变化状态空间的适应性等方面对A^*算法进行了优化和改进。 相似文献
3.
分支限界法在游戏地图寻径中的应用 总被引:1,自引:0,他引:1
分析了游戏地图寻径中的宽度优先,深度优先和启发式搜索算法,提出了一种基于宽度优先直接标记路径的分支限界搜索算法,最多使用O(N+L)的时间完成最短路径搜索,能很好地适用游戏地图中复杂地形的寻径要求。 相似文献
4.
路径搜索是游戏中非常重要的一部分,A*算法是最常用的搜索算法,但是使用A*算法搜索出的路径的真实性常常不能让人满意。本文介绍A*搜索算法及存在的路径问题,针对该算法在游戏中暴露的问题,提出一种平滑改进的算法,较好地解决了这个问题。 相似文献
5.
本文对路径规划中比较常见的A*搜索算法进行研究,对几种基于A*搜索算法的路径规划方法如A*单向搜索、A*双向搜索及A*二次搜索进行讨论,并分析其优缺点,同时提出两个有待解决的问题。 相似文献
6.
7.
动态拓扑网络最短路径启发式算法 总被引:1,自引:0,他引:1
针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法.在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围.采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率.仿真试验结果表明该算法具有良好的性能. 相似文献
8.
机器人学是现在及未来科技发展的重点,路径规划是机器人学中的一个重要课题.生物界一些群居动物有严格的等级制度和职责分工,受社会群居动物行为启发,提出社会群体搜索算法(social group search algorithm, SGSO).社会群体搜索算法对群体的分类及信息反馈机制——领导-追随机制的制定,降低了早熟的概率,交叉变异和淘汰机制的引入增加了搜索范围,减少了陷入局部最优的可能.同时,对提出的社会群体搜索算法进行了分析,从理论上证明了算法的收敛性;将社会群体搜索算法应用于机器人路径规划进行仿真,从实验中验证了算法的有效性,并与遗传算法和粒子群算法比较,进一步证明了社会群体搜索算法在机器人路径规划问题中的有效性和高效性. 相似文献
9.
10.
PAN Jian-sheng 《数字社区&智能家居》2008,(36)
在游戏软件中,人工智能是一个重要而又复杂的模块,而寻路算法是人工智能运用于电子游戏中的最基本问题之一。针对游戏中路径搜索的特点,在对一般搜索算法、常见搜索算法和启发式搜索技术进行详细地分析与研究的基础之上,结合实际应用情况,对A*算法进行了一些优化与改进。 相似文献
11.
为实现不同条件下的无人机自主航路规划,提出一种变步长稀疏A*算法。当遭遇紧迫环境时,缩小稀疏A*算法(SAS)的搜索步长,使无人机安全通过,提高了搜索精度和算法的鲁棒性,否则,保持较大的搜索步长扩展,保证搜索的高效性;并依据动态稀疏A*算法(DSAS)的思想,给出了应用于实时航路规划的多步搜索方案。仿真结果表明,算法简单有效地实现了复杂环境下的航路规划以及动态环境下的在线实时航路规划。 相似文献
12.
针对实际飞行环境中无人机的三维航线规划问题,提出了一种创新启发式优化算法——牛顿帝国主义竞争算法(NICA,Newtonian imperialist competitive algorithm).该算法能够根据无人机的飞行轨迹,从起始位置到任务目标位置生成平滑的航线路径,约束航线规划,使得目标完成任务的时间最小化.该算法也能为无人机在真实地形上的航线提供最佳轨迹路径.最后通过与ICA、GA和PSO算法进行比较,验证了改进算法的有效性.结果表明:改进帝国算法提高了全局最优解的搜索能力,在收敛速度和精度上优于其他3种算法,适合用来解决无人机的三维航线规划问题. 相似文献
13.
研究无人机路径规划优化问题,针对在城市环境下执行飞行任务前,需要根据所经城市内已知的建筑物信息以及飞机本身性能的限制计算出飞行轨迹,并根据规划出的路径完成飞行任务。在给定起始点和目标点上,提出了一种城市建筑物遮挡模型的无人机路径规划方法。主要包含两方面的内容:一是利用圆柱虚拟城市建筑物环境使建筑物对无人机的遮挡面积可计算;二是在计算出无人机飞行的水平平面上(x,y)点遮挡值的基础上,给出了无人机搜索区域等分的沿对角线折线走法的优化路径规划,得到一条遮挡面积最小的路径并进行仿真。仿真结果表明,规划方法能够快速有效地完成规划任务,获得满意的航迹,为无人机优化路径提供了依据。 相似文献
14.
基于分层道路网络的新型路径规划算法 总被引:6,自引:1,他引:6
为了降低路径规划算法的搜索空间,同时使得规划的结果更加合理,提出一种分层路径规划算法.该算法利用道路网络中道路的不同等级特性对路网进行分层处理,构造分层搜索策略,达到加快路径规划速度的目的.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的一个应用实例.实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在1s之内. 相似文献
15.
16.
针对复杂海洋环境下水面舰艇航路规划时出现的大地图寻路速度慢、航路安全性差、航路不平滑等难题,结合电子海图提出了一种改进A*算法的航路规划方法。提出一种自适应的改进启发函数,在搜索节点时加入目标节点的方位信息,加快了A*算法搜索路径的速度;加入迫使航路远离障碍物的安全距离,解决了传统A*算法沿障碍物边缘寻路导致航路安全性差的问题;对原始航路进行二次优化,在对原始路径提取转折点后,通过判断任意两个转折节点的直线可达性,将转折节点之间的实际距离转化为距离矩阵,使用Dijkstra算法优选出航路长度更短的关键转折点,最终使用二阶贝塞尔曲线对航路转折处进行平滑处理,以满足航路平滑且易跟随的要求。仿真实验表明,相对于传统A*算法,改进算法规划的路径具有寻路速度更快、航路距离更短、航路安全性更高的特点。 相似文献
17.
18.
采用一种并行的A*算法实现了复杂地理环境下低空飞行器的三维路径规划。该算法将A*算法的基本操作设计成并行执行形式,并利用OpenMP将其线程化,结合约束条件,最终完成在三维空间中避开障碍物的路径搜索过程。使用建模工具Creator和开发工具Vega为仿真平台,完成对复杂地形地貌场景的设计,在此基础上对上述算法进行了验证。仿真结果表明该并行方式较之串行方式能获得更快的寻优速度,加速比也随着规模的增大而提高。 相似文献