星际争霸 - 寻路算法

星际争霸 - 寻路算法

游戏单元的寻路算法是普通玩家根本感受不到的游戏模块。 但一旦出现问题，玩家就会变得非常愤怒，大家都会感觉天塌下来，因为连路都走不了了。 两者都做不好。 而在星际争霸的开发过程中，确实也有寻路完全失效的时候。

正如之前提到的，当《星际争霸》的开发顶着总是只有两个月发布时间的压力时，我唯一感到庆幸的是暴雪的管理层已经经历了前作的不断延期。 因为寻路模块的问题，整个游戏陷入了无法完成的困境。

事实上，任何时候我们都会遇到一系列的问题，阻碍我们发布稳定的游戏。 在游戏开发后期，我们主要的开发工作就是修复游戏中的各种缺陷和数千个错误。 虽然许多错误都是小问题，只需一点时间即可修复，但其他错误则要棘手得多。 例如多人同时在线游戏中的同步问题，需要开发团队的多名成员花费数周的调试和调试才能解决这样的问题。 这种同步问题在多人在线即时战略游戏中非常常见。 比如《帝国时代》、《超级指挥官》等热门游戏就存在类似问题，发布后也没有完全解决。

除了一些特定于游戏类型的错误之外，还会出现与游戏开发过程相关的其他问题。 例如，控制神族航母单位的代码进度总是落后于其他游戏单位。 因为我们圣神航母对于游戏中几乎每一个行为都有自己特殊的处理方式。 因此在游戏开发的某个时刻，控制航空母舰的代码被放入一个单独的分支中。 这个分支已经离游戏主代码越来越远，导致根本没有合并的可能。 因此，主代码中添加的所有新功能都需要在航母分支上重新实现。 主代码中修复的所有问题迟早都会在航母的行为中被发现，但修复起来会更加困难。

但这一切都不是导致星际争霸频繁抢票的罪魁祸首，而是寻路。

并不是说整个寻路逻辑有问题。 相反，我们的寻路算法在正常情况下工作得很好。 但有足够的边缘条件导致我们的游戏单元出现问题，足以阻止游戏发布。 游戏单位在战场的某些部分总是会出现问题，要么非常缓慢地一点一点地向目标移动，要么在某个区域盘旋但从未向目标移动。 整个进攻部队会缓慢移动，仿佛陷入泥潭，仿佛所有人都决定停下来开个战前会议。

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

虽然我从来都不是即时战略游戏的顶尖玩家，但在游戏发售前我就玩得不错，因为我发现人类机甲巨人在这种有寻路问题的环境下有着巨大的优势。 由于体型巨大，机甲泰坦需要比其他陆地单位更大的寻路空间，所以如果我刻意将机甲泰坦移动到地图上一些无法行走的障碍物处，对方的小单位就会因为寻路问题，无法移动到巨人身边，所以在寻路的过程中就被机甲巨人杀死了。 但不幸的是，我的这个优势在数值调整后就消失了。 。 。 。

早期的寻路算法确实有点粗糙，但是在开发初期就选择了合适的算法。 但由于后期发展方向上的一些错误决策，导致整个游戏的寻路异常。

我们是如何走到这一步的？

在我的上一篇文章中，我描述了寻路的困难。 《星际争霸》基于《魔兽争霸 II》引擎，但《魔兽争霸》中的地图是从俯视角度渲染的。 在这个引擎中，我们使用瓦片排列方法来组织地图。 地图中的所有图块都是32*32像素的小方块，每个方块又分为16个8*8像素。 小网格。 我之所以以这种方式构建地图引擎，是因为这种渲染方法在我们最早的任天堂游戏机游戏中运行良好。 这个时期的游戏机有直接的硬件支持绘制8*8像素的小网格，并且将该功能移植到PC上非常简单。

因为《魔兽争霸1》和《魔兽争霸2》中的摄像机角度几乎都是俯视图，游戏地图上的单位（树木、地形、建筑物等）要么是水平的，要么是垂直的，所以我们的渲染引擎将整个世界渲染为带有方形瓷砖的地图，在这样的方形地图上寻找路径是相对容易的。 地图上的每个 32*32 像素图块要么是可步行的，要么是不可步行的。 下图中我用绿色框起来的瓷砖是一些不可步行区域的边缘。 特别注意左边的军营建筑。 虽然艺术图片并没有完全覆盖它所占据的96*96像素区域，但它让人认为下面两个角的方块是可以行走的（红框内），但实际上它是一个无法跨越的区域。

