寻径方法的现状

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

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

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

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

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

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

问题：什么是智能？

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

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

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

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

请先想想《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寻径方 法所发现的“正确”（未必是最佳！）大路径退出区域。

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

创造图表

NavGrid或者NavMesh模型已经够用和够好了，在某些情况下无需任何定制选项。如果你想一次创造一款电子游戏，即那种与他人相似的电子游戏，那么它们就很适合你。如果你的 游戏中没有多少NPC，你也不介意他们有时候（或者经常）做出一些人们在行走时根本不会出现的奇怪举动，那么你就没有必要寻找更好的解决方案了。

但是，未来的电子游戏不会使用含有不具有人类行为的NPC。更新的模型应该提供无需定制的新功能，从而实现更好的表现效果。

当前的Navgrid和Navmesh模型具有优势，但劣势则更明显。这两者在某些情况下的离线计算时间都过长了。如果你的游戏中含有多名一起活动的NPC那就不可以使用这两种模型了。

除此之外，针对更宏大并且需要建设高度的3D关卡，我也不建议使用Navgrid。在这种情况下使用Navgrid会增加关联性，导致路径计算更为复杂，从而产生明显的运行问题。

现实中的路径点：焦点

现实中的路径点是否存在相似之物呢？要知道路径点，或者任何形成导航地图的多边形都是NPC在关卡内移动的必需要素。也许你从来没有想过人类和动物在现实中移动都有相似的 参照。真正的人类，会根据自己的需求在一条路上采用数量有点的“战略性”位置。

请注意真正的路径。例如，一栋建筑内的路径。你知道没有任何人能够真达自己的目标，除非他身处一个户外区域。他需要更改方向。你是否认为我们能够找到重制真正的人类必 须更改方向的位置这一规则呢？

其目标仅考虑人类通常需要更改方向的关键点。这些点可能与走廊相近，介于两个相邻柱子之间，或者靠近一个门柱。

微场景

如果你看一眼某个场景，尤其是人造的场景，你就会看到走廊窄于该场景相邻环节（见图1）。两个墙体形成一个走廊从而创造了一个微场景，门柱是一个狭小的微场景，靠近另一 个柱子或墙体的柱子也形成了一个微场景。

我们有不同的Mental Map创造方法来区分微场景。其中一个更简单（也更快）的方法可能就是场景中确定的一系列关键点所产生的线段。第一件事就是检查相关点是否处于一个对 象内部 。此时只需要考虑位于外部的相关点。

这里每X个衡量单位都会有一个点。这里的X是与NPC类型范围相兼容的值。我将这一方法称为Radar Node Generation，因为它模拟移动雷达创建其环境表现的方式。

这个解决方案会模拟我们首次踏上一条新路径，记录位置等一系列行为。在现实中，我们的大脑并不会记录下我们所经过的所有位置。另一方面，我所提议方法还会模拟我们大脑 计算混乱局面之间的空间这种原始行为（拥有眼睛的所有动物也有这个特点）。

该算法会从每个点发射两条线段：一条在左，一条在右，这两者都指向最远的点。这个方法的执行方式多种多样。例如图2。我们之后就可以查看其中是否存在与更近对象，或者该 系列追随点的碰撞。如果之前一个点没有在右侧找到更接的对象，并且找到了当前的一个点，我们就会清楚有个对象更接近这个点。

我们应该能够长度、宽度和高度上制作这个行为。但尽管如此，它还是要取决于关卡复杂度以及开发者。

焦点

什么是焦点？这种点是人类需要改变方向的战略位置。实际上，这个点是人类改变方向的最后一个有用的位置。人类事实上会很自然地更改方向，它始于焦点之前。

焦点对于人类来说有另一个重要性。因为我们的大脑不能像视频一样持续记录一条路径，它只能记录一些重要的地点。Kevin Lynch曾在其著作中提到心理地图（对于某城市的心理 地图）的研究：“我们对于一座城市的认知通常不是持续性的，而是局部性，分裂式的，会混杂其他考虑因素。几乎会运用到每种感官，而该图像却是与所有感官相反的。”

他在对于城市心理表征的研究中提到，心理地图应该包含以下类型的数据：

*路径：街道，人行道，轨道以及其他人们会行走的通道。

*边缘，例如墙体、建筑和海岸线等边界物。

*地区，由一些标志或特点所区分出的较大城市部分。

*节点、焦点和交叉点。

*地标，可以作为外部参照点的可辨识性物体。

一个极为可靠的模拟物应该考虑到Lynch所提到的所有数据。当然，这样就会创造出无法在任何游戏中执行的庞大算法。一个好方法就是针对模拟人类和动物采用最重要的标识。

我们应该将焦点布置在微场景中的哪个地方？我们应该将其布置于微场景的每个入口。这些位置是一条真正路径的节点，也将成为我们心理地图的节点。每个微场景必须拥有一两 个入口。准确的位置应该是介于创造了微场景的物体之间的中心点。

我们有不同焦点定义的关卡。例如，像图1左半部分，就仅针对每个内部物体的单个维度定义焦点。或者像图1右半部分那样，同时针对宽度和长度定义焦点。而开发了高度的关卡 还需要通过查看高度来找到焦点。

前提

根据我在执行BPF方面的一点经验，这里必须定在一些前提条件，即你要很好地执行这个模型所需用到的规则。鉴于文章篇幅所限，我无法在些描述我所搜集到的所有前提条件。以 下仅简述我认为比较重要的前提条件：

1.入口

我们在每个微场景中可以有1至2个入口。

2.可视性

微场景的焦点在其局限或者内部中形成并且可以彼此相见。例如，由两个大物体组成的走廊，置至一个更广阔场地的中间，从而创造了两个焦点，每个都位于走廊起点或终点。而 在微场景焦点无法彼此相见的地方，我们应该添加一个或更多新焦点。这样每个焦点至少都可以看到另一个焦点。

3.两者合一

如果微场景很小，涉及一个中间NPC（例如介于两根柱子之间）的垂直或纵向维度，而不是创造两个焦点时，算法就只会创造一个焦点。最终两个被删除的焦点中间区域就会产生一 个焦点。例如，看看图1中的两个门柱，你就可以看到这种前提的结果。

4.静态物体的半径距离

要考虑关卡中静态物体和表面局限性之间由用户定义的半径距离。这有助于避免产生与静态物体碰撞的焦点之间产生的线段。

5.追随最后一个可视的焦点

焦点只是人类和动物在路径上需要更改方向时所考虑区域的一部分。但是，在路径上行进的过程中，BPF不会让代理走向路径上的下一个焦点，而是其所能“看到”的“最后一个焦 点”。这是一个进一步提升代理可信度的创新，也是真正的人类替换成代理时所出现的行为。

看看上图。位于建筑左部的绿色圆圈就是NPC出现的位置，而橙色圆圈则是它的目标。更粗的绿线是NPC所会使用的路径，而较细的紫色线段则是被选择的路径。紫色线段标识着可行的变化，只有能够跳跃的NPC能够看到它们。

