Minecraft 里的学问（三）：僵尸为什么知道绕路

夜里一只僵尸在追你。你绕过一道墙，它跟着绕；前面有个坑，它绕开走；熔岩湖边上，它贴着边不下去。

看起来它认识路。但它没有眼睛认路，也没有任何想绕开的念头——它做的每一件事，都是一次计算的结果。

这篇讲四件事。游戏怎么把你的世界变成一道数学题，它怎么解这道题，它为什么偶尔会犯傻，以及这套算法是谁想出来的。

第一步，把世界变成一张图

对寻路系统来说，世界不是方块搭的，是格子拼的。每一格能走的空间是一个点，两格之间能走通，就连一条线——走平地代价是 1，走对角线是 1.41，斜着走要多花点。

然后有些格子会额外加价。火这一格代价 16，挨着火一格也贵 8，水里走一格加 8，仙人掌旁边同样 8。

还有一类更干脆的：岩浆、仙人掌本身、关着的门，直接标成不可通行。不是贵，是此路不通——它压根不会被算成一个选项。

僵尸碰火会烧起来、跳崖会摔伤，这些惩罚就是把它在现实中会吃亏的地方，提前折算成价格。一张带价格的图就画好了，剩下的问题是：在图上找一条从僵尸到你、总价最低的路。

第二步，解这道题

最笨的办法是把所有的路都试一遍再挑最便宜的，图小还行，格子一多就是天文数字。所以游戏用的是 A* 算法。它的思路是给每个尝试过的格子记两个数：从起点走到这里实际花了多少，和从这里到你大概还要走多少。两个数加起来，就是这个格子的总分。

每一步都从总分最小的格子继续往下试。

举个最小的例子。你和它之间隔着一堵墙：往左绕要 6 步，往右绕 4 步但第一步得先往回退。只看眼前的话往回走是亏的，可 A* 给每条路都记了账——已经走了几步，直线距离还剩几步。往右的那条虽然先退，但它的直线距离短，总分反而更低，它就会选右边。它算的是整条路的总价，不是眼前这一步的得失。

僵尸版本还有个细节：那个估计还要走多远的数被乘了 1.5 倍。等于让它更急躁——更愿意往靠近你的方向冲，不太愿意先退开绕远。代价是它找到的路不一定真是最短的，换来的是算得快。

第三步，它为什么会犯傻

算快了就要省着算。寻路有一个节点预算，试的格子数到了上限就停。

停了不代表找不到路，而是它会退而求其次：挑一个离你最近但还没验证通不通的点，先往那边走。多数时候没问题，但如果绕行的代价太大——比如绕一整片火海——预算耗尽的时候它还没绕出来，就会选那条看起来直、实际要穿火的路。

你见过的僵尸明明会绕火，却一头走进火里，多半就是这一刻发生的。

还有卡住。如果障碍太大，它每算一次都只够走到障碍边缘，下一次重算又从头来过，就会在同一堵墙前面反复撞。僵尸的反应还有半秒上下的延迟，因为路径不是每帧重算的，是每隔零点几秒重算一次——这半秒里它走的是上一条旧路。

顺带一提，追着你跑的时候它还会顺手拆你家木门。普通难度下门被砸出裂纹但砸不开，困难难度有一成左右的僵尸能真把门拆了。

三点说明。一，戴僵尸头颅可以把它的侦测距离减半，它看不清你，绕路也绕不到你。二，骷髅和僵尸不同，它会边打边躲。三，Java 版僵尸 35 格内锁定玩家，基岩版是 16 格，数字以你玩的版本为准；另外僵尸不怕水但也不会游泳，走进水里会一直沉到水底，泡久了就变成溺尸。

这套算法是谁想出来的

1968 年，斯坦福研究院的三个人发表了 A* 算法——彼得·哈特、尼尔斯·尼尔森、伯特伦·拉斐尔。他们当时在做一件跟游戏没关系的事：给一台叫 Shakey 的机器人规划路线。

Shakey 是世界上第一台能自己规划行动的移动机器人，名字直译就是摇摇晃晃，因为它走得确实不稳。它要在房间里绕开障碍走到指定位置，就需要一个算法帮它找路。

三个人的分工也很有意思。尼尔森先提出只看离目标还有多远；拉斐尔补了一句，把已经走了多远也加上；哈特证明了，两个数加在一起时，什么条件下能保证找到最短的那条路。

名字同样是内部记号演变来的：他们把那类算法统称 A，加个星号，表示其中保证最优的那一版。所以僵尸名字里那个星号，本意是我保证这条最短——当然，前提是没撞上节点预算。

这套算法也不只用在游戏里。外卖骑手的路线、导航软件的规划，背后都是同一类问题：在一张图上，找一条代价最低的路。