怪物战斗阻挡与寻路

本文主要从如下几个方面描述某项目里怪物战斗阻挡与寻路的相关细节：

1.为什么要有战斗阻挡。

2.战斗阻挡与寻路的技术实现。

3.一些关于细节的优化点。

1.为什么要有怪物战斗阻挡​?

如果怪物间没有战斗阻挡,那么怪物的追击,寻路,会表现得比较傻，部分玩法会无法实现。

例如下图是玩家战斗过程中常见的一种情况:

图中绿色的圆圈代表玩家控制的角色,

图1-1：玩家进入几个怪物的战斗视野范围，怪物会按黑箭线条的路径往玩家移动；

图1-2：怪物已经足够靠近玩家了，开始扎堆攻击玩家。

图1-3：玩家向下方移动，怪物继续扎堆，并按黑色线条的路径追击玩家。

上述的情景在2.5D俯视视角的游戏里特别明显（见图1-3）。

图1-3 早期版本里怪物追击玩家的截图

这样的战斗体验比较不爽：

游戏设计里的群控，聚怪等技能会变得可有可无；怪物不会包围合击玩家，玩家会觉得怪物很傻，战斗很没意思。还有一些依赖堵截怪物前进的关卡玩法会无法实现，例如在某些关卡里，需要玩家召唤出一批友方防守NPC，以堵住敌对怪物的前进...等等。有了战斗阻挡，玩家的战斗跑位会更有紧张感，战斗时如果不及时跑位就会很容易被怪物围堵群殴。

总的来说，如果没有怪物战斗阻挡，怪物AI、技能、关卡等与战斗相关的设计都会受限，战斗体验会比较差，这对于一个以战斗体验为亮点的游戏来说，是难以接受的。

图1-4 战斗体验要给力

2、战斗阻挡的技术实现方案

2.1、游戏世界里，阻挡数据的描述

图2.1-1 物体在地图里的阻挡面积

要实现战斗阻挡，先要描述世界里物体的阻挡数据。如上图(图2-1)所示，项目的世界是格子的世界，怪物，玩家，建筑之间的阻挡面积是按格子计算的，例如上图中的怪物A是 2x2 的面积。

图2-2阻挡面积的数据描述

图2-2里的MGrid是指一个地图格子,每个格子的阻挡值是用(半个char类型)也就是4个bit来表示的（这里为什么不用一个bit,后面在阻挡分级里会描述）。

2.2、战斗寻路与移动----简单实现

有了阻挡的数据描述,接着要结合这些阻挡数据实现战斗寻路。

图2.2-1 简单的带阻挡寻路移动流程

图2.2-1所示的整体流程比较简单，就是在每tick的前后设置和清理怪物当前所在位置的地图阻挡值。

图2.2-2 位置变更描述

图2.2-2 里,T0时刻 和 T1时刻相差一个tick的时间。假设一个tick的时间内,红色的怪物移动了一个地图格子,那么它所占的地图格子就会被设置上阻挡值（图中的有阻挡的格子为灰色）。

上述带阻挡的移动方案是比较常见的处理方法，在很多单机游戏中都会使用，但如果要应用到多人在线的MMOG里，会出现因后台程序 tick的间隔过长而引起穿插的问题。

在怪物tick的间隔比较短的情况下，怪物的行为表现是很理想的，因为每个tick的位置是连续的，但在MMOG里，同时处理的怪物有近几万个，怪物的tick间隔一般会在200ms，甚至500ms左右，那就必然会出现穿插的情况。

图2.2-3 怪物移动穿插

图2.2-3中，黄色怪物和红色怪物各自按黑色箭头的路径移动，由于tick的间隔比较长，每tick的移动距离是2个格子。这样两个怪物就能互相穿插过去了。

要解决上述穿插的问题，就需要在上述方案的基础上加入插值检查的逻辑。

2.3、战斗寻路与移动--带插值的实现

插值的方法,会经常用在处理游戏物件碰撞检查上。

图2.3-1 基础的插值碰撞判断示例

在图2.3-1里，图左侧:红色怪物往黑色的墙移动,由于tick间隔比较长,判断点没有和墙体检查，导致怪物能穿越墙。图右侧：在红色怪物移动的路径上，多加了一个插值点的判断，这样就能判断识别出怪物在路径上和墙体有碰撞了。

