游戏菌儿
本回答可能涉及到一些比较难以理解的计算机问题，其中绝大部分是当时星际争霸开发者的原话，大麦我尽量用比较直白的说法和大家说说吧。
在星际争霸1开发的过程中，有一个BUG一直没办法被很好的解决，就是游戏中单位在自动寻路的时候总是会莫名其妙的卡住原地不动，或者是在原地打转。这个问题让暴雪的程序员头疼不已，也是因为这个BUG让星际争霸跳票了好几次，直到在游戏发售前两个月依然没办法有效的解决，还是当时的首席程序员Patrick Wyatt想到了一个超级简单粗暴的方式才终于解决了这个问题。今天就来和大家说说星际争霸中这个寻路BUG为何如此难以被解决。顺便说一句，这个问题不仅出现在星际争霸中，上个世纪的贴图RTS游戏或多或少都有这个毛病，可以说几乎是曾经所有RTS游戏的通病。
BUG如何出现的？
星际争霸最初在设计的时候其实有点问题，他用的是老式的魔兽争霸游戏引擎，却用最新的C++语言来进行编程，而当时程序员们了解C++这门语言的非常少，所以他们都是在边做星际争霸边学习C++的。
魔兽争霸的游戏引擎在绘制地图优化时会将地图分割成均匀密布的36*36像素的正方形方块，而每一个这样的方块又会被分割成16个8*8像素的小方块。而魔兽争霸的引擎之所以如此优化地图是因为魔兽争霸1和2的游戏视角都是由上到下的俯视方式，如此分割地图不仅清晰明了而且运算效率也很高，有点儿类似于国际象棋的棋盘。大家可以看看下图就能够理解游戏引擎是如何分割地图的。玩过华容道的应该就很容易理解哈哈。
单位在这些格子上的时候系统会开始判断这些小方块中是否有被占用的体积，来判断单位是否可以通过这个地方。
其实星际争霸在开发初期游戏的视角也是这种由上到下的俯视视角，但是开发到一半突然决定将视角改成等角投影风格。说白了等角投影就是普通玩家们口中所说的2.5D游戏。像暗黑破坏神、博德之门、传奇以及现在一些页游就都采用的是等角投影风格。
现在来看等角投影的游戏风格看起来已经特别过时，但是在星际争霸那个年代这绝对是高大上的代表哈哈。当时暴雪也是为了追求游戏品质才临时将星际争霸改成等角投影。但是问题却来了，虽然表面上看是变了，但是底层地图引擎却没有从新写成等角投影的菱形格子而是依旧沿用正方形格子，这就是导致后来寻路设计经常出现BUG的根本原因。
更改了视角的星际争霸为了保证单位在通过一些上坡、下坡或者斜着的路口时寻路功能正常运行，就必须将原来8*8像素的小方块都加入判定。这样地图的分辨率就会被提高，而系统要判定的面积和计算量就会增加16倍！大家就能理解为何当时星际争霸刚出来的时候对于电脑的配置会要求这么高了吧。
计算机运算量的增加还是其次，关键是正方形的小格子在一些斜着走的地方会被切割成各种各样不规则的形状，哪些格子能走哪些格子不能走都需要程序员一个一个地标记出来。咱们来看看下图就能知道我所说的是什么意思。
在红线以外的小格子是不允许走的，在红线以内是允许走的，然而哪些被切开的8*8像素的小格子又是一个非常麻烦的判定。
简单粗暴的解决方法
这时候星际争霸已经开发了一大半了，此时在重写游戏引擎那不知道游戏得到什么时候才能发售因此程序员们这能硬着头皮开始去写星际争霸的寻路代码。首先就是用穷举的方式，将所有地图可能出现的情况想出来，然后一一为他们写代码。就单纯这一项工作，就足足写了好几个月的时间。
后来有一段寻路代码一直有问题，就是农民在采矿的时候常常会自动停下来卡在原地不动。当时程序员们考虑将每个水晶能支持的农民采集数量减少，并且拉大水晶之间的距离，但是这样做就又会严重影响到游戏的平衡还有节奏，如此一改而牵连到的东西将更多，是个得不偿失的选择。
本来在采矿时可以用A*算法来实现，这是一种静态路网中求解最短路径最有效的直接搜索方法。但是在密集的采矿区域，十多个农民在相互交错着移动，A*算法就没办法很好的解决了。
在反反复复的试了无数次以后，他们发现自己实在没办法修改这个BUG，而星际争霸又马上又要发售了，于是Patrick Wyatt大笔一挥，BUG不改了，直接把农民设计成在采矿时无碰撞体积就好了。
总算在游戏发售前把这个最关键的问题解决了，后来星际1跳票两年以后终于在1998年正式发售。不过即使发售之后，玩家们也发现了游戏中还有很多的BUG，至于这个寻路问题嘛，也一直是玩家们一直吐槽的敌法。
简单的做个结尾
其实关于寻路的这个东西，真的是早期RTS游戏非常难以解决的问题，不知道大家有没有听说过一款国产RTS游戏血狮，当年的血狮就是在寻路算法上做的一塌糊涂，才导致了游戏中单位不是在原地转圈就是在发呆。
其实RTS游戏中这个寻路算法对于后世的科技发展有非常大的意义，不论是像魔兽世界这样的MMORPG还是LOL这样的MOBA，都离不开寻路算法。老一辈的游戏程序员们用他们的智慧为后世留下了许多宝贵的财富哈哈。
