原文地址：
多少次你曾在交通堵塞的时候想：“嘿，我知道我想要去哪里，并且我确信，每个在我周围的人也知道他们想要去那里。如果我们能够彼此合作，我敢打赌，我们将更轻松，更快速的到达各自要去的地方，而不用相互追尾。”，当你非常沮丧的时候，你会发现那些焦躁的上班族并不是最合作的。不过，如果你是一个游戏玩家，那些不合作的，采集资源的农民和步兵造成的沮丧，可能比现实生活中因交通堵塞造成的更严重。实时的计算出如何使上百个移动单位在复杂的游戏地图上移动——通常被称为寻路——这是个艰巨的任务。虽然寻路是一个热门的行业术语，它只是我们解决方案的一半。“运动”，即执行一个给定的路径，是解决方案的另一半。对于即时战略游戏，运动单位齐头并进一起寻路。一个斧头兵需要一个计划（如，一条路径），可以帮助他应该选择什么样的路线从城镇的一边走到另一边，去帮助延缓敌人的入侵。如果他不执行这样的计划，没有一个优良的移动系统，你的战机可能因此全失。
游戏开发者可能已经访问了一些寻路的主题，比如Brian Stout (October/November 1996)写的”Smart Move: Path-Finding“以及Swen Vincke (June 1997)写的”Real-Time Pathfinding for Multiple Objects”，我并不想重复同样的话题，而是希望从另外一个角度去接近问题，比如执行那些已经寻找出来的路径。在这个文章中，我会覆盖一个有效率的运动系统的基本组件，在下个月的游戏开发者杂志中，我还会给出一个指南性的文章，关于扩展这些基本理论到高阶运动以及实现。虽然在这个文章的例子主要是针对RTS游戏，但是这些方法同样适用于其他类型的游戏。
面向游戏开发者的移动问题
在我们进入协调单位运动这个课题前，我们观察下一些今日面向游戏开发者的移动问题，大部分这些问题都不得不在最小化CPU占用以及最大化精确、智能运动间权衡。
移动单个单位对比移动多个单位，移动单个单位显然容易得多，但是移动单个单位的方法往往很少能够直接有效的适用于移动成百上千的单位。如果你设计一个容纳上百个单位的系统，那么你需要对你的CPU占用非常谨慎。
大部分运动方式的特点是CPU密集型，极少的游戏在移动上百个单位的时候会支持高级移动行为，比如加速减速。移动一个大型船只或者重甲单位如果加上加速减速会增加更多的真实性，但是真实性带来了更多的CPU消耗。真实的运动计算比较复杂，因为你需要每帧通过时间、加速度重新计算新的速度。当我们扩展我们的运动系统来处理一些预测时，我们将会看到，这些计算加速以及减速也会将问题复杂化。建模一个转向半径也是困难的，因为许多寻路算法不能够将转向半径考虑进去。因此，虽然一个单位能够寻找到一个路径，但是他也许不能跟随这个路径移动，因为它的转向半径的限制。大多数系统通过减缓单位速度做急转弯来克服这个缺陷，但是这个同样需要额外的一组计算。
主游戏的更新循环长度不一。大多数游戏使用上次更新到本次更新的时间间隔作为下次更新的长度，但是这种每次更新的长度不一的方案会导致单位运动系统出现问题（可查看下图）。单位运动算法在长度固定的计算中会运行得更好一些，一些比较好的更新平滑系统可以缓和这个问题。
图1：每次更新会导致单位移动不同的距离（可变的更新长度）
处理单位碰撞。一旦一个单位接触到另外一个单位，你怎么把他们重新分开呢？一个天真的解决方案就是从来不允许单位进行碰撞，在实践中，虽然，这个严格强制执行的代码很难写。不管你写多少代码，你的单位总是能找到一个方法来重叠，更重要的是，这种解决方案是不现实的。在许多情况下，单位应该被允许重叠一点点，帝国时代的白刃战应该是这样的一个案例。对于零碰撞重叠的限制常使单位也走出原始路线与其他单位对抗，这将使他们暴露在不必要的额外伤害上，所以你不得不决定多少碰撞重叠区域是你的游戏可以接受的及相应解决的。
地图复杂度。地图越复杂，好的移动方式就越来越难被查找出来。当游戏世界以及地图越来越复杂和真实，在这个世界的移动要求越会越来越高。
随机地图还是可控的场景？因为你无法硬编码可行走路径，随机地图显然会更复杂，包括寻路。当寻路越来越消耗CPU，唯一的选择（除了降低地图复杂度和移除随机地图外）就是降低寻路的质量。当寻路质量下降时，需要运动系统质量的上升才能收拾残局。
最大的物体密度。这个问题比其他任何问题都能够显示出运动系统需要怎样的精确度，如果你的游戏中仅有极少数的运动物体会跟其他物体接触（比如大部分第一人称射击游戏），那么你可以做一个相对简单的运动系统，但是如果你的游戏含有上百的运动物体，而且这些物体需要实时碰撞、移动检测（比如一个单位需要通过两个单位之间狭小的缝隙），那么运动系统需要很大的的精确度以及质量。
简单的运动算法
让我们用一些伪码来开始一个简单的、基于状态机的运动算法（列表1），虽然这套算法不仅仅做跟随路径移动，而且当碰撞被检测到的时候重新寻路，它在2d以及3d游戏中都工作得很好。我们将会以一个给定状态开始迭代，直到找到一个路径点去移动。一旦发现一个路径点，我们跳出这个循环，并做这个移动。一共有三种状态：等待路径，到达目标，增加路点。在游戏更新中，单位的移动状态将会被保留，此举的目的是为了支持未来的一些事件，比如在以后的游戏更新中自动增加寻路点。通过保留单位的移动状态，我们失去一些机会，单位将会在当前更新中记录一个决定，下个更新执行这些决定，这是第一个步骤，我们将在下几个计划中进行介绍。
我们假设我们已经获取了一个路径，而且这个路径是精确有效的（意味着不会发生碰撞），由于大多数策略游戏都会有相对比较大的地图，一个单位穿越一个地图需要几分钟，在这段时间中，这个地图有可能会改变，而这些改变将会使原始路径无效，所以我们将会在状态循环中进行一些简单的检测。针对这点，如果我们发现一个碰撞，我们将会进行重新重新寻路，稍后，我们将会有几种方式去避免重新寻路。
列表1. 伪移动算法
移动状态循环 { 当处于递增路点状态： 递增路点 如果我们在巡逻 获取下一个路点所定义的巡逻方向 设置状态到等待路径 否则 如果我们已经没有路径点了 设置状态到到达目标 否则 设置状态到等待路径 当处于到达目标状态： 做恰当的通知（如果需要的话） 完成移动，停止移动动画，退出方法 当处于等待路径状态： 寻路并保存路径 如果失败了，退出方法 计算我们期望路点的朝向角度 修改单位角度（可能会手转向半径限制） 使用这个新角度，计算新位置 如果新的位置导致了碰撞 设置状态为等待路径状态 返回顶部循环 使用当前的和未来的位置： 如果我们移动前比移动后更靠近路点 设置状态为递增路点状态 返回顶部循环 如果我们这次移动将要跳过路点 设置状态为递增路点状态 跳出循环 } 设置相应的加速度 做实际的移动 设置或者更新动画 更新到预期的位置
碰撞检测
任何碰撞检测系统的基本目的就是找出两个单位碰撞了，暂时我们将会将所有碰撞简化为两个实体间的碰撞。下个月我们将会覆盖复合碰撞（涉及三个以上实体）。一旦检测到碰撞，每一个实体都需要知道这个碰撞，目的是为了做出合适的移动决策。
在大多数策略游戏中基本的碰撞检测都将实体当做球体进行检测（在2d中则是圆），这样的系统是否合适取决于具体的游戏要求。即使一个游戏实现了更复杂的碰撞检测，比如有向包围盒，或者甚至更低级的多边形碰撞检测。但是维护一个总的包围球通常能快速的消除潜在碰撞，这个将会改善性能。
这里有三种实体类型需要在碰撞检测系统中考虑：一个单一单位，一组单位，以及一个队列（图2）。所有的这些类型可以使用一个单一的球体做快速的碰撞剔除（消除进一步碰撞检查），事实上，单一单位可以简单的使用一个球体作为他的所有碰撞检测，而群组以及队列则要做更多的工作。
图2 碰撞实体
对于一组单位，可以接受的下限是检测所有群组单位的碰撞，就其本身而言，这个方法将会允许一个非该群组的单位愉快的坐在这个群组中间。对于我们来说，我们可以忽略这个差异，因为队列将会提供额外更多的严格碰撞检测。
一个队列需要与群组同样的检测，但是这些检测必须进一步确保队列内部没有碰撞。如果一个队列在队员之间有空隙，非队列队员去插入这些间隙是不可接受的。另外，队列一般没有机会去重塑或者打破。尽管如此，当队列因为有障碍物没有路径时实现一些游戏逻辑，重新在障碍物另外一边，让重新打断以及重组，是个不错的方案。
对于我们的系统，我们将会实时跟踪碰撞检测，直接碰撞代表着目前现有的两个物体间的碰撞。未来的碰撞代表着会发生在一个指定点的碰撞（假设两个物体不会改变他预期的移动行为）。在所有这些情况下，直接碰撞将有更高的优先级。我们也会跟踪每个碰撞的状态为：未解决，解决中和已解决。
离散以及持续模拟
大多数移动算法本质上都是离散的，那就是说，移动一个单位从A点到B点是不需要考虑在两点之间的任何东西的，然而持续模拟将会考虑这些。在充斥着延迟的网络游戏中，快速移动的单位将会在一个游戏更新中移动一大段距离。当离散模拟加上这些长更新，单位可能跳过那些本应该与他们相撞的物体。对于资源收集单位，没有人介意太多，但是玩家很少希望敌方单位能穿过你的城墙。虽然大多数游戏解决这个问题的方案就是限制单位移动的长度，但是这个离散模拟问题相对比较容易解决（见下图3）。
一个解决这个问题的方法就是将每次移动分割为更小的一系列移动。以移动单位的大小考虑，我们使采样间隔足够小，保证没有其他单位可以适合在两个样本点之间。然后我们对每个点运行碰撞检测系统。计算所有这些点的碰撞检测看起来代价有点过高，但是随后我们会看到一个潜在的方法来抵消大部分成本。
【图片丢失】 图3 解决离散模拟的问题
另外一种方案就是创建一个移动线，这个移动线段代表的就是单位从A点移动到B点的线段，这个系统创建不需要额外的数据，但是碰撞检测相对比较复杂，我们将简单的球型碰撞检测转变成了一个更为昂贵的涉及找一个点到线段的最短距离问题。大多数3d游戏已经实现了快速的分层系统，如可见体剔除，所以我们可以重用这些作为碰撞剔除，为了快速的缩小潜在碰撞检测数量，我们可以花更多时间检测小组物体碰撞。
预测位置
现在，我们有一个简单的运动算法和一个系列的单元碰撞，我们还需要得到怎样好的单位合作呢？那就是位置预测。
预测位置只是一组位置（包含方向及时间戳），显示一个对象将在未来（见下图4）的位置。一个运动系统可以使用相同的运动算法计算这些位置。计算的位置越精确，他们就越有用。位置预测并不是立即无消耗的，不过让我们看看如何抵消额外的CPU使用率。
大多数显而易见的优化就是每帧避免重新计算所有的预测位置。一个简单的滚动列表可以工作良好（见下图5），你可以每帧滚下过去的一些位置以及增加一些新的位置，保持预测的滚动列表在同一个尺度。而这个优化摆脱不掉的是首次启动的成本（你需要创建一套完整的预测位置），他对剩余的运动才有常数时间的成本。
【图片丢失】 图4：仔细看看这个预测位置
下一步的优化是创建一个预测系统，它可以处理点和线，因为我们的碰撞检测系统已经支持了点和线，它应该可以简单的增加这些支持到我们的预测系统中。如果一个单位在一条直线上运动，我们可以指定一个密闭的体积，通过当前位置、未来位置以及单位的软移动半径。尽管如此，如果物体有转向半径，事情变得更加复杂。你可以尝试存储曲线作为一个函数，但是那样太过昂贵。相反，你最好做点抽样，创建正确的预测点（参见下图6），最后，你真的需要一个系统无缝的支持点和线预测，使用线尽可能的减少CPU消耗。
图5 预测位置的滚动列表
【图片丢失】 图6 使用转向半径的预测位置
最后一项优化很重要，而且可能有点不直观，如果我们希望这个预测系统使用尽可能少的开销，我们不希望重复计算每个单位的预测位置以及做另外的计算去移动他，因此，解决方案就是预测准确的位置，然后使用这些位置去移动对象。这种方式，我们每次移动只计算一次，所以没有额外的开销，除了上文提到的额外的启动时间。
在实际的实现中，你可能仅仅使用一个更新步长去做这个预测。当然所有的更新步长不太可能一致的。如果你盲目的移动一个单位从一个预测位置到下一个而不注意下一个实际更新步长的位置，你会遇到一些问题。一些游戏（或者游戏中的一些物体的子集）可以接受这种不精确。那些我们开发的一些游戏都会在最后增加一些插值，这样可以快速的调整一系列的不精确预测点。当你持续的调整一系列的预测位置时，你也需要不断的重新组织和计算。
剩余的大多数实现难度主要来自于我们使用预测位置做碰撞检测，你可以简单的看到为了对比预测位置而作的组合爆炸。尽管如此，为了有一个良好的协调单位移动，我们不得不去知道单位最近需要去的位置以及他们可能会碰到的其他人。这里需要一个良好且快速的碰撞检测系统。如同大多数三维引擎一样，最大的优化来至于快速的消除潜在的检测，这样可以让你使用更多的cpu时间在大多数的可能的碰撞上。
单位与单位的合作
我们已经创建了一个复杂的系统用来检测物体将来的移动位置，它也支持3d移动，而且这个系统也不会比简单的系统花费更多的cpu时间，而且它也提供了一个精确的未来移动列表。现在我们进入了一个有趣的部分。
如果我们将工作做好的话，大多数的我们需要处理的碰撞都是将来的碰撞（因为我们已经避免了大多数的立即碰撞（在他们发生以前））。虽然对于处理任何未来的碰撞的基本方法是停止以及重新寻路，尽量避免激发寻路器是非常重要的。
下面的碰撞解决方案集合是一个如何处理单位与单位碰撞问题的完整方案
未解决的碰撞
样例一、如果两个单位都没在移动
1、如果我们是低优先级的单位，不做任何事情
2、如果我们是是高优先级的单位，计算出哪个单位将要移动，并告知这个单位找一个最短的路径去解决碰撞问题，改变碰撞状态为已解决。
样例二、如果我们没有在移动，另外一个单位在移动，我们不做任何事
样例三、如果我们在移动，而其他单位已经停止：
1、如果我们是高优先级单位，另外低优先级的单位可以逃离这个路径，则计算没的到达点（这个点是我们将要通过碰撞需要到达的点），另外通知低优先级的单位逃离这条路径（如下图7）。改变碰撞状态为解决中。
2、否则，如果我们可以避开其他单位，则避开其他单位并解决碰撞状态。
3、否则，如果我们是高优先级单位，而且我们可以将低优先级单位推离我们的路径，则将它推离，改变碰撞状态为解决中
4、否则，停止，冲i性能寻路，解决碰撞。
样例四、如果我们在移动，其他单位也在移动
1、如果我们是低优先级的单位，则我们不做任何事
2、如果我们与硬碰撞半径相交，而且我们是高优先级单位，则通知低优先级单位调到样例伞。
3、否则，如果我们是高优先级单位，计算我们的将要到达点，兵告诉低优先级单位降速并避开碰撞。
正在解决的碰撞
1、如果我们是在解决样例一碰撞情况的移动单位，而且我们到达了我们的期望点，则解决碰撞。
2、如果我们是样例3.1，低优先级和高优先级的单位已经通过了他们的目标点，开始返回原来的位置，并解决冲突。
3、如果我们是样例3.1的高优先级单位，等待（减速或者停止）直到低优先级的单位滚粗这条路，然后继续。
4、如果我们是样例3.3的高优先级单位，而且低优先级单位可以滚粗这条路了，这跳到样例3.1
5、如果我们是样例4.3的低优先级单位，而且高优先级的单位已经通过了目标点，回到正常的速度，并解决冲突。
协调的单位移动最重要的一个组件之一就是区分优先级以及处理争端，没有一个可靠、良好的优先级系统，你可以会看到单位在跳旋转木马舞，因为每个单位都要求其他单位让开，而么有一个单位有能力对这个要求说不。这个优先级系统也可以考虑碰撞的严重程度，一个简单的启发式是考虑最高优先级的碰撞以及解决穿过的所有其他硬碰撞，再考虑软碰撞，如果硬碰撞还需要很远的时间再考虑，那么你需要花费一些时间去处理更多当下的软碰撞。取决于游戏，解决机制可能也需要基于单位密度进行变化，如果一个大型的肉搏战创建了大量的混合硬碰撞（在剑士们之间产生的），你最好将你的CPU时间使用在解决所有的战斗碰撞，而不是去解决遥远区域收集单位之间的软碰撞。一个跟踪高碰撞密度区域的额外好处是你可以影响其他单位的寻路远离这些区域。
基本的规划
计划是单位合作的一个关键因素，所有的这些预测还有计算应该越精确越好，不可避免的，事情总会出错。我们制作帝国时代的移动一个最大的错误之一就是在参考单帧数据做决定。每一个决定总是正确的，但是我们没有跟踪到未来的更新。结果，单位做了决策，在执行决策的过程中却遭遇了困难，然后又需要重新下决策，然后将他们重新拉回原始路径，只能在下个更新中不断的开始整个循环。计划修正了这个重复。我们保留旧的，已经解决的冲突足够久，这样我们就可以在将来的困境中参考这些数据。当我们执行了一个躲避，比如我们记住我们躲避的那个单位，因为我们已经创建了一个可行的解决计划，这里没有必要与其他在碰撞中的单位做碰撞检测，除非其中一个单位重新获取了新的命令，或者发生其他改变。一旦我们完成了躲避调遣，我们可以恢复正常的碰撞检测状态。你在下个月可以看到，我们将会一次又一次重用这个计划理论完成我们的目标。
简单的游戏已经是过去式了，简单的移动同样也是。我们覆盖了创建一个可靠的，可扩展的移动系统的所有基本理论，一个基于状态的移动算法，一个可扩展的碰撞检测系统，一个快速的位置预测系统，所有的这些组件一起工作可以为碰撞解决创造出一个确定的方案。
下个月我们将会扩展这些理论去涵盖高级的移动主题，比如群体移动，成熟的队列移动以及复合的碰撞解决方案。我们也将会涉及更多的关于实现这些主题的细节。