一种改进的群体智能寻路算法

摘要

以游戏中群体智能角色的路径搜索为研究背景,提出一种改进的群体智能寻路算法.该方法把游戏寻路过程划分成三个阶段:第一阶段为预处理阶段,针对特定的目标点,采取逆向路径搜索策略,建立最优解路径表.第二阶段,针对动态障碍物的避让,运用实时A*算法生成局部动态路径,并与初始路径进行拼接.第三阶段,对找到的路径进行关键点优化和Catmull-Rom 样条平滑处理.实验结果表明该方法在游戏开发中的实用价值.%Taking path search of group intelligent agents in games as the research background, the paper proposes an improved group intelligent pathfinding algorithm. This method divides the whole process of game pathfinding into three stages. The first stage is the pre-treatment stage, aiming at the specific target, it takes reverse path search strategy and establishes the optimal solution path table. In second stage, for the situation of dynamic obstacles avoidance, it uses A* algorithm to generate partial Wai dynamic path, and stitches with the initial path. The third stage optimises the key-point of the found path and smoothes it with Catmull-Rom splines. Experimental results demonstrate the practical value of the method in game development.