Intelligent Path Search Algorithm And Its Application In The Game

Path planning in game maps calculates a shortest collisionless path for virtual characters from the current location to the target location.It's one of the most basic problems in artificial intelligence that related to electronic games.Algorithms of patch finding in game maps mainly contain A*algorithm and genetic algorithm.But the design of the two algorithms in this field are both inadequate.It presents the slow speed and the low success rate in the calculation of the path planning.Some improvements were proposed to overcome their deficiencies in this paper.Because A*algorithm is a quite mature algoritthm and a lot of improvements have been implemented by other researchers,only a simple step was proposed to improve the heuristic of the method.The improved A*algorithm can adjust its search behaviors according to the number of obstacles in the maps to get both high search probability to the shortest path and fast speed at the same time.Genetic algorithm is the focus of this paper,some improvements were proposed as follows:1)A coding mode based on grid coordinates is proposed to make it easy to smooth the path.2)A method of generating chromosome without breaking and loop is proposed to improve the quality of the initial population.3)A selection operator that can keep both the diversity of the population and the good individuals is proposed to avoid the local optimal solution.4)To speed up the evolution,a mutation operator based on heuristic depth-first search is introduced and the crossover operator is adjusted to follow the mutation operator.5)An optimal population size selection method is proposed to give consideration to both the ability of searching and the computing speed,while the genetic algorithm is set to a fixed number of generations.Finally,the validity of the above improvements is verified by experiments.It is also compared with the traditional genetic algorithm and the improved algorithms proposed by other researchers.