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