浅谈人工智能寻路算法在电子游戏中的研究和应用

唐李顺

摘 要：在电子游戏设计与开发中，人工智能（AI）作为提升与改善游戏质量核心技术，其发展需求越来越高。寻路算法是人工智能系统中最基本也是最重要的部分，目前应用最为广泛的AI寻路算法为A*算法，该算法在一定程度上实现了游戏人工智能系统的优化。基于此，本文有相关概念出发，对A*算法在电子游戏中的应用进行了分析。

关键词：人工智能；电子游戏；寻路算法

1 人工智能寻路算法的相关概述

1.1 人工智能

人工智能（Artificial Intelligence简称“AI”），是基于计算机与机器人技术研发的基础上形成的用于模拟、扩展以及延伸人智能行为与逻辑的技术、方法、理论以及应用系统的新兴知识学科[1]。人工智能涉及范围广泛，包括计算机科学、语言学、哲学、数学、自然科学、心理学以及社会科学等等。在电子游戏产业发展中，运用人工智能为游戏的虚拟环境以及游戏各种人物角色整填灵动性与真实性，进一步提升了游戏的可玩性，有利于游戏产业的优化发展。

1.2 最短路径算法

最短路径算法是游戏AI寻路算法中应用最为广泛的路径搜索算法。在数学、运筹学、数据算法分析中具有普遍分析与介绍。非启发式最短路径算法（Dijkstra算法）和启发式最短路径算法（A*算法）是最短路径算法中的典型代表。其中非启发式Dijkstra算法是在基于某点的基础上，由起点（中心点）向外逐渐拓展至终点，从而找到最短路径的算法。该算法由于计算的节点相对较多，在运算构成中其速度以及效率不高。启发式A*算法是在基于优先搜索的基础上进行启发式搜索的一种算法，即，在游戏路网图的一个起点位置，线进行广度搜索，用以确定搜索区域，在利用函数估价方法对路图网进行评估式启发式搜索，通过确定最佳路径，在搜索确定，从而逐渐发现搜索目标，A*算法是游戏设计与开发中较为常用的一种路径搜索法。

2 人工智能寻路算法在电子游戏中的应用

2.1 电子小游戏中简单寻路算法的应用

在电子小游戏中，人们对于游戏效果的要求并不高，尤其是简单的动作型电子小游戏，在设计构成中注重游戏人物角色侧重于寻路、闪避以及跟踪行为的编程设计。例如，对于小游戏中的非玩家控制角色（Non-Player Character简称“NPC”），常常处于既定的区域范围中行走，当玩家操作角色进入到其范围内时，NPG将进行一定的攻击或躲避行为。在这一构成中所应用的寻路算法主要有随机寻路算法、追踪算法以及闪避算法。

2.2 大型电子游戏中AI启发式A*算法的应用

在大型电子游戏中，对游戏音效、视觉效果以及人物角色的要求更高也更为严格。游戏玩家操作角色以及非玩家操作角色的人性化需求，是保证游戏质量的关键所在。目前，在大型电子游戏中应用最为广泛的寻路算法为A*算法，对包括攻击、躲避、寻路、阻击、转向、跳跃等行为以及虚拟空间的感知进行了设定与编程。因此，在大型电子游戏人工智能寻路算法的应用通常由5个基本框架构成，包括Behavior（角色行为）、Brain（脑思维）、Agent（非玩家操作角色代理）、Perception（非玩家操作角色感知）、Physical（RPG Model）（NPC物理模型）。

游戏AI控制系统的运转由非玩家操作角色（NPC）开始，非玩家操作角色通过大脑（Brain）的思考，基于A*算法，针对玩家操作角色的物理模型（RPG Model）信息数据搜索游戏场景，并从命令列表中（Command Que）选用所要执行的行为（Behavior），并将信息传递给非玩家操作角色代理（Agent），人工智能控制系统对RPG Model进行行为操作，在此过程中其寻路算法流程如下图。

2.3 对游戏人工智能A*算法优化思考

在游戏设计过程中，需对人工智能A*算法进行一定的测试与调试，从而提升AI寻路系统的优化性。在测试过程中，往往会遇到诸多问题，对此游戏设计人员需进行及时而有效的处理，用以保证游戏的可玩性。例如，在大型电子游戏AI寻路系统中，由于游戏内容复杂，游戏中的点数量相对较多，因此NPC在尽心寻路搜索时，所达到的具体位置会出现集中与密集的现象。但是如果，路点数量过多，在一定程度上降低了NPC寻路速度；路点数量较少，又会在一定程度上使得NPC寻路寻路速度过快，并在一定程度上降低游戲的真实性。因此，在游戏设计与测试过程中需运用寻路算法进行反复而全面的测试与考虑。

3 结论

基于人工智能系统在游戏软件开发与设计中的应用与完善，电子游戏AI寻路算法的优化与改进成为人们关注的重点，对电子游戏质量的提升与创新发展具有重要意义。

参考文献

[1]何文雅.3D游戏场景中虚拟角色的智能寻径应用研究[D].华中师范大学，2009.

（作者单位：成都理工大学）