游戏里NPC眼中的世界是怎样的？浅谈电子游戏的导航系统
在游戏中，如何找路一直是个难题。正如同笔者之前开FF14的5.0后在水晶都的痛苦一样，明明地图上看起来只有几米之隔，但是实际上那扇大铁门只是个封闭场景贴图，你得从其他地方的梯子绕过去才能到任务目标脸上。
那么在游戏NPC的眼中，这个世界又是怎样的呢？尤其是有些地形复杂，NPC却又会随机生成的游戏里，它们为什么不会在游戏里迷路呢？
这就得从游戏里的导航机制开始说起了。
一般来说，游戏的导航分为三种模式：格子（Grid）、路径点（Waypoint）、导航网格（Navmesh）。
首先是格子：
这种方法将原始地图分割成许多的小格子，在计算机中表示为一个二维数组，用0和1分别表示障碍和可行走区域。能够通过的地方就是0，障碍物就是1。
这种简单的结构可以让二进制的AI一下子就明白：哪里可以通过，哪里是障碍物。而且修改简单也更容易实现，多用于简单的平面游戏和早期游戏。可惜遇到了3D地图，或者那些弧形的场景就歇菜了。
这里我们其实可以举个不太恰当但是很直观的例子。你在MC里画像素画和雕塑就是这个感觉，每个格子都是独立的单位，简单的搭建图形突出一个有手就行。
但是如果你想画一张超精细的像素画，你就得用海量的方块来画一张超级大的地图画，还得拉远了看。而方块少的画曲线表现也很拉胯，一切问题在不引入其他系统的情况下都是靠加块完成，结果电脑又要吃不消。
这时候，我们就需要路径点导航法了。
这种方法会在地图中标注一些路点，寻路只能发生在路点和路点之间，在AI的眼中，这个世界的通行方法就是从一个点移动到另一个点。成都理工大学的唐李顺硕士的论文《浅谈人工智能寻路算法在电子游戏中的研究和应用》中讲的更加明白：
这种方法比较经济，虽然人工操作方面多了点。尤其是要手动设计路线。但是它更接近于一个路线设定功能，而非需要智能算法的空间表征。
当然，如果你需要的是在一个复杂的3D场景进行多种可能下的移动，那么大家往往会选择导航网格。
导航网格是一种用于在复杂空间中导航寻路、标记哪些地方可行走的多边形网格数据结构。当然很多时候，它会被用于承载更多的功能：比如标识该位置的地形、该位置角色应该采用什么动作（行走、游泳、攀爬）。
众多凸多边形组成了整个导航网格，它就像一份立体版的数据地图。把地图的每一块都分割出了对应的属性，这些属性会作为寻路算法的计算参数，从而计算出最适合的路线。
导航网络的优势在于能精确地表征世界。虽然做不到百分百还原真实地图，但是它无疑比格子和路点都更精确。并且引入了Z轴的高度信息，使得表示3D地图成为可能。要说缺点，可能就是太过复杂和占用内存，毕竟你总要读取这个网络的数据才能开始工作。
在AI眼中，游戏世界就是由这些满是数据的网格组成，它们用算法来思考，比看着游戏贴图的玩家更方便的获取信息和计算最短路线。这就是为什么NPC除非故意这么设计，不然很难迷路。
在《上古卷轴5》（简称老滚5）里有一个都市传说：“只要你追着狐狸，就能找到宝箱。”
这个传闻从发布之初就被人津津乐道，以至于开发组进行了非正式调查，询问“谁加了这种彩蛋逻辑？！”
当时属于开发团队的乔尔·伯吉斯后来出面解释了这个传说。
当时包括伯吉斯在内的几个人都接受了盘问，但没有人承认有做过这种彩蛋。直到伯吉斯确认了脚本并没有任何相关内容后，才有了一个猜想：
他们的寻路规则里限制了老滚5中AI的行动范围。在老滚5这种开放世界RPG中，NPC会在城市中漫游，但名为 Navimesh 的系统决定了NPC在地图上可以去的地方/不能去的地方。
大多数情况下，AI会根据情况做出决定，比如“跑向玩家”或“躲在阴影中”。而狐狸被设置为只能“逃跑”，所以它只能沿着“逃跑”对应的导航网格移动，直到和玩家拉开到了多少距离，才会停止逃跑。
而逃走的狐狸之所以会前往宝藏，是因为在老滚5中，到物体的距离是通过“导航网格数”而不是米来计算的，并且导航网格的密度根据游戏中的位置而有所不同。而算法没有有理由在的荒野这样的空间里设置多条路线，以至于荒野中的网格密度很低。
相反的是，在像营地这样的地方，设置了很多阻碍移动的障碍物。结果就是营地分配了更多导航网格。
遇到玩家的狐狸开始 “逃离玩家”，然后移动到一个有许多导航网格的地方，以确保相对距离。这种时候，最容易移动到的地方就是附近的营地，而且由于营地等是最有可能放置宝物的场景，这才导致了追着狐狸能够找到宝箱的都市传说。
可以看出，三种导航机制本质区别在于AI眼中的世界是怎样的，属于一种空间表征的差别。而设计师给予AI的寻路算法，则决定它们会在这个世界中以怎样的逻辑进行移动。
而很多令人哭笑不得的“智障AI”，比如撞墙，跳楼，自杀，就是因为算法没有计算到这种可能。
举个例子就是《血源诅咒》中的“二师兄”巨猪。它们在距离玩家比较远时，会使用冲撞的能力来突进攻击玩家，这时它的AI导航路径便是一个简单的向玩家直线移动的追踪状态。这个状态在大平地上无往不利，但是一旦遇到一些墙角，或者模型碰撞突出道导航网格没有完美还原的位置，就会被原地停住，死于玩家的穿模攻击和绕后掏肾。
所以AI眼中的世界，是和我们不一样的，如果我们也有一个标注好“这里是空气墙”，“这里是通道”，“该路线通往四艺区”，想来我们也不会迷路！
只是如果这样，沉浸感要大打折扣了。这也是为什么很多海外MMO没有自动寻路的功能之一，毕竟迷路，也是专属玩家的快乐。
本文参考内容：
《寻路建模的三种方式比较》by长三月
《浅谈人工智能寻路算法在电子游戏中的研究和应用》BY唐李顺