基于最优路径存储的游戏寻径算法

Game Path Finding Algorithm Based on the Optimal Path Storage

研究了应用于游戏中的多个路径搜寻算法,以及游戏路径搜寻的一些特点,提出了基于最优路径存储的寻径算法.主要是通过最优路径矩阵存储部分的最优路径,减少大量路径的重复计算,提高游戏中的路径计算效率.针对游戏场景角色的移动引起路径点通行状态的变化导致当前的最优路径失效,提出了路径更新算法,更新最优路径矩阵当中的最优路径.另外,针对地图路径点规模增大的情况,提出了地图路径点分块处理的策略,然后对每一子块分别使用最优路径矩阵进行路径存储.

Researching some path finding algorithms used in the game, as well as some of the features of game path finding, and giving the routing algorithm based on the optimal path storage. Storing part of the optimal path through the optimal matrix to reduce the large number of repeated path computation, and improve the efficiency of path computation in the game. For the role movement in game scenes changing the state of path points to pass lead to the optimal path of the optimal path matrix invalid. Path update algorithm is given to update the optimal path of the optimal path matrix. As map path points become larger and larger, map paths are divided; then paths are stored for each sub-block using the optimal path matrix.