当前位置：首页 > news >正文

Games104——游戏引擎Gameplay玩法系统：基础AI

news 来源：原创 2025/5/14 16:18:27

这里写目录标题

寻路/导航系统Navigation
- Walkable Area
- - Waypoint Network
  - Grid
  - Navigation Mesh（寻路网格）
  - Sparse Voxel Octree
- Path Finding
- - Dijkstra Algorithm迪杰斯特拉算法
  - A Star（A*算法）
- Path Smoothing
Steering系统
Crowd Simulation群体模拟
- 群体模拟模型
- - 微观方法：基于规则的模型
  - 宏观方法
  - 综合方法
- 避免碰撞
- - 基于力的模型
  - 基于速度的模型–速度障碍法
Sensing环境感知
经典决策算法
- 有限状态机（Finite State Machine）
- - 层次有限状态机（HFSM）
- 行为树（Behavior Tree）
- - 可执行结点
  - 控制结点
  - 黑板（Blackboard）

AI分为16、17两节课讲，大纲如下：
在这里插入图片描述

寻路/导航系统Navigation

基本思路：

Walkable Area

需要让ai知道哪些部分可以通过（包含走路、跳、翻越攀爬、载具可过等不同情况，还要考虑物理碰撞）。

其表达方式有Waypoint Network、Grid、Navigation Mesh、Sparse Voxel Octree（空间八叉树）等。每种方式都尤其优缺点，因此游戏经常使用多种方式结合。

Waypoint Network

早期游戏引擎用的多，通过设置道路关键点（如道路两边）并用算法插值关键点得到路网，寻路时先找到距离当前位置和目标位置最近的路网点，再通过路网连通（就像坐地铁一样），如下图：
在这里插入图片描述

优点是好实现、效率高，缺点是不方便动态更新、总走路中间

Grid

地图网格化，类似光栅化，如下图：
在这里插入图片描述

优点是便于动态更新，缺点是精确度取决于格子大小、存储空间浪费、效率比较低、难以表达层叠结构（比如桥）

Navigation Mesh（寻路网格）

现代游戏引擎最普遍的方法，即把地图上所有可通行的区域连起来（用凸多边形），主要用物理碰撞与预测路线，既可以解决路线僵硬问题，又能应对层叠结构
在这里插入图片描述

优点是支持3d、精确、灵活、动态，缺点是生成Navigation Mesh的算法非常复杂，并且只能“寻路”，不能飞机3d空间导航

怎么生成Navigation Mesh呢？
现在基本都是自动生成，用一些开源库如recast，voxelization后去计算可通行区域；然后再通过计算离边缘最近的edge voxel，得到一个类似距离场的东西；

再找到每个区域距离边缘最远的中心点，用洪水算法向外扩散，直到覆盖所有区域，在通过进一步处理（比如连通区域变为凸多边形之类，比较复杂），这就是我们的生成的Mesh了
Polygon Flag
通过地形标签生成不同区域的mesh
Tile
那如果地图在动态变化怎么办，比如路障被用户打掉了。可以使用Tile把地图分块，部分地图更新后只需要重新计划该块tile即可

把空间分成一个个Tile，当Tile改变时只需要更新这个Tile即可
Off Mesh Link
建立一些手动的连接点和连接线可以让寻路变得更加复杂，增强拓展性

Sparse Voxel Octree

把空间体素化，通过求交导航。可以表达3d空间的导航，主要用于航空航天游戏。但缺点是存储消耗大
通过八叉树划分空间
在这里插入图片描述

Path Finding

以上每种方式都可以把各个几何元素的中心连接为点图，只要找到最短路径即可。
在这里插入图片描述
所谓寻路问题主要就是解决两个问题：

找到一条起点到终点的道路
尽可能的少走弯路

这个过程也有几种算法，比如经典的：

深度优先搜索（Depth-First Search）：找到一个分支一直走，如果没有路就退回来，直到走到终点为止（时间换空间）

广度优先搜索（Breadth-First Search）：每一个step都向全部子节点扩散一步，直到找到终点（空间换时间）
但以上两种方式都比较费，并且不能计算加权最短路径，所以还需要更多算法帮助：
在这里插入图片描述

Dijkstra Algorithm迪杰斯特拉算法

