谢吉刚

(南京工业职业技术学院计算机与软件学院，江苏南京，210023)

0 引言

路径搜索是一项在各个领域中广泛应用的重要技术，是计算机游戏尤其是在角色扮演类、战略类游戏的重要组成部分。智能游戏中的路径搜索就是玩家根据地图场景中各类物体的分布信息，控制角色找到从起点到目标节点之间最佳路径的过程[1]。除了基本的避障算法之外，目前该领域已经有许多路径搜索算法，有传统的启发式A*寻路算法，基于抽象图的HPA*、M-A*等寻路方法，考虑地图分布信息的CDHPA*分层路径搜索算法等[2]。这些算法虽然各有不同的优缺点，但都是希望快速找出一条最优路径，使角色能够尽快到达目的地。

角色扮演游戏简称为RPG游戏，一般就是玩家控制角色在虚拟空间中不断地自主探索，并在探索过程不断的提升[3]，场景一般都会比较大，而且会随着游戏剧情的展开而动态的变化，现有的寻路方法难以适应这些要求。本文提出一种专门针对角色扮演游戏特点的寻路算法——分层避障寻路算法。该算法使用分层处理提高搜索效率，A*算法选取最优路径，避障处理解决场景的动态变化问题，兼顾了大场景的快速寻路，同时也能够体现出角色的探索过程，保证了玩家的游戏乐趣。

1 典型路径搜索算法

1.1 简单避障算法

虚拟场景中的寻路，简单说就是向目标点靠近的过程。如果没有障碍物，用基本的跟踪算法就可以实现。在有障碍物的地图中，需只要使用一定的避障策略才能到达目的地。具体的有试探法、轮廓跟踪法等[4]。

试探法的基本思路是当智能体与障碍物发生碰撞后，先退后左转或右转一定角度，然后向前移动一段距离，再根据目标位置调整朝向进行寻路。或者随机的移动一段位置。该方法虽然简单，但会使智能体显得比较笨拙。相对真实和高效的寻路技术是轮廓跟踪，就是在智能体遇到障碍物一定距离时，就旋转移动方向使之绕着障碍物的轮廓进行移动[5]。

避障算法属于盲目的搜索，不能实现最优寻路，但是响应快，无论多么复杂的场景，多少对象的同时寻路，系统都会立刻响应，而且这种盲目性在游戏过程中显现出来的探索过程也正是RPG游戏所需要的，适度的探索在一定程度上能够增加游戏的真实感。但是如果起始点和目标点距离较远，或者障碍物分布比较复杂，比如典型的U型障碍，单纯使用盲目避障算法可能会导致角色多次迂回、很长时间不能到达目的地[6]，这是玩家所不能接受的。

1.2 A＊算法

盲目搜索算法又叫做无信息搜索，一般只适用于求解比较简单的问题[7]。有信息搜索称为启发式搜索，其在搜索过程中加入了特定问题领域的启发信息，使得每次搜索向着最有希望的方向进行。最经典的启发式搜索算法为A*算法，该算法被广泛应用在目前流行的即时战略游戏中，同时也是大量后续寻路算法的基础。关于虚拟场景的最优寻路问题中最为著名的是A*寻路算法，其他很多方法都是基于此方法。A*算法是一种典型的启发式搜索算法，经常被用于游戏人工智能的寻路实现中,主要是通过检查特定状态的相邻或邻接状态来搜索从起始状态到目标状态的最小代价路径[8]。它使用启发函数f(n)来估计当前节点到目标点的距离并决定一步如何进行。其构造原则是尽量使求解问题的搜索耗费和路径成本之和最小，所以使得搜索总是向着最有希望的方向发展，其性能依赖于地图的分布和具体任务。当地图规模较大时，耗费大量的存储和时间，性能急速下降，往往不能满足游戏的实时性要求[9]。而且，对于多个对象寻路的时候效率很有影响。所以直接使用A* 算法不能满足RPG游戏的要求。

1.3 分层抽象算法

由于A*算法不能满足大规模地图的寻路问题，大量的研究人员基于A*算法开发了一系列基于抽象思想的分层路径搜索算法，其主要思想是对地图进行抽象分层，建立一个层次结构，将原始地图变成一个多层次的小地图。在进行路径搜索时，首先从最高层次进行抽象搜索，在下一层进行细化，直到最后一层得到实际路径。

分层网格化有几种方式，1996年Hotle，Perez等人提出的HPA*算法提出简单的做法是根据场景的规模，选择一个系数均匀分区。这种做法算法简单，分区快，但未考虑地图场景中障碍物的分布信息，这使得空旷区域会出现多余分区，这样采用A*寻路算法会使寻路速度及路径最优性降低[10]。当HPA*在含有大片空旷区域的地图上进行寻路时此缺点尤为明显，而真实的计算机游戏地图中总是存在大量的空白区域。改进的算法是M-A*算法，该算法每次执行寻路任务时根据起始点与目标点的信息重新对地图进行划分，并且在划分时只针对包含起点与终点的子区域进行细分，直到该区域只包含起点或终点[11]。M-A*算法在进行分区时考虑了不同寻路任务对于算法的影响，依据起点与终点的信息进行分区并构造四叉树，改善了A*算法在最坏情况下的计算复杂度，并且得到最优路径。使用多尺度环境信息进行分层同样缩小了搜索空间，但M-A*在每次分区前需要给定起点与终点的信息，对于同一幅地图的多次寻路任务需要进行多次分区，大大增加了玩家的在线等待时间。而RPG游戏通常寻路对象会比较多，而且分布在不同的位置。还有一种Quadtree算法是一种通过考虑地图场景中的障碍物分布信息将地图进行分区抽象的分层路径搜索算法[12]。该算法首先将地图进行均匀四分，然后分别判断每一个子区域中所有单元格的状态。若当前分区中的所有单元格均为障碍或非障碍则不再进行细分，否则将单元格继续四分，直到每一个分区中都只包含一种状态的单元格。Quadtree算法在分区时虽然考虑了地图中障碍物的分布信息，但其要求每一个分区都只能包含一种状态的节点，导致抽象节点非常多，耗费了大量的内存，且不能保证找到最优路径。因此这种方法只能对于大规模地图还是显得无能为力。

抽象分层思想的使用加速了寻路速度，减小了存储耗费，解决了大规模地图的寻路问题。但在分层及寻路时不考虑地图场景中障碍物的分布信息或在任何区域都使用A*方法进行寻路，大大降低了空旷区域上的搜索效率，另外如果地图动态变化，就需要对地图进行再一次预处理，增加了很多资源耗费，有时候效率可能反而会有所下降。

2 分层避障搜索算法

从前面的分析我们可以看出，避障算法响应快，但过于盲目；A*寻路算法能最优寻路，但不能适应大地图；分层能够提高搜索效率，但是不能适应地图的动态变化，这几种算法都有各自的优缺点，单纯使用其中任何一种算法都不能很好地解决RPG游戏这种大场景、多对象、快速响应的动态大场景寻路问题。结合这三种方法，本文提出一种新的路径搜索算法——分层避障搜索算法。具体算法思路可以分为分层预处理，避障寻路两个过程进行实现。为了论述简单，只选择某一游戏地图的部分场景作为示例（如图1）。下面结合该例对该算法进行详细论述。

图1 游戏场景图

2.1 分层预处理

首先对场景进行分层预处理。该过程包括分层网格化、确定关键点、构成抽象图三个步骤。考虑到本算法需要采用的碰撞检测算法的特点，这种算法对于空旷区会直接沿着直线前进，不会影响效率。因此直接采用均匀分区的方式分层，这样算法很简单，而且即使有大片的空旷区也不会影响算法效率。对于分区的大小的确定，本算法认为应该把角色的尺寸考虑进来，因为简单避障寻路算法的主要问题是避免角色进入较大的U型甚至C型障碍，一般而言，相对于角色尺寸10倍以内的U型障碍角色都不需要花太多时间就能够绕出来。因此本算法采用均匀分层，分层网格选定为角色尺寸10倍左右即可。为提高计算效率，一般采用对分法，即先将该地图均匀分成2×2网格，再分成4×4网格直至将地图分成10倍角色大小左右的网格。这样最后结果就总会以2的整数次幂划分。本例将地图分成4×4网格。然后把每一个网格分成8×8子网格。每个子网格大小就与角色大小基本一致了。网格化之后再标记子网格，黑色区域为障碍区域，白色区域为可通行区域（如图2）。

图2 分层网格化后的地图

确定关键点是指在相邻区域的边界上定义边界之间的关键点，这些关键点将会作为后面的搜索依据。根据分层网格的大小和分层方法的不同，关键点的选择规则也几种不同的方法。在大部分分层算法（如HPA*）中，采用的是遍历两个相邻区域的公共边界，然后去公共边界上最长的连续非障碍区的中点作为关键点[13]。有的算法（如M-A*算法）采用的是最长的连续非障碍区的两个端点作为关键点[14]。本算法分层网格相对于寻路角色而言比较小，因此采用的基本确定规则为:遍历所有相邻的四个区域（如Area1、Area2、Area3、Area4），找出公共边界上的最长的连续非障碍物网格作为相邻网格的出入口，若该非障碍区小于区域边界的1.2倍（如Grid1，本例选择10），则确定该区域中点为关键点。反之，若该非障碍区大于区域边界的1.2倍（如Grid2），则将该区域边界对分，然后这两个对分区中点为关键点。也就是说对于较大的可通行公共边确定两个关键点，较小的边确定一个关键点。这样可以避免寻路时角色出现明显的绕行。最后确定关键点仍然在图2种标出。

