发表于2013-02-28 16:15| 7145次阅读| 来源Code of Honor| 53 条评论| 作者Patrick Wyatt
游戏单位的路径寻找功能是很多玩家从未关注的东西，除非它存在巨大的问题，然后这个并不重要的问题会引发玩家更大的愤怒，最终导致“毁灭世界”的大灾难。在StarCraft的开发过程中，很多时候其路径寻找功能完全不起作用。
随着StarCraft开发的延长，它看起来像是个不会完工的项目：永远离发布还有两个月，但没有认识征兆显示正在接近传说中的发布日期。“幸运”——我有意地使用这个词——的是，Blizzard之前就有拖延游戏发布的经验。
我们一直都有“目标”（尽管用“期望”也许更好） 发布日期，但除非游戏已经准备完毕，否则我们并不打算发布它。Blizzard“静待完善”的政策意味着承诺只发布高质量产品，也意味着无法保证游戏的发布日期。
无论如何，若想发布最终 产品，我们还需要解决一系列难题。和其他游戏游戏一样，在开发的收官阶段总需要寻找并修补各式各样的缺陷，其数量可以千记。
有的只是小问题，只需稍作修补；不幸的是，并非所有缺陷都是如此。
其它的，比如之前提到的多人同步bug，会需要编程团队多个成员持续工作数周来解决。其他程序员，比如 Ages of Empires和Supreme Commander的开发者，也报告过类似的同步bug经历。
有的bug与开发过程本身相关。Protoss Carrier（神族的航空母舰）相比于其他单位总是有延迟，因为它处理任何事情的方式与众不同。在某个时间点，Carrier的控制从游戏代码主干中分支出来，然后在重新集成时发生了预料之外的问题，因此任何其它单位新增的功能都需要为Carrier重新实现；每次其它单位中修复的bug，也会在Carrier发现类似bug，不过修复起来更加麻烦。
但拖延StarCraft发布的最大问题还要数路径寻找问题。
路径寻找功能并非完全坏掉的，恰恰相反，大多数情况下表现得非常好，但是很多边界情况下的问题导致游戏迟迟无法发布。
游戏单位常常会卡住，在战场上停下来。大多数情况下，它们最终能够找到正确的路径，缓慢地向前进或者在周围旋转；但有时候会越来越挤，最终无法再前进一步，整个任务会陷入上下班一样的堵塞状况。
这个问题让玩家感到沮丧，也让AI变得虚弱，经常无法平衡任务并且浪费设计时间。
虽然我并非顶级RTS玩家，但是在游戏发布前我还是算擅长的，因为我发现Goliaths（人族巨人）因为差劲的路径寻找问题被过度加强了，因此通过小心指引Goliaths绕过障碍，我就能在关键时刻顶住火力，战胜“宏”玩家。可惜的是，Goliaths被平衡后我的技巧就不再起作用了。sigh
早期的路径寻找功能非常粗糙——虽然有精选的算法指引单位运动，但是项目过程中一些糟糕的决定导致其天生残疾。
我们怎么会在这里？
在之前的一篇文章里，我提到了路径寻找难题。StarCraft使用了Warcraft的游戏引擎，使用tile引擎来渲染地形，而这个tile引擎为处理16个8×8组成的32×32方形单元做了专门的优化。我在Warcraft中设计这样的架构是因为：之前为超级任天堂和Genesis开发游戏时都运作良好。这些游戏机有专门绘制8×8tile的硬件支持，而这些功能在PC上也容易模拟。
因为Warcraft I和II和的视角近乎是自上而下，游戏地图上所有物体（森林、地形、建筑）的边缘都是是水平或者垂直，因此渲染引擎将世界当作正方形tile地图来渲染有益于路径寻找，在这两个游戏中，每个32×32的像素块要么可通过要么不可通过。如下图，我将可通过的tile注以绿色边缘。图中有的tile显示为可通过，实际上不可以；在下方你能看到兵营建筑的图形就不能 填满它所坐落的48×48区域，剩下两个看起来可通过，实际上不可通过的tile。
tile为32×32的Warcarft 2地图
但是，为了将StarCraft变得更有视觉吸引力（详情请见《StarCraft: Orcs in Space 在欺骗中浴火重生》），开发团队将其切换为对角形式。但是底层的地形引擎并没有为对角tile重新设计，仅仅重新绘制了tile。
新视角看起来非常不错，但为了保证路径寻找的正常工作，必须增加路径寻找地图的分辨率：现在精细为16个8×8的tile。得益于更高的分辨率，地图上也可以呈现出更多的单位，这也意味着为了搜寻更大的路径空间需要花费更多的计算能力。
现在路径寻找更具挑战性，因为tile的对角线边缘将很多正方形tile不均等地分割了开来，这样确定一个一个tile可通过或者不可通过变得更加困难。为了保证所有的tile标记的正确，需要更多的计算工作。
StarCraft地图编辑器非常难写，因为很多为了将对角图形放置在方形地图上带来了很多边界情况。编写特制的“tile修复”代码至少需要数月时间。
和使用了对角渲染引擎的Diablo不同，StarCraft开发团队不得不继续使用旧引擎，尽管每周都会发现更多的新问题。
这张图显示了一座桥是如何以8×8的拼；tile组成的，有几个标注为了绿色。透视角度的贴图不均等地覆盖在tile上，这导致大桥的两边都出现了楼梯一样的边缘，正如你在图中所见，红线将每个tile都切割为不规则的形状。
使用8×8tile的StarCraft
因为项目一直受到离发布仅剩两个月的压力，所以不可能为了让路径寻找变得更容易而重新设计地形引擎，也因此路径寻找功能一直难以完善。为了解决棘手的边缘问题，路径控制代码成为了一个巨大的状态机，用来处理各种专门的“让我离开这里”的命令。
高峰时间
如果说路径寻找问题有一个最严重的情况，那一定是采伐单位（人族SCV，虫族drone，神族probe），它们在采集水晶或者vespene gas（之后的矿物“minerals”）会产生严重的堵塞，最后慢慢停止。当玩家在忙于管理进攻或者第二基地时，基地的采伐单位就会堵塞，因此金库不再有收入，然后玩家会发现因为没有足够的金钱而无法继续建造。
资源采集的基本问题在于，玩家希望最大化每个矿源采伐者的数目以获得最多的金钱。采伐者会经常来往于矿产与基地之间，所以经常会和其他采伐者相向而行，并且“撞”在一起。一个狭小的空间涌入了过多的采伐者，往往会导致其中大部分会阻塞在一起直到矿藏被采伐完。
我们如何从这里出去？
我记不清那时是自愿还是被要求来解决这个问题了，在阅读了大部分的路径寻找代码后，我明白了自己并没有那么聪明以至“解决这个难题”，因此我想出了一个肮脏的小把戏。
程序员经常会沉迷于寻找最纯粹、简洁甚至崇高、神圣的解决方案，但在项目中必须有所舍弃。如果解决得很好，没有人会注意到实现背后邪恶的妥协，正如Brandon Sheffield在《Dirty Coding Tricks》一文中所写的那样。
我的想法很简单，只要采伐者往采矿的方向前进，或者是往回运送矿物时，它们会自动忽略与其它单位的碰撞。通过消除采伐者单位间碰撞的代码，运输过程再也不会遇到阻塞的状况，因此采伐者能够高效地运作。
如果你选中大群正在采集水晶的采伐者并命令其停下来，你会发现他们 会立刻展开、寻找没有被其它单位占领的tile。
如果你仔细观察的话会发现这很明显，但它就是在你的眼前隐藏了——并没有触发你视觉意识层面，当然专业玩家和地图开发者/MOD开发者除外。
简而言之，它就是管用，这就是最好的技巧。
虽然，想要完成游戏还有很多工作要做，但是这次技巧让我们免于重新开发游戏引擎，节约了很多时间。
其它单位的路径寻找问题开发团队已经能够胜任了，因此没什么可说的，尽管Protoss Dragoon（神族龙骑士）是个例外，因为它作为最大的地面单位，还是经常会出现路径寻找问题。
最终结果是，路径寻找已经足够胜任，我们也从中学到了沉重的教训。
原文链接： Code of Honor
相关文章：