可以解决有权图中最短路径问题，参考这个大佬的文章：图论：Dijkstra算法——最详细的分析，图文并茂，一次看懂！
截图自大佬博客:
在这里插入图片描述

但是对于游戏来说，有时候并不需要真的“最优路径”，只要按照大致方向走就行了，所以引入了下边的A Star算法

A Star（A*算法）

用的最普遍，是一种启发式算法，通过有选择的节点搜索找到最短路径，因此更快，常用于游戏或机器人导航。
原理是通过计算一个代价函数：f = g（从原点已经走过的路程的代价，一般累计路程距离） + h（到终点还有多远的代价，一般用欧拉距离或x+y），来逐步寻找最优下一步的路径（按照网格或mesh的划分），原理有些类似梯度下降。
在这里插入图片描述

在这里插入图片描述

Path Smoothing

把无效的运动尽可能踢掉

Funnel Algorithm烟囱算法：类似于人走路时对道路的感知，如下图：
在这里插入图片描述

从起始点看向下一个三角形，视野卡在三角形两端，如果能全部在视野中，就继续看下一个三角形，更新视野，直到某一个三角形被挡住一部分时，左边被挡沿左视野边走，右边被挡沿右视野边走；
走到被卡视野的遮挡点后，再重新进行上述过程；
如果迭代过程中发现终点就在视野里时则直接向终点走。

Steering系统

载具的移动受限于它们的移动能力：油门、刹车、转向等，所以经常会在寻路中被障碍物卡死

steer behavior：

Seek/Flee：包括追踪、巡逻、流场跟随、路径跟随
速度匹配：快到目标点减速，减速到速度为0时刚好到达目标点，比如火箭发射会用到
一致性：角速度的加速和减速，比如npc看向主角

Crowd Simulation群体模拟

现在的游戏城市环境交互等越来越丰富，那群体模拟必不可少，比如一群鸽子突然飞走，一群npc四散逃跑等。群体模拟需要做到：避免碰撞、成群的来回移动（Swarming）、编队运动（motion in formation）

群体模拟模型

群体模拟模型大致有三种：
微观方法（Microscopic)：自底向上的定义每个个体的行为，合起来就组成了群体行为。
宏观方法(Macroscopic)：定义群体宏观的运动趋势，所有个体按照该趋势移动。
综合方法(Mesoscopic)：将群体分组。既有宏观的趋势，也有微观的个体行为。

微观方法：基于规则的模型

比如动物的群体动力学，用简单规则控制每个个体的运动：

分离（Separation）：避开自己的所有“邻居”（斥力）
凝聚性（Cohesion：朝向群体的“质心”移动
一致性（Alignment）：和邻近的对象朝向同一个方向移动

在这里插入图片描述

好处是规则简单，坏处是宏观上是不可控且不怎么受人影响。

宏观方法

从宏观的角度模拟人群的运动，通过设置可通行区域和有势场或流体力学的控制运动，类似粒子系统运动？
在这里插入图片描述

综合方法

结合了宏观和微观方法，把群体分为很多小组，每组分别运动，同时组里的个体也有一点自己的区别。比如红警里圈出一群小兵运动时就是这样。
在这里插入图片描述

避免碰撞

这部分如果给ai做效率非常低，所以需要用一个碰撞系统帮助ai决策

基于力的模型

相当于使用距离场给障碍物增加一个反向力
在这里插入图片描述

好处：可以被拓展去模拟更慌乱的人群的行为。
坏处：类似于物理模拟，模拟的步骤应该足够小。

基于速度的模型–速度障碍法

类似人眼处理方式：当两个物体在同一速度线上行走，就都靠左边避让一点。
在这里插入图片描述

当参与的对象不止两个时，A 对 B 的避让可能又会影响到 C。所有需要做一些优化：Optimal Reciprocal
Velocity Avoidance（ORVA）。其数学复杂度非常高，不过实际中也会用基于力的方式替代（结果没那么丝滑但能用）
在这里插入图片描述

Sensing环境感知

对世界的感知是我们和ai决策的依据，感知分为内部和外部信息：

