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

开发者分享游戏中的寻径与AI设置试验过程

发布时间:2012-10-10 11:02:19 Tags:,,,

作者:Tyler Glaiel

最近我刚完成了我的第一款商业游戏(《Closure》),现在的我变得非常无措,不知道自己下一步该怎么走。在经过几个月的思考与游戏,我最终决定 开始创建一个游戏样本,我希望借此机会好好利用我在过去几年里所实验的 AI。

几年前我无意中看到了一篇文章,其核心内容是关于通过“扩散”和“气味”去发挥寻径和AI的功效。我非常好奇文章中关于寻径所提到的所有紧急行为,不过事实上我并不是很理解文章中所提到的大多数内容,所以我花了点时间进行深入研究,并明确了引起各种紧急行为的AI和寻径的理念,同时也想办法避开了“扩散”元素以及其中所包含的数学内容。

首先我们必须掌握一定的背景,为了理解这篇文章你就必须了解什么是寻径。也就是掌握最基础的寻径算法(即戴克斯特拉算法)。你可以借助洪水填满法进行理解。即你始于一个网格空间,并将所有未经碰触的邻元素扔进一个队列中,不断重复这些点并将其标注为已碰触。你将记录下每个队列所添加的点,而当你找到目标时,你只需要向后追踪路径便能够明确最短的路径了。

关于这篇文章的第一个核心要点在于,你必须完全改变你对于寻径的看法。我的意思是保存寻径路径而不是让每个实体通过运行自己的寻径算法去明确发展方向。通过下图便能够较清楚地理解我想要表达的意思:

pathfinding(from gamasutra)

pathfinding(from gamasutra)

寻径数据贯穿着整张地图——从玩家开始(在截图上由各种颜色所标记)。一般情况下这种算法总是慢于寻径的运行,因为在目标找到“最短路径”前你不会轻易中断这种运行。但是你只需要运行一次就够了,而无需面对每个敌人都运行一次。每个瓷砖都有其价值所在,从0值开始算起直到玩家输掉游戏,并且每个新增加的瓷砖都会具有更高的值(在当前值的基础上+1),从本质上来看每个瓷砖的值都取决于有多少瓷砖远离了玩家。

可以说这是寻径的一种查阅数据表。比起使用昂贵的寻径操作系统去寻找敌人接近玩家的方式,如今的开发者只需要浏览这一查阅数据表便可。如果你的游戏终止于第3个或第4个瓷砖,你便只需要查阅相应瓷砖的值即可,并找到任何接近于玩家的瓷砖。这种方法即简单又快捷,能够帮助你在避免任何性能问题的前提下随时明确敌人的路径。

pathfinding(from gamasutra)

pathfinding(from gamasutra)

(在这一样本中,敌人将在瓷砖中随机选择一个位置而朝着目标移动,从而呈现出各种路径的多样性)

当你在了解寻径时还会发现,你必须给予瓷砖一个穿越“成本”。就像穿越河流或泥土将花费4个值,而穿越道路只需要花费1个值。这种改变非常直白。一开始你便需要在寻径算法中进行设置(游戏邦注:在现有瓷砖值基础上+1),然后再相对地做出改变(现有瓷砖值+现有瓷砖成本)。你需要使用优先排列方法进行存储,因为在成本改变时按顺序抽出瓷砖并不是一种合理的方法。你总是希望能够以较低的成本去抽出每个瓷砖,而优先排列方法能够帮你实现这一目标。

随之我们便来到了该文章的第二大要点,即敌人对于寻径的影响。让我们利用敌人去提高玩家每通过一个瓷砖的成本。我决定每个敌人将能够提高瓷砖的成本为1。也就是你可以在一个瓷砖上添加4个敌人,这也意味着瓷砖处于“饱满”状态,这时候较廉价的路径便是绕着瓷砖前行而不是穿越它。让我们通过以下图表进行了解:

pathfinding(from gamasutra)

pathfinding(from gamasutra)

绿色的路径较长,但是所需要的成本也较低——因为玩家无需穿过拥挤的敌人。这时候玩家将能够获得来自AI的紧急行为,因为AI们将迅速扩展并“环绕”着玩家,而无需基于任何特殊情况去编写代码。通过以下截图我们可以看到在“拥挤的走廊”上梯度的变化有多快。

pathfinding(from gamasutra)

pathfinding(from gamasutra)

以下又是另外一种情况,即敌人拥挤地穿越走廊,而外沿的敌人将脱离群体并往相反的方向移动——尽管这么做会让路径显得更长。

pathfinding(from gamasutra)

pathfinding(from gamasutra)

关于这种方法的另外一大吸引力便在于,在一个广阔的领域中,敌人不只是面对着你并直接走向你,他们也将不断扩散并想办法靠近你,这种设置比起让敌人直接走向玩家或只呈现出一丁点的随机性有趣多了。这会让玩家感受到敌人也具有一定的独立性,并且AI也显得更加智能化。

pathfinding(from gamasutra)

pathfinding(from gamasutra)

