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

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

一、前言

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

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

尴尬的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 入手。

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

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

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

寻路方式一：使用 Navigation2D

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

以下是简单的代码：

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 导航寻路的优缺点：

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

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

Navigation2D AI

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

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

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

AI path finding by Game Endeavour

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

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

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

# 查找可行的移动方向，父类方法
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

比较一下优缺点：

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

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

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

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

enmyAI-with-raycasts

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

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

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

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 脚本中，我觉得各有千秋，如果在玩家脚本中：

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

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

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

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

三、总结

简单地讲述了三种寻路方式，应用场景各不相同，小游戏中可能三种情况都适用，而横屏游戏中可能需要另辟蹊径了。另外，前文提到的使用多个网格式 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 ，后续继续更新，原创不易，希望大家喜欢！

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

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

Godot

Godot游戏开发实践之三：容易被忽视的Resource Godot游戏开发实践之一：使用High Level Multiplayer API制作多人游戏（下）