用于游戏NPC路径规划的改进遗传算法*

李井颂， 钱 谦,3, 孙铭会

(1.昆明理工大学 云南省计算机技术应用重点实验室，云南 昆明 650500；2.吉林大学 计算机科学与技术学院，吉林 长春 130012；3.吉林大学 符号计算与知识工程教育部重点实验室，吉林 长春 130012)

计算与测试

用于游戏NPC路径规划的改进遗传算法*

李井颂1， 钱 谦1,3, 孙铭会2,3

(1.昆明理工大学 云南省计算机技术应用重点实验室，云南 昆明 650500；2.吉林大学 计算机科学与技术学院，吉林 长春 130012；3.吉林大学 符号计算与知识工程教育部重点实验室，吉林 长春 130012)

针对游戏非玩家控制(NPC)路径规划中传统遗传算法计算速度慢、正确率低等问题，设计了改进型遗传算法。提出了最佳种群规模估计方法，设计了基于精英主义思想的遗传算子。根据游戏地图的特点，引入了基于启发式深度优先搜索的变异操作。与传统遗传算法以及其他学者的改进算法进行了对比实验。实验结果表明：算法能够在保证正确率的前提下，提高计算速度，并且在多目标的环境下同样适用。

人工智能； 路径规划； 遗传算法； 种群规模； 精英主义； 启发式深度优先搜索

0 引 言

计算出游戏非玩家控制(NPC)角色从起点到目标点的最短路径是游戏开发中最基本的问题。游戏NPC属于智能Agent的一种，研究出快速且高效的寻径方法,而且对于车辆路径规划[1]和机器人路径规划[2]以及最短路径路由问题[3]都有重要的借鉴意义。游戏地图一般存在多条从起点栅格到终点栅格的最短路径。而遗传算法由于其并行搜索方式，每次运行时一般可以得到不同的路径，被广泛用到游戏寻径计算中[4～6]。

传统遗传算法存在计算速度慢、正确率低等诸多问题。因此，多位学者对其进行了改进。黎忠文等学者[4]提出了节点复杂度算子的概念。节点复杂度，即图中边的条数和节点个数平方的比越大代表可行走的区域越宽广，采用较大的交叉率与变异率来避免陷入局部最优解。此做法虽然提高了搜索成功率，但是增加了运行时间。孙宝林[7]和李擎[8]主要对遗传算法中的传统随机变异进行了改进，使变异能够朝着最优解的方向进行，虽然缩短了求得最优解所需的进化代数，但是计算速度并没有明显提高。

在遗传算法中，种群规模越大，全局搜索能力就越强，但是速度也就越慢[9]，而遗传进化代数与网络规模相关性并不大[10]。故本文提出了一种最佳种群规模估计方法，期望使用的种群规模具有全局搜索性而又不浪费；设计了基于精英主义思想的遗传算子，以保留种群中的优秀个体；引入了基于启发式深度优先搜索的变异操作，以缩短进化到最优解所需的迭代次数。

1 传统遗传算法游戏NPC路径规划

1.1 游戏地图介绍

游戏地图由多个图层构成，图层栅格常被称为瓦片，每个瓦片都有自己的唯一坐标(图1)。在碰撞检测层中，通过定义瓦片的“键——值”对定义该瓦片作为可通过节点还是障碍物节点。

图1 游戏地图示意

1.2 遗传编码与初始群体的生成

在遗传编码时，一般将瓦片的坐标作为基因进行实数编码，染色体的第一个基因为起点坐标，最后一个基因为终点坐标，中间的基因为路径经过的每一个瓦片的坐标。

在生成染色体时，由起点出发，随机选择当前结点的邻居节点中的可通过节点，将其坐标加入染色体，依此循环，直到找到目标点为止，生成了一条染色体。重复上述操作，直到达到指定的种群规模。

1.3 遗传操作

遗传操作包括选择、交叉、变异3种操作：1)选择操作常用精英选择方式，即用部分优秀个体替换部分较差个体[11]。2)交叉操作首先找到两父代染色体的共有基因集合，然后从中随机选取基因作为交叉点进行交叉，从而避免了交叉后产生的子代染色体所代表的路径不连通的现象。3)变异操作首先将父代染色体删除，然后随机生成一条新的染色体，作为子代染色体。

2 基于改进遗传算法的游戏NPC路径规划

2.1 确定种群规模与遗传算子的执行顺序

种群规模过大，会影响计算速度；过小，又会降低全局搜索能力。本文定义最佳种群规模bestpop的计算公式为

