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

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

发布时间:2014-04-16 16:55:28 Tags:,,,,

作者:Giovanni Guarino

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

寻径方法的现状

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

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

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

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

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

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

AI in Blood Bowl(from bloodbowlgame)

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寻径方法所发现的“正确”(未必是最佳!)大路径退出区域。

即便在这个层面上,这个方法也与寻常方法截然不同。它尽量最小化人们需要考虑的微路径数量。人类实际上会通过查看目标(或者它的方向),并检查最近的首个焦点上的路径来决定要使用哪条路径,以便向较近的目标前进。(本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

Path Finding for innovative games: Navigation UNDER REVIEW

By Giovanni Guarino

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 elaboration

In 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 to think 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. (source:gamedev


上一篇:

下一篇: