Godot游戏开发实践之二:AI之寻路新方式

2020-08-01 by Liuqingwen | Tags: Godot | Hits

一、前言

AI 一直是游戏开发中一个热门词汇,当然这不是人工智能的那个 AI ,而是指有着人类思想的 NPC 或者聪明的敌人等等。根据游戏的类型和复杂程度, AI 的实现可以很简单,也可以非常复杂。作为新手,本文不会讨论所谓高级 AI 的实现方式,那太不现实,不过我们可以先从最简单、最常用也是最实用的 AI 寻路探索开始入手,进而丰富我们的小游戏!

本文目标是让我们这些新手游戏开发者们都:能用得起 AI 、能用好 AI 、能做 ai (别念出声!),嘿嘿!其实,游戏中的寻路方法非常之多,我所见到过的就有好几种,这些方法有难有易,具体实现机制见仁见智,我现在将自己熟悉的几种方式写出来,比较其优缺点,并和大家一起讨论讨论,如何避免下图中的尴尬。当然,如果您有其他更好的方法请务必留言告诉我,非常感谢! sunglasses

尴尬的AI

主要内容: AI 寻路新方法探索
阅读时间: 6 分钟
永久链接: http://liuqingwen.me/2020/08/01/godot-game-devLog-2-introduce-a-new-AI-path-finding-method/
系列主页: http://liuqingwen.me/introduction-of-godot-series/

二、正文

说到 AI 寻路不得不说 Unity 中的 NavMeshAgent 了,真的很实用,也很强大。在 Godot 中,虽然也有 Navigation 节点的实现,不过功能实在有限,当然这会在 4.0 的版本中有所改善,这是后话,现在我们不谈 3D ,我们从简单的 2D 入手。 smiley

Godot 中的 AI 寻路方案大概有以下几种:

  1. 使用内置的 AStar 类,对于自动生成的网格地图非常有用,结合多线程效率也高
  2. 使用内置的 Navigation2D 导航类,比较方便且实用,但是有较大的局限
  3. 结合 RayCast2D 射线对路径进行判断,有比较好的解决方案,但是算法复杂,我也没找到通用的方式
  4. 使用大量的 Area2D 对地图可行路径进行判断,看上去比较复杂,没有详细了解过

关于 AStar 的用法我在之前的文章中有简单的介绍,如果感兴趣建议参考油管上一个非常详细的视频教程: A* Pathfinding Tutorial (Unity) ,尽管是用的 Unity 但是算法是通用的,这里我不再赘述。接下来一起讨论第二和第三种,以及新的寻路方式。

寻路方式一:使用 Navigation2D

这种方式使用起来非常简单,在场景中添加 Navigation2D 节点,然后结合 TileMap 或者自定义导航多边形 NavigationPolyInstance 节点进行可行区域绘制,在 TileMap 中绘制可行区域需要在 TileSet 中绘制相应的 Navigation 形状即可,可以参考我之前的文章: Godot3游戏引擎入门之七:地图添加碰撞体制作封闭的游戏世界

以下是简单的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
func _findMoveDirection(delta : float, target : Node2D) -> Vector2:
var dir := Vector2.ZERO
if _navigation == null:
return dir

# 使用导航的方法找出可行路径
var path := _navigation.get_simple_path(self.position, target.position)
_path = path
# 注意:第一个点可能是AI自身所在点,这时候会返回 Vector2.ZERO 导致不移动
while dir == Vector2.ZERO && ! path.empty():
dir = (path[0] - self.position).normalized()
path.remove(0)
return dir

使用 Navigation2D 导航寻路的优缺点:

  1. 优点:简单易用
  2. 缺点一:对地图的依赖比较大
  3. 缺点二:由于不考虑物体大小,所以会发生在转角处卡住的情况

正因为 Navigation2D 把移动物体当做无限小的点来处理,导致了寻路可行性大减,如下图:

Navigation2D AI

也有一些补救措施:修改导航地图;扩大可行区域与障碍物之间的间隙;尽量使用圆形、胶囊型碰撞体。

寻路方式二:使用 Ray/RayCast2D 射线

如果在普通寻路过程中能够提前检测到故障而绕行,那么是否可以避免碰撞的发生呢?我在网上看到了 Game Endeavour 大神的一个实现思路:

AI path finding by Game Endeavour

我尝试了一下,最终没有完全实现类似的效果,如果大家有更好的实现思路请告知,感谢!下面是代码,我没有使用内置的 RayCast2D 类,而是自定义的射线类:

