游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

分享AI寻径方法之避开物体和平顺移动

发布时间:2014-04-21 16:11:37 Tags:,,,,

作者:Giovanni Guarino

本文主要是关于创新型游戏的寻径话题。我所描述的模型是基于主张人类智能并非仅仅由逻辑所决定的这一科学论断。生物寻径法(BPF)目前仍处于研究阶段,不过作者已经在数款游戏中采用这一方法。(请点击此处阅读本系列第1第2部分

避开动态物体

今天,有些游戏开发者发现某物体与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方法会产生这个问题)。

请看以下例子。

图1(from gamedev.net)

图1(from gamedev.net)

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

图2(from gamedev.net)

图2(from gamedev.net)

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

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

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

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

心理地图

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

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

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

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

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

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

总结

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

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

关于生物寻径的话题目前仍局限于研究领域,虽然你已经从这些文章发现了一些成功执行的基础。我希望能够推出一个关于BPF的开源项目,加快这种新方法的研发速度。(本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的研究,如需转载请联系:游戏邦

Path Finding for Innovative Games: Object Avoidance and Smoothing Movement

By Giovanni Guarino

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 case 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 the time 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


上一篇:

下一篇: