Minecraft 裏的學問（三）：殭屍爲什麼知道繞路

夜裏一隻殭屍在追你。你繞過一道牆，它跟着繞；前面有個坑，它繞開走；熔岩湖邊上，它貼着邊不下去。

看起來它認識路。但它沒有眼睛認路，也沒有任何想繞開的念頭——它做的每一件事，都是一次計算的結果。

這篇講四件事。遊戲怎麼把你的世界變成一道數學題，它怎麼解這道題，它爲什麼偶爾會犯傻，以及這套算法是誰想出來的。

第一步，把世界變成一張圖

對尋路系統來說，世界不是方塊搭的，是格子拼的。每一格能走的空間是一個點，兩格之間能走通，就連一條線——走平地代價是 1，走對角線是 1.41，斜着走要多花點。

然後有些格子會額外加價。火這一格代價 16，挨着火一格也貴 8，水裏走一格加 8，仙人掌旁邊同樣 8。

還有一類更乾脆的：岩漿、仙人掌本身、關着的門，直接標成不可通行。不是貴，是此路不通——它壓根不會被算成一個選項。

殭屍碰火會燒起來、跳崖會摔傷，這些懲罰就是把它在現實中會喫虧的地方，提前折算成價格。一張帶價格的圖就畫好了，剩下的問題是：在圖上找一條從殭屍到你、總價最低的路。

第二步，解這道題

最笨的辦法是把所有的路都試一遍再挑最便宜的，圖小還行，格子一多就是天文數字。所以遊戲用的是 A* 算法。它的思路是給每個嘗試過的格子記兩個數：從起點走到這裏實際花了多少，和從這裏到你大概還要走多少。兩個數加起來，就是這個格子的總分。

每一步都從總分最小的格子繼續往下試。

舉個最小的例子。你和它之間隔着一堵牆：往左繞要 6 步，往右繞 4 步但第一步得先往回退。只看眼前的話往回走是虧的，可 A* 給每條路都記了賬——已經走了幾步，直線距離還剩幾步。往右的那條雖然先退，但它的直線距離短，總分反而更低，它就會選右邊。它算的是整條路的總價，不是眼前這一步的得失。

殭屍版本還有個細節：那個估計還要走多遠的數被乘了 1.5 倍。等於讓它更急躁——更願意往靠近你的方向衝，不太願意先退開繞遠。代價是它找到的路不一定真是最短的，換來的是算得快。

第三步，它爲什麼會犯傻

算快了就要省着算。尋路有一個節點預算，試的格子數到了上限就停。

停了不代表找不到路，而是它會退而求其次：挑一個離你最近但還沒驗證通不通的點，先往那邊走。多數時候沒問題，但如果繞行的代價太大——比如繞一整片火海——預算耗盡的時候它還沒繞出來，就會選那條看起來直、實際要穿火的路。

你見過的殭屍明明會繞火，卻一頭走進火裏，多半就是這一刻發生的。

還有卡住。如果障礙太大，它每算一次都只夠走到障礙邊緣，下一次重算又從頭來過，就會在同一堵牆前面反覆撞。殭屍的反應還有半秒上下的延遲，因爲路徑不是每幀重算的，是每隔零點幾秒重算一次——這半秒裏它走的是上一條舊路。

順帶一提，追着你跑的時候它還會順手拆你家木門。普通難度下門被砸出裂紋但砸不開，困難難度有一成左右的殭屍能真把門拆了。

三點說明。一，戴殭屍頭顱可以把它的偵測距離減半，它看不清你，繞路也繞不到你。二，骷髏和殭屍不同，它會邊打邊躲。三，Java 版殭屍 35 格內鎖定玩家，基岩版是 16 格，數字以你玩的版本爲準；另外殭屍不怕水但也不會游泳，走進水裏會一直沉到水底，泡久了就變成溺屍。

這套算法是誰想出來的

1968 年，斯坦福研究院的三個人發表了 A* 算法——彼得·哈特、尼爾斯·尼爾森、伯特倫·拉斐爾。他們當時在做一件跟遊戲沒關係的事：給一臺叫 Shakey 的機器人規劃路線。

Shakey 是世界上第一臺能自己規劃行動的移動機器人，名字直譯就是搖搖晃晃，因爲它走得確實不穩。它要在房間裏繞開障礙走到指定位置，就需要一個算法幫它找路。

三個人的分工也很有意思。尼爾森先提出只看離目標還有多遠；拉斐爾補了一句，把已經走了多遠也加上；哈特證明了，兩個數加在一起時，什麼條件下能保證找到最短的那條路。

名字同樣是內部記號演變來的：他們把那類算法統稱 A，加個星號，表示其中保證最優的那一版。所以殭屍名字裏那個星號，本意是我保證這條最短——當然，前提是沒撞上節點預算。

這套算法也不只用在遊戲裏。外賣騎手的路線、導航軟件的規劃，背後都是同一類問題：在一張圖上，找一條代價最低的路。