接下来构成抽象图。对任意四个相邻区域中的任意两个关键点，使用A*算法确定该两点在该区域范围内是否连通，若能够连通，确定它们的最优的连通路径，形成关键点路径抽象图（如图3）。至此预处理过程结束。

2.2 避障寻路

关于行进路线的确定，传统的诸如HPA*算法等基本是采用依据给定的起点和终点信息，找到其所在子区域，然后利用A*算法找出起点和终点到相邻关键点的最优路径，然后将该路径插入到抽象图中，然后进行平滑处理形成起点到终点的最优路径[15]。这种方法仅仅减小了A*的计算规模，每次形成最优路径还是需要一定的计算耗费，因此如果出现多个对象同时寻路就可能出现迟滞现象，会让玩家不能接受。另外一旦地图发生变化，比如新建了一个基地，或者增加或取走一个宝箱等等，就需要再次进行地图预处理，形成新的路径抽象图。因此本算法在起点和终点到它们的相邻关键点采用简单避障寻路，在行进过程中进行碰撞检测，这样即使有多个对象同时寻路，也不会出现迟滞现象。因此本算法从起点到邻近关键点就采用最简单的带碰撞检测的直线寻路算法。

图3 关键点路径抽象图

具体搜索过程可以如下描述。假定角色需要从位置Start移动到位置End。首先判断起点和终点是否处于被包围状态，如果是，不必寻路。然后判断是否在同一区域，如果是，就直接利用避障直线寻路算法即可。反之则分别确定起点和终点所在区域，并选取该区域中的最近关键点分别作为起始关键点和结束关键点。这里选取了A点为起始关键点，B点为结束关键点。然后使用A*寻路算法在抽象图层次中搜索一条最优的从关键点A到B的抽象路径。之后运用避障算法使角色从起点Start搜索移动到A点，同样，当角色到达终点区域的结束关键点B点后，运用避障搜索移动到终点End。至此整个寻路过程结束。

该过程部分主要代码如下：

bool Role_PathPlanner::CreatePathToPosition(Vec tor2D TargetPos,std::list＜Vector2D>&path)

//如果起点或终点处于被包围或其他原因，不能寻路

{ if(ClosestNodeToBot==no_closest_node_found)

{ return false }

//如果起点和终点处于同一个区域，不必搜索，直接避障寻路

if(!m_pOwner()->GetWorld()->isPathObstructed(m_pOwnerPos(),TargetPos,m_pOwner->BRadius()))

{path.push_back(TargetPos);

Return true }

//创建A*搜索类实例，在起始和结束关键点之间搜索一条路径

Astar searh(m_NavGraph,CloseNodeToBot,CloseNode ToTarget);

Std::list＜int>PathOfNodeIndices=search.GetPathToTarget();

//搜索成功，开始行进

if(!PathOfNodeIndices.empty())

{path.push_back(TargetPos);

return true; }

//搜索失败

else

{return flase } }

2.3 地图动态变化的处理

如果地图发生变化，传统的做法就是重新预处理，生成新的抽象图。对于RPG游戏而言，地图变化会比较频繁，每次变化就生成新的抽象图显然不合适。本算法针对不同地图的动态变化采用不同的处理方法。如果新的障碍不在抽象路径上，那么并不影响寻路，不需要任何新的处理。如果正好在抽象路径上出现了一个新的障碍，如图3中的Obstracl。由于角色在行进过程中同时进行碰撞检测，当检测到障碍存在，即启用避障算法行进到下一个关键点，到达下一个关键点之后继续沿原有抽象路径前进即可。如果在沿抽象图行进过程中遇到三次以上的障碍，说明地图变化已经比较大了，本次寻路虽然继续进行，但同时呼叫系统重新进行预处理，生成新的抽象图。

3 结语

经过将分层避障算法应用于RPG游戏发现，该算法由于经过分层预处理，大大减小了A*算法所存在的计算规模问题。对起点位置向起始关键点利用避障算法寻路，避免了路径规划过程的等待时间，这一点尤其在多个角色的同时寻路的时候显得尤其明显，而且近距离的避障试探过程显得更加符合实际情况，远距离采用A*寻路使角色能够快速到达目的地。在寻路过程中增加碰撞检测，很容易地解决了RPG游戏的地图动态变化问题。