— AI分享站

Archive
Tag "势力图"

游戏AI在做决策的时候,最重要的参考依据就是当前游戏世界信息,这其实和人做判断的时候是一样的,我们在做出一个决定的时候,脑中会闪过很多我们已经收集的信息,包括所见,所听,直觉(基于以往的经验)等等。所以,我们如何去抽象游戏世界信息,并收集起来以供AI使用,也是非常值得我们去思考和探讨的问题。

当然,不同的AI决策,对于游戏世界的信息需求是完全不同的,不同的游戏,对于游戏世界的抽象方式也不完全相同,因此,关于游戏信息收集的实现是一种“游戏特定”(Game specific)的问题。说句题外话,正是由于AI中充满了很多“游戏特定”的问题,所以AI不像渲染,声音,网络等其他游戏模块,它很难做成一个“引擎”,不过也正是因为每个游戏的AI需求都不同,因此AI编程也充满了魅力和创造力 :)

虽然存在这样或者那样的不同,但就像我一开始分析的,无论是否存在一个单独的模块来收集并存储游戏世界信息,这确实是AI程序中必不可少的单元。这次我想和大家探讨一个我一直在考虑的想法,虽然在我做过的项目中还没有完全用到(零星的用到一点,没有抽象成单独的模块),不过作为一个思维笔记记下来,还是很有必要的。

假设我们写一个篮球游戏中控球队员的AI,如果我们不考虑复杂的战术配合,一般来说,控球队员要么带球突破,要么直接投篮,要么传球给会造成威胁的空位球员,考虑到篮球场上瞬息万变情况来,如果单纯的if-else,会很难罗列出全部的条件,所以我们可能会采用模糊AI的决策逻辑,比如分数系统,不过,由于今天我们讨论的是收集和存储游戏世界信息的问题,所以对于AI决策相关的东西,我们暂且不讨论。我们仅仅来看,在这个问题中,AI决策时候可能需要知道哪些游戏世界信息:

  1. 场上己方球员的分布
  2. 场上对方球员的分布
  3. 球场上哪里比较有威胁(靠近篮筐的地方)
  4. 球场上哪里比较不安全(比如有强力防守队员,或者防守队员人数很多)
  5. 场地的构成(三分线位置,三秒区)
  6. 球员的相关信息(比如球员能力,位置,当前行为等等)
  7. ……

如果把上面的信息分个类别的话,可以分成以下4种

  • 静态实体信息(比如5)
  • 静态抽象信息(比如3)
  • 动态实体信息(比如1,6)
  • 动态抽象信息(比如4)

静态和动态的概念比较好理解,“静态”就是值不随着游戏的进行而变化的信息,“动态”就是随着游戏的进行会一直改变的信息,像场地信息就是静态的,不会改变的,像场上对方球员分布就是属于动态信息,因为他们的位置是一直变动的。而我这边提到的“实体”信息,指的是“真是存在”的信息,“抽象”是指“自定义”的参考信息。像场地信息,就是实体信息,因为类似三分线位置都是实际存在的信息,但像球场上哪里有威胁,那就是我们根据需要,自己定义的信息了,可以不断的调整和修正。

我借鉴了3D渲染中“帧缓冲区”(Frame Buffer)的概念,想用一种类似的方式来存储游戏世界信息,因为我们看到上面我们需要收集的信息中,不管是静态还是动态,实体还是抽象,很多都是和游戏地图相关的(除了6),所以我们就可以用一种“图”的方式来存储信息,称之为“游戏信息图”(Game World Info Map)。

首先我们按需求将游戏地图栅格化,比10×10,当然,粒度的大小取决于对于精度和效率的平衡。每一个格子就相当于“帧缓冲区”中的像素,然后我们可以创建多个这样的“图”,和创建多个“帧缓冲区”一样。每个图都代表上述信息中的一项内容,图中的每个格子都根据信息的内容填入0.0 ~1.0的值。

例如,我们要建立一个“场地威胁图”,我们定义0表示完全没有危险,1表示薄雾浓云愁永昼威胁值最高,那我们就可以这张图的相应的格子中填入相应的值,而且因为这是静态信息,所以只需要在游戏开始时填入就可以了,当我们填完每一个格子的时候,我们就得到了这样一张“场地威胁图”。对于动态信息的情况,我们需要在每一帧(或者每几帧)对“图”中的信息做一次更新,比如“场地危险图”,就是这样的动态“信息图”,需要根据防守队员的情况来实时更新。这样当我们填完所有的“图”信息后,AI决策时就可以知道任意时刻,在地图上的任意点上的相关信息了。

小地图的情况(如上例)可以直接做栅格化,但对于地图比较大的情况,如果直接栅格化的话,更新起来性能太低,这种情况可以考虑采用层次化的图模型,先将地图分成大块的格子,在大的格子里再细分成小格子,当查看距离近的信息的,采用精细的格子信息,查看远处的时候,采用粗略的信息,这样就可以在效率上取得一些平衡。

