MMOG中NPC的路径搜索算法的研究

Study of NPC Pathfinding Algorithm for MMOG

MMOG中传统的寻径方法只为NPC提供一条最优路径,导致群体NPC移动时发生堵塞.本文提出一种基于迭代加深思想的DIDA*算法,提供多个较优的路径解决群体NPC移动问题.由于地图信息的变化,NPC在移动过程中遇到未知障碍物,本文采用一种局部连接Hopfield神经网络训练NPC实时躲避动态障碍物,实验结果表明DIDA*算法可以使群体NPC快速找到目标节点,路径变化时NPC可以绕过障碍物到达目的地,适应MMOG中环境的动态变化.

The traditional pathfinding algorithm in MMOG can only provide an efficient path for NPC. It could result in congestion of colony NPC when they are moving. This paper proposes DIDA^＋ algorithm based on iterative deepening. It can provide many a better path to solve the problem of colony NPC moving. With the variation of map information, NPC may encounter obstacles while moving. This paper uses a kind of local connected Hopfield neural network model to train NPC to avoid the obstacles in real-time environment. The experiment results show that the colony NPC can search the goal fleetly by DIDA^＋ algorithm. When the path changed, NPC can avoid the obstacles then reach destination, so it is adapted for MMOG＇s dynamic environment.