然而，当开发团队为了增加游戏效果，决定将星际争霸地图改为45度斜视地图时，游戏中单位的边缘不再像以前那样是垂直或水平的，每个分段变成了对角线，步行区域的分辨率对于这样的地址的先前图块来说变得太粗糙，我们必须增加步行区域网格的分辨率。 所以在星际争霸中，每个8*8像素的小格子用来表示一个区域是否可以行走，而不是之前的32*32像素的小格子，所以寻路的计算量是以前的16倍。 这样的分辨率虽然可以让地图放置更多的小尺寸单位，但同时也成倍增加了寻路所需的计算量。

尤其是在制作地图编辑器时，如果想要在正方形渲染的地图上放置对角线的地图单元，需要考虑很多极端的问题，因此产生了很多补丁代码来弥补这些问题。 为了处理所有这些边缘问题，相关开发人员花了几个月的时间。 虽然暗黑破坏神也使用了45度倾斜的地图，他们使用了新的地图渲染引擎，但是星际争霸团队一直在使用之前的引擎，导致我们每周都会发现这样的冲突的新问题。 。

下图所示，为了将桥梁的边缘行走区域投影到方形渲染引擎上，我们使用了多个8*8像素网格。 对角艺术资源在这些网格上不均匀地映射行走边缘，导致行走区域边缘呈现锯齿状。

因为游戏总是距离发布只有两个月的时间，所以绝对没有办法说服大家坐下来重构整个地图引擎，让地图编辑器和寻路算法的开发变得更容易。 所以寻路确实有效，但是在很多奇怪的边缘情况下会出现很多问题。 于是整个寻路算法变成了一个巨大的状态机，到处都有补丁代码，让游戏单元在特定的困境中找到正确的路线。

收藏

如果有什么问题比你的攻击小队决定在敌人开火前原地不动并聚集在一起吃下午茶更严重的话，那就是你的聚集小队，被玩家称为农民单位。 负责收集基地中的水晶和能量。 通常这些单位会挤在一起然后停下来。 当玩家忙着操作作战单位或扩建第二基地时，主基地的农民并不是聚集在一起，而是互相拥抱。 所以当你发现的时候，你的现金流已经崩溃了，你会变得非常生气。

虽然最主要的原因是收集面积其实相当小。 为了更大限度地提高收集效率星际争霸比赛地图，玩家会安排大约三名农民来处理每个水晶。 这些农民的行走路线都是从主基地到资源点，而且几乎都是重叠的。 如果你有足够多的聚集农民，他们总是会互相碰撞，最终使寻路变得不可能。

如何处理

我忘记了我是自愿还是被迫处理这个 *** 寻路问题。 但当我读完整个寻路模块后，我发现以我的智商根本不可能解决这个问题，所以我开始思考如何做一些技巧让游戏看起来没有问题。

程序员往往痴迷于寻找一个问题最纯粹、最抽象、最干净甚至最本质的解决方案，但这往往需要有人在项目中做出一些牺牲，对一些问题做出一些听起来脏兮兮的解决方案。 如果你的“邪恶妥协”足够好，没有人会注意到。 关于这一点，你可以阅读这篇文章：Dirty。

我的想法很简单：当农民向资源点移动时，或者当他们获取资源并开始向主基地移动时，他们将完全忽略与其他单位的碰撞。 是的，在星际玩家群体中，我的这种妥协有一个特殊的名字，叫做“刺穿地雷”。 当农民完全无视其他单位的碰撞时，即使他们在狭窄的范围内工作，也不会被其他单位阻挡而停止工作。 你可以通过一些简单的方法发现我的这个修正。 当你选择许多同时采矿的农民并命令他们停止时，每个农民都会开始寻找周围没有其他农民占据的地方停下来。 向下。

这样的解决方案对于大多数玩家来说是很自然的，不会被注意到，因此它成为了游戏的一个特色，也成为了玩家的一项技能。 游戏中还有很多其他的问题，这样简单的妥协所达到的效果可以让我们不用花大量的时间去重构底层。 游戏中很多地方都存在这样的妥协，所以最终将寻路模块调整到了良好的状态。 虽然解决方案不是很优雅，但这已经是我们在项目中能达到的更好效果了。