bestpop=[n/min{row,col}]

(1)

式中n为地图的可通过节点数；row为地图的行节点数；col为地图的列节点数；min{row,col}表示行、列较小者的节点数；[ ]为四舍五入取整运算。式(1)中用行或列的较小者中的节点数作为分子，而不用行、列的平均节点数，目的是首要考虑搜索成功率，而把计算速度放在次要位置。

不同于传统遗传算法，为使交叉算子和变异算子更好地配合，本文将遗传算子执行顺序设置为：选择、变异、交叉。

2.2 设计适应度函数

本文直接将染色体的长度定义为染色体的适应度，即

fitness(xi)=distance(xi),i=1,2,...,M

(2)

式中xi为第i个个体，distance(xi)为第i个个体的长度，M为种群规模。相应地调整进化规则：保留适应度小的染色体，淘汰适应度大的染色体。

2.3 生成初始种群

传统遗传算法在生成染色体时会产生环路，从而产生大量较差个体。初始群体的优秀程度是提高算法时间效率的关键[12]，为了避免产生环路，采用文献[13]的做法：凡是加入到染色体的节点，都做一个标记，只有没有被标记过的节点才能被选作新的节点。同时又产生一个新的问题：由于加入到染色体的节点都做了标记，如果生成染色体的过程中遇到了“死胡同”，程序将无法退出“死胡同”。因此，首先判断当前基因邻居节点中可行走的节点数是否为0。如果是，则从染色体中删除当前基因，再考察当前基因的上一个基因。如图2，生成染色体的过程中已经走进了“死胡同”，此时节点D位于染色体头部，节点D的邻居节点中可行走的节点数为0，因此把节点D从染色体头部删除。继而考察节点C，因为之前考察过节点D，已经对节点D做了标记，故节点C的邻居节点中可行走的节点数也为0，继续删除，直到考察节点A，从而退出“死胡同”。

图2 死路现象

由于染色体生成过程比较复杂，这里用流程图表示(图3)。

图3 染色体的生成过程流程

重复过程，直到达到式(1)计算出的种群规模为止。

2.4 选择操作

精英主义可以加快收敛速度[14]，因此，只对种群中的优秀个体进行变异和交叉操作。为避免由此带来的可能陷入局部最优的危险，设计了一种既可以保留优秀个体又可以增加种群多样性的选择算子，即，保留种群中80 %的优秀个体，其余20 %的个体用随机生成的个体代替。

2.5 变异操作

由于传统的变异操作采用的是随机变异的形式，收敛速度慢，多位学者对其进行了改进。文献[7]在染色体中随机选择一个基因作为变异点，从起点到变异点的基因保持不变，由变异点开始，随机选择当前节点的可通过邻居节点加入到染色体，直到找到目标节点为止。文献[8]是在染色体中随机选择一个基因作为变异点，再从该变异点的邻居节点中随机选择一个节点作为新染色体的中间节点，用A*算法生成一条从该中间节点到起点的路径，再用A*算法生成一条从该中间节点到目标点的路径，连接两条路径作为新的路径。为满足游戏实时性的要求，设计了一种启发式深度优先搜索算法，用于变异操作，具体步骤如下：

1)从待变异父代路径Vold中随机选择变异节点i(不包括起点和目标点)；

2)由节点i开始，选择其邻居可通过节点中距离起点最近的节点加入到染色体，直到找到起点为止，作为路径Vfront；

3)再由节点i开始，选择其邻居可通过节点中距离目标点最近的节点加入到染色体，直到找到目标点为止，作为路径Vback；

4)连接Vfront，Vback，并将重复的节点i从中删除一个，形成新路径Vnew作为子代路径。

传统变异操作的随机性可能对优秀个体造成破坏[15]。考虑到从优秀个体中选取的变异节点i更有可能在最短路径上，算法只对40 %的优秀个体使用启发式深度优先搜索算法进行变异，使路径达到“拉直”的效果，进而让优秀个体更优秀。需要说明的是，启发式深度优先搜索算法速度非常快，并且在没有障碍物时，得到的路径是最短路径；但是遇到障碍物尤其是U形障碍物时，会绕弯路。如图4所示，实线是将A作为变异点得到的路径，虚线是将B作为变异点得到的路径。通过后续的交叉操作，有很大的概率得到更短的路径。

图4 启发式深度优先搜索算法效果示意

2.6 交叉操作

