遊戲菌兒
本回答可能涉及到一些比較難以理解的計算機問題，其中絕大部分是當時星際爭霸開發者的原話，大麥我儘量用比較直白的說法和大家說說吧。
在星際爭霸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，都離不開尋路算法。老一輩的遊戲程序員們用他們的智慧為後世留下了許多寶貴的財富哈哈。
