一、前言
AI 一直是游戏开发中一个热门词汇，当然这不是人工智能的那个 AI ，而是指有着人类思想的 NPC 或者聪明的敌人等等。根据游戏的类型和复杂程度， AI 的实现可以很简单，也可以非常复杂。作为新手，本文不会讨论所谓高级 AI 的实现方式，那太不现实，不过我们可以先从最简单、最常用也是最实用的 AI 寻路探索开始入手，进而丰富我们的小游戏！
本文目标是让我们这些新手游戏开发者们都：能用得起 AI 、能用好 AI 、能做 ai （别念出声！），嘿嘿！其实，游戏中的寻路方法非常之多，我所见到过的就有好几种，这些方法有难有易，具体实现机制见仁见智，我现在将自己熟悉的几种方式写出来，比较其优缺点，并和大家一起讨论讨论，如何避免下图中的尴尬。当然，如果您有其他更好的方法请务必留言告诉我，非常感谢！
主要内容： AI 寻路新方法探索
阅读时间： 8 分钟
永久链接： 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 把移动物体当做无限小的点来处理，导致了寻路可行性大减，如下图：
也有一些补救措施：修改导航地图；扩大可行区域与障碍物之间的间隙；尽量使用圆形、胶囊型碰撞体。
寻路方式二：使用 Ray/RayCast2D 射线
如果在普通寻路过程中能够提前检测到故障而绕行，那么是否可以避免碰撞的发生呢？我在网上看到了 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 ，效果如下图：
比较一下优缺点：
- 优点：比较灵活，适用于各种复杂地形
- 缺点：实现起来不简单，算法貌似比较复杂
- 缺点：复杂的射线检测导致计算量较大，大量 AI 可能需要帧率的优化
上面两种方式各有千秋，视情况而选择。接下来，介绍一种结合路径点跟踪和 RayCast2D 射线而改进的 AI 寻路方式。
寻路方式三：使用位置记录和 RayCast2D 寻路
这个新的寻路方式来源于网上的一篇博文，原文链接： Enemy AI: chasing a player without Navigation2D or A* pathfinding ，效果图：
图片过大，请参考原文，或者关注本人公众号
原文中的代码我就不解释了，思路是这样的：
- 玩家根据时间片段不断记录自己的行踪位置
- 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()
效果如上图，对于跟踪目标位置的记录是在 Player 脚本中还是 AI 脚本中，我觉得各有千秋，如果在玩家脚本中：
- 优点：只需要玩家 Player 一个脚本记录位置，所有 AI 都可以读取，非常方便
- 优点：大量 AI 进行路径跟踪时，这种情况显然更加节省内存
如果按我的方式，将记录点集合置于 AI 代码中，那么优缺点是：
- 优点：高度解耦， AI 跟踪谁就记录相应目标的位置信息
- 优点：高度自定义，每个 AI 记录目标位置的时间间隔可以不同，可以根据 AI 碰撞体大小而定
- 优点：更方便地 Debug ，比如画图
- 缺点：内存明显耗用较多
用哪种方式都行，总体来说，这种新的寻路方式确实令人大开眼界，简单而高效！这不正是我们想要的吗？哈哈。
三、总结
简单地讲述了三种寻路方式，应用场景各不相同，小游戏中可能三种情况都适用，而横屏游戏中可能需要另辟蹊径了。另外，前文提到的使用多个网格式 Area2D 节点检测路径做 AI 寻路的也有，大家可以参考这个视频： Optimierung, Pathfinding, Kickstarter Buch, Neuer Gegner! - Spindle DevLog 。切记生搬硬套，开发过程中视情况而定吧。
最后，示例代码已经上传，关于场景结构本文就不做介绍了，我简单用下图描述如何在 Godot 创建继承于父场景的子场景，以及修改场景实例的子节点属性：
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 ，欢迎关注我的微信公众号（第一时间更新+游戏开发资源+相关资讯）：
