计算机游戏中地图路径发现算法的优化与实现

在概述地图路径发现问题的基础上，给出了一个平滑A＊算法所得路径的方法．为了达到平滑路径的目的，先采用了最直接的路线，忽略了转弯，然后用一个预平滑过程来处理路径，在A＊算法找到路径后再进行处理．讨论了如何改进A＊算法的启发函数．给出一个引导型A＊算法，主要的改变是将结点空间从二维扩展到三维，使搜索过程能曲线转弯，避免了碰撞障碍物，实现了“合法”转弯．

Optimization and implementation of pathfinding algorithms for game maps

Based on the summary of the pathfinding questions, a method of smoothing the path which A＊ algorithm computed was given. In order to achieve this effect, we firstly took the most direct route, regardless of the angle, and then used a new pre-smoothing path before the standard A ＊ algorithm found and completed its path. We introduced how to modify heuristic of A ＊ algorithm, and gave a directional A ＊ algorithm. The main change to the algorithm was the addition of a third dimension to two-dimension node, which enabled searching process include curved turns, and avoid collisions.