在电子游戏的设计和开发中,随着硬件性能的不断升级,游戏的音效和视觉效果都得到了极大的提高和改善。但人工智能技术的研究和应用还相对落后,因而游戏中非玩家角色的行为表现就显得很单调笨拙,严重影响游戏的品质。因而近年来人工智能渐渐成为改善和提高游戏质量的热门研究课题,非玩家角色的行为既要聪明智能又要丰富多样。在游戏软件中,人工智能是一个重要而又复杂的模块,而寻路算法是人工智能运用于电子游戏中的最基本问题之一。在当今游戏工业界,A*算法是被大家最广泛使用的人工智能寻路算法,也是最有效的最短路径搜索算法。A*算法实际上是一种基于广度优先搜索基础上的启发式搜索算法,通常采用估价函数:f(n)=g(n)+h(n)对当前的搜索位置进行评估。A*算法最缓慢的部分是在开启列表中寻找F值最低的节点,二叉堆方法通过对开启列表进行快速排序等,极大的优化了开启列表内节点元素的查找以及增删速度,一般在大多数场合会加快2～3倍,并且随着路径长度增加,搜索速度呈几何级数提升(10倍以上)。在大地图上,只用一种网格密度进行寻路,通常或者很慢,或者走路不够真实。分层寻路方法可极大地加快了A*搜索速度,它先在整个地图范围内使用低密度网格的宏观寻路方法,直至靠近目标对象后,再切换到高密度网格的微观寻路方法,一般游戏地图越大,A*搜索速度提高地越明显。通过将A*搜索算法应用于掌机游戏Gauntlet的人工智能寻路系统后,实际验证和测试了改进和优化后的A*搜索极具时间效率和空间效率。