分享电子游戏AI寻径方法之导航篇

发布时间：2020-02-11 06:50:10 阅读：次来源：收纳柜厂家

这是我关于寻径新方法的系列文章的第一篇。它是我过去数年在游戏AI、哲学和进化心理学方面的部分研究和心得。

寻径方法的现状

当前所有电子游戏AI模块都是使用数年前的模型制作而成的。相对于当今电子游戏其他软件的飞速发展来说，这其中有些模块已经算是历史悠久了。

例如，我甚至没有找到任何详细说明人们何时开始首次执行Navigation Mesh(或Navmesh)，我只能说这一模式至少从2004年时就开始使用了。它与Bavigation Grid这一使用最普遍实际上也是最先进的方法一样含有为电子游戏制作路径的图表。

尽管如此，Waypoint Natigation仍然、运用于大量简单的游戏，甚至年代比Navmesh还要久远。如果我们比较AI模块与图像模块(这里是指渲染游戏的图像模型)的进步，就会发现当人们首次使用路径点导航时，图像已处于CGA技术的水平。这些年来图像模块方面的进步甚为惊人。

你可能会说计算机图像的进步很大程度上得益于硬件的进化。但这里仍然存在一个问题：在过去10年中，如果我们不提OCC模型(与智能代理相关的心理方法)以及其他基于代理的方法，实际上仍然未被电子游戏所用，我们也无从见识到可以称这真正新颖或者强大、可共享的进步。

原因?大部分是因为，尽管认知科学兴起，对于内行人而言，关于人工智能话题的方法在过去数十年几乎从未发生变化。未来电子游戏的寻径方法将是什么模样?它有没有可能是在我们过去数十年的模型上制作模块?

我个人认为，未来电子游戏将与当代电子游戏截然不同。对于开发者来说，这里的问题并不在于这些游戏将呈现什么面貌，而是如何建设AI来支持新功能。我有一个关于“智能”话题的不同方法。我这一方法始于人类并非从天降落的物种，完全不同于大自然其他物种这个意识开始。这促使我去了解进化心理学，我相似它有助于AI开发首个真正的虚拟人类。

AI in Blood Bowl(from bloodbowlgame)

问题：什么是智能?

对电子游戏来说，什么是智能?智能不过是一个用于提升人类管理世界的能力的工具。它是地球自然选择的一个最强大的工具，但仍然只是同象牙，或者我们与其他灵长动物共享的对生拇指一样的工具。进化心理学将称为进化适应。这方面有许多研究和发现，神经科学和心理学领域已经指出情感会影响人类(动物)智能，如果没有它单纯的逻辑就是无用之物。

这种对于智能的思考极大改变了你在电子游戏，以及任何其他人类或动作模拟物中所发现问题的解决方法。例如，我对于寻径问题的解决方法就是考虑人类(动物)拥有自己的记忆地图这个现实。但这种记忆的结果通常不会与实际的地图对应起来。

即便是创建图表的导航方法也是截然不同的。在我看来，这应该考虑到我们如何向一个实体目标前进。这个方法带有相对于当前所采用方法的数个新功能和表现性能提升。

首个话题——-创新游戏导航

请先想想《I am alive》、《Spiderman》、《古墓丽影》、《波斯王子》、《刺客信条》或其他需要玩家角色攀爬、跳跃以及做出其他不寻常动作的游戏。在这类题材几乎所有的游戏中，都有一些由NPC所做的不自然行为。最明显的一个证据就是当NPC想抓住/杀死玩家时，“决定”不攀爬追随玩家。他们只想让玩家完成攀爬动作以便攻击他，或者在攀爬过程中从可行走的区域将其击毙。

这并不是一个符合逻辑和生物学行为，因为除非所有NPC都像了解自己的鞋子一样了解周围的建筑，他们不能确定玩家能够从自己手上逃脱。为了重制一个正确的人类行为，NPC应该使用类似钳子的策略：有些NPC追随攀爬的小偷/敌人/玩家，而有些NPC则试图跑去阻断玩家的出路。但要如何实现这种操作呢，如果寻径导航系统无法将墙体视为“可用区域”呢?电子游戏程序员很少赋予NPC攀爬和追随爬行的玩家这种能力。这是因为要实现这一操作，他们必须定制寻径模块，令其更复杂，而这一模块通常不可用于其他只需要玩家行走和奔跑的电子游戏。

我所谓的“生物寻径”(BPF)这个新方法可以从根本上解决这个问题。游戏中只能在两个微场景相接的地方含有焦点(自然生成)。即使前进的路发生变化(因为它是一堵墙或者其他“可攀爬”的表面时)也要有一个焦点。每个来自某个节点的线段都有相应权重(与一个A*方法对话)，而这个权重可以根据每个“NPC类型”穿越这条路(游戏邦注：例如通过攀爬、游泳、行走等)的能力来计算。这个解决方法包含一个更普遍的NPC管理方式，它要求对NPC进行“物种”分类。

好消息在于，使用这一方法，你可以为每种NPC选择不同的最佳路径，而每个NPC又能够根据自己的能力在平面上行动。相对于当前方法，它使用的节点数量较少，这就在路径设计上有了更大的进步。除非游戏使用大量不同类型的NPC(我还没有见过这种游戏)，否则其线下的路径设计所需投入时间应该不会超过当前的方法，但会给予我们更多功能和更广泛的解决方案。

没错，这远比一个纯粹的路径那般系统更复杂。尽管如此，现在的电子游戏已经远比《太空入侵者》或《吃豆人》更先进了，我们可以确定地说所有RPG、MMORPG、射击和战略题材的主流游戏本身就非常复杂了，所以也应该毫不犹豫地为NPC采用新功能。

节省运行时间

在过去数年中，越来越多电子游戏包括大型关卡。很显然关卡越大，就越难以保持NPC计算其到达目标的可接受表现，以并且NPC数量也更多了。

我知道有些电子游戏开发者已经意识到这个问题是开发过程中最消耗时间的环节之一。实际上，我们对于涉及人类模拟的问题的思考还是太逻辑性了。如果我们用人类来取代NPC，就会从人类角度去想寻径问题，从心理学角度来考虑。

当人类尝试思考一个更大的区域，以及如何到达目标地时，他通常会在脑中形成一些最重要的图像，场景的部分环节(例如城市的模块)，然后将每个区域想象成一个黑匣子。这种方法甚至对我们的寻径问题来说都很有帮助，因为它可避免计算最大程度的细节。Lynch已经在1960年做过关于更好地分析路径问题的人类心理研究。

有些游戏已经使用了二维寻径方法。事实上，作为直接源于人类行为心理研究的工具之一，它适用于整个生物寻径方法。

这个方法允许你仅执行自己所需的计算，并以此来节省时间。实际上，你确定NPC会穿过所有路径呢?NPC在半路上被杀死，或者说找到一个新路径，做出一些不寻常之举的机率有多大?在这些情况下，大型关卡中的整体路径计算都是无效的。应该广泛使用将大型计算分解成数个更小的由NPC执行的计算，因为它是有利于强化表现性能的好方法。这可以让NPC更具“人性化”而无需执行大量的整体运行表现。

BPF使用了寻径的两个层面：District和Zone寻径方法。前者是我在之前章节解释过的内容，后者就用于解决在更短的路径穿行，以便到达更近的目标，或者通过由District寻径方法所发现的“正确”(未必是最佳!)大路径退出区域。

即便在这个层面上，这个方法也与寻常方法截然不同。它尽量最小化人们需要考虑的微路径数量。人类实际上会通过查看目标(或者它的方向)，并检查最近的首个焦点上的路径来决定要使用哪条路径，以便向较近的目标前进。