开启辅助访问
 找回密码
 注册帐号

扫一扫,访问微社区

蛮牛译馆

关注:531

当前位置:游戏蛮牛 技术专区 蛮牛译馆

查看: 1207|回复: 16

[人工智能] 通用平台游戏AI寻路技术

[复制链接]  [移动端链接]
排名
2387
昨日变化

18

主题

31

帖子

862

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
173073
好友
1
蛮牛币
2594
威望
0
注册时间
2016-9-30
在线时间
387 小时
最后登录
2017-5-29

活力之星

发表于 2017-4-26 11:19:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册帐号

x
本帖最后由 BabelGuo 于 2017-4-26 11:29 编辑

通用平台游戏AI寻路技术


本文我们将会探索一个强大的,通用的AI实现技术来通过“跳和跑”的方法到达任意目的地。这种方法适用于静态地图和类似梯子的垂直移动和滚轮的水平移动。

如果你正在写“跳和跑”风格的游戏,你可能会想要在里面添加一些人工智能。不管是在自己身上还是敌人或者别的什么上,里面总是会有一个人要去追赶另一个人的情况。经常会出现的是,程序员只会使用那些容易实现的AI,当面对麻烦的跳跃,灵活的角色,或者一些移动的风景时机会放弃使用AI。
本文提出了一种技术通过AI到达静态地图上的任意位置。如果开始和结束在固定的位置,那么AI会利用适时的跳跃或者场景移动来实现(但事实这并不总是如此)。
我们将理论与实际进行结合。在以后的文章中将进一步讨论包括可移动或可破坏场景的例子。 这种技术已经用在了Nomera上,可以在www.dotstarmoney.com 或者Twitter(@DotStarMoney)上找到。

1.png

在进一步讨论之前,确定是由于几何水平的制约而没法实现更加简单的算法。也就是说:所有的碰撞都是因为正方形网格形成的(在大多数2D游戏中)。在这些条件下,可以通过简单的技术得到可靠的AI路径,这种方法主要是为那些希望游戏AI用于人形模型上的情况。

准备工作
在开始前,如果有数据图形和图的遍历算法的知识更好。你还需要数学矢量来预处理和测量物体表面的距离。这种技术适用于由静态水平路面和移动场景组成的情况,同时非水平方向不会发生不断变形的情况。访问作为线段的静态碰撞数据非常重要;虽然这种技术可以很容易地扩展为支持使用任何几何对象的碰撞,但这样可以简化操作。


计划
通俗而言:作为开发人员,引擎记录了你在平台之间的跳跃,从平台跳起/下落的点作为输入,直到你移动到另一个点。这个数量作为一条“边”,保存了输入的记录。 当AI要通过时,它将一系列平台作为顶点, (现在开始我们称之为节点),同时将它们之间记录的边作为图。AI通过选择不同的节点获取路径,沿着记录的边到达终点。还有许多重要的区别需要注意,不过现在只关注常见的就行。.
我们使用的是这两种技术的结合。它们分别是,创建路径图,或者“利用路径创建AI的数据结构”遍历路径图,或者“在给定的方向下引导对手”。显然后者依赖于前者。创建路径图总结如下:
1.    加载静态碰撞数据并计算一系列节点。
2.    加载任意的水平记录的边(路径),同时加入到各自的起始节点。
3.    使用碰撞模型和移动参数,记录节点间的路径并且加入到图中。
4.    退出水平方向时,导出记录的边。
现在还不是非常明了,但我们将会逐步分解。目前要做的就是抓住要点。
遍历路径图的总结:
1.    接收目的地节点和距离该节点的距离;计算源(起始)节点的参数。
2.    计算路径,使用任意从原点到目的地的图遍历算法,路径由一系列节点和边缘构成。
3.    指导AI通过行走从一个节点到达一条边(或者是跑,这由AI决定),同时在到达路径的边时保持正确的速度。
4.    一旦AI以可以接受的位置和速度到达路径中下一条边的起始位置,那么就放弃AI的自动控制,开始通过逐帧的记录进行控制。
5.    当输入结束时,让所有的AI控制节点变回自动移动。
6.    重复最后三步直到到达目的地。
有点感觉没?开始分解每一步吧。


