作者简介
Wyatt, "Pat" ，1991年加入硅与神经键（暴雪前身），三位创始人以外的第一个员工。自1994年起任暴雪研发副总裁，2000年从暴雪离职创办公司，后推出『激战』系列游戏。
Pat作为元老级员工，参与了几乎所有暴雪早期游戏的开发——包括暴雪起家时的几款SFC游戏，也包括后来脍炙人口的三大系列：『魔兽争霸』初代和二代（制作人+主程）、『星际争霸』（程序）、『暗黑破坏神』初代和二代（程序）。
（详细请阅读：About me - Code Of Honor）
关于博文和翻译
此文讲述了星际争霸开发过程中关于单位寻路问题的困难、一个打破思维定式解决难题的小故事，以及Pat对项目管理的反思（吐槽）。
题目和文中的「hack」一词在编程语境特指「不直观、不优雅、丑陋却有效的解决方案」，颇有「不拘一格」「简单粗暴」之意味，不知汉语中哪个词汇可以精确对应，因此特地保留。
如果有译错之处，请在评论区指正，谢谢。
——@
—————以下是正文—————
游戏中的单位寻路（*译注1）这个事，好使的时候玩家不会去注意它，不太好使的时候一点小毛病就能让人怒删游戏。而星际争霸，在开发阶段曾经有那么一段时间，寻路根本完全不能使。
星际争霸的开发过程一拖再拖，似乎永远都无法完成：这游戏总是号称还有两个月就发售，完成度却从来没有接近那个迷之发售日。「幸亏」——这个词我故意用的——暴雪有过跳票的前科。
虽然我们一直就有「目标」（其实说是「愿望」更合适）发售日期，我们还是尽量不要对外公开它，直到什么时候有相当把握能按期做完游戏。暴雪的「等它做完」政策保证了产品的高品质，另一方面，也相当于承认了没人知道具体什么时候游戏能做完。
无论如何，在完成项目之前我们碰到了一堆问题，使游戏无法上市。和其它进入开发尾声阶段的游戏一样，大量的毛病等着被发现和修复，而且遗留bug数以千计。大多数bug是小毛病，三两下就能修好。可惜并不是所有bug都这样。
其它的，例如多人对战同步bug，需要编程团队中的好几个人专门花时间——有时一个问题就要花上几周。其它游戏的开发者也吐槽过类似的修同步bug的经历：『帝国时代』和『最高指挥官』。（*译注2、3）
一些bug是由于开发流程本身不完善产生的。神族的航母，动不动就被其它单位甩在后面，因为它总有自己的一套……无论干什么都是。在某个时间点，航母的代码从主代码中分支出来，然后在自成一派的道路上渐行渐远，到了没有任何希望重新整合回去的地步。所以，不管什么时候给其它单位加了一个新功能，都得再给航母重新写一遍。什么时候给其它单位修了一个bug，航母的代码里也会发现类似的bug，而且只会更隐蔽、更难处理。
不过，导致星际争霸跳票的最大原因是单位寻路。
并不是说寻路功能彻底是坏的。大部分情况下它工作得相当不错，但「极端情况」（*译注4）却多到让游戏没法发售。
游戏中的单位会卡住，在战场上傻站着不动。他们经常拼命地想要寻找路线，一步一挪、原地打转，就是不往正确的地方走，有时候还会挤在一起无法动弹。整个大军陷入停滞，就像晚高峰的国贸桥。（*译注5）
这个问题不光是让玩家不爽，同时还让AI变得更弱智，进而数值平衡也做不下去、浪费设计工时。
尽管我从来算不上是RTS高端玩家，在游戏发售前我还是玩得挺厉害的，因为我发现人族的机器人（）被做得太强了。初衷是为了弥补它们寻路时的弱智，机器人比其它的地面单位体型大，所以寻路时需要更宽阔的空间。而通过微操仔细控制走位，我就能高效利用机器人逆天的火力来干掉不会微操的对手，打赢本来互相平推赢不了的仗。可惜我这招好景不长，机器人被重新平衡以后就不管用了。哎。
早期的寻路功能非常粗糙——虽然算法是精心挑选出来的，但效果却大打折扣，这都是因为项目中的一些错误决策。
我们是怎么陷入困境的？
之前的一篇博客中（*译注6）我提到过寻路是个麻烦事。星际争霸是基于魔兽争霸引擎制作的，引擎绘制地图时针对这样的方式优化：使用32×32像素的方形图块，每个图块又由16个8×8像素的小方格组成。我之所以把魔兽争霸设计成这种结构，是源于之前做SFC和MD游戏的经验。这些主机硬件支持8×8图块的绘制，在PC上这也很方便模拟。（*译注7）
由于魔兽争霸1和2的镜头视角基本是从正上方鸟瞰俯视，地图上各种物体（森林、地形、建筑）的边缘都是横平竖直的，所以图像引擎用方形图块来表现世界有助于简化寻路逻辑。在这两个游戏中，每个32×32的图块要么能通行，要么不能通行。下面这张图中，我用绿框圈出了一些图块。有些图块看起来能通行但实际上不能，你可以看看那个兵营，美工画的房子并没有填满整个96×96的占地，结果左下和右下两块看着好像能走、其实是过不去的（红框）。
魔兽争霸2的寻路地图使用32×32图块
但是星际争霸开发到一半的时候，团队把游戏画面改成了等角投影风格（*译注8），使它看起来更高大上（详见之前的博文）。而实际上底层的地形引擎并没有重写成等角投影的菱形格子，只有贴图变了。
新的镜头视角看着很爽，但是为了保证寻路功能正确运行，寻路地图的分辨率必须增加：现在每个8×8的小方格都独立标记能否通行，寻路地图的尺寸一下变成了之前的16倍。更好的分辨率虽然让地图能够挤下更多单位，却同时也意味着寻路时的计算量大幅增加。
寻路问题变得更复杂，因为斜着画的边缘把正方形的格子给切得乱七八糟的，难以确定这些小格子到底能不能走。为了正确标记所有小格，需要进行大量的工作。而且地图编辑器也相当难写，因为要考虑把斜着的形状叠在正着的图块上时造成的大量极端情况。写这些专门「搞定图块」的代码花了几个月。
尽管各种毛病层出不穷，每周都能发现新问题，星际争霸开发团队却坚持使用旧引擎，不像暗黑破坏神那样用原装的等角投影渲染引擎。
下图展示了这个桥是怎么用8×8的格子做出来的，我用绿框标出了一些格子。如红线所示，在近似于等角投影的视角下，贴图斜着把这些格子切成了不规则的形状，搞得桥的两边都是锯齿型的边缘。
星际争霸的寻路地图使用8×8的小方格。
因为项目永远还有两个月就要完工，重写整个地形引擎、使寻路算法简单化肯定是「来不及」了（*译注9），所以只能生写寻路代码。为了处理各种奇葩的极端情况，用于寻路的代码量暴涨，变成了一个巨型状态机，包括各种特殊的「让我出去」的hack算法。
堵车时间
如果说寻路算法当中存在一个最主要的大问题，那就是农民单位（SCV、Drone、Probe）在采矿或者采气的时候会堵车，它们会互相挤成一团、动弹不得。当玩家忙着控制前线部队打仗、或是开分基地的时候，老家的农民却自己堵在路上，切断了经济收入。然后玩家一抬头，发现兵营里造兵的大长队早就因为缺钱而停工了。
资源采集的基本问题在于玩家肯定想造满农民，一刻不停地采每一块矿，多多益善。这些农民们在矿点和基地之间来来往往，所以它们经常会和对面过来的农民撞个满怀。当一小块地方挤了好多农民以后，完全有可能发生其中一些卡在中间动不了的情况，直到矿点被采秃为止。
我们怎么脱离困境？
我现在已经记不清当时是自愿的还是被请过来处理这个问题的了。上下看完整个寻路代码以后，我意识到以我的智商不可能「解决这个问题」。所以我用了一个操蛋的hack来跳过它。
面对问题时，程序员们可能会纠结于寻找一个最为纯粹、抽象、简洁、高雅的解决方案，但是项目中有时也需要一些牺牲。如果处理得足够好，没有人会发现背后那些邪恶的妥协，例如 在『Dirty 』一文中写的东西。
我的办法很简单：当农民在去采矿的路上，或是抱着矿运回家的路上，它们忽略与其它单位的碰撞。取消了农民的碰撞代码，它们再也不会堵在一起了，然后大家就可以愉快高效地采矿。
玩家是可以发现这个特殊处理的。如果圈选一大群正在采矿的农民，然后按H让它们停止，它们会立刻散开、找一个没有被其它农民占领的位置。
当你仔细观察时这个处理很明显，但乍一看上去却隐藏得很自然——它并不会引起普通玩家的特别注意，虽然专业级玩家和做地图的可能会发现。
简而言之，这招就是管用，这就是最好的一种hack。
虽然还有很多其它工作要做，但这个hack让我们可以不用花时间进行大幅重写。其它的寻路问题都是开发团队可以解决或者忽略的。不过神族的龙骑兵（）后来还是饱受吐槽，作为体型最大的地面单位，这玩意经常找不到路。
最后的结果是，寻路效果还不错，并且我们都学到了沉重的一课，不要把一厢情愿的期望当日程管理工具。
—————正文完—————
另，Pat在评论区介绍了一下寻路算法的实现：
寻路算法是Brian （所以他在这个话题有更高的发言权），基本套路是这样的：
读图的时候，把地图分成若干个相对较小的区域（平均每个区域大概10×10个32×32的图块大），这些区域互相挨着，而且内部没有大个的障碍物。区域内部的寻路可以用A*搞定，撞到障碍的几率很小。
读图的时候，创建一个更高层的地图用来储存区域间的邻接关系。区域是不规则形状的，所以这个高层地图相当于一个节点图，而不是图块地图。
区域间的寻路，在高层地图上用A*实现。这样就不需要计算每一个8×8的小方块，不然太耗时间了。
当单位移动时，对它们占领的小方块进行标记，然后用一大堆特殊逻辑，包括各种极端情况、单位行为、敌军vs友军，来遍历这些被占的小方块。如过我没记错的话，这些特殊逻辑还包括一个状态机，大概有40个不同状态。
飞行单位的寻路行为有另一套算法，这个是显然的。我打算写另一篇文章，聊聊飞行单位使用的另一个hack（*注：这篇文章坑了）。
评论（0）