图2.3-2 加入插值的怪物tick移动寻路流程

图2.3-3 加入插值后的地图阻挡值示例

在图2.3-3里，红色怪物把每Tick间会预测经过的路径，都插值上适当的点，并在地图上设置上阻挡值。

图2.3-4 加入了插值后，原来怪物穿插的问题被解决了

但加入插值后，也会引入新的问题：

图2.3-5 怪物间会出现较大的间隔

加入插值后，怪物在每tick间占用了和它真实体积差异极大的阻挡。这样在游戏里就会看到怪物和怪物间的移动间距会非常大，有些很不合常理的场景出现，如图2.3-5：

T0时刻红色怪物把路径上的4个格子都设置了阻挡值, 到T1时刻，红色怪物已经离开了第一个阻挡格子，但由于红色怪物必须等1Tick完成后才会恢复占领格子的阻挡值，所以当黄色怪物开始寻路移动的时候，黄色怪物就只能等待或者绕路了。这样当很多怪物一同追击玩家时，怪和怪之间会有很大的空隙，很稀疏，没有怪物入潮水般涌来的感觉。

2.4、战斗寻路与移动----阻挡分级的实现

要解决上述间隙大的问题，就要加入阻挡值分级的逻辑。

图2.5-1 阻挡分级的示例

图2.5-1里的基本思路就是在一个大tick时间里，根据时刻的不同来细分插值点，并把插值点占领的阻挡值分级。

同一tick内，由于有阻挡分级和规则的存在，就可以较好地处理间隙大的问题了：

图2.5-2 两个怪物紧贴的情况

图2.5-2里，图上侧：红色怪物往前走,占领了四个阻挡。图下侧：同一个tick周期里，红色怪物身后的黄色怪物也要往前走。判断规则开始,黄色怪物要把A格子占领为1级阻挡，判断的时候发现A格子里已经有0级阻挡，1>0,所以A格子能成功被黄色怪物设置成1级阻挡值。在战斗的追击表现上,就是黄色怪物会紧贴着红色怪物前进。

这个插值分级阻挡的思想，就是把一个大的tick时间分割成各个小时间片来考虑，利用一次tick时间来尽量做有效的事情。

2.5、战斗寻路与移动----寻路的实现与优化

接下来就要解决在带阻挡的情况下，怪物如何有效寻路的问题。

在战斗体验上，寻路体验表现最好的是A*，不过A*极耗性能，下面讨论的就是在平衡战斗体验的情况下，让寻路更有效率，战斗体验更好。

图2.4-1 怪物的基本整体寻路策略

上图所示的基础策略里，主要原则是减少对A*寻路的依赖和调用次数,在保持怪物战斗表现的基础上尽量少用A*。

远距离寻路就使用脚印寻路，近距离的话就使用边沿寻路。如果还失败的话，就在根据包围检查，四方向检查等初步判断原则来决定是否真的使用A*，也能尽量规避A*失败的情况（A*失败是最耗性能的，会用试尽遍历深度后才会失败结束）。

同时，合理地设置A*的搜索深度，并限制server每tick间对A*的调用次数，这样整个寻路性能就基本可以控制在能接受的范围。

下面会对边沿寻路，包围检查，四方向检查等进行细节的介绍。

图2.4-1 边沿寻路流程

边沿寻路的复杂度也是线性的，在怪物多的情况下特别好用。由于阻挡形状是不规则的，有可能会出现越绕越远的情况，这里可以加一个偏移值的控制,控制绕的方向要基本和目标点方向一致。这个算法很古老，传说中game boy 上的很多游戏，都是采用这种基本算法的。

图2.5-1 包围过滤

在同屏怪物数量达到一定程度的时候,使用包围过滤和四方向过滤的逻辑来规避调用A*也失败的情况。

包围过滤：以当前位置格为起点，使用图形学里填充封闭图形的算法逻辑，递归染色附近的格子（最大10个格子），如果是封闭的，那么怪物就是被围死。

如果怪物被围死，或者玩家被围死，那么就放弃使用A*算法。

图2.5-2 四方向过滤

四方向过滤：以玩家为中心，把玩家的周围分成4分格，如图2.5-2所示。

黄色怪物第一次寻路调用A*寻路玩家的位置，如果失败，就把黄色怪物和玩家的距离S1，设成是在“第三分格”的最短A*失败距离。如果同一个tick里红色怪物要对玩家寻路，那会先计算和玩家的距离S2，并找到当前分格的最短失败距离， 如果大于这个最短失败距离，就会放弃A*寻路。 如果要判断更准确的话，可以考虑把4分格细分为8分格。

3.一些关于细节的优化点。

3.1、利用A*失败路径来逼近目标

图3.1-1 A*失败的逼近过程

图3.1-1 是一有桥等狭窄地形的场景，红色怪正在和蓝色的玩家单位战斗，黄色怪在桥外面。 这个时候，黄色怪是怎样也无法找到到达蓝色玩家的路径的，因为有红色怪的阻挡。

那怎样让黑色怪的表现是自然的呢？原来的做法是让它在外面随机扰动跑一下，或者用边沿寻路包围，但这样的表现并不自然。

考虑A*算法会遍历附近的格子并给每个格子到目标的路径估值。 那么在A*寻路失败的过程中已经寻到逼近玩家的最短路径了（如上图的红线路径所示），只是没有记录下来。只要在A*里加一个逻辑，在寻路失败的时候记录搜索过程中最短的估值的路径（虽然不是成功的路径），并返回出来，这样在寻路失败的时候，黑色怪也可以获得这个最短路径跑过去，逼近玩家，让战斗的气氛更紧张。

3.2、大体积的怪物嵌入了场景阻挡里

上图里，黑色阻挡是静态的地形阻挡，红色的怪因为自身面积很大，被阻挡卡主了，它怎样才能成功走出来攻击玩家呢？

红色怪是怎么跑进去的？原因有很多，如被技能打飞进去的；施放瞬移技能进去的；种怪种错位置了；寻路的bug，自己跑进去的；怪物是召唤生物，被召唤的出生点就是这里等等...

要实现怪物战斗阻挡的方案，就一定要考虑怪物部分被卡住，如何离开的问题。找解决方案的时候考虑过很多方法，如先判断怪物是否卡住，再判断它是否有正在从阻挡里出来的趋势，(要判断这个趋势,就要考虑例如它身体覆盖了多少个阻挡格子，下一个路径点是否比前一个位置点覆盖的阻挡格子有减少等...),方案想得很复杂。

不过最后的解决方案倒很简单: 如果怪物身体面积有一个格子和静态地形阻挡重合的话，就把这个怪物当作1*1的体积怪处理，直至它完全脱离困境。

3.3 BOSS 被卡住了

见上图,黄色怪在前面站着不动，一直射箭攻击玩家，玩家也在射箭攻击boss,但boss是近战类型的，寻路又被前面的小怪挡住，跑不出来了，一直被挨打。

解决思路：复杂的想法是给怪物加上优先级，低级的要让路给高级的。但这个实现的复杂度很高，而且怎样让boss通知小怪也是个大问题，然后各种群体协调算法就出来了...

解决方案：boss有阻挡, 小怪移动的时候要考虑boss的阻挡, 但boss移动的时候无视其他怪物的阻挡，这样boss就能穿越黄色的怪，冲出来攻击玩家。（因为boss一般体形都比较大，从小怪身上穿越的时候感觉有点像跨过去，表现上也不会太糟糕）

3.4 其他细节

在一些割草型的战斗里，如怪物一露面就会被秒杀掉的，就不用考虑寻路的策略，直接直线或者固定路径跑到玩家视野内，让玩家击杀。

在一些很有策略性的战斗场景，如精英boss战等，就要加大怪物的搜素路径深度，提高该怪物的tick 优先级，以让怪物表现得更有战斗技巧。

要有好的怪物战斗体验，还有很多更深入的细节要考虑配合，如怪物战斗时不能太活泼，以避免出现一直根据当前地图场景寻路，动作不停抖动的情况；美术表现上，如果加上战斗移动时的凝视动作，这样一些掉头跑的路径就不会显得奇怪；怪物寻路总是失败时，加上挑衅的动作待机，这样战斗气氛就更浓烈；同时也要考虑美术资源的成本。

本文作者：woodzheng(郑润宗)