游戏场景中基于势场的交互寻路方法

在即时战略游戏中,路径规划是一种重要且常见的任务。游戏的实时性要求玩家能够快速寻找一条进攻的路径,而且游戏单元之间普遍存在的交互作用对寻路质量有着重要的影响。传统的寻路算法如Dijkstra算法虽然能够找到最优路径,但是耗时较多,而且未体现真实游戏中的交互。为此选取RTS游戏中一种典型的攻防场景,提出基于人工势场的快速高效动态寻路方法,同时为了体现RTS中游戏单元之间的交互性,将模糊测度引入到势场寻路中。实验结果表明,采用人工势场法寻路较Dijkstra算法耗时少、路径平滑;而引入模糊测度体现了真实游戏中单元之间的交互影响作用,与真实的游戏场景更为接近。     

即时战略游戏的智能流场寻路算法设计与实现

针对即时战略游戏中多智能体寻路时间长和移动碰撞阻塞的问题,提出一种基于组合式改进的流场寻路算法。首先,采用红黑树存储数据,提高数据的存取速度;其次,采用惩罚函数将非线性的偏微分方程问题转化为线性的无约束问题,简化完整代价值的计算方式;最后,引入前置邻接点关联节点,生成流场方向。该算法与改进前的流场寻路算法相比,路径计算时间减少20%,平均移动时间稳定在20 s。实验结果表明,在即时战略游戏中采用改进后的流场寻路算法能够有效缩短寻路时间,提高智能体移动速度,提升游戏人工智能水平。     

A~*算法在cocos2d-x游戏开发中的研究和应用

路径搜索系统是游戏系统中非常重要的一部分,好的路径搜索算法对于游戏的重要性不可言喻。A*算法是当前游戏开发中使用最为广泛的算法,也是游戏人工智能路径搜索中的研究重点。A*算法总是寻找估价值最小的节点,从而能够找到最短路径。笔者首先对A*算法原理进行深入研究,再深入研究其在cocos2d-x寻路的应用和实现。     

一种改进的群体智能寻路算法

以游戏中群体智能角色的路径搜索为研究背景,提出一种改进的群体智能寻路算法。该方法把游戏寻路过程划分成三个阶段:第一阶段为预处理阶段,针对特定的目标点,采取逆向路径搜索策略,建立最优解路径表。第二阶段,针对动态障碍物的避让,运用实时A*算法生成局部动态路径,并与初始路径进行拼接。第三阶段,对找到的路径进行关键点优化和Catmull-Rom样条平滑处理。实验结果表明该方法在游戏开发中的实用价值。     

游戏地图中的分层动态路径搜索算法

在大型游戏地图环境中,玩家必须对动态地形做出即时反应,而动态寻路算法对改变节点的位置非常敏感。为此,结合增量路径搜索(LPA*)算法和分层路径搜索(HPA*)算法,提出一种分层动态路径搜索(HPLPA*)算法。对地图分层形成抽象图,并在动态环境中及时更新,采用LPA*搜索,找到抽象路径再细化,以此形成本地路径。实验结果证明,与LPA*和HPA*相比,该算法更有效。     

基于陷阱层次的预处理寻路算法

针对当前寻路算法不能很好满足某些实时性应用中需要快速找到最短路径的要求,提出一种基于陷阱层次预处理的寻路算法。通过在预处理阶段探测出陷阱,即在实际搜索中并不需要的区域,在进行路径搜索时削减掉这些区域,使得无用空间的探索大幅度减少,提高了搜索效率。实验结果表明,该算法不但显著地减少了节点数的扩展,节约了搜索时间,而且保证了路径寻找的最优化,对于提高寻路算法的性能是一个切实可行的解决方案。     

基于Silverlight网页游戏的寻径优化算法

为了解决A*路径搜索算法在Silverlight网页游戏中的搜索费时和路径曲折等问题,在结合光线跨越算法和引入父结点指针的二叉堆存储开启列表的A*算法的基础上,提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有研究的基础上使用光线跨越算法减小A*算法搜索规模,同时将动态关键点技术与光线跨越算法结合来优化算法返回的路径。将该算法在游戏所使用的网格地图中进行实验,实验结果表明,该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径,同时缩短寻路的时间消耗和所寻的路径长度,提高游戏的可玩性。     

面向3D场景智能寻路技术综述

智能寻路技术是人工智能的一个重要应用,该技术被应用到许多领域,其中在大型3D场景游戏中的应用尤为广泛。对现有智能寻路技术包括场景地图表示法、路径搜索技术分别进行了研究对比,分析每种方案的优劣势,总结了智能寻路技术的发展趋势。     

游戏人工智能中的高级寻路技术

本文探讨了现有的A*(Astar)寻路算法,并在此基础上进行优化,增加动态寻路的概念,A*算法是针对静态物体的寻路,实际游戏中会出现许多动态物体,如移动的队友或怪物,本文在寻路过程中将考虑和动态物体的碰撞,优化现有算法,大大提高游戏的真实度。实验证明,该算法在大规模的地形上寻路效果也较好。     

复合寻路策略在手机游戏中的应用研究

复合寻路算法成功应用于手机游戏CrazyWar。该寻路算法包含三个寻路模块:直线寻路模块、A*寻路模块、航点寻路模块。提出的复合寻路算法先通过航点算法得到一个总体的大致路径,再在寻路精细方面由直线寻路模块和A*寻路模块处理,从而解决了A*寻路模块中随搜索地图增长而资源消耗也呈几何增长、大范围搜索耗时过长以及提高估值因子所带来的路径准确度降低的缺点。通过理论分析和实际应用表明:复合寻路算法在寻路速度、资源消耗、寻路效果上均优于单一寻路算法,具有很好的推广性与实用价值。     

用分层关联方法求有向图中所有Hamilton回路的算法

首先建立了有向图中初级通路的关联关系,并对初级通路的关联关系进行了分析,得到了关于初级通路关联关系的一些重要结果．然后,对初级通路的关联关系进行了分级分层．在此基础上,设计了求有向图中所有Hamilton回路的算法．该算法利用长度为k的初级通路及其分层关联关系逐步求长度为k＋1的初级通路及其分层关联关系的方法,求得有向图的所有Hamilton回路．通过理论分析可以看到,所设计的算法与已有的求有向图的所有Hamilton回路的算法相比,避免了大量的重复计算,从而降低了算法复杂度,为求解Hamilton回路问题提供了新思路．     

导航系统中多目标路径平滑化规划的研究

路径规划是车辆、机器人出行、无人机航路推荐和计算机游戏等许多应用中的关键任务。现有的大多路径规划常简化为单目标优化问题进行求解。但在现实生活中,还需要同时考虑多种规划目标,且用于规划路径的目标之间还存在着彼此不能变换的问题。在熟知的路径规划算法（D*Lite）上提出了一种新的多目标路径平滑化规划算法-平滑多目标D*Lite算法。通过构造一条初始多目标平滑路径,当检测到环境变化时采用增量搜索思想,仅更新受影响结点并从当前结点重新进行规划得到一条新的多目标平滑路径。仿真结果表明,该算法不但能有效躲避突发障碍物,规划路径拐点较少,还能提高搜索效率,可有效应用于具有不同非交互规划目标的导航系统。     

基于改进A*算法的移动机器人路径规划研究

A*算法广泛应用于移动机器人路径规划中，而传统A*算法在寻路时，普遍存在搜索时间较长、效率低下等问题，因此，采用双向搜索的方式，对传统A*算法加以改进，该算法在路径规划过程中，可同时进行正反向路径搜索，同时采用正反向搜索交替机制，保证了最终目标节点搜索在连线中点区域内相遇，从而缩短了寻路计算时间。在MATLAB平台上，针对改进后的A*算法进行仿真实验，结果证明，双向A*算法减少了规划时间，且可生成最优路径。最后，将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上，进行现场实验，实验结果表明，双向A*算法减少了寻路计算时间，从而使得路径搜索效率得到显著提升，且规划路径合理，满足路径规划要求。     

一种基于改进A*算法的室内导航路径规划方法

路径规划是室内导航研究的关键技术之一。A^*算法是一种常见的路径规划算法,当区域的点数量较少时,找寻最优路径是最有效的直接搜索方法。但当路径点规模较大时,使用数值优化算法求解最佳路径的难度急剧增加,导致规划时间所需时间过长,不符合实时性要求。为提高路径规划方法中的效率和稳定性,在梳理室内导航路径规划已有算法和方案的基础上,分析了A^*算法的基本思想与实现步骤,并针对室内导航中A^*路径算法存在的问题,提出了一种改进型A^*算法优化的方案。利用用户对最短距离和直行路程的需求,在位置计算中,引入同时考虑方向和距离启发信息的启发函数,把POI点与寻路节点分开处理,以映射的方式建立联系。将该方案应用于室内导航中A^*算法实现伪代码,对算法改进前后进行算法效率测试。结果表明,改进后A^*算法的整体效率提升了近50%,改进型A^*算法在室内导航路径规划的效率和稳定性比较优,达到了加速导航算法的目的。     

基于分块路径缓存的在线路径搜索算法

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法。对路网重采样得到路网密集度图像,提出路网分块算法ISODATA。根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法。实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s以内,降低网络地图服务路径计算服务器负荷。     

基于灰度图像边缘检测的3D游戏路径搜索*

着重研究了3D游戏中路径搜索算法。其路径搜索算法内容包括障碍认知与标志、A*路径规划、高度代价函数与路径最短相结合的,由计算粒度引出的基于静态障碍物体碰撞检测的动态路径规划。该算法在实际的游戏引擎中进行了测试,其效率和实时性都满足要求。     

三维最短路径分析算法的实现及其可视化

最短路径算法是路径搜索领域的重要问题,也是最优路径分析算法的基础。论文设计并实现了适用于栅格地形数据的数据存储结构。在分析A*算法思想的前提下,将计算机图形学中的直线求交算法应用到启发函数的计算中,实现了针对规则栅格地形数据计算最短路径的算法并将其进行了三维可视化显示。