共查询到20条相似文献,搜索用时 109 毫秒
1.
游戏开发中智能路径搜索算法的研究 总被引:8,自引:3,他引:8
路径搜索是许多游戏特别是即时战略游戏的核心组成部分,首先介绍了游戏中路径搜索的相关概念。路径搜索的算法有很多,不同的搜索算法有其不同的搜索策略、时间效率、空间消耗与应用场合。分析对比了多种路径搜索算法的运行数据之后,详细讨论了A^*算法。由于游戏中的路径搜索有其自身的特点,针对游戏中路径搜索的具体要求从搜索效率、路径的真实平滑性和动态变化状态空间的适应性等方面对A^*算法进行了优化和改进。 相似文献
2.
文章在对A*搜索和启发式搜索技术进行详细分析与研究的基础上,将A*算法应用于flash游戏中的寻路,并在此基础上分析出A*算法的实际应用时间效率和空间效率。 相似文献
3.
本文对数字化交通地图中最短路径算法设计进行了研究和探讨,在传统的Dijkstra算法的基础上提出了一些合理的改进方案,并将改进后的A^*算法和邻接表结构与原有Dijkstra算法及传统的数据存储结构进行了比较。在A^*算法中,任意两点之间最短路径的搜索具备一定的方向性,即搜索的结点数明显地少于Dijkstra算法的搜索结点数,系统响应速度明显快于采用原始Dijkstra算法的响应速度,A^*算法的效率明显提高。 相似文献
4.
针对即时战略游戏中多智能体寻路时间长和移动碰撞阻塞的问题,提出一种基于组合式改进的流场寻路算法。首先,采用红黑树存储数据,提高数据的存取速度;其次,采用惩罚函数将非线性的偏微分方程问题转化为线性的无约束问题,简化完整代价值的计算方式;最后,引入前置邻接点关联节点,生成流场方向。该算法与改进前的流场寻路算法相比,路径计算时间减少20%,平均移动时间稳定在20 s。实验结果表明,在即时战略游戏中采用改进后的流场寻路算法能够有效缩短寻路时间,提高智能体移动速度,提升游戏人工智能水平。 相似文献
5.
一种改进的群体智能寻路算法 总被引:1,自引:0,他引:1
以游戏中群体智能角色的路径搜索为研究背景,提出一种改进的群体智能寻路算法。该方法把游戏寻路过程划分成三个阶段:第一阶段为预处理阶段,针对特定的目标点,采取逆向路径搜索策略,建立最优解路径表。第二阶段,针对动态障碍物的避让,运用实时A*算法生成局部动态路径,并与初始路径进行拼接。第三阶段,对找到的路径进行关键点优化和Catmull-Rom样条平滑处理。实验结果表明该方法在游戏开发中的实用价值。 相似文献
6.
7.
PAN Jian-sheng 《数字社区&智能家居》2008,(36)
在游戏软件中,人工智能是一个重要而又复杂的模块,而寻路算法是人工智能运用于电子游戏中的最基本问题之一。针对游戏中路径搜索的特点,在对一般搜索算法、常见搜索算法和启发式搜索技术进行详细地分析与研究的基础之上,结合实际应用情况,对A*算法进行了一些优化与改进。 相似文献
8.
9.
10.
A*算法广泛应用于移动机器人路径规划中,而传统A*算法在寻路时,普遍存在搜索时间较长、效率低下等问题,因此,采用双向搜索的方式,对传统A*算法加以改进,该算法在路径规划过程中,可同时进行正反向路径搜索,同时采用正反向搜索交替机制,保证了最终目标节点搜索在连线中点区域内相遇,从而缩短了寻路计算时间。在MATLAB平台上,针对改进后的A*算法进行仿真实验,结果证明,双向A*算法减少了规划时间,且可生成最优路径。最后,将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上,进行现场实验,实验结果表明,双向A*算法减少了寻路计算时间,从而使得路径搜索效率得到显著提升,且规划路径合理,满足路径规划要求。 相似文献
11.
为了减少AGV(Automate Guide Vehicle,自动导引车)的运输路径长度和转折次数,提出了改进的A星算法,采用几何方法对传统A星算法规划出的路径进行进一步优化。首先遍历路径上的所有节点,剔除路径中冗余节点和不必要拐点,获取仅包含起点、必要拐点、终点的路径。最后计算AGV在拐点处的旋转角度及旋转方向,使AGV在拐点处能够调整自身姿态。并分别对传统A星算法、蚁群算法和改进A星算法进行了对比实验。实验结果表明该方法不仅保留了A星算法运算速度快的优点,还能够有效地规划出距离短且平滑的路径。提高了AGV的运行效率,降低了AGV的耗能。 相似文献
12.
通过理论分析,结合实际应用,在GIS节点数很大的数字地形图中,从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析,较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A★算法四种算法代价及优缺点. 相似文献
13.
粗糙域Voronoi图离散生成算法研究 总被引:3,自引:0,他引:3
Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A‘算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A’算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A’算法估价函数权值与粗糙域粗糙特性正相关,并以此获得r算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。 相似文献
14.
为提高足式移动机器人的避障能力和路径规划效率,提出一种凸优化与A*算法结合的路径避障算法.首先,基于半定规划的迭代区域膨胀方法IRI-SDP(iterative regional inflation by semi-definite programming),通过交替使用两种凸优化算法快速计算出地面环境中无障碍凸多边形及其最大面积内切椭圆,用于移动机器人的局部避障和任务动作规划;然后,结合经典的A*算法,建立机器人局部和世界坐标系、机器人质心轨迹转换模型、碰撞模型和启发式代价函数,在全局环境中寻找最优成本最小的路径;最后,通过仿真实验验证该算法的有效性. 相似文献
15.
针对洪涝灾害中存在积水障碍区的卡车-无人机协同配送的最优路径及最短配送时间问题,建立了一种整数规划模型,并提出了一种两阶段启发式算法,第一阶段将积水障碍区进行二维网格化处理并确定无人机运输救灾物资时卡车的安全等待点以及各等待点无人机运送客户的集合,第二阶段提出阶段性规划算法,结合改进A*算法与非线性收敛因子的模拟退火鲸鱼算法对卡车绕积水障碍区的配送路径进行优化,在确保卡车行使安全的前提下,将A*算法的全局寻优性及鲸鱼算法的局部搜索精确性结合。解决存在积水障碍区的救灾物资配送问题,最后通过实例验证了所提出方法可以快速安全地解决洪涝灾害中救灾物资的避障配送问题。 相似文献
16.
迷宫搜索算法的比较研究 总被引:1,自引:1,他引:0
研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较.在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度.通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用. 相似文献
17.
在全局光照算法中,光子图算法是一种与视点无关的物空间辐射度近似计算方法,提出了一种基于重要度驱动采样的自适应Projection map算法,利用它可以在光子图算法中提高光子发射的有效性和准确性,加快渲染速度并取得更好的图像质量.实验表明,该算法能够有效地减少光源发射光子的次数,提高光子的命中率,具有相当的应用价值. 相似文献
18.
19.
20.
周先曙 《数字社区&智能家居》2010,(6):1403-1405,1412
最短路径问题是在给定的网络图中寻找出一务从起始点到目标点之间的最短路径。该文分别从动态规划、Dijkstra、A*算法、遗传算法这四种算法设计方法入手,概述了各种设计方法的原理,提出了求解最短路径的算法思想,并对算法进行分析.提出了改进方法。 相似文献