内部的信息包含位置、血量、护甲状态、增益状态、可以被自由获取的东西等等；外部的信息包含静态空间信息如Tactical Map战术地图、掩体等和动态信息如influenceMap人群热力图、视角图、游戏物体等。
在这里插入图片描述
这些非常类似人类对世界的感知（并不是上帝视角），有视觉、听觉并随距离衰减，有活动范围、视野等，但如果感知太多会影响性能，因此一般会取舍几个，并范围内共享信息

经典决策算法

经典决策算法有：
有限状态机（Finite State Machine）
行为树（Behavior Tree）：AI最核心的体系
层次任务网络（Hierarchical Tasks Network)
目标驱动的行为计划系统(Goal Oriented Action Planning)
蒙特卡洛搜索树(Monte Carlo Tree Search)
深度学习（Deep Learning)

有限状态机（Finite State Machine）

根据一些条件转换（Transition）一个状态到其他状态
在这里插入图片描述
比如吃豆人的状态机示例：

好处：容易执行、容易理解、对于简单例子，应对起来非常快
坏处：可维护性差，特别是添加和移动状态；重用性差，不能被应用于其他项目或角色；可扩展性差，很难去修改复杂的案例

层次有限状态机（HFSM）

把状态机分为很多层或模块，每个状态机之间有相互的接口，复杂度可控；虽然能部分解决上述问题，但是会造成一定的性能下降，难以跳模块，反应速度也会下降。15年前的很多游戏就是这么做的，属于“古老”的方法。
在这里插入图片描述

行为树（Behavior Tree）

行为树和人的思考类似，例如人碰到一个敌人，会根据自己的状态来选择追击还是撤退。（一些复杂的商业决策也有类似决策树的逻辑）
在这里插入图片描述

可执行结点

分为条件节点和动作节点
条件结点可以立马执行完，而行为结点有一定过程，例如追鬼，首先得有寻路系统，然后还需要转向系统。行为也分为正在进行和失败等几种状态。
在这里插入图片描述

控制结点

在这里插入图片描述

Sequence 顺序执行，&&：从左到右便利子节点，如果某个子节点返回 Failure 就停止整个行为，或者时所有子节点都成功执行，返回 Success，并执行该行为。
Selector 条件执行，||：根据条件尝试所有子节点，一旦某个子节点满足条件，立马作出该决策。
Parallel并行执行：一个 AI 体可以同时进行多个行为，例如对于射击游戏来说可以同时进行移动和射击。
Decorator装饰节点：起修饰作用，例如循环执行、执行一次、计时器、定时等。

注意行为树tick更新时要每一帧都从根节点开始判断，这一点上也可以优化为正常从上一帧的节点继续，但某些优先级高的event会更新整棵树。
在这里插入图片描述

黑板（Blackboard）

用于记录行为状态，用于把数据与逻辑分离
在这里插入图片描述

行为树的好处：
模块化、层级组织（每个子树可以被看作是一个模块）
可读性高
容易维护，并且修改只会影响树的一部分
反应快，每个 tick 会快速的根据环境来改变行为
容易 Debug，每个 tick 都是是一个完整的决策。
行为树的坏处
如果不优化，每个 tick 都从根节点触发，会造成更大的开销
反应性越好，条件越多，每帧的花销也越大

QA
行为树和if else有什么区别：if else就是最简单的行为树，行为树类似goto、jump等语言指令
ai如何从环境中提取数据（感知）：环境数据类型多数量多，其实很难读取，可以用引擎中的反射等技术解决；ai提取数据时效率其实不高，需要对感知做规划和指令
如何处理垂直邻面的NavMesh生成？根据高度设置为断开的悬崖或是可通过的障碍，如果可以攀爬另说

原文链接：

这里写目录标题

寻路/导航系统Navigation

Walkable Area

Waypoint Network

Grid

Navigation Mesh（寻路网格）

Sparse Voxel Octree

Path Finding

Dijkstra Algorithm迪杰斯特拉算法

A Star（A*算法）

Path Smoothing

Steering系统

Crowd Simulation群体模拟

群体模拟模型

微观方法：基于规则的模型

宏观方法

综合方法

避免碰撞

基于力的模型

基于速度的模型–速度障碍法

Sensing环境感知

经典决策算法

有限状态机（Finite State Machine）

层次有限状态机（HFSM）

行为树（Behavior Tree）

可执行结点

控制结点

黑板（Blackboard）

相关文章：