龙源期刊网 http://www.qikan.com.cn
基于多目标遗传算法的游戏路径规划研究 作者：刘大瑞 冯镍
来源：《软件导刊》2014年第01期
摘要：为游戏中非玩家控制角色（NPC ）设计自动寻路算法是人工智能研究领域的一大热点。首先模拟多目标游戏地图作为实验平台，然后以路径长度、路径安全程度和对游戏角色的耗费为评估目标，提出了基于多目标遗传算法的路径规划方法。经过实验验证，算法虽然比A*算法实时性差，但其对地图全局有很好的把握，在多目标环境下，其得到的路径存在明显的全局最优。
关键词：多目标优化；遗传算法；游戏NPC ；路径规划
中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2014）001004902 作者简介作者简介：刘大瑞（1987-），男，四川大学计算机学院硕士研究生，研究方向为数字娱乐与人机交互。
0 引言
随着游戏产业的快速发展，对游戏质量的要求逐步上升，玩家希望看到趣味性足、挑战性强的高质量游戏。为了提高游戏质量，大量游戏引入了非玩家控制角色[1]（NPC ）与玩家进行交互，以提高游戏的可玩性和真实性。因此，NPC 的行为研究成为游戏设计者关心的重要因素。而在游戏中，NPC 的行为除与玩家交互外，主要就是自主寻路，其所选路径的质量决定其自身的智能性和游戏的真实性。
对于游戏NPC 智能路径规划的研究，提出过许多方法，主要有A*算法及其改进算法[2，3]、遗传算法[4]、蚁群算法[5]和神经网络方法[6]等。但在实际应用中，游戏设计者普遍选择A*算法，这是由其较高的正确率和较好的实时性决定的。但是，随着游戏地图[7]的多样化，仅仅用路径长短去评估路径质量是不够的，游戏地图中通常还需要考虑路径的安全性、路径的耗费等多个方面。在此情况下，A*算法就变得不适用，由此诞生了许多不同的方法。其中，孙纯哲提出了双蚁群交叉算法[8]，但该方法未考虑连续障碍物，实时性差。此外，Xiao J，Z.Michalewicz[9]提出了线性加权的改进A*算法，其只是将多个目标进行简单加权相加，得到启发函数，故该方法存在主观性和随意性。针对以上情况，本文提出了一种多目标遗传算法的路径规划方法。
本文为游戏中的NPC 寻路，提出了一种多目标智能路径规划算法，并将其与传统寻路算法进行对比，突出其在游戏中智能自动寻路的优点。本文使用基于多目标的遗传算法优化路径，同时引入帕累托最优解集[10]作为寻路结果，在综合考虑多个寻路目标平衡的基础上，获得满足条件的最优解集。最后，从解集中，筛选满足游戏情景的最优路径选择。
龙源期刊网 http://www.qikan.com.cn
基于多目标遗传算法的游戏路径规划研究 作者：刘大瑞 冯镍
来源：《软件导刊》2014年第01期
摘要：为游戏中非玩家控制角色（NPC ）设计自动寻路算法是人工智能研究领域的一大热点。首先模拟多目标游戏地图作为实验平台，然后以路径长度、路径安全程度和对游戏角色的耗费为评估目标，提出了基于多目标遗传算法的路径规划方法。经过实验验证，算法虽然比A*算法实时性差，但其对地图全局有很好的把握，在多目标环境下，其得到的路径存在明显的全局最优。
关键词：多目标优化；遗传算法；游戏NPC ；路径规划
中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2014）001004902 作者简介作者简介：刘大瑞（1987-），男，四川大学计算机学院硕士研究生，研究方向为数字娱乐与人机交互。
0 引言
随着游戏产业的快速发展，对游戏质量的要求逐步上升，玩家希望看到趣味性足、挑战性强的高质量游戏。为了提高游戏质量，大量游戏引入了非玩家控制角色[1]（NPC ）与玩家进行交互，以提高游戏的可玩性和真实性。因此，NPC 的行为研究成为游戏设计者关心的重要因素。而在游戏中，NPC 的行为除与玩家交互外，主要就是自主寻路，其所选路径的质量决定其自身的智能性和游戏的真实性。
对于游戏NPC 智能路径规划的研究，提出过许多方法，主要有A*算法及其改进算法[2，3]、遗传算法[4]、蚁群算法[5]和神经网络方法[6]等。但在实际应用中，游戏设计者普遍选择A*算法，这是由其较高的正确率和较好的实时性决定的。但是，随着游戏地图[7]的多样化，仅仅用路径长短去评估路径质量是不够的，游戏地图中通常还需要考虑路径的安全性、路径的耗费等多个方面。在此情况下，A*算法就变得不适用，由此诞生了许多不同的方法。其中，孙纯哲提出了双蚁群交叉算法[8]，但该方法未考虑连续障碍物，实时性差。此外，Xiao J，Z.Michalewicz[9]提出了线性加权的改进A*算法，其只是将多个目标进行简单加权相加，得到启发函数，故该方法存在主观性和随意性。针对以上情况，本文提出了一种多目标遗传算法的路径规划方法。
本文为游戏中的NPC 寻路，提出了一种多目标智能路径规划算法，并将其与传统寻路算法进行对比，突出其在游戏中智能自动寻路的优点。本文使用基于多目标的遗传算法优化路径，同时引入帕累托最优解集[10]作为寻路结果，在综合考虑多个寻路目标平衡的基础上，获得满足条件的最优解集。最后，从解集中，筛选满足游戏情景的最优路径选择。