1
2
3
4
5
6
7
8
# 射线类,检测玩家是否可以移动的射线,用于记录射线状态
# 比重越高,选择该射线方向进行移动的可能性越大
class Ray:
var length := 0.0 # 长度
var dir := Vector2.ZERO # 方向
var canMove := true # 玩家是否可以移动
var playerWeight := 0.0 # 相对于玩家的比重
var moveonWeight := 0.0 # 相对当前移动方向的比重

这里 playerWeightmoveonWeight 分别表示相对于玩家方向、当前移动方向的两个比重,都是通过点乘得到,具体实现方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 查找可行的移动方向,父类方法
func _findMoveDirection(delta : float, target : Node2D) -> Vector2:
var vector := target.global_position - self.global_position
var dir := vector.normalized()
var length := vector.length()
_updateRays(delta, vector, _currentRay.dir) # 更新射线当前帧状态
_findRayDirection() # 在更新状态后找出合适的方向
return _currentRay.dir if _currentRay else Vector2.ZERO

# 更新射线碰撞状态、射线比重
func _updateRays(delta : float, targetDir : Vector2, moveDir : Vector2) -> void:
# 获取 world space state 用于发射射线
var state := self.get_world_2d().direct_space_state
for ray in _rays:
# 使用 world space state 发射射线检测是否碰撞
var collision := state.intersect_ray(self.global_position, self.global_position + ray.dir * ray.length, [], 0x1)
if collision:
ray.canMove = false
else:
# 射线没有碰撞前提下测试该射线方向是否可以移动
ray.canMove = ! self.test_move(self.global_transform, self.moveSpeed * delta * ray.dir)
# 射线的玩家比重为:方向向量点乘玩家方向向量
ray.playerWeight = targetDir.dot(ray.dir)
# 射线的移动比重为:方向向量点乘当前移动方向向量
ray.moveonWeight = moveDir.dot(ray.dir)

# 查询合适的用于跟踪移动的射线
func _findRayDirection() -> void:
var raysSameSide := [] # 与当前移动方向角度不大于90度的无碰撞射线集合
var raysOtherSide := [] # 与当前移动方向角度超过90度的无碰撞射线集合
for ray in _rays:
if ray.canMove && ray.dir.dot(_currentRay.dir) > 0:
raysSameSide.append(ray)
elif ray.canMove:
raysOtherSide.append(ray)

# 当前射线没有发生碰撞则找出与玩家方向最合适的射线
if _currentRay.canMove:
for ray in _rays:
if ray.canMove && ray.dir.dot(_currentRay.dir) > 0:
raysSameSide.append(ray)
for ray in raysSameSide:
if ray.playerWeight >= _currentRay.playerWeight:
_currentRay = ray
# 当前射线发生碰撞或者不能移动,找出能移动的合适射线
else:
var newRay : Ray = _currentRay
# 优先检测同一方向的射线
if ! raysSameSide.empty():
newRay = raysSameSide[0]
for ray in raysSameSide:
if ray.moveonWeight > newRay.moveonWeight:
newRay = ray
# 如果同一方向的射线全部发生碰撞,则检测另一方向
elif ! raysOtherSide.empty():
newRay = raysOtherSide[0]
for ray in raysOtherSide:
if ray.playerWeight > newRay.playerWeight:
newRay = ray
_currentRay = newRay

从代码上看,这种方式处理起来有点复杂,性能也不如 Navigation2D ,效果如下图:

Raycasts AI

比较一下优缺点:

  1. 优点:比较灵活,适用于各种复杂地形
  2. 缺点:实现起来不简单,算法貌似比较复杂
  3. 缺点:复杂的射线检测导致计算量较大,大量 AI 可能需要帧率的优化

上面两种方式各有千秋,视情况而选择。接下来,介绍一种结合路径点跟踪和 RayCast2D 射线而改进的 AI 寻路方式。

寻路方式三:使用位置记录和 RayCast2D 寻路

这个新的寻路方式来源于网上的一篇博文,原文链接: Enemy AI: chasing a player without Navigation2D or A* pathfinding ,效果图:

enmyAI-with-raycasts

原文中的代码我就不解释了,思路是这样的:

  1. 玩家根据时间片段不断记录自己的行踪位置
  2. AI 发射射线到目标位置检测是否有碰撞,如果无碰撞则继续前进
  3. 如果发生碰撞,则依次发射射线到玩家的每个行踪点,找出没有碰撞发生的点,按指向该点的路径继续跟踪

