基于多目标A～＊算法的游戏NPC路径规划

为游戏中非玩家控制角色(NPC)设计自动寻路算法是人工智能领域研究的一大热点,随着游戏环境的复杂化,仅仅将路径长度作为游戏NPC路径规划的目标已经不能满足真实游戏场景的寻路要求。实际的游戏寻路需要获得满足多个目标的折中最优路径,这才符合人工选择的路径结果。由此,提出了基于代价向量多目标A*算法的路径规划方法——MOVA*算法。通过将新方法寻路结果与人工选择路径进行实验对比,得出所提算法比传统路径规划算法实时性高、灵活性强,其获得更加智能、接近人工选择路径的寻路结果。

基于随机游走的多目标A~*算法的改进

针对基于降维技术改进的多目标A~*(NAMOA*dr)算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A~*(RWNAMOA~*dr)算法,其基本思想是当NAMOA~*dr算法陷入高原搜索时,利用随机游走策略及时找到一个出口(具有被上次扩展标签的启发值非支配的启发值的标签)逃离该高原搜索。针对NAMOA~*dr算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOA~*dr算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOA~*dr算法比NAMOA~*dr算法的运行时间平均减少了50.69%,占用的空间平均减少了约10%,能够为现实生活中加速多目标路径搜索提供理论支撑。