我喜欢这种方法所体现出的技术性。游戏中同时混合了技术和艺术的设定非常有趣,我也非常热衷于寻找更多方法将这样的技术带进游戏中。这也是我的大多数游戏理念的源泉。《Closure》的游戏理念便是源于此(利用光进行实验),并且这一方法有可能成为这款新游戏的支柱。我真的非常高兴自己能够在创造特别的游戏之前选择原型创建这一工作。

本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

Some experiments in pathfinding + AI

by Tyler Glaiel

Hey there, Tyler here. Having recently completed my first commercial game (Closure), I’ve been sorta at a loss as to… what do I do next? After a few months of thinking and well, playing games more often than I probably should be doing, I’ve come up with a concept that I really like and have started prototyping. That’s not the important part of this article though. I’m not gonna reveal core details of the game yet, it’s way too early, but it IS a perfect chance for me to apply an AI thing I’ve been experimenting with for a few years now.

I stumbled across this paper a few years ago, which talks about pathfinding and AI using “diffusion” and “scent” as a core part of it. I was very curious about all the emergent behaviors the paper described in regards to pathfinding stuff, but the actual paper was a bit over my head at the time, but I took the time to dig through it and pull out the few concepts regarding AI and pathfinding that led to the emergent behaviors described in that paper, while avoiding all the talk about “diffusion” and the math involved in that.

A bit of background first, to follow this article you’ll need a basic understanding of pathfinding. Just the most naieve pathfinding algorithm you know (which is Dijkstra’s algorithm). If you don’t understand it, picture it as a flood-fill. You start at one grid space and throw all its untouched neighbors onto a queue, repeat with those points and mark them as touched (in the order they were added to the queue). You keep track of which points added which to the queue, and when you find your target, just trace the path backwards from it, and you have your shortest path.

Now, the first core point from that paper is, you need to flip the way you think about pathfinding. By this I mean, store the pathfinding data as its own thing, rather than having each entity run its own pathfind() algorithm to determine which way to go. Here’s a simple visualization of what I mean

Pathfinding data is flood-filled throughout the map, starting from the player (and represented by color in this screenshot). This algoritm is SLOWER than running pathfinding normally, because you don’t cut it off ever since the goal here isn’t to find a “shortest path”. But you only need to do it once, not once per enemy. Each tile has a value, which starts at 0 for the tile the player is over, and each newly added tile has its value increased by one (current tile value + 1), so in essence, every tile’s value is how many tiles away from the player it is.

This is basically a lookup table for pathfinding. Rather than running an expensive pathfinding operation to find out which way to go for an enemy to reach the player, you simply look up the pathfinding table. If you’re over tile 3,4 you just look up the value of that tile,find whichever neighboring tile is closer to the player, and GO THAT WAY. Its simple, and fast, and lets you have a metric shit-ton of enemies pathfinding at any given time without any performance problems.

(In this sample the enemies pick a random position within the tile they want to move towards as their target, to give some variation to the paths they take)

Another thing you might read about when learning pathfinding is giving tiles a COST to path through. Like, maybe going over a river or through mud costs 4 while going over road costs 1. This is a simple change. From before, where you set (current tile value + 1) in the pathfinding algorithm, you change it to (current tile value + current tile cost). You NEED to use a priority queue now as your container, since pulling out tiles in the order they were added is not correct when the costs vary. You want to always pull the tile with the lowest cost out of the available options, and this is what a priority queue is for. You can look up more details on how this works in almost any pathfinding tutorial that covers A*.

This brings me to the second point from that original paper, which is that enemies should have an effect on the pathfinding. Let’s do this by using enemies to increase the cost of passing through a tile. My choice here is, each enemy increases the cost of the tile it’s over by 1. You can fit ~4 enemies on one tile, which means if a tile is “full”, the CHEAPER path is going around it, rather than through it. Look at this diagram for a sample

The green path is longer, but has less cost cause it doesn’t need to move through that crowd of enemies. You now get emergent behavior from the AI, since they’ll spread out and do a much better job of “surrounding” the player, without ever having to code that in as a specific case. You can see it here, look how fast the gradient changes in the “crowded hallway”.

And here’s another one, where enemies are so crowded trying to get through a hallway that ones on the outer edge decide to leave and go flank instead, despite that path being a lot longer

Another VERY APPEALING aspect of this, is that in large open areas, enemies don’t just face you and walk directly towards you, they tend to spread out a bit while still trying to get close to you, which makes for a far more interesting behavior than simply walking directly towards the player, or even walking directly towards the player with a little randomness. This just feels…. good. They feel like they have some sort of independence to them, the AI seems intelligent when its actually STUPIDER than most AIs.

I love technical stuff like this. Its fun, games are a melding of technology and art, and I love figuring out ways to apply cool technology like this to game stuff. Its where most of my game ideas come from. Its where Closure’s idea came from (experimenting with lighting), and it seems to be forming the backbone of this new game too. I’m glad I decided to jump into prototyping this stuff before working on the thing that makes the game SPECIAL (which will remain a secret for a while, at least until I have something more resembling an actual game). Why that is will have to wait for another post.(source:GAMASUTRA)


上一篇:

下一篇: