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

摘要

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