可以看出来,这个思路非常的简单而且有效!这里我的实现方式稍做了修改:我把记录玩家,也就是目标的行踪点数据放在了 AI 脚本中,而非玩家的脚本。核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
export(float, 0.0, 10.0) var recordTimeInterval = 0.1    # 记录跟踪目标位置的时间间隔
export(int, 1, 100) var maxTargetPositionRecords = 8 # 记录位置点的最大数量
export(float, 0.0, 100.0) var minDistanceToRecord = 1.0 # 允许记录位置距离上一点的最小距离

onready var _raycastTarget = $RayCastTarget as RayCast2D # 直接指向目标的检测射线
onready var _raycastStatic = $RayCastStatic as RayCast2D # 指向记录下的目标移动点的射线
onready var _trackTimer := $TrackTimer as Timer # 跟踪记录位置计时器

var _trackPoints := [] # 跟踪目标的位置点集合
var _trackTarget : Node2D = null # 跟踪目标,也可以用父类中的 target.get_ref() 代替

func _findMoveDirection(delta: float, target : Node2D) -> Vector2:
_trackTarget = target
if _trackTimer.is_stopped():
# 开启记录计时器
_trackTimer.start()

var dir := target.global_position - self.global_position
# 更新射线的指向,强制更新检测结果,如果没有碰撞则优先按此方向移动
_raycastTarget.cast_to = dir
_raycastTarget.force_raycast_update()
# 如果AI与目标之间有碰撞或者不能移动,则开始检测记录下的目标行踪点数组
if _raycastTarget.is_colliding() && _raycastTarget.get_collider() != target || self.test_move(self.transform, moveSpeed * delta * dir.normalized()):
# 循环遍历所有记录点,寻找可以移动的点
for point in _trackPoints:
var newDir = point - self.global_position
# 更新射线指向记录点,强制更新检测结果
_raycastStatic.cast_to = newDir
_raycastStatic.force_raycast_update()
# 如果指向该点的射线有发生碰撞,可以移动,那么按该方向移动
if ! _raycastStatic.is_colliding() && ! self.test_move(self.transform, moveSpeed * delta * newDir.normalized()):
dir = newDir
break

return dir.normalized()

Path Tracker AI

效果如上图,对于跟踪目标位置的记录是在 Player 脚本中还是 AI 脚本中,我觉得各有千秋,如果在玩家脚本中:

  1. 优点:只需要玩家 Player 一个脚本记录位置,所有 AI 都可以读取,非常方便
  2. 优点:大量 AI 进行路径跟踪时,这种情况显然更加节省内存

如果按我的方式,将记录点集合置于 AI 代码中,那么优缺点是:

  1. 优点:高度解耦, AI 跟踪谁就记录相应目标的位置信息
  2. 优点:高度自定义,每个 AI 记录目标位置的时间间隔可以不同,可以根据 AI 碰撞体大小而定
  3. 优点:更方便地 Debug ,比如画图
  4. 缺点:内存明显耗用较多

用哪种方式都行,总体来说,这种新的寻路方式确实令人大开眼界,简单而高效!这不正是我们想要的吗?哈哈。

三、总结

简单地讲述了三种寻路方式,应用场景各不相同,小游戏中可能三种情况都适用,而横屏游戏中可能需要另辟蹊径了。另外,前文提到的使用多个网格式 Area2D 节点检测路径做 AI 寻路的也有,大家可以参考这个视频: Optimierung, Pathfinding, Kickstarter Buch, Neuer Gegner! - Spindle DevLog 。切记生搬硬套,开发过程中视情况而定吧。

最后,示例代码已经上传,关于场景结构本文就不做介绍了,我简单用下图描述如何在 Godot 创建继承于父场景的子场景,以及修改场景实例的子节点属性:

Inherited Scene and Editable Children

AI 寻路相关资源(油管上的)我打算上传到云盘中,在后续文章中分享给大家。之后我还会发文解析如何将 Unity 中的 Pluggable AI With Scriptable Objects 系列转到 Godot 中,大家拭目以待吧。

本篇的 Demo 以及相关代码已经上传到 Github ,地址: https://github.com/spkingr/Godot-Demos , 后续继续更新,原创不易,希望大家喜欢! smile

PS: Demo 中画出来的射线状态(红色代表碰撞,其他颜色则表示无碰撞)有点问题,我还在研究中……

我的博客地址: http://liuqingwen.me ,我的博客即将同步至腾讯云+社区,邀请大家一同入驻: https://cloud.tencent.com/developer/support-plan?invite_code=3sg12o13bvwgc ,欢迎关注我的微信公众号:
IT自学不成才


Comments: