论文部分内容阅读
近年来,如何把人工智能理论应用于游戏开发,提高游戏的用户体验和运行效率成为研究的一个主要问题。论文针对游戏中的路径最优化展开研究。其研究目标是为游戏中的角色规划出一条从起点到目标点的无碰撞路径,并提升路径搜索效率和优化路径质量。论文针对游戏中的全局路径规划和局部避障展开研究,并把相关算法应用于《纷争大陆》游戏的开发。论文主要工作包括:1)针对大规模地图的全局路径规划问题,论文将A*算法与Bresenham算法相结合,并采用分层策略提高搜索效率。尽管A*算法被广泛应用于游戏中的地图全局路径规划,但是A*算法搜索无效节点多,在大规模地图中搜索效率低。论文将A*算法与Bresenham算法相结合,有效减少了无效节点的搜索数量。同时论文采用分层搜索策略,将寻路系统分成离线处理阶段与在线处理阶段。实验仿真表明,论文算法可以减少45%~65%的节点搜索数量,分层搜索策略可以将搜索效率提高数倍,且地图规模越大,提升越显著。2)针对势场栅格法在实时避障中存在的目标点不可达和局部最小点问题,论文提出改进斥力势场函数和模拟流水法设计分段函数,使游戏角色忽略无效障碍物,并以最短路径到达目标点。在动态变化的游戏地图中,人工势场法可以帮助角色在行进过程中躲避障碍物。论文在人工势场法的基础上提出适用于栅格地图进行寻路的势场栅格法,针对势场栅格法中存在的目标点不可达和局部最小点的问题分别通过改进斥力势场函数和模拟流水法解决。模拟结果表明,论文改进斥力势场函数可以使全局路径更加光滑并可以最终平稳到达目标点,模拟流水法可以帮助角色找到脱离局部最小点区域的最短路径。3)在上述算法研究基础上,设计并实现了游戏《纷争大陆》的智能寻路系统。论文描述了游戏《纷争大陆》开发框架和总体功能模块的设计,特别是寻路模块的设计和开发。游戏寻路系统主要包括地图构建,全局寻优,实时避障和世界地图四个模块。最后论文给出了游戏部分效果图。目前,《纷争大陆》已经完成开发,正在内部试运行。论文所研究的路径规划算法能够适应游戏中各种地图,性能稳定,明显提升了游戏用户体验。