逐步实现寻路


创建路径图
路径图由平台/节点组成,节点间的连接就是记录/边。第一次定义平台和记录构成是很重要也是很困难的。
节点/平台有以下特性
·        线段的子集组成了几何地形。
·        假定重力正常,所有节点的段落起源于第一个顶点,其x坐标小于第二个。(这可能会因为反向重力逆转)。
·        每个节点的后续部分接着上个节点的结尾。
·        每个节点可以通过AI沿着其表面通过。
以上这表达了什么呢?主要意思就是:一个节点可以通过AI在不跳跃或者下落的情况下穿越整个场景,同时AI可以从任一节点到达其他节点
这是水平几何碰撞的图片:
2.png

这里有我们所提取的所有节点(有序,独立且清晰)。在执行过程中,当水平面被加载后节点提取开始执行,当水平路径建立后不用返回和标记任何面。你会注意到这基于“所有表面都是可行走的:”

3.png
注意: 这张图有个小问题261是两个不同的节点,但是正如你所见,它们应该是同一点。
这取决于存储的水平几何体,可以使用一些额外的信息将任意节点连成线段。
另一重要的是,如果沿着一个节点有静态的几何体产生阻碍(像一堵没有着地的墙),你需要沿着障碍划分节点。例子中没有体现,如果不检查的话会导致大麻烦。
一旦有了节点,你就完成了创建路径图的第一步。我们还需要知道如何确定位置。位置用于寻路来确定来源和目的地,它是一个节点(这种情况下通常是数字), 同时沿着坐标点进行水平位移。为什么是水平距离而不是沿着节点的弧长?假设AI的身体碰撞在一个沿着向上的斜坡上的正方形或者圆形表面。其表面会碰到内角吗?不,相反,位置是根据水平位置测量的,所以我们可以视节点为“弯曲的,水平线”。
为了完成第二和第三步,我们需要证明边/记录到底是什么。

边有以下属性:
·        一条边有起始位置和边缘位置两个不同的节点。(如果要创建平台跳跃的快捷键,那么可能是相同的节点!)
·        边有一系列的帧输入记录,在边上提供一个AI的起始位置和起始速度,这将会指导AI由目的位置到指定位置。
·         
有几件事要说:生成的帧记录了一系列的精确碰撞和运动属性,这作为被创建的边路径的AI,这是非常有必要的。最大的问题是,帧的记录是从哪来的…是你!
接下来是跳跃:
在Nomera开发者模式的游戏引擎里,记录可以当玩家从一个点起跳或者落下时打开,一条新边在指定位置被创建,它等于下落或者起跳的位置。这时玩家记录了输入的每一帧。当在一个节点下落/起跳,大概有几帧的跨度,在起始点和当前点及路线的位置记录结束并作为一条边添加。
换句话说,你正在记录着玩家的输入,如果AI与起始位置对齐,那么可以放弃控制来让这些输入到达目的位置。
同样重要的是,当记录的时候,玩家的碰撞和移动属性应该瞬间切换到AI上,边被标记为“只能被”AI获取,AI记录了其属性。
创建路径图的第二步是加载任意之前创建的边,第三是实际记录的过程。怎么记录完全取决于你。这里是一个绘制Nomera的边。线段连接了起始点,但是没有记录路径,这通过以下技术实现:

4.png

左上角可以看见来自游戏内边编辑器的标记。这允许删除任意你不满意的边,否则不要让AI进行尝试。它还显示了帧的输入记录。
当然,边需要更多的属性,不仅仅是一条记录帧,也包括起始和结束位置。正如前文所提,边的起始速度至关重要,以后会变得越来越明显。这也有利于访问大量的帧,因为在寻找到目的地的最短路径非常有用。
此时,你应该有能力搭建一个记录了边信息平台节点的路径图了。接下来是更有趣的事,如何使用这个AI路径图。