为配合变异操作，算法只对40 %的优秀个体进行交叉操作，具体步骤如下：

1)列举出父代个体V1和V2中共同含有的节点集合Nc(不包括起始节点和目标节点)；

2)从Nc集中随机选择一个节点i，i∈Nc，作为交叉点；

3)判断可能得到的子代个体中是否至少有一个其长度均小于V1和V2，如果是，则进行步骤(4)，否则,放弃交叉；

4)交换交叉点后的所有节点。

3 环路处理

虽然在初始种群的生成中避免了环路，但是交叉操作和变异操作又会产生环路。所以，每当交叉和变异之后都要对环路进行处理。处理环路的方式采用文献[16]方法，即处理最大的环路如图5。

图5 环路处理方法

4 实验与结果分析

实验程序使用C++语言基于Cocos2d-x游戏引擎编写。在Layer类的init()方法中，将地图信息映射到一个二维数组。基因用指针表示，使用p=new int[2]命令为指针分配内存，其中p[0]为节点的横坐标，p[1]为节点的纵坐标。染色体用STL中的list〈int*〉数据类型，适应度用size()方法计算，交叉使用splice()方法实现。

实验从随机选取的几款地图类游戏中随机选取了10张地图(其中含节点总数为169的地图6张，节点总数为240的地图4张；若地图中有多个起点或目标点，则随机选取一对起点和目标点)，然后用Tiled地图编辑器模仿这10张实际游戏地图建立了10张实验所用地图，并用Dijkstra算法计算出每张地图的最短路径的长度作为最短路径长度的标准。

需要说明的是，文献[4]的改进算法是通过节点复杂度算子确定交叉率与变异率，故在本实验中不为其预先指定交叉率和变异率。为做到各参数与本文的改进算法一致，将传统遗传算法、文献[7]及文献[8]所用的选择操作优秀个体置换比例设为20 %，交叉率设置为0.4，变异率设置为0.4。除本文改进算法通过式(1)动态确定外，其余算法均固定种群规模为15。

由于在实际游戏开发中，都是预先指定遗传算法的进化代数。故实验也采用指定进化代数的方法，并让算法在每张地图上运行100次，将平均运行时间定义为算法在该地图上的运行时间；并将运行结果与标准最短路径长度做对比，将等于标准最短长度的运行次数在总次数中占的比例定义为算法在该地图上的正确率。

实验对比了本文的算法、传统遗传算法、文献[4]的算法、文献[7]的算法以及文献[8]的算法，进化代数取4，10，20进行了3组实验，通过记录的每张地图的运行时间及正确率，计算出了10张地图的平均运行时间与平均正确率，结果如表1、表2、表3所示。

表1 进化代数为4的实验结果

表2 进化代数为10的实验结果

可以看出，本文的算法较传统遗传算法、文献[4]的算法以及文献[7]的算法在运行速度及正确率上均有大幅提升。正确率虽然不及文献[8]，但是平均运行时间较之缩短了很多，而游戏NPC决策的实时性是游戏开发中首要考虑的性能，所以设计的改进遗传算法更适用于游戏NPC路径规划。

表3 进化代数为20的实验结果

5 在多目标环境下的应用

多目标环境是指游戏地图中含多种因素，要求NPC不但要以路径最短为目标，而且要有避开危险区域的能力。与此同时，多目标遗传算法也取得了长足的发展[17,18]。有学者将其用到游戏NPC路径规划中来[6]。将路径中每个节点与危险区域的距离总和作为路径安全参数，再将路径长度、路径安全、路径耗费按照重要性加权求和，作为适应度函数。但是这种做法会加大计算量，影响游戏NPC行为决策的实时性。本文在将地图信息映射到二维数组时，通过计算每一个瓦片与危险源的距离，判断该瓦片是否位于危险区域，并在数组中用特殊的字符标记。在生成染色体及变异时，不考察位于危险区域的节点。将上述方法与文献[6]中的方法进行对比实验，实验结果如图6所示(其中黑色区域为障碍物，灰色为危险区域)。不难看出，使用本文的算法同样能使NPC具有避开危险区域的能力，且速度更快，简便易实现。

图6 将本文算法与文献[6]中的方法进行对比的实验结果

6 结束语

针对游戏NPC路径规划中传统遗传算法计算速度慢、正确率低等问题，设计了一种改进遗传算法，提出了一种最佳种群规模估计方法，设计了一种启发式深度优先搜索变异方式，并使用了精英主义思想优化遗传算子。实验表明：算法能够在保证正确率的前提下，缩短运行时间，而且在多目标环境下同样适用。

[1] 饶卫平,杨任农,雷晓义,等.基于多智能体遗传算法的战术航段优化[J].传感器与微系统,2016,35(3):41-43,48.

[2] 王海英,蔡向东,尤 波,等.基于遗传算法的移动机器人动态路径规划研究[J].传感器与微系统,2007,26(8):32-34.

[3] 唐义龙,潘 炜,李念强,等.基于量子遗传算法的无线传感器网络路由研究[J].传感器与微系统,2011,30(12):68-70,74.

[4] 黎忠文,覃志东,王全宇,等.游戏引擎最短路径搜索优化遗传算法设计[J].计算机应用研究,2014,31(1):76-79.

[5] 付朝晖,丁 梦,喻 昕.游戏编程中的寻路算法研究[J].湖南工业大学学报,2007,21(4):84-87.

[6] 刘大瑞,冯 镍.基于多目标遗传算法的游戏路径规划研究[J].软件导刊,2014,13(1):49-51.

[7] 孙宝林,李腊元,陈 华.基于遗传算法的最短路径路由优化算法[J].计算机工程,2005,31(6):142-144，162.

[8] 李 擎,谢四江,童新海,等.一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较[J].北京科技大学学报,2006,28(11):1082-1086.

[9] Chang Wook Ahn,Ramakrishna R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J].IEEE Transactions on Evolutionary Computation,2002,6(6):566-579.

[10] 康晓军,王茂才.基于遗传算法的最短路径问题求解[J].计算机工程与应用,2008,44(23):22-23,35.

[11] Hong Qu,Ke Xing,Takacs Alexander.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing,2013(120):509-517.

[12] Lee Jaesung,Kim Dae-Won.An effective initialization method for genetic algorithm based robot path planning using a directed acyclic graph[J].Information Sciences,2016(332):1-18.

[13] 段俊花,李孝安.基于改进遗传算法的机器人路径规划[J].微电子学与计算机,2005,22(1):70-72,76.

[14] Tsai Ching-Chih,Huang Hsu-Chih,Chan Cheng-Kai.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J].IEEE Transactions on Industrial Electronics,2011,58(10):4813-4821.

[15] 王友钊,彭宇翔,潘芬兰.基于贪心算法和遗传算法的仓储车辆调度算法[J].传感器与微系统,2012,31(10):125-128.

[16] Wu Wei,Ruan Qiuqi.A gene-constrained genetic algorithm for solving shortest path Problem[C]∥Proceedings of the 7th International Conference on Signal Processing,Beijing,China:2004:2510-2513.

[17] Mohamed Cheikh,Bassem Jarboui,Taicir Loukil.A genetic algorithms to solve the bicriteria shortest path problem[J].Electronic Notes in Discrete Mathematics,2010(36):851-858.

[18] Liu Linzhong,Mu Haibo,Yang Xinfeng,et al.An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems[J].Applied Soft Computing,2012(12):506-515.

Improved genetic algorithm for path planning in games NPC*

LI Jing-song1, QIAN Qian1,3, SUN Ming-hui2,3

(1.Yunnan Key Laboratory of Computer Technology Applications,Kunming University of Science and Technology,Kunming 650500,China; 2.College of Computer Science and Technology, Jilin University,Changchun 130012，China; 3.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China)

To improve the performance of genetic algorithms for path planning in games,an improved genetic algorithm is proposed.A way to estimate the optimal population size is used.New genetic operators based on elitist strategy is designed.A mutation method based on heuristic depth-first search is introduced.The proposed algorithm is compared with the traditional genetic algorithm and the improved algorithms proposed by other researchers to show the validity of the algorithm.Experimental results prove that the proposed algorithm can shorten the running speed of the algorithm while assuring success rate and it is also effective in multi-objective environment condition.

artificial intelligence(AI); path planning; genetic algorithm; population size; elitist strategy; heuristic depth-first search

2016—06—15

国家自然科学基金资助项目(31300938,61300145)；吉林大学符号计算与知识工程教育部重点实验室开放课题项目(93K172016K10)

10.13873/J.1000—9787(2017)06—0114—05

TP 18

A

1000—9787(2017)06—0114—05

李井颂(1989-)，男，硕士研究生，研究方向为人工智能。

钱 谦(1981-)，男，通讯作者，博士，副教授，从事视觉认知科学工作,E—mail:qianqianyn@126.com。