星际争霸 - 寻路算法

7 minute read

星际争霸 - 寻路算法

游戏单位的寻路算法，是一般的玩家应该完全没有感觉的一个游戏模块，但是一旦出现了问题，玩家就会变得很愤怒，所有人都会觉得天要塌了下来，因为你连走个路都做不好。而且在星际争霸的开发过程中，寻路的确多次出现完全不能工作的情况。

之前提到过，当星际争霸的开发陷入到永远只有两个月就要发布的压力下，我让唯一感到幸运的是，暴雪的管理层已经有过之前游戏持续跳票的经验。因为出现在寻路模块上的问题，导致整个游戏陷入无法完成的困境。

其实在任何时候，我们都有一系列的问题阻止我们能发布出一个稳定的游戏，在游戏开发的后期，我们的开发主要工作就是修复游戏中的各种缺陷和数以千计的错误。不过很多错误是很细小的问题，修复它们只需要花一点点时间，但是另外一些问题就要棘手得多。例如多人同时在线游戏里面的同步问题，就需要开发团队中多个成员花上几周的时间全力去调试和除错才能完成这样一个问题。而这样的同步问题在多人联网的即时战略类的游戏中很常见，例如帝国时代、超级指挥官这些流行的游戏中都有发布之后还没有完全解决的类似问题。

除了一些因为游戏类型而产生的特定的错误以外，另外一些问题的产生和游戏开发流程相关。例如神族的航母单位，控制它的代码进度总是落后于其他游戏单位。因为我们圣神的航母在游戏的几乎各种行为上都有自己特殊的做法。所以在游戏开发的某个点上，已经将控制航母的代码放到了一个独立的分支中。这个分支和游戏的主干代码越走越远，导致现在完全没有任何合并的可能性。于是所有在主干代码上添加的新功能需要在航母的分支上重新实现一遍，所有在主干代码上修复的问题，你迟早会在航母的行为上发现，只是更加难以修理。

但是这一切都不是导致星际争霸频繁跳票的元凶却是寻路。

并不是整个寻路的逻辑都出现了问题，相反在正常的时候我们的寻路算法工作的非常好。但是有足够的边缘条件让我们的游戏单位出现问题，足以导致游戏无法发布。游戏单位总是会在战场的某些地方出现问题，要么就是非常缓慢的一点一点的向目标移动，或是在一块区域里面转圈圈却总是不向目标前进。整个进攻的单位会像进入泥潭一样缓慢的挪动，看起来就像是大家决定停下来，开个战前会议一样。

这个问题让玩家非常的沮丧，同时也让游戏的 AI 看起来像是傻子。在这样的问题困扰下，整个游戏的数值平衡也无法设计，关卡难度也无法控制。导致整个设计部门的工作白费。

虽然我从来不是一个即时战略游戏的顶尖选手，但是在游戏发布之前我却打得不错，因为我发现人族的机甲巨人在这种寻路问题的环境下有非常大的优势。机甲巨人由于其巨大的体型，所以它比其他陆地上的单位需要更大的寻路空间，所以如果我特意将机甲巨人移动到一些地图上不能行走的障碍边上，对方的小型单位会因为寻路的问题无法移动到巨人的边上，导致在寻路的过程中被机甲巨人干掉。但是很可惜，我的这点优势在数值重新平衡之后就没有了。。。。

早期的寻路算法的确有些粗燥，但是在开发的初期也挑选了适合的算法，不过由于后期的一些错误的研发方向的决定导致整个游戏的寻路不正常。

如何到了这步

在上一篇文章中，我描述了寻路的困难。星际争霸是建立在魔兽争霸 II 的引擎之上，但是在魔兽争霸中地图是以一种顶视图的角度来渲染的。在这个引擎中，我们用一种瓦片排布的方式来组织地图，所有地图中的瓦片都是一个个32*32像素的小方块，每个方块中又被分成了16个8*8的小格子。我之所以这样构造地图引擎是因为这样的渲染方式在我们最早的任天堂主机的游戏里工作的很好。这个时期的游戏主机有直接的硬件来支持绘制8*8像素的小格子，这种特性移植到 PC 上也是非常简单的事情。

因为魔兽争霸 I 和 II 中的摄像机角度几乎都是顶视图，所以游戏地图上的单位（树木、地形、建筑等）要么是水平的要么是垂直的，所以我们的渲染引擎将整个世界都渲染成了方形的瓦片地图，在这样的正方形组成的地图上进行寻路是相对容易的。地图上每一个32*32像素的瓦片，要么是可以行走的，要么就是不可行走的。下图中那些我用绿色框框住的瓦片就是一些不能行走区域的边缘。特别注意一下左边的兵营建筑，虽然美术的图片没有完整的覆盖它所占的96*96像素的区域，让人以为下方的两个角落的方块是可以行走的（用红色框框住），但其实是不能穿过的区域。

但是，当开发团队为了将游戏的效果增加，决定将星际争霸的地图变为45度斜视角地图时，游戏中单位的边缘就不再是之前的垂直或水平了，每一条分割都变成了一条斜线，之前的瓦片对于这样的地址来说，行走区域的分辨率变得太粗，我们必须增加行走区域网格的分辨率。于是在星际争霸中，每一个8*8像素的小格子用来表示一个区域是否可以行走，而不是之前的32*32像素的瓦片，于是寻路中的计算量就是之前的16倍。虽然这样的分辨率可以让地图放下更多的小体型的兵种，但是也指数级别的增加了寻路中需要的计算量。

特别是制作地图编辑器时，想要将对角的地图单位放置到正方形渲染的地图上，需要考虑很多的极限问题，于是很多为了弥补这些问题的补丁代码就产生了。为了将这些边缘问题全部处理好，相关的开发人员花了几个月的时间。虽然暗黑破坏神也使用了斜45度的地图，但是他们使用了全新的地图渲染引擎，星际争霸团队却一直在使用之前的引擎，导致了我们每周都会发现在这样的冲突下产生的新问题。

下面的这幅图就展示了为了将一座桥的边缘行走区域可以投射到正方形的渲染引擎上，我们使用了多个8*8像素的格子。对角线的美术资源将行走边缘不平均的映射在这些格子上，导致了行走区域的边缘是一个锯齿状的图形。

因为游戏总是只有两个月就要发布，于是完全没有办法说服大家坐下来，重新重构整个地图引擎，从而让地图编辑器的开发和寻路算法的开发变得容易一些。所以寻路的确是工作的，但是在很多奇葩的边缘情况下就会出现很多问题。于是整个寻路算法变成了一个巨大的状态机，到处都是补丁代码用来让游戏单位在一个特定的困境下找到正确的路线。

采集

如果说还有其他问题比你的攻击小队决定在敌人的火力之前停步不前，围在一起喝个下午茶还要严重的问题，那就是你的采集队伍了，玩家俗称农民单位，这些单位负责在你的基地里面采集水晶和气。这些单位经常会堵塞在一起，然后停下来。当一个玩家忙着进行战斗单位的操作，或是进行第二个基地的扩展，你主基地的农民却不去采集，而是互相拥抱在一起。于是当你发现的时候，你的现金流就已经崩溃了，你也会变得非常愤怒。

虽说主要的原因是，采集区域其实相当狭小，玩家为了满足采集效率最大化，会安排每块水晶都有三个左右的农民进行工作。这些农民的行走路线都是从主基地到资源点，几乎都是重叠的，如果你的采集农民足够多，他们总是会撞在一起，最后导致寻路无法进行。

如何处理

我忘记我是自愿还是被强迫要求来处理这个采集寻路的问题了。不过当我阅读完了整个寻路模块之后，我发现以我的智商是不可能解决这个问题的，于是我开始想怎么做点小技巧来让游戏看起来没有问题。

程序员往往执着于找到针对一个问题最纯粹、抽象、干净甚至是本质的解决方案，但往往需要有人在项目里面做些牺牲，对于一些问题做一些听起来很脏的解决方案。如果你做的“邪恶的妥协”足够的好，没人会注意到。关于这点，可以看看 Brandon Sheffield 的这篇文章：Dirty Coding Tricks。

我的思路很简单：当农民们向资源点进行移动时，或者当他们拿着资源开始向主基地进行移动时，他们就会完全无视和其他单位的碰撞，是的，在星际争霸玩家群体中，我的这种妥协有了一个专有名字叫做“穿矿”。当农民完全无视其他单位的碰撞时，就算在一个狭窄的范围内进行工作，也完全不会被其他单位阻挡从而停下来不去工作。你可以通过一些简单的方法发现我的这个修正，当你同时选中很多个正在采矿的农民，并命令他们停下，这时每个农民就会重新开始寻找周围一个没有被其他农民占用的地方停下。

这样的解决方案对于大多数的玩家来说反倒是很自然，不会被察觉的，于是这反倒成了游戏的一个特色和玩家的一个技巧。游戏中还有很多其他的问题，通过这样简单的妥协达成的效果可以避免我们花费大量的时间来重构底层。游戏中很多地方都有这样的妥协，所以最终寻路模块被调校到一个不错的状态，虽然解决的方案不是很优雅，却是我们在项目中可以做到的最好的效果。

comments powered by Disqus