|
|
即时战略游戏中如何协调对象移动
作者：Dave C. Pottinger
翻译改写：lzc
在图论中人们研究了通过怎样的计算才能找到一条从A点到B点的通路，以图论本身来说这已经解决了从A到B的问题，剩下的只是从A沿着找到的路线移动到B就可以了。这样的认识基于一个默认的假设--道路中的一切障碍物都是固定的，但是在现在已经广泛流行的即时战略类游戏中问题却远远不止这些。举个例子说上下班高峰期的时候，路上的每一个人都清楚地知道自己的目的地和所要走的路径，但是由于某些个人不遵守规则或其他人为原因还是会造成堵车现象。而如果这样的事情发生在一个即时战略的游戏中，那么带给玩家的沮丧感和愤怒将远超过现实中的堵车现象。当游戏中的一个士兵接到玩家的命令要从基地的一侧移动到另一侧以帮助抵抗敌人的进攻时，它需要一个计划(更明确的说是一条寻找出来的路线)使它能够到达目的地，但很可能在它移动的过程中预定的路线上出现了变化(例如玩家让工人们在士兵的必经之路上修建一个建筑或另外一批士兵出现在路上，从而堵塞了道路)，这时如果没有一个优秀的移动系统，那么之前的寻道工作等于是白费工夫。
本文将介绍一种相当有效的个体移动系统，以从另一个角度探讨游戏中的自动移动问题。虽然本文主要是针对即时战略类型，但所介绍的方法可以很容易的扩展到其它的类型中使用。点击此处查看部分基本定义，这里查看原文。
一些需要解决的问题
在进一步深入到我们的移动系统中之前，我将先简介一下人们在解决移动问题上遇到的一些问题，这些问题是消耗最少的CPU时间的同时达到最佳的智能效果和最高的移动精度的关键。
首先让我们对比一下同时移动单个对象与同时移动数十、数百个对象的不同。一次移动一个对象是非常简单的，但是一个可以相当完美的移动单个对象的算法并不一定能很好地解决数百个对象的同时移动，这其中最大的问题就是CPU时间的消耗。请一定要切记如果你要制作一个需要同时移动大量个体的游戏程序，那么在CPU的使用上一定要非常的保守。
某些移动算法是很依赖CPU速度的，这就是那些要同时移动大量个体的游戏中只有很少的一部分支持高级的移动方式(例如个体的加速和减速)的原因。玩家们总是认为游戏中的大船和被重装备武装起来的战士们应该具有能够加速和减速的能力，这样才能体现出真实性，但是这小小的真实性将会增加超乎想象的额外的CPU计算工作。这种情况下事实上用来处理个体移动的时间增加了，因为你不得不花费更多的时间来计算加速度，从而获得新的速度值。在后面我们扩展例子程序到处理移动的预操作部分时，你将清楚地看到这样的工作所增加的计算复杂度有多大。另一个将会大大增加CPU计算量的问题是个体的转动半径。大多数寻道算法都不考虑个体的转动半径(转动半径是指一个个体原地旋转一周所需的最小圆的半径，因为我们不可能让一个士兵倒退着走上半张地图去袭击敌人的基地，所以经常需要个体进行旋转)对道路选择的影响。于是就会出现一种情况，虽然我们的一头大象已经找到了一条通往目的地的通路，但是它却不能沿着这条路线移动到目的地，因为路线中的一个拐角面积要比大象的转动半径小一些。大多数移动系统通过减缓个体的速度，再作出一个缓慢而更节省空间的转身动作(相信很多人都看到过即时战略游戏中士兵在拐角处被堵住时所作的动作吧)来解决这一问题，但这种方法会极大的增加CPU的计算量。
正如大家所想象的那样，即使是即时战略游戏也并不是即时的，而是不断的进行循环，在每次循环中处理游戏的全部数据和玩家的指令(我们可以称它为UL-Update Loop)。为了增加游戏的性能，一般采用的方法是记录上一次UL的所消耗的时间，以预测下一次UL大约将要花费的时间(为了能尽可能地逼近即时处理，这样做是很有必要的)，但是这就给个体的移动带来了大问题--每次UL中个体的移动距离很可能是完全不同的，下面的图1就是这种情况的一个例子。负责个体移动的算法显然在面对每次移动相同距离时比每次都要为所有移动个体计算不同的时间下移动出的不同距离并将其显示出来要轻松得多。当然，如果游戏的UL系统制作的非常优秀，那将略微改善一点这样的窘境。
图1.不同的UL时间将导致运动个体
每次UL中移动不同的距离
不要忘记处理个体移动中的碰撞问题。一旦你的游戏中的士兵们碰撞到了一起，你要怎样将他们分开呢？一种方法是是个体之间根本不发生碰撞，但在实际的应用中这是不可能做到的。不仅仅是实现这要求的程序代码非常难写，而且无论你写再多的代码也是无用的，这些个体总是会找到一些途径来使彼此重叠在一起，而在更多的情况中，这些个体的重合是必须的。一些使用近距离兵器进行战斗的游戏，例如《帝国时代》，就是一个要求个体重合的实例。另外，如果你要限制你游戏中的个体不能碰撞在一起，那么他们很可能为了避开彼此而离开预设的移动路线，暴露在其它对手的攻击之下，受到意外的伤害，这会使玩家对你的游戏极端不满。因此你必须决定好你的那些个体相互靠的有多近，重合多少是可以容忍的，还要设法处理由这些决定所带来的问题。
注意考虑地图的复杂性。在复杂的地图上实现良好的移动的算法比简单地图上做到同样效果的算法要复杂得多，由于现在地图越来越倾向于复杂和真实，对于移动算法的要求也进一步提高了。
随机生成的地图可能造成意想不到的问题。由于不能通过给固定道路编写预定路线来减小寻道的难度，因此随机生成的地图在复杂性上要更高于预设地图，尤其对于寻道而言。当寻道变得使CPU负担过重时，唯一的解决方法是降低寻道的精度和质量，这时就要求提高移动算法的质量以弥补寻道上的不足造成的程序反应迟钝。
一定要认真处理各类个体的体积和由此产生的空间问题，这个问题最能说明你所需要的移动算法的精度。如果你的程序中需要移动的物体很少，以至于几乎不会出现彼此互相碰撞的情况(例如大部分的第一人称射击游戏)，那你可以放心地使用一些简单的算法。如果你的程序所要处理的移动物体非常多，并且还要处理彼此的碰撞和诸如检测两个个体之间的缝隙是否足够更小的个体从中间穿过等等操作，这时对你的移动算法在精确度上和质量上的要求将会使计算量大幅度的增加。
一个简单的移动算法
让我们从一个简单的对个体状态进行处理的移动算法的伪码(点击这里看伪码)开始，这个算法所作的只是简单的使用一条给定路线前进，当遇到碰撞和冲突时重新寻道，因此它能在2D和3D游戏中都表现得很出色。使用该算法，我们将从一个给定的状态开始，持续循环直到找到一个可行的位置作为中继点作为个体移动的目标去接近之后才跳出循环。移动状态将会在整个UL中保存下来，这将使我们能够正确的设置未来的状态，例如"自动"添加中继点。这种保存机制可以保证减少一个个体在下一次UL中作出与当前UL移动相反的判断的可能性。
我们假定被给定了一条通向目的地的路径，并且这条路径在提供给我们时是精确的，并且是可行的(也就是不会发生碰撞)。由于大多数即时战略游戏拥有巨大的地图，以至于一个个体可能要花费几分钟的时间来走完整个路程，而在这几分钟里地图上可能发生使当前路径不在可用的变化(例如在路径上新建了建筑)。为了解决这个问题，现在我们加入少许碰撞检测，一旦遇到碰撞，就进行重新寻道。在后面你将看到，我们可以采取几种方法来避免重新寻道，以减少CPU消耗。
碰撞检测
所有碰撞检测系统的基本目标都是判断两个个体是否发生了碰撞。这次我们所介绍的碰撞检测都是假设两个物体的碰撞，将来我们会专门介绍大量物体互相碰撞的检测问题。但无论是两个物体还是多个物体发生碰撞有一点是共同的：每个物体都要收到碰撞信息以便作出适当的响应(分开彼此)。
大部分即时战略游戏中使用的简单的碰撞判断实际上是将每一个个体看作一个球体(2D中是圆)，再进行简单的球体碰撞检测，而不在意这样简单的判断是否能够满足游戏对于碰撞的要求。这样做确实有利于提升性能，即使一个游戏要进行非常复杂的碰撞判断--例如判断击出的拳头是否击中敌人，或者甚至是低精度的多边形(polygon to polygon)交叉判断，这时为可能出现的碰撞保有一个球体区域往往也能够提升程序的性能。
当我们设计一个碰撞检测系统时要注意面对3种截然不同的实体：单个的个体、一群个体的集合以及经过队形编制的个体群(就像《帝国时代2》中的阵形一样，见图2)。事实上对所有这3种类型使用简单的球形判断都能工作得很好，单个个体可以简单的使用单个球体进行它的全部碰撞判断，而对于其它两种情况只需要再稍微增加一点工作量。
图2.碰撞检测中所要面对的3种
不同的试题类型
对于一群个体的简单集合来说，可以接受的碰撞检测下限是对整个组中的每个个体进行检测。这种方法将允许那些不属于你所选定的组的个体轻松的混入你的组队中。相对来说，对编队所要进行的碰撞检测就要更加复杂一些了。我们还应该认识到这种简单的组群还有一种特殊的性质决定了我们应该尽可能的简化对它所采用的碰撞检测方法--这种组群应该能够随时随地的将排列方式变换成任何可能的适应当地空间大小的阵形。
对于编队来说，不仅仅要进行如上面的组群那样简单的个体碰撞检测，还要进行大量更加复杂的检测操作。首先要保证编队中的个体之间不能互相碰撞，同时如果编队中的各个个体之间有一定的缝隙，还要保证任何一个不属于该编队的个体不能占用这一空间。另外，一个编队应该不能改变队形或重组，但是游戏的规则又可能规定当没有足够大的通路提供给整个编队保持队形穿越某一障碍物时，编队可以先散开，待各个体越过障碍物之后再重新组成编队，这样的设计更加体贴玩家。
我们可以尝试使用基于时间的碰撞描述机制。立即碰撞用来描述当前正发生在两个个体之间的碰撞；未来碰撞用来记录预计在程序运行的后续时间中将会发生在预定地点的碰撞(当然，前提是将要碰撞的对象都不改变各自的移动路线)。在任何情况下立即碰撞的情况都应该比未来碰撞的情况更优先被处理。同时我们也应该定义碰撞的3种状态：未处理的、正在处理和已处理完毕的。
使用"离散"的算法达到"连续"的效果
大多数移动算法从根本上都是"离散"的，不同于数学上的离散定义，这里所说的"离散"指移动算法在按照给定路径从A点移动到B点的过程中从不考虑中间路径上可能出现什么东西，相反，在"连续"的算法中就会考虑这些情况。这样做的一个问题就是当我们进行一个Internet游戏时(众所周知，由于网络速度的限制，这类游戏的UL时间一般较长)那些速度较高的个体很可能在一次UL时间中移动相当大的一段距离(由于UL时间变长)，而当这样增长的UL连续出现时很可能出现个体跃过了其它本应发生碰撞的个体。如果这样的情况出现在一个工人的身上那并不会有人在意，但显然任何玩家也不会希望敌人能够从辛苦建设的城墙中穿越而过进而攻击玩家的基地(某些早期及时战略游戏中出现的"穿墙"的BUG就是有这种问题造成的)。大部分的移动系统现在采用限制个体移动距离的方法来对付这一问题，该方法可以有效的简化所需的处理。在离散型的移动算法中解决这类问题的方法如下图所示：
图3."离散"移动系统中解决问题的方法
一种有效地解决方法是将一次移动拆分成多次移动的集合。这种拆分需要满足一定的移动距离上的要求，这要求就是要保证每次移动的距离刚好短于任何个体的长度，这就可以保证不可能有任何个体移动到当前个体的路径上来，从而避免了从其它个体之上跨越过去的情况。当每次这种拆分后的移动结束时我们就要使用碰撞检测系统对个体的当前位置进行碰撞检测。你可能会想到如此频繁的计算大量点的碰撞信息将会极大的增大系统消耗，没关系，在后面的章节中我们将会介绍一种方法来降低这种计算对系统的消耗。
另一种方法是创建一种称之为移动线路(Move Line)的对象。我们可以使用这条移动线路来描述个体的移动，个体的原始位置作为线段的起点，目的地作为线段的终点，就好像《红色警报2》里所表现出来的那样。这种方法并不用添加新的数据，但是会加大碰撞检测部分的复杂性--我们必须把简单的球形碰撞检测修改为对一个点到一条线段的距离的检测，而这样做将会增加计算的难度，也会消耗更多的时间。大多数3D游戏都已经实现了一种可以快速挑选出可被游戏者观察到的物体的分级系统(也就是能够迅速地判断出游戏中的哪些物体处于玩家角色的视野之内的系统)，我们可以对该类系统进行修改，使它们可以用来快速挑选出那些在我们的游戏中可能发生碰撞的个体。这样做的好处是大幅度地减少了需要进行碰撞判断的个体的个数，于是所需要的计算量常常就能够降低到所能允许的范围之内了。
位置预测
经过上周的工作，我们已经有了一个简单的移动算法和一个管理个体碰撞的列表，还有什么工作是强化个体之间协作所必需的呢？位置预测(Position prediction)。
预测的位置只不过是一个位置列表(至少包含个体的运动方向和时间标记，有时也需要记录加速度等信息)以指出未来某时刻个体所在的位置，参考图4。一个移动系统可以将用来实现个体移动的算法拿来负责计算个体的位置预测，这些预测越准确其可用性也就越大。当然预测计算也会增大计算量，为了不降低游戏的效率，下面我们就来讨论一下如何减少多余的CPU消耗。
图4.位置预测的图示
显然，最方便的优化方法是避免在每一帧中重复计算每一个已经预测过的个体位置。一个简单的移动列表可以实现这样的目的并且能够工作得很好：你可以在每一帧中从表内删除当前的位置，并向表内添加新的预测位置以维持列表长度固定(见图5)。虽然这一方法并不会减少个体开始移动时创建整个列表的计算量，但可以保证在剩余的移动过程中维持固定数量的计算。
图5.位置预测使用的移动列表及其操作示意
下一种优化方法是设计一种能够处理点和线的位置预测系统，由于我们的碰撞系统支持处理点和线，因次添加这一功能将是很容易的事。如果一个个体按照一条直线进行移动，那么我们可以利用当前个体位置、预测位置和个体运动半径来指定一段移动的轨迹及范围。然而如果个体正在进行一次圆运动那么整个处理就会略微复杂一些。当然你可以将这种运动过程作为一个函数保存起来，但这显然会加大系统的负担。作为替代可以尝试通过对圆上的点进行取样来作出正确的位置判断(见图6)。最后，再次建议一定要使用能够实现对点和线的无缝交替处理的预测系统，以便在任何可能的情况下通过使用直线来减少对CPU的耗用。 |
|
楼主: oraclelang
IP卡
狗仔卡
楼主
显身卡