遍历路径图

在深入使用路径图前,有一件事要先实现。
本质上是通过路径记录AI动作,用AI控制拥有相似界面的玩家,这是个好主意。假设玩家类如下:

[C#] 纯文本查看 复制代码
class Player{
    public:
    
    // ...
    
    void setInputs(int left, int right, int jump);
    
    // ...
    
    private:
    
    // ...
}

“左,右,和跳”都来自于键盘的输入。首先,这是你在边的每帧记录的值。其次,由于人工智能还需要一个“设置输入值”的控制接口,为什么不是真实的接口呢?因为这样更加模块化:
[C#] 纯文本查看 复制代码
enum PC_ControlMode{
    MANUAL,
    RECORDED
}  
 
class PlatformController{
    public:
    
    // ...
    
    void setManualInput(int left, int right, int jump);               
    void bindRecordedInput(RecordedFrames newRecord);
    
    int getLeft();
    int getRight();
    int getJump();
    
    void step(timestep as double);
    
    // ...
    
    protected:
    
    PC_ControlMode controlMode;
    RecordedFrames curRecord;
    
    void setInputs(int left, int right, int jump);
    
    // ...
    
}
 
class Player : public PlatformController{
        
    // ...   
    
}
 
class AI : public PlatformController{
     
    // ...
    
}

现在,AI和玩家被控制使用可扩展的界面来决定是否手动控制或者记录。这对过场动画这种玩家没有控制权的预录制非常方便。
好的,那么我们想要AI控制类似黑盒风格的方式:
[C#] 纯文本查看 复制代码
         createPath(positionType destination);
         step(double timestep);

前者在当前位置和目的位置间设置了路径,后者提供了setInputs()来让AI到达目的地。在框架中,包括创建路径到最后的进入路径。现在来看看创建路径。
路径由一个有序序列组成,它有一个交替的节点和边作为起始以带我们到达最后的目标节点作为结束。

首先需要确定当前位置,节点在空中处于静止的状态。当我们在节点上时,需要节点的引用和水平位置。(还记得通用类position吗?)

为了构建路径,我们使用了图遍历算法。在执行的过程中使用Djikstra's算法。对于存储的每个节点,我们会在给定的边存储其位置(以后将会调用 edgeStartNodeCurrentPositionX)。因此,对于给定边的权重如下:

[C#] 纯文本查看 复制代码
         edgeFrameLength = number of frames in the edge recording
         walkToEdgeDist  = abs(edgeStartX - edgeStartNodeCurrentPositionX)
        
         edgeWeight = edgeFrameLength * TIMESTEP + walkToEdgeDist / (HORIZONTAL_WALKING_SPEED)
        
         if(edgeDestinationNode == destinationPositionNode){
                 edgeWeight += abs(edgeEndX - destinationPositionX) / (HORIZONTAL_WALKING_SPEED)
         }

如你所见,最终边的权值以秒计算,同时记录走到了边起始处的时间。这个计算并不准确,这与敌人疾跑时的移动不同。我们也检查是否在目的节点上,如果这样,从边结束位置行走到目的地的时间就被加到权重上。
如果边的权重能计算,那么可以使用Djikstra's算法!(或者任何其他的图遍历算法,如果使用欧几里得距离到目的类型启发式,A*会更好)。
现在应该有路径了!我们几乎已经完成了同时覆盖框架的四个步骤,没有太多事情要做了。一般而言,我们有两种方式来处理是在节点还是边上。
如果在节点上,我们从当前朝向的位置走到下一位置。现在提到了前面,需要知道边输入的起始速度。这是因为通常情况下,当开始或者停止行走时,AI可能出现加速或者减速的情况。这些速度可能在边的起始处就存在了。正因如此,当走向起始位置时,我们可能需要减速或者后退才能以跑/步行开始。
一旦到达了边起始的位置,我们可能不会精确地匹配边的起始位置。在实践的位置上很少有超过一半的像素。重要的是到达了临界边的位置,这将会关闭AI控制的位置/速度。
现在准备放弃控制的记录了。
如果在边上,那么每帧通过边提供的控制同时增加记录读取边的数量。就是它了!终于,就要完成了,如果记录的框架完整,那么AI会在下一节点登录的同时将控制结束。

其他
还有一些方法可以优化代码。
强烈建议添加游戏路径记录和删除界面来帮助你简单地构建水平路径:Nomera 大约需要10分钟来设置水平路径,这很有趣。
节点的自动提取也会变得非常方便。如果你能独立完成,添加自动提取会让工作流非常简单。
对于节点参数的快速检索,Nomera在一个Hash表里存储了所有节点和每个节点所有的边。 为了简单地显示,边也存储在了一个控制列表来展示屏幕上的起始/目的线段。
如果你没有注意到,像梯子和绳索这样没有碰撞的静态交互块通过这种技术自动地处理。 加入“上”键来爬梯子,如果“上”键被记录并且AI使用相似的接口将会注册输入的同时进行攀爬。

总结
我们注意到了一种方案,AI在一个有任意几何碰撞的水平platforming上,其允许AI完全控制platformer。首先生成了水平的路径图,然后从图构建路径,最后指导AI通过路径。
能运行吗?当然!下面是gif:

http://i.imgur.com/Ynhun7J.gif

这些人物被设定为“聚团模式”。无论我到哪它们都恨不得跟着钻进我的身体


       蛮牛译林军福利多多哦!

扫描下方二维码关注游戏蛮牛官方微信~每日都有精选干货与你分享呦~
224536xgafsesicocfag9c.png.thumb.jpg




回复

使用道具 举报

排名
115
昨日变化

2

主题

1486

帖子

4387

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
47709
好友
0
蛮牛币
2994
威望
0
注册时间
2014-10-5
在线时间
1075 小时
最后登录
2017-5-29
发表于 2017-4-26 15:41:18 | 显示全部楼层
哎...今天够累的,签到来了游戏源码下载...

回复 支持 反对

使用道具 举报

排名
46663
昨日变化
22

0

主题

1

帖子

3

积分

Rank: 1

UID
219535
好友
0
蛮牛币
17
威望
0
注册时间
2017-4-26
在线时间
0 小时
最后登录
2017-4-26
发表于 2017-4-26 20:32:56 | 显示全部楼层
GOOD GOOD GOOD

回复

使用道具 举报

3偶尔光临
197/300
排名
8074
昨日变化
2

0

主题

55

帖子

197

积分

Rank: 3Rank: 3Rank: 3

UID
210517
好友
0
蛮牛币
670
威望
0
注册时间
2017-3-7
在线时间
46 小时
最后登录
2017-5-27
发表于 2017-4-27 08:51:20 | 显示全部楼层
谢谢分享!

回复

使用道具 举报

4四处流浪
330/500
排名
10256
昨日变化
6

0

主题

223

帖子

330

积分

Rank: 4

UID
181594
好友
0
蛮牛币
127
威望
0
注册时间
2016-11-7
在线时间
45 小时
最后登录
2017-5-28
发表于 2017-4-27 09:45:59 | 显示全部楼层
真不错!!!!

回复

使用道具 举报

3偶尔光临
240/300
排名
6871
昨日变化
1

0

主题

33

帖子

240

积分

Rank: 3Rank: 3Rank: 3

UID
10951
好友
0
蛮牛币
590
威望
0
注册时间
2013-12-23
在线时间
81 小时
最后登录
2017-5-6
发表于 2017-4-27 11:51:37 | 显示全部楼层
好牛的感觉

回复

使用道具 举报

排名
25484
昨日变化
3476

1

主题

5

帖子

18

积分

Rank: 1

UID
215906
好友
0
蛮牛币
44
威望
0
注册时间
2017-4-1
在线时间
6 小时
最后登录
2017-5-27
发表于 2017-4-27 17:04:20 | 显示全部楼层
学习了 谢谢分享

回复

使用道具 举报

排名
21221
昨日变化
9

0

主题

59

帖子

81

积分

Rank: 2Rank: 2

UID
219197
好友
0
蛮牛币
63
威望
0
注册时间
2017-4-24
在线时间
10 小时
最后登录
2017-4-29
发表于 2017-4-29 17:47:52 | 显示全部楼层
GOOD GOOD GOOD
[发帖际遇]: kenroesh 乐于助人,奖励 2 蛮牛币. 幸运榜 / 衰神榜

回复

使用道具 举报

0

主题

4

帖子

8

积分

Rank: 1

UID
178234
好友
0
蛮牛币
5
威望
0
注册时间
2016-10-25
在线时间
6 小时
最后登录
2017-5-11
发表于 2017-5-2 14:24:14 | 显示全部楼层
感觉好厉害

回复

使用道具 举报

3偶尔光临
252/300
排名
17039
昨日变化
3

0

主题

93

帖子

252

积分

Rank: 3Rank: 3Rank: 3

UID
24055
好友
1
蛮牛币
5
威望
0
注册时间
2014-5-6
在线时间
139 小时
最后登录
2017-5-22
发表于 2017-5-3 11:16:35 | 显示全部楼层
原文链接在哪里?

回复

使用道具 举报

4四处流浪
445/500
排名
4226
昨日变化
2

1

主题

68

帖子

445

积分

Rank: 4

UID
44919
好友
1
蛮牛币
785
威望
0
注册时间
2014-9-15
在线时间
140 小时
最后登录
2017-5-9
发表于 2017-5-5 17:23:04 | 显示全部楼层

mark,后面再看哈哈
[发帖际遇]: HELLO613 乐于助人,奖励 2 蛮牛币. 幸运榜 / 衰神榜

回复 支持 反对

使用道具 举报

排名
13588
昨日变化
2

0

主题

11

帖子

60

积分

Rank: 2Rank: 2

UID
205264
好友
0
蛮牛币
160
威望
0
注册时间
2017-2-6
在线时间
17 小时
最后登录
2017-5-27
发表于 2017-5-8 15:40:33 | 显示全部楼层
补充点AI知识

回复

使用道具 举报

6蛮牛粉丝
1398/1500
排名
1319
昨日变化

26

主题

197

帖子

1398

积分

Rank: 6Rank: 6Rank: 6

UID
124569
好友
24
蛮牛币
6494
威望
0
注册时间
2015-10-4
在线时间
497 小时
最后登录
2017-5-27
发表于 2017-5-17 18:06:37 | 显示全部楼层
感觉好厉害

回复

使用道具 举报

3偶尔光临
189/300
排名
8831
昨日变化
2

2

主题

43

帖子

189

积分

Rank: 3Rank: 3Rank: 3

UID
134499
好友
0
蛮牛币
236
威望
0
注册时间
2016-1-12
在线时间
64 小时
最后登录
2017-5-23
发表于 7 天前 | 显示全部楼层

谢谢分享!

回复

使用道具 举报

3偶尔光临
278/300
排名
12932
昨日变化
301

2

主题

194

帖子

278

积分

Rank: 3Rank: 3Rank: 3

UID
173610
好友
0
蛮牛币
790
威望
0
注册时间
2016-10-6
在线时间
48 小时
最后登录
2017-5-29
发表于 6 天前 来自Mobile--- | 显示全部楼层
感谢楼主分享~,不过这是之前版本的吧?

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册帐号

本版积分规则

快速回复 返回顶部 返回列表