用“图”来表示世界信息的另一个好处是,可以方便的将信息绘制出来(在地图上,或者在外部的调试工具中),而不用面对一大堆的数据,如果再将不同的值配以不同的颜色来显示的话,那将大大的降低AI调试的难度。

可以看到,其实“图”的概念,就是对于游戏世界信息中和地图有关的信息的抽象,像我前段时间提到的“势力图”(Influence Map),就是“信息图”的一种应用。“信息图”的想法并不是我的独创,其实可能大家或多或少以前在编写游戏AI的时候也用到过,但我觉得整理一下的话,可以作为一种比较通用的结构来提炼出来,在AI中加以运用。希望对大家有所帮助。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

最近在程序中遇到一个AI决策问题,简要描述和图示如下:

在一张开阔的地图上(几乎没有障碍物),有一些会任意移动的“敌人”,我们要实现一个NPC的AI,使他在做接近目标点的移动决策的时候,能避开这些“敌人”所在的危险区域,而选择相对安全的方向去移动。

im_pic_1

这有点类似于一个寻路算法,不过,和一般的A*算法问题有点不一样的是,在这张开阔的地图上并没有预先设置的路点(Way Point)帮助寻路,而且所有的“障碍物”在这里都是动态的,这样就造成预先计算一条路径的意义并不是很大,正所谓计划赶不上变化嘛。所以我们需要另一种方案来处理,在这里,我用到势力图(Influence Map)来辅助AI寻路。

所谓势力图(Influence Map),也就是一种对于世界信息的预处理,计算和存储地图上的势力数据。比如说,我站在地图的某个点上,那我所站的这个位置,我就对它产生了最大的“势”,因为别人不可能再占据这个点了,由我这个点向外越远的地方,我对其的影响力就越小,也就是我所产生的势越小,用图画出来的话,就像一个靶子一样,所以可以称之为势力靶图如果我们用分数来表示的话,中心就是10分(最大值),然后随着离中心点距离的增大,造成的势力值越来越小。

im_pic_2

另外,势力靶图是可以叠加的,如下图阴影处的势力值,就是4(2+2),叠加后如果超过最大值(10),就按最大值来取,比如多个势力值叠加后为12,超过了10,那这个点的势力值还是取最大值10。

im_pic_3

如果我们对每一个地图上的物体(不管静态还是动态的),计算势力值的话,我就可以得到当前时刻该地图的势力图。当然,为了更好的表示势力图,我们可以先为地图做网格化,然后在每一个格子中存入该格的势力值。我们回到上面这个问题,假设当前这个时刻,NPC和三个敌人的分布就如图片1所示,那我们就可以根据这样的分布,计算出当前的势力图:

im_pic_4

值得注意的是,我这边用了方型的势力靶图,主要是为了简化计算,从效果上来说,和圆形的差别并不是很大,另外,我为势力值定了4级的标准(10,7,4,1),势力值的级数一般是看具体的需要,可多可少,自行权衡既可,有了这样的势力图,我就知道哪些地方是“相对安全”的地方,比如,0,1的格子,在往目标点寻路的时候,就可以尽量往安全的地方选择了。

一般AI决策前,我们需要很多对于世界数据的收集和抽象,势力图作为其中的一种,可以看到,提供了对当前时刻,当前地图中物体的大致分布情况的抽象,可以很好用来帮助我们做AI寻路的决策,其实不光是寻路,其他AI决策问题,如果需要,也可以用势力图做参考数据,比如足球游戏中,如果我们要选择传球给一个处在空档的球员,我们就可以用势力图,来寻找哪一个球员处在空档的位置,等等。

对于势力图,还有几点需要补充一下:

  1. 对于势力图的更新,大可不必每帧计算,因为对于一个场景来说,就算是有运动的物体,一帧的时间里,其变化还是很小的,所以,可以根据需要把更新的周期拉长,以优化势力图的计算
  2. 方型的势力靶图一般可以满足需求,比起圆形的来说,势力图计算的性能上更有优势
  3. 可以把势力靶图做成运动方向凸起的形状,因为如果是需要转向的物体,他背后的势力值应该是衰减的很快的,或者说延伸的很近的,而在其当前运动方向上的势力值,则延伸的比较远
  4. 需要将势力图画出来(无论是在屏幕上,还是在另一个工具中,见我以前的关于AI调试的文章),以帮助调试。

这次对于一开始的那个问题,我们引出了势力图的介绍,至于具体如何基于势力图来寻路,我用到了类似于“导向性寻路”(Steering Behavior)来实现,以后有机会再写吧。

好,这次就这些了,希望对大家有所帮助。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More