正如你所见，NPC会考虑的第二个焦点并非所选择路径上的第二个，而是第三个焦点。NPC会使用的第三个焦点则是其所选择路径上的第五个。这是因为之前所提到的规则。在这个规则中，运行时间会要求NPC不可因为跟随所选择路径上的焦点而浪费时间。NPC会使用所选择路径，而NPC在当前焦点只能看到“最远但仍具可视性”的焦点。

这个例子的结果就在于，NPC将使用的焦点只会有两个而不是五个，这就是心理地图所能提供的焦点。这类解决方案不只是创造更少的路径节点，甚至还会提升人类行为模拟度。

想象一下在身处于NPC相同的情境中真正人类的行为。抛弃所有的路径和节点，想象他在这种情况下是何表现。如果他决定跟随我们的NPC会用到的路径，他当然就会直走，直到碰到建筑中的障碍为止。之后他会开始转向并再次直走，直到建筑又出现障碍，或者到达他的目标为止。

创新游戏的寻径模式应该是怎样的？

回到关于这个话题的普遍讨论，我们可以说创新游戏在不久的将来将拥有更多功能和更好的性能。此外，我们还应该在无需向（并不提供这些功能的）AI模型叠加过多复杂性的前 提下实现这些表现性能。

详细来说，创新型的寻径模型应该提供：

*更快速的单个图表离线计算*；

*赋予NPC使用多类路径的能力，例如允许NPC在路径上行走和奔跑，甚至是跳跃、攀爬、游泳等；

*根据每种NPC种类的生理特征，赋予不同NPC选择不同路径的能力；

*更快速的“可信最佳路径”运行时间计算”**；

*在不添加复杂性的前提下解决路径上的动态物体问题；

*找到同种NPC的多个目标（例如，掩体和笨重的物体）***；

*当墙体和大型物体更改其位置时动态调整图表；

*总是考虑到每个NPC的心理地图可能与实际地图并不相同****。

(*)相对于运行时间计算来说，这并非一个强制要求。

(**) 正如心理学所示，我们无法:1)像手上拿着地图那样清楚地记住地图，尤其是在该区域已有一段时间并不“呈现”在NPC面前的时候；2）要避免那种情绪以及快速作出混乱推 理的需求，之后确定的路径通常不会是逻辑所提议的选择。

(***) 我想“明智”的游戏会采用自然的NPC人类，以便更好的使用下一代寻径解决方案和创新型决策制定系统的新功能。

(****) 心理学显示人类还可能忘记部分已经用过的路径，或者忘记焦点的准确序列。

可信的路径选择

区域最佳路径选择

BPF与典型的“仅靠逻辑”式的方式截然不同，它不使用当前用于寻找更短路径的算法时会更管用。这里就没有必要追究细节方面的问题了。但是也有一些因素可以让过滤器在无需 借助其他算法的情况下选择单个路径。例如，情感权重，心理地图错误，NPC种类的特点，或者关卡的数量，通常有助于挑选出唯一的理想路径。

例如，一个广阔的关卡可能使用10个区域。通常情况下，每个区域都有4个其他与之相连接的区域（除非关卡还要开发高度）。除非该关卡是一系列区域，或者关卡极其庞大，否则一般目标与NPC之间的距离不会超过2个区域。通常情况下，我们没有必要采用任何关于区域关卡的最佳路径算法。

这里有一个可重制人类行为，用于限制路径数量的简单而有效的解决方案。其目标是避开所有首个区域距离NPC及其目标之间的直线过远的路径（假设NPC知道地图）。之后你还要移除至少包括一个用于“避免”NPC类型的区域的路径。

例如，在以下情况中，决策制定系统或者在设计过程中的开发者应该将该区域标注为“避开”类型：

*如果该区域充斥大量可能杀死NPV的危险怪物。

*如果该区域充满不可行，或者不适用于该NPC类型的微场景。

*如果该路径包括更黑暗的区域，以及NPC的个人特点将其视为没有胆量进入的区域。

另一个过滤器就是每个路径的“长度感”。这个过滤器应该难以执行，但却真的很管用。它是我们大脑中最常用的过滤器之一。人类和最高智能的动物会考虑一条路径的长度感。 生物体的长度感是由多个因素决定的。其中之一就是过去的旅程所发生的情绪（那种感觉越好，其想象的长度就越短）。

另一个就是路径多为直线或曲折的这一现实。如果你想使用这个符合某些心理研究的过滤器，你甚至可以为任何焦点创造一两个标注。你还可以创造其他过滤器，但我它是相对于 路径类型来说最重要的一者。这个标注的职责就是存储始于该焦点的微场景的类型。

从本文的图片中可以看到，一个焦点可能仅靠近一个微场景（图1），或者介于两个微场景中间（图4）。未被选中的标注意味着该迷你场景是直线的，而有被选中的标注则意味着 它是曲折的。该路径上被选中的标注数量越多，NPC使用该路径的可能性就越小。

（图4：焦点及其两个标注指示两个相邻微场景的类型）

更进一步的过滤器就是NPC对于这些区域的认知。这是另一个精心设计的人类模拟方法所要考虑的重要功能。BPF可以随机创造区域地图的情况，制作每个NPC或物种。如果是长寿的 NPC，你就应该记录每个NPC所行走过的地点。

通常情况下会产生1至2条路径，最多只有3条。如果有多条路径时应该使用哪个路径呢？最应该选择的是包含NPC走向目标时穿过最多次区域的路径。但这个解决方案会被每条路径 所包括的区域数量所抵消。

过滤器应考虑以下方面：

*只能选择首个区域离NPC及其目标之间的直线不会过远的区域路径。

*只能选择不含“避开”区域的路径。

*考虑路径的长度感。

*只能选择含有已知区域的路径。

如果这一筛选结果产生了一条以上的区域路径：

*那就选择拥有区域数量较少/或者NPC及其目标之间的直线被穿行过更多次的区域的路径。

内部可信的路径选择

在确定要跟随哪条区域路径后，NPC就得开始解决在当前区域内部的寻径问题。之后，在进入下一个区域时，再重复一遍这种做法。将关卡划分为多个区域（方块）通常会产生多个 可行（或者更管用）的表面连接两个区域的情况。这意味着NPC在特定区域路径上进入下一个区域可能有多个解决方法。

将路径划分为两个关卡可以加快可信路径选择的运行时间，并迫使你将寻径划分为多个步骤。尽管如此，要正确使用这一方法，你还是需要应对一些新问题。

如果两个区域之间有走廊，那就有两个关于路径设计时间阐述方面的问题：“死亡路径”以及区域走廊的连接性。事实上，如果某个连接了两个相邻区域的可行路径深入了无法穿 过下一站的区域，那么NPC之前就该知道这个问题了。

为了修复这个问题，我们在设计时间应该为每个区域选择从一个相邻区域进入另一个区域的路径。这可能会是一项很耗时间的计算，尤其是相邻区域之间的走廊数量极多的时候。 此时可以人为更改区域，以免两个区域之间存在太多联系。

无论如何，其算法应该遵从以下原则：

A-选择区域

A1-选择某一边至少有一个通向相邻区域的区域。

A11-针对每个走廊检查它是否存在可通向另一个相邻区域的路径。如果有，将该走廊标注为可同另一区域兼容的走廊。

这里没有必要计算每条路径的长度了。

BPF的运行时间环节将使用与通向下个区域相关的可行走廊的数据，以便检查该选择哪条走廊走向下个区域。

如果这里存在1条以上通下向个区域的走廊，就要由NPC来决定要走哪条路。你可以使用区域关卡寻径所采用的同种过滤器来选择。我建议考虑长度感以及相对于走向目标的直线走 廊距离来选择。

要开始内部路径运行时间选择，你必须知道内部路径以及通向下个区域的走廊的早期环节。前者是NPC进入区域的所在地，或者NPC所在位置。当你两者兼具时，你应该选择该路径 走向下条路径寻找目标。即使如此，你也要使用之前所提到的过滤器。但你可以决定要使用哪一种还是全部使用。

注意，如果你的项目是策略型战争游戏那就不可以用这种NPC思维方式。策略型战争游戏是每个NPC已经清楚路径的少数游戏类型。在这种情况下，比较好的解决方法仍然是仅靠逻 辑的方法。你应该添加的唯一过滤器就是目前NPC的情感觉醒水平（游戏邦注：相当于音乐的音量）。但这并非直接由PF系统所管理的问题。

尽管如此，你还是很容易注意到生物寻径方法远比目前使用的寻径方法速度更快。我之所以如此确定是因为BPF的执行方式更轻便。

总结

生物寻径方法是一种不但对人类、僵尸、怪物和外星模拟物，甚至是智能动物都很有创新性的解决方法。

尽管如此，我们还是不可低估寻径问题之下的情感因素。即使是决策的能力，也不是一种仅靠逻辑就可制定的功能。Plutchik称情感是一切有机体在追求个体生存时所需要的基本 适应性。他认为6亿年前的寒武纪中发生的自然选择很大程度上与情感有关。这8种适应性是结合、拒绝、毁灭、保护、繁殖、机体重组、定向和探索。

这意味着，多种动物都具有心理导航的最重要过滤器。

所以，人类解决寻径问题的方式与动物有何不同？其区别相当之小，主要与逻辑的使用相关。这也并不完全正确。但其中深刻原因我无法在此详述，也难以用代码重现。

多数动物无法通过训练更好地驾驭自己的情感，也无法考虑1个以上的过滤器选择。如果你想区分人与动物在寻径选择方面的行为（或者不同智能的动物行为），只要使用针对最简 单动物的一个过滤器即可。之后，当你遇到人类（或者更高智能动物）时再运用其他过滤器。

你应该时时使用的唯一过滤器就是关于首个焦点指向目标方向的路径选择。

关于本文最后一个考虑就是：两个（或多个）层次的寻径方法要求你采用允许NPC具有更多目标层次的决策制定系统。这是你选择BPF时需要牢记在心的另一个重要问题。

避开动态物体

今天，有些游戏开发者发现某物体与NPC当前路径相关叉时，就会迫使自己的AI执行方法重新计算最佳路径。所幸并非所有开发者都会采用这一做法。这一操作行为的结果，从NPC 的可信度和表现性能来看，无疑是消极的。

寻径过程中的动态物体是一个陌生的问题，但在我看来根本就不是个问题。我们应该首先将这个问题划分成两种情况：

1.一个物体正向NPC当前路径移动。

2.一个物体在移动并且被置于NPC的当前路径。

应该采用不同方法对应这两种情况。事实上，如果某物体是移动的，我们就得担心NPC与该物体发生碰撞的可能性。尽管一个可能发生的碰撞永远不能导致我们更改路径，除非同个 地点有大量移动物体。如果这种情况发生了，你应该检查自己的游戏和模拟设置。事实上，如果某个地点含有大量移动物体，就应该在图表上标出它拥有更高的权重。

当某物体（或者另一NPC）向NPC目前正在使用的路径移动时，唯一的解决方法就是避开它。但这不可改变已经决定好的路径设置。而针对某物体正在移动过程中被置于NPC当前路径这种情况下，除非该物体大到足够阻挡整个走廊，否则你就要用物体躲避算法来解决问题了。

BPF的合理物体躲避算法应该是怎样的？这里没有什么可考虑的参考或者防范措施。你只能在避开物体时使用该算法。当NPC避开物体时，该算法就必须中止了。之后寻径系统将会 再次激活，该NPC会继续走向其下个焦点。

如果物体过于宽大挡住了去路，无法掉头了又该如何？我们是否需要另寻出路？我完全赞同避开这个解决方法。人类在遇到真正的问题时，并不会受逻辑所主宰。尽管这很难理解 ，但还是得承认情绪会操纵我们的行动。只有筛除了带有情绪的事件后，我们才可能思考和使用逻辑。

如果是人类，开始走上一条路径时，如果发现有问题就会试着想象（而非计算）这里还存在一条有助于扭转局面的分支路线，以便自己继续走完同条路径。在人类走完这条路的时 间有限的情况下，考虑改变路径实现在太复杂了。只有发生危险才能改变这个方法，但它却与寻径系统没有直接关系。

所以，即便是在最糟糕的情况下，也没有必要开始从当前位置到目标的寻径计算。合理的人类模拟的正确解决方法是找到从当前位置到超越该物体的首个焦点的“最简单”次级路 径，或者使用避开物体算法。

在人类的寻径问题解决方法中永远不存在计算，只有估算。估算会考虑到转折次数和焦点数量：在我们看来路径上不存在（像视频一样）的持续记录，只会有关于焦点的一些片断 。因此，如果人类看到一张地图，他会更好地估计每条路径的长度。

任何焦点都会接近于一个微场景。这对我们有帮助，因为它让我们知道一个物体不可能占据一个以上的微场景（除非是一个巨大的物体）！

平顺移动

尤其是在复杂或开阔路径中，我认为网格和网眼导航并不会因为地图上的节点数而给予NPC足够的可信度。一条路径上实际上有4个数量等级的节点：

1.节点太少，或者置于无意义的位置上：NPC不可能像人类一样行走，因此它会产生不可预测的结果。

2.“焦点”上布置少量节点：NPC会像人类一样作出反应（目前仅有生物寻径法能够做到）。

3.许多节点：NPC行业与人类大相庭径。没有良好的（有时候浪费时间）平顺算法，NPC会产生类似于醉汉的行为（当前的导航解决方案就可能出现这种问题）。

4.太多节点（数十倍乃至数百倍于焦点数量）：NPC行为会同人类有所相似。但离线和运行时间计算非常棘手（NavGrid方法会产生这个问题）。

请看以下例子。

你可以由此看到由Navigation Grid做成的凸面多边形数量，下图则是由Mental Navigation所做的相同地图，Navigation使用了BPF方法。你可以看到Navigation Map所能创造的节 点数量和相对线段比当前导航方法所能创造的更多。

当前导航方法的另一个问题在于它们几乎任何线段都要使用到平顺算法。对于可以开发高数量节点的方法，这只会恶化其表现效果。

Mental Navigation焦点之间的任何走廊也需要平顺算法。尽管如此，相比当前寻径方法的整体执行时间而言，它的成本已经最小化了，因为其焦点数量较少。

这里有必要再次提起BPF的另一个前提条件：如果非相邻微场景的两个节点之间存在一个静态物体或深谷，NPC将会使用躲避物体算法在这些焦点之间移动。

这个规则甚至可以被另一个方法所取代，即移动一个甚至两个焦点的方法而不是使用避开物体算法来克服这个问题。

心理地图

心理地图是一个考虑到人类（和动物）如何在大脑中建立导航地图的方法。在之前的文章中我已经提到了这个模块最重要的部分。尽管如此，我们还是要重申一下你在执行BPF之前应该考虑的一些因素。

正如我一再强调，人类智能并不只有逻辑。决定智能的因素还包含其他比逻辑更重要的因素。正如一些生物和神经学发现的证据所示，智能并非人类的专利。

所有的灵长目动物都有高智能。例如黑猩猩可能会使用250个文字的语言。而海豚和狗等其他动物则有中度智能。但在所有这些物种之中，它们的智能基础几乎都是相同的。但人类开发出了大量动物无法拥有的“心理适应性”。

我想说的是逻辑仅是生物智能的尖端，但它并非一种独特的元素。情感和其他数种因素是智能的最基本构成元素，如果没有这些因素我们无法理解周围的世界。

这种推理的结果是什么？两个事实：A）人类的某种或多种情绪过高或过低时，就会产生非逻辑的行为；B）动物在寻径方法上，当遇到路径选择或避开一个物体时几乎也会采用相同的做法。

目前我们还没有能够代表整个世界智能的完整模型。我是指在整个智能世界中，包括情绪、心情、感情、信仰和个性特征，更别提年龄差异、社会规则和激素的模型。这不难推测 出，BPF的执行目前还难以发挥其最佳功效。

总结

那么，我们已经能够处理寻径过程中的情绪问题，以便更好地模拟人类行为？也许还没有那么快，但已经有一些人正尝试创建可靠的AI模型。我认为推出一个以更高可信度模拟人 类和动物行为的解决方案不久就会来临。

不论如何，你甚至可以创建一个并不用到情绪的BPF执行方法。

关于生物寻径的话题目前仍局限于研究领域，虽然你已经从这些文章发现了一些成功执行的基础。我希望能够推出一个关于BPF的开源项目，加快这种新方法的研发速度。(本文由游戏邦编译，转载请注明来源，或咨询微信zhengjintiao )

path finding ai artificial intelligence navigation meshes navigation grid mental navigation intelligent agent dynamic avoidance biological path finding psychology

This is the first of three articles that treat a new approach for the Path Finding. It’s a part of the studies and experience I made in the last years, in the fields of the Artificial Intelligence for Games, Philosophy and Evolutionary Psychology.

The current panorama of the Path Finding

All the Artificial Intelligence modules for Videogames are made by using models thought several years ago. Some of those models are rather old, taking into consideration the fast growing of the other software modules of videogames.

For example, even I didn’t found any source that specifies when the Navigation Mesh (or Navmesh) has been implemented for the first time, I can state that this model is used at least from the 2004 (and then 10 years ago). It is, together with the Navigation Grid, the most used and, practically, the most advanced approach to obtain the graph for making paths for videogames.

Nonetheless, the Waypoint Navigation is still used in a multitude of simple games, and is even older than the Navmesh. If we compare the improvements in the AI modules with the ones of Graphic modules (I mean the ones that render the game), we could see that, referring to when the waypoint navigation has been used for the first times, the graphics were at level of the CGA technology. The evolution made by the Graphic module, in these years, is enormous.

Ok, you could say that computer graphics has been largely helped by the evolution of the hardware. The problem, though, remains: in the last 10 years, if we avoid to mention the OCC model (relative to the psychological approach to the intelligent agents) and some other agent-based approach that, by the way, are still practically unused in videogames, we can’t say to have witnessed something that could be defined as really new, or a strong, sharable improvement.

The reason? Mainly because, despite the advent of the cognitive science, the approach to the artificial intelligence topic by the insiders is never changed in decades. How the path finding of the videogames of the future will be? Is it possible that it will have modules made on models that we have from decades?

Personally, I reckon that the videogames of the future will be far different from the currents. The problem for developers is not how they will be, but how to build AI models able to support new features. I had a different approach, respect to the classic one, about the “intelligence” topic. I started from the consciousness that we humans are not a species fallen from the sky, completely different from all the other species of Nature on Earth. This brought me to know the Evolutionary Psychology, from which I profitably tapped several theories that, I’m sure, will help AI to develop the first, real, virtual living being.

A topic question: what is intelligence?

What is Intelligence, speaking about what is important for videogames? Intelligence is not more than a tool to improve the human ability to manage the environment. It’s the more powerful tool ever made by natural selection on Earth, but still a tool like the elephant tusks, or the opposable thumbs we share with the other primates. The Evolutionary Psychology calls them Evolutionary Adaptations. There are a lot of studies and findings, in Neurosciences and Psychology that state the fact that emotions take part of the human (and animal) intelligence, and without them the sole logic is useless.

This way to think at intelligence changes dramatically the approach to any problem you find in videogames, and with any other human or animal simulation. For instance, my approach to the path finding issue takes into consideration the fact that humans (and animals) have their own way to memorize maps in mind. The result of this memorization often doesn’t correspond to the actual map, more often than we would admit.

Even the approach to the navigation for building the graph is completely different. In my opinion, it should take into consideration how we move toward a physical target. This approach carries several new features and performance improvements, in respect to the ones currently adopted.

I try in few words to explain some of the main thoughts that are at the base of this new approach. First of all, I need to title the parts in which I divide the news.

Navigation

Graph Population

Best Path Identification

Dynamic Objects Avoiding

Smoothing Movements

Mental Map

First Topic – Navigation for innovative games

Please think about a game like “I am alive”, “Spiderman”, “Tomb Rider”, “Prince of Persia”, “Assassin’s creed” or one of a lot of others where the player’s character is able to climb, jump and make other unusual actions. In almost all the titles of this genre, there are some unnatural behaviours done by NPCs. One of the most evident is when NPCs want to catch/kill the player and, in order to do that, “decide” not to climb and follow the PC. They only expect the player to finish his climbing actions in order to attack him, or try to shoot him from the walkable area when it’s climbing.

This is not a logical and biological behaviour, because unless all the NPCs know the buildings around them like their shoes, they can’t be sure that the PC could flee from their hands. In order to reproduce a correct human behaviour, NPCs, for example, should use the simple tactic of the pincer: some of them follows the thief/enemy/PC by climbing behind him, while the others try to run and block his way out. How to do that, though, if the Path Finding Navigation
system can’t use walls as “usable areas”? Videogame programmers rarely make their NPCs able to climb and follow the climbing player. This is because, in order to do that, they should customize the path finding module, making it more complex and often not usable for other videogames in which the player only has to walk and run.

A new approach, that I baptized “Biological Path Finding” (BPF), resolve the problem at its root. There should be focal points (automatically generated) only in the places where two micro-environments meet. This brings to have a focal point even where the way to proceed changes because the different micro- environment is vertical, that is a wall or some other “climbable” surface. Each line that comes from a node will acquire a weight (talking with an A* approach) that will be calculated in base of the ability of each “kind of NPC” to traverse it, by climbing, swimming, walking etc. This solution involves a more general management of NPCs, whom should be categorized in Species.

The good news is that, with this approach, you can have a different best path for each Species of NPC, while each NPC is able to move along the level based on its own ability. The better performance in elaborating the paths thanks to a lower amount of nodes, respect to the current approaches, mitigate the fact that the path elaboration, with this approach, will be done for each species. Unless the game uses dozens of different species (I never found a game like that!), the total amount of time for elaborating the paths off-line should be not higher than the ones of the current approaches, but giving us more features and wider solutions to adopt in videogames.

Yes, it’s something more complicated than a mere, simple path navigation system (do and use), like most of the current videogames have. Nonetheless, videogames are already evolved from the first ones like Invaders or Pacman, and we can surely say that all the main titles in genres like RPG, MMORPG, Shooters and Strategy are very complex per se, so that the cost for having new features for NPCs could be paid without too much regret.The need to ease the run-time elaborationIn the last years, more and more videogames contain larger levels. It’s obvious that the larger the level, the harder is remaining into acceptable performance when NPCs calculate their paths to catch the target and the number of NPCs is higher.

I know that several videogame developers recognize that problem as one of the most time-consuming during the development. The fact is that we continue tothink too logically to the issues that involve human simulations. If we think, instead, to have a person in place of each NPC, we should then linger on to the way with which humans think about the path finding, speaking from the point of view of the Psychology.

I don’t want to write down here a book again (I already made it, and in the next month will be published), so I need to condensate some thoughts in a shorter version. When a human tries to think about a larger zone and how to reach his destination, he usually has some mental images about the most important, for him, parts of the environment (blocks of a city, for example), and then think about each zone as a black box. This approach helps a lot, even with our path finding issue, because it avoids calculating the path at the highest detail. One of the studies in Psychology that better analyse the issues related to paths traveled by humans has been done by Lynch (1960).

The double dimension for path finding has been already used in some games. The fact is that in the Biological Path Finding it fits the overall approach, being one of the tools that derive directly from a psychological study of the human behaviour.

What this approach brings is the fact that you save time in making only the calculation that you really need. In fact, are you sure that the NPC will travel all the path? How high is the possibility that the NPC will be killed along the path, or will find a good reason to find a new path again or, in any case, do something different? In these cases, the calculation of the overall path in a large level has been made in vain. The approach of breaking large calculations into several, smaller ones made “along the road” by NPCs should be used widely, because it’s a good way to enhance the performance. In any case, this lets the NPC be more “human” without making heavy the overall performance.

Then, the BPF takes use of two dimensions of Path Finding: the District and the Zone Path Finding. The District Path Finding is the one I explained in the previous paragraphs, the other is the one that resolve the need to walk along a short path, in order to catch a closer target or exit from the district (if necessary) from the side required by the selection of the “correct” (not the best!) macro-path found by the District Path Finding.

Even at that level, the approach is completely different from the usual. It tries to minimize the amount of micro-paths that has to be kept into consideration. Humans, in fact, take a decision about the path to use, in order to move toward a closer target, by looking at the target (or in direction of it) and check only the paths that have their first focal point not distant, in terms of angular degrees, respect to the direct direction toward the target.

This way to select the path has been already addressed by other researchers, for example by Douglas Jon Demyen (2007) in his thesis.

Conclusion

In my next articles, I’ll continue to talk about a Biological Path Finding approach, and more precisely talking about the other five topics already named in this article.

path finding ai artificial intelligence navigation meshes navigation grid waypoint navigationm mental navigation intelligent agent dynamic object avoidance biological path finding psychology

In the previous article, I mentioned a new approach you should consider if you want to build next-gen, innovative games, called Biological Path Finding (BPF). I always thought that the most used models are not a bible, to use without thinking about, and that doubts are often the factor that brings our mind to create better AI models.

Please note that you need to read the previous article of this topic (relative to the Navigation), before reading this one.

Graph Creation

NavGrid or the NavMesh models are enough and good, without any customization, in several circumstances. If you want to build a single video game a time, for a video game similar to others, they can be perfect for you. If you have few NPCs living together, and you don’t mind that they sometimes (or often) do what humans never do when walking, there is no reason why you should find for something better.

Conversely, the future of video games will not use NPCs with a less-than-good human behaviour. Newer models should provide new features without the need to customize, to have better performance.

The current Navgrid and Navmesh models have good pros, but even stronger cons. Both could make, in several circumstances, long time for the off-line calculations. You should not use them when there are several NPCs living together in a wider level. If you want your game go fast, or if the correctness of the human behaviour is a must, you shall find something new and different.

Besides, it’s not recommended the use of Navgrid for wider 3D levels, whom also develop in height. The use of the Navgrid in that context raises connections a lot, letting the path calculation be even more complex, with obvious performance issues.

Waypoints in the reality: the focal points

Can waypoints have a counterpart in the reality? You know that waypoints, or any kind of polygons that form a navigation map, are fundamental for NPCs to move across levels. Probably you never thought that also humans and animals need to have similar references when they move in the reality. A real human, with his needs, have to have a limited number of “strategic” positions along a path.

Please put your attention to a real path. For instance, a path inside a building. You know that no living being can go straight to its target, unless it is in an open space. It has the need to change direction. Do you think we can find a rule with which reproduce the positions in which a real living being should necessarily change its direction?

The goal is considering only points where a human need usually to change his direction. These points can be next to a corridor, between two neighboring columns, a doorpost and so on.

Micro-environments

If you take a look at an environment, especially a human-made one, you can see there are some parts where the passage is narrower respect to the contiguous parts of the environment (see the figure 1). Two walls forming a corridor make a micro-environment; a doorpost is a thin micro-environment; a column close to a wall or to another column forms a micro-environment.

There can be different ways to build the Mental Map and, then, identify micro-enviroments. One of the easier (and the faster, in case you have one or more wider zones in the level) is possible thanks to the launch of linecasts from a series of points defined in the environment. The first thing to do is checking whether the reference point is inside an object or not. Only the reference point outside objects will be considered.

There will be a point each X units of measure. The X is a value compatible with the width of the species of NPCs. I named this approach Radar Node Generation, because it emulates the way with which a moving radar builds up its representation of the environment.

This solution simulates the behaviour of our mind when, the first time we walk a new path, records positions, clutters and so on. In the reality, our mind don’t record all the positions in which we have been (as stated by Lynch). On the other hand, the approach I have proposed emulates, also, the ancient behaviour of our mind (shared with all living beings whom owns eyes) whom calculates the spaces between clutters.

The algorithm will launch two linecasts from each single point: one to its left and one to its right, both toward the farthest point. The implementation of this approach can vary. Anyway, see the figure 2 for an example. We then need to check whether there is a collision with a closer object respect to the previous or the following point along the series. If, for example, the previous point hasn’t found any closer object on the right of it, and the current point has found one, we could clearly state there is (from this point on) an object closer to the point.

We should/could made this action in length, width and height. Nevertheless it depends on the level complexity, and is up to the developer. There are several tips that makes the action performance-compliant, but it’s not the place in which to talk about it.

Figure 1

Figure 2

Focal Points

What are Focal Points? These kinds of points are the strategic position in which living beings need to change direction. In reality, that point is the last useful position for them to change their direction. Living beings, in fact, change direction smoothly, starting a bit before the focal point.

Focal point have another great importance for living beings. As our mind can’t record in memory a path with something similar to a video, something continuous, it records only the important places. I prefer to mention what Kevin Lynch said in his prominent contribution and study of mental maps (referred to the mental map of a city): “Most often our perception (of the city) is not sustained, but rather partial, fragmentary, mixed with other concerns. Nearly
every sense is in operation, and the image is the composite of them all.” (Lynch, 1960, p 2.).

Always referring to his studies of the city mental representation, he said that mental maps should contain the following types of data:

paths: the streets, sidewalks, trails, and other channels in which people travel;

edges, perceived boundaries such as walls, buildings, and shorelines;

districts, relatively large sections of the city distinguished by some identity or character;
nodes, focal points, intersections;

landmarks, readily identifiable objects which serve as external reference points.

A strictly reliable simulation should consider all the data mentioned by Lynch. Anyway, this would build a huge algorithm that no one will implemented in any game. A good approach, then, is taking all the most important notice for a human and animal simulation.

Where we need to put the Focal Points respect to the micro-environment? We should position them one for each entrance of the micro-environment. Those positions are the nodes of a real path, and will be the nodes of our Mental Map. Each micro-environment must have one or two entrances. The exact position will be the central point between the objects creating the micro-environment.We can have different levels of Focal Point identification. For instance, one that identifies focal points only for a single dimension for each inner object, like in the Figure 1 in the left part. Or, like in the Figure 1 in the right part, one that identifies FP for both the width and length dimension. A level that develops even in height should also find FP by checking with the height dimension.

Postulates

My (little) experience in implementing the BPF leads me to say there must be some postulations, some rules that you should use to make a great implementation of this model. I can’t describe all the postulations I’ve collected, because of the reduced space of an article. The ones I don’t describe, anyway, are not too much. Their importance, also, is less than the ones of the postulations I’m going to describe.

1- Entrances

We can have one or two entrances for a micro-environment.

2- Visibility

A micro-environment is such if the focal points created at its limit or inside it see one each other. For example, a corridor formed by two big objects, placed in the middle of a wider place, leads the design-time elaboration create two focal points, each at the beginning (or ending) of the corridor. Where the focal points of the micro-environment can’t see one each other (in case of a rounded corridor, for instance), we should add one or more new focal points
along the micro-environment. In this way, each focal point can see at least one other focal point.

3- Two become One

If the micro-environment is small, speaking about one dimension (horizontal or vertical) referred to the size of a medium NPC (for instance, between two columns), instead of creating two focal points, the algorithm will create only one. This resultant focal point will take place in the middle of the space between the deleted focal points. For instance, look at the two doorposts in the Figure 1, where you can see the result of this postulation.

4- Radius Distance toward static objects

Consider a user-defined radius distance between the static object of the level and the limit of the surface. This could help in avoiding to have lines between focal points that collides with static objects.

5- Follow the last visible Focal Point

Focal points are the only parts of any zone that humans and animals consider, in a path, when they need to change direction. However, during the movement along the path, the BPF (Biological Path Finding) states the agent will go not toward the next focal point, but toward the “last focal point”, along the path, the agent can “see”. This is an innovation that improve further the agent’s credibility, and this is what really humans do when are in place of agents.

Figure 3

Look at the previous image. The Green Circle, located in the left part of the building, is the position where the NPC takes place, while the Orange Circle is its target. The wider green line is the path the NPC will use thanks to the BPF, while the thin violet line is the selected path. The Violet Circles, instead, sign the change of viability, and only the NPCs able to jump (at a defined height) will see them.

As you can see, the second focal point the NPC will take into consideration is not the second in the selected path, but the third. The third the NPC will use is the fifth of the selected path. This is because of the previously mentioned rule. With it, the run-time approach states the NPC will not lose time by following each focal point of the chosen path. Contrarily, the NPC will use, of the chosen path, only the “farthest, still visible” focal points the NPC can see from the current focal point.

The result for the example is that the number of focal points the NPC will use is only two, instead of five, as provided by the path of the mental map. A solution like that will not only produce, most likely, the lesser number of path nodes ever, but even will improve the human behaviour simulation.

Consider a real person in the same context of the NPC of the linked image (the building is a church). Throw away all the paths and focal points, and imagine how he behaves in that context. If he decides to follow the path that our NPC will use, he certainly goes straightforward, until the encumbrances of the buildings will allow him. Then, he will start to turn (a bit in advance respect to the focal point) to go another time straight until the building will allow him, or until he reaches his target.

Please note that here there has been an almost completed discussion about the Mental Map of the BPF. Nonetheless, in the last article I prefer to talk again about that part, because its better implementation should consider some other factors.

How a Path Finding model for innovative games should be?

Coming back to the general discussion of this topic, we can say the generation games and, especially, the innovative games, in the early future will have the need to have more features and better performance. Also, we will have the need to reach those performance without putting complexity over complexity on an AI model that does not already provide those features.

In detail, an innovative path finding model should provide:A faster off-line calculation of the single graph, respect to the current ones*.

Ability to use multi-genre paths for NPCs, by letting NPCs use not only walk and run along the path, but even jump, climb, swim etc.Ability to have different good paths for different species of NPC, according with the physical characteristics of each NPC specie run-time calculation of the “believable best path”**

Resolve the problem of the dynamic objects along the paths with no added complexity

Find multiple targets even of the same species (for example, shelters and bulky objects)***

Change the graph dynamically when walls and big objects change their positions

Take always into consideration that the mental map of each NPC can be different from the actual map****

(*) This is not a mandatory need, respect to the one of the run-time calculations.

(**) As the Psychology states (Lynch, 1960, )(Tversky, 1993) we can’t: 1) Remember a map as if he owns the map physically on his hands, especially if the zone is not “lived” by the NPC for a while. 2) Avoid that emotions and the need to decide fast confuse reasoning, and then the decided path can often be not the one the logic would propose.

(***) It’s time, I reckon, that ‘smart’ games will adopt the natural subdivision among NPCs, in order to better use the new features of the next-gen path finding solutions and innovative decision-making systems.

(****) Psychology states that humans can also forgot parts of an already-used path, or make mistakes in remembering the exact sequence of the focal points (Moar, Bower, 1983)(Sadalla, Montello, 1989)(Hirtle, Mascolo, 1992)(Byrne, 1979)(Lloyd, Heivly, 1987)(McNamara, 1986)

Believable Path Selection

District Best Path Selection

BPF is so different respect to the classic, “only-logic” approach, that work better without any use of the current algorithms used to find the shorter path. It’s worth not going into details, for this issue. However, there are several factors for which the filters can bring to select a single path with no help of other algorithms. For example, the weight of emotions, mental map errors, the traits of NPC species or the limited number of levels, will usually bring to have only one path that overcomes all the filters.

For example, a wide level could use 10 districts (see my previous article for more details). Normally, each district could have four other districts connected to them (unless the level develops even in height). Unless the level is a sequence of districts, or the level is huge, it’s rare that the target is distant more than two districts from the NPC. Usually, then, it’s useless to adopt any calculation of the best path, about the District level (see the previous article).

There is a simple and effective solutions to limit the number of paths that reproduces the human behaviour. Its goal is avoiding all the paths whose first district is not far from the straight line between the NPC and its target (presuming the NPC knows the map, at least broadly). After that, you should also remove the paths containing at least one district checked as “to avoid” for the species type of NPC.

For instance, the decision-making system or even the developer in design-time should flag the district as “to avoid” (or even the developer in design- time):

If a district is full of dangerous monsters that can kill the NPC.

If a district is full of micro-environments non-viable, or is viable with difficulty for that NPC species.

If the path contains a darker zone, and the personal traits of the NPC (if available) depicts it as a non-courageous individual.

Another filter is the “sensation of length” of each path. Look at this filter, because it should be difficult to implement but really useful. It is one of the most used filters by our mind. Humans and the most intelligent animals should consider the sensation of length of a path (Sadalla, Staplin 1980)(Maki, 1981). There can be several factors that could take place in defining the length sensed by a biological entity. One of them is the emotions proven during the past traversals (the better the sensations proven, the smaller the perceived lenght).

Another one is the fact that the path is mostly straight or tortuous. If you want to use this filter that matches with some psychological studies (Sadalla, Staplin, 1980), you can even create one or two flags for any focal point. There are even other filters you can create, but let me say this is on of the most important among the ones relative to the typology of the path. The duty of this flag is store the type of the micro-enviroments that starts after the focal point.

As you can see in the figures of this article, a focal point can stay close to only one micro-environment (see the Figure 1), or in the middle of two micro- environments (see the Figure 4). The flag unchecked could mean that the mini-environment is straight, while the flag checked means that it is tortuous. The higher the number of checked flags along the path, the lower the likelihood that any NPC will use that path.

Figure 4

An example of a focal point and its two flags suggesting the type of the two adjoining micro-environment.

A further filter is about the NPC knowledge of the districts. This is another important feature that a well-done human simulation could consider. The BPF could create randomly the knowledge map of the district, made per NPC or per Species. In case of long-living NPCs, you should do it by recording the places travelled for each NPC.

Normally, the result should be one or two paths, maximum three of them. What is then the one to use, if there are more than one of them? The path to use will be the one containing the highest number of districts traversed by the linecast that goes from the NPC toward the target. This solution, though, should be counterbalanced by the number of districts of each path.

To recap the filters:

Only the district paths whose first district is not far from the direct line between the NPC and its target

Only paths without “to avoid” districts

Sensation of the Length of the Path

Only paths with known districts
…

If the result is more than one district path:

Take the path with the lower number of districts or/and consider the higher number of district traversed by the direct line between the NPC and its target

Inner Believable Path Selection

After having decided the district path to follow, the NPC has to start to resolve the path finding inside the current district. Then, when inside the next
districts, redo the same for that district. Dividing the level into districts (cubes) normally leads to have several cases into which more than one walkable (or better usable) surface links two districts. This means that an NPC could have more than one solution to go to the next district of the chosen district path.

Dividing the paths into two levels speeds up the run-time selection of the believable path, and forces you to split the path finding into more than one step.
Nonetheless, to use the approach correctly, there are some new issues with which you should face with.

In case of the passage between two districts, there are two things the design-time elaboration of the paths should check: the “dead paths” and the connections between passages through districts. In fact, if one of the possible paths whom connect two adjoining districts stops into the district without the possibility to pass to another one, the NPC should know previously about this issue.

To fulfil the problem, in design-time we shall select, for each district, the paths that travel the district by going from one adjoining district to another district. This could be a time-consuming calculation, especially if the number of the passages between adjoining districts is high. This could be a good reason to change manually the districts, to avoid having too many links between two districts.

Anyway, the algorithm should be the following:

A – select the district

A1 – select one side of the district where there is at least one passage to the adjoining district

A11 – For each passage, check if there is a path that conduct to another adjoining district. If so, flag the passage as compatible with the passage to that district (in the way you wish).

There is no need to calculate the length of each path, and this helps a bit.

The run-time part of the BPF will use the data relative to the possible passages to the next districts, to check which passage to select for going to the next district.

If there are more than one passages that traverse the district toward the next one, the NPC mind should decide which to use. How? You should use the same filters adopted to the district level of the path finding. Anyway, I suggest to use one or two, between the sensed length and the distance of the passage respect to the direct line toward the target.

To start the run-time selection of the inner path, you need to know the early part of the inner path and the passage to the next district. The former is where the NPC is entering the district, or where the NPC is placed. When you have both, you shall select the path to use for arriving to your next path finding goal. Even in this case, you should use the filters already discussed. It’s up to you to decide which of them, or use all.

Note, though, that this way of thinking of the NPC is not the right way if your project is a tactical war game. The tactical war game is one of the rare cases in which the paths could be already well known by each NPC “at the table”. In this case, then, a good solution remains one of the correct, only-logic approaches. The only filter you should add is the level of arousal of the emotions currently lived by the NPC (arousal is, for emotions, something similar to the volume for the music). This is, though, an issue not direct managed by the PF system.

Nonetheless, you could easily note the Biological approach should be faster than the current ones. The reasons I affirm that is because the actions executed by BPF are lightweight. In fact, in any case there is a reduced number of nodes in the graph, even thanks to the paths leveling (see the first article for more info).

Conclusion

The biological approach to a path finding, inherent the Biological Path Finding, is an innovative solution not only for humans, zombies, monsters and aliens simulation, but even for intelligent animals.

Nevertheless, never underestimate the role of emotions under the path finding issue. Even the ability to decide, like the one explained in this article, is a feature made not only by logic. As a confirmation of this statement, Plutchik said that emotions are basic adaptations needed by all organisms in the struggle for individual survival (1980, p. 145). He suggested that the selection occurred in the Cambrian era, 600 million years ago, was responsible for most of our emotions. The eight adaptations are incorporation, rejection, destruction, protection, reproduction, reintegration, orientation and exploration.

This means, also, that a wide variety of animals can share the most important filters of the Mental Navigation.

So, what differs from humans way to solve a path finding to the ones of animals? The difference is rather small, and is specifically related to the use of logic. This is not entirely true, by the way. Nonetheless, the causes of this are so deep and so difficult to reproduce in code that I prefer not to mention.

Most animals cannot use training to better govern their emotions, and they are also unable to consider more than one deduction about the filters adopted. If you want to distinguish the human behaviour to the animal one (or among animals with different intelligence) toward the decision for the path selection, use only one filter for the simplest animals. Then, apply other filters when you are facing with humans (or more intelligence animals).

The only filter you should always use is the one about the selection of the paths whose first focal point is toward the direction of the target.A last consideration I wish to put into the article is the following: as you could state, the two (or more) level Path Finding requires you to have a Decision-Making system whom allows NPCs have more levels of goals. This is another important issue to bear in mind when you chose the BPF.

The next article will focus on the Mental Map, Dynamic Object Avoidance and Smoothing movements.

artificial intelligence navigation meshes navigation grid waypoint navigation mental navigation mental map intelligent agent emotional agent dynamic object avoidance biological path finding psychology smoothing algorithm

This article concludes the topic of Path Finding for innovative games. The model described is based on scientific evidences which assert that human intelligence is not made only by logic. The Biological Path Finding approach is still in the research phase, even if the writer already adopted it in a couple of games.

Dynamic Object Avoiding

Nowadays, some game developers force their AI implementation to recalculate the best path when an object is intersecting the current path of an NPC. Fortunately, not all developers use this approach. The outcomes of that action, speaking in terms of credibility of the NPC and about performance, are definitely negative.

Dynamic Objects in Path Finding is a strange issue, and in my opinion is a non-problem. We should first divide the issue into two main cases:1. an object is moving toward the current path of an NPC

2. an object has moved and been placed along the current path of an NPC

The way to react to these two cases should be different. In fact, if an object is moving, we have to worry about the possibility of a collision with this object. A possible collision, though, never should lead us to change the path, unless there is a high amount of moving objects in the same place. If this ase happens, you shall check your game or simulation setup. In fact, a place in which there can be multiple moving objects should have lines of the graph with a higher weight.

When an object (or another NPC) is moving toward a line of a path used by an NPC, the only problem to face with is avoiding it. This though must not change anything in the decision, already taken, of the path to follow. A similar problem you’ll have with an object that has moved and placed along a line of the path used by an NPC. In this case, unless the object is so wide to block completely the passage, you need to treat it with the Object Avoidance algorithm.

How should be a proper Object Avoidance algorithm for the BPF? There is no preference or precaution to consider. You should use the algorithm ‘only’ to avoid object. When the NPC has avoided the object, the algorithm must go to its end. After that, the Path Finding system will be active again, and the NPC will go straight toward its next focal point.

What if the object that is blocking the path is so wide that makes impossible any trial to turn it? Do we need to find another path? I absolutely prefer avoiding this solution. Humans, when inside a real and physical problem, are not dominated by logic. Even if it’s difficult to understand, emotions manages our actions. Only after having filtered events with emotions, we may think and then use logic.

A human, when started on a path, if there is a problem along it, tries to imagine (not calculate!) a sub-path that helps him to turn the problem and continue along the same path. It’s too complicated considering to change path, and the time is never enough for a human walking along the road. Only a danger can change this way to do, but it’s something that has not to do directly with the path finding system.

So, even in the worst case, there is no need to start the path finding calculation from the current position to the target. The correct solution for a proper human simulation is finding the “simplest” sub-path from the current position to the first focal point beyond the object, or using the Object Avoidance algorithm.

In the human approach to the PF problem, there is never a sort of calculation, but rather estimations. Estimations consider the number of turns and the number of focal points: in our mind there is no continuous registration (like a video, for example) of the path, but only flashes about the focal points.
Thus, if the human saw a map, he will have a better chance to make a better estimation of the length of each path.

Any focal point is close to a micro-environment. This helps us, because it’s impossible that an object occupies more than one micro-environment (unless is a giant object!).

Smoothing Movements

Especially in case of complex or wide and open paths, I reckon that grid and mesh navigation don’t give enough NPC credibility because of the number of nodes in the map. There are, substantially, four grades of quantities of nodes in a path:

Too few nodes, or/and placed in senseless positions: it’s not possible for the NPC to walk as a human, and then it will have unpredictable results; [possible with the Waypoint approach]

Few nodes placed in the “focal points”: the NPC reacts like humans do; [currently proposed only by Biological Path Finding];Many nodes: the behaviour of the NPC is far from being similar to the one of humans. Without a good (and sometimes time-expensive) smoothing algorithm, the NPC will have a behaviour similar to one of a drunken man [can happen with the current navigation solutions].

Too many nodes (from dozens to hundreds of times more than the focal points): the behaviour of the NPC comes back to seem similar to the one of humans. The off-line and run-time calculations, though, become really expensive [can happen with NavGrid].

Take the example below.

Figure 1

You can see here the number of convex polygons (squares) made with the Navigation Grid and, below, the same map treated with the Mental Navigation, the Navigation made with the Biological Path Finding approach. You can see the number of nodes and relative lines that Navigation Map will create is higher in the current navigation approach in respect to the new one.

Figure 2

Another problem, for the current navigation approaches, is the need to make use of the smoothing algorithm almost for any line. For an approach that develops a high amount of nodes, this worsens performance.

Mental Navigation needs the smoothing algorithm for any passage among focal points too. Nevertheless, the cost is minimal if referred to the overall time of execution of the current path finding approaches, because of the small number of focal points.

There is now the need to cite another postulate of the BPF: if there is a static object or a ravine between two focal points referred to non-contiguous micro-environments, NPCs will use the Object Avoidance algorithm to move between those focal points (see the previous paragraph).

This rule could even be substituted by another that, instead of using the Object Avoidance algorithm, moves one or both focal points in order to overcome the issue.

The Mental Map

Mental Map is the approach for building a Navigation map that takes into account how humans (and animals) actually build the mental maps in their mind. In the previous section I already treated the most important part of this part of the module. Nonetheless, there are some factors you should consider before thinking how to implement the BPF.

As I’ve written several times in some different places, human intelligence is not only logic. It’s rather the contrary. Into the cauldron of intelligence there are other ingredients with an importance higher than logic. As the evidences of several findings made in biology and neuroscience can witness, intelligence is not owned only by humans.

All primates have a high intelligence. Despite what you may think, a chimpanzee for example may use a language with 250 words! Other animals have a moderate intelligence, like dolphins and dogs. The base of intelligence is nearly equal among all these species. The human species, though, developed a multitude of “psychological adaptations” that animals don’t have, or have in a simpler version.What I want to say is that logic is only the diamond tip of the biological intelligence, but it’s far from being the unique ingredient. Emotions and several other factors are the very basic ingredient of intelligence, and without them we could not understand the world that surrounds us.

What are the outcomes of this reasoning? Two facts: A) Humans, when the arousal* of one or more emotions is high or too low, tend to have non-logic behaviours; B) Animals, in terms of path finding approach, have almost the same way of doing things when faced with a path selection or an object avoidance.(*) – Arousal is, for emotions, something similar to the volume for a radio receiver.

There has not been, so far, any complete model able to represent the whole world of intelligence. I mean, for whole world of intelligence, a module containing emotions, moods, sentiments, beliefs and personality traits, not to mention the age differences, social rules and hormones. This leads us to think that, at least for a while, BPF could not be implemented at its best.

Conclusion

So, is it already possible to treat emotions in the Path Finding, in order to better simulate human behaviours? Maybe not immediately, I think, but soon. There are some guys trying to build a solid AI model (and I’m one of them, even if I follow a different, in some ways easier road than others). I reckon thetime for a solution which simulates humans and animals behaviour with a higher reliability is coming.

Anyway, you can even build an implementation of the BPF that makes no use of emotions. For the rest, you can find in the first and the second article the main ingredients of the Mental Map Navigation.

The topic of the Biological Path Finding still belongs to the field of research, even if in these articles you can find the base for making successful implementations too. It’s my intent to put on an Open Source project about BPF, to speed up the development of this new approach.（source：gamedev)