Research On Path-finding And Behavior Decision Techniques In Game AI

The Game Artificial Intelligence(AI)system is an important part of the game software.It aims to help the virtual characters adapt to the changes of the environment in the game continuously,and then responses reasonably to the players,finally,it makes the virtual role more intelligent.The game AI system can be divided into three parts,namely the perception system,the action system and the decision system.As the core system,the decision system works together with the basic action system to ensure the level of AI and the experience of the players.In order to improve the efficiency and stability of game AI in game software,there come the studies of the path-finding technology and behavior decision technology in game AI.This thesis studies how to speed up the path-finding algorithm and increase the applicability of the algorithm.In order to make the behavior decision of the game character adapt to the change of the game environment,this thesis introduces the reinforcement learning algorithm in the behavior tree and studies how to obtain stable control strategy of reinforcement learning in behavior tree and improve the control efficiency of algorithm in behavior tree system.The main research work of this thesis is embodied in the following three aspects:(1)A * algorithm based on path-reuse is proposed to solve the problem that A * algorithm is inefficient in game path-finding.Firstly,according to the characteristics of the game path,the heuristic function of the algorithm is improved to reduce the exploration of useless nodes,so that the path finding is along the correct direction.Then,by setting the anchor points,the idea of path-reuse is used to further reduce the node search and the resource consumption of the algorithm,so as to improve the speed of path finding.After setting the mobile priority for the dynamic object,the A* can applied to dynamic path finding.Finally,through the experiments comparison of path-finding,it's proved that the optimized path-finding algorithm can improve the efficiency in the game path-finding.(2)To solve the problem that the behavior tree is complex and lack of learning mechanism,the idea of reinforcement learning is applied to the design of behavior tree,so that the behavior tree can adjust its structure according to the variable environment and adapt in the game to adapt to the environment.Then,after the analysis of the problem of unstable control and low efficiency of reinforcement learning in the behavior tree,this thesis proposes a stable reinforcement learning algorithm,which improves the updating method of the state value and the reward function.By the use of increasing criteria of state value and continuity criteria of the action,the action which is not conducive to the convergence of the algorithm is removed to improve the control precision of the algorithm and ensure the stability control strategy.Through the experimental comparison of the behavior tree,it is verified that the stable reinforcement learning algorithm can obtain stability control strategy in the behavior tree and improve the learning efficiency of the algorithm to a certain extent.(3)Aiming at the problem of low efficiency of reinforcement learning in behavior tree,this thesis proposes an option algorithm based on qualitative action.Firstly,from the perspective of time-sharing,this thesis analyses the reason why of the low efficiency of the learning strategy,and then realized the step-by-step exploration strategy by defining the qualitative action and the sub-optimal qualitative action judgment criteria.By using the sub-optimal strategy and the optimal strategy of the hierarchical learning system,the contradiction between the final optimization degree of the behavior tree system task and the learning speed of the system can be relived,and the accuracy of the algorithm control is ensured with the convergence speed of the algorithm decreasing at the same time.Finally,through the experimental comparison of the behavior tree,it is proved that the option algorithm based on qualitative action can quickly converge in the behavior tree and obtain stable control effect,and improve the efficiency of the reinforcement learning algorithm in the behavior tree.