【笔记】《游戏编程算法与技巧》7-12

绪

本篇是看完《游戏编程算法与技巧》后做的笔记的下半部分. 这本书可以看作是《游戏引擎架构》的入门版, 主要介绍了游戏相关的常见算法和一些基础知识, 很多知识点都在面试中会遇到, 值得一读.

全文8.2k字, 预计需要27分钟

7 物理

平面的表示

1. 游戏中习惯用点斜式来表示平面, 需要: 平面上任意一点P, 法线n, 平面到原点的最小偏移(也就是原点法线方向上的距离)d

1. 三角形可以很方便地确定一个平面:
   1. 任意一个顶点可以作为P
   2. 两个边向量叉乘后标准化可以得到法线n
   3. 由向量点乘公式可以知道, 将任意点P与原点形成的向量与法线相乘得到的结果就是点在法向量上的投影距离, 由于点在平面上, 法线与平面垂直, 因此此时的结果就是距离d
2. 通常表示平面的结构体中只保存法向量n和距离d, 然后通过将某个需要判断的点带入形成的平面公式中是否为0来判断点是否在平面上

射线与线段

1. 射线通常以参数方程表示, 需要: 起点R0, 射线方向向量v, 发射持续时间t

1. 实际使用的时候不会使用真正的射线, 而是使用有终点的线段
2. 通常表示射线的结构体中保存起点坐标和终点坐标, t由[0, 1]表示, 0代表起点坐标, 1代表终点坐标

各种碰撞体

包围球: 最常见也最简单, 利用两个点之间的距离差值与半径和做比较来判断是否碰撞, 适合作为碰撞检测的最外一层快速筛选判断目标

class BoundingSphere{
    Vector3 center;
    float radius;
};

轴对齐包围盒(AABB): 也相当常见, 每条边都与轴平行, 用两个角点来表示, 常用于人形角色, 因为人形角色通常在xy平面上变化很小(旋转), z轴上不改变(身体一般垂直朝上)

class AABB{
    Vector3 min_p;
    Vector3 max_p;
};

朝向包围盒(OBB): 不再要求与轴平行的包围盒, 核心就是用完整的8个点或6个面表示盒子, 且盒子随包围的目标的旋转而旋转

胶囊体: 常用于人形角色, 作为AABB的替代. 可以看作带有半径的线段

class Capsule{
    Vector3 start_point;
    Vector3 end_point;
    float radius;
};

凸多边形(凸包): 一般从目标模型的一些显著的顶点上采样并连接生成的一个新多边形, 判断效率很低但是精准度是最高的

组合几何体: 也就是对每个模型嵌套多个不同优先级的碰撞体, 然后从简单到复杂逐步排除场景中需要渐层的碰撞体, 直到最后用最精确的方法判断剩余的碰撞体, 从而在效率和效果上进行平衡

碰撞检测

1. 球与球: 用球心的距离差与半径和比较判断, 为了减少开平方的开销, 通常直接对比平方的结果

1. AABB与AABB: 检测无交叉速度更快, 以下四个条件(2D形式)只要满足了一个就能返回当前AABB无交叉, 都不满足时就交叉了.

1. 线段与平面: 核心就是联立将线段的公式代入平面的方程中, 判断是否存在t的可行解(0~1内). 注意这里t的求解式中, 要通过提前判断v与n是否平行来排除除零异常(平行时, 带入判断线段的点是否在平面上)

1. 线段与三角面: 先判断是否与三角面形成的平面相交, 然后判断这个交点是否在三角形内. 第一步如上, 第二步通常采用凸多边形扫描法, 从某个顶点开始, 以A为顶点, P为交点为例, 如果

, 也就是三个叉乘都同向(也可以在规定顶点序为顺序的情况下判断是否与法线同向), 那么这个点就处于内部. 这个算法可以推广到所有同平面的凸多边形, 同向判断通常以点乘后的正负号来判断

1. 球与平面: 最简单的方法就是计算球心在目标平面法线n方向上到原点的距离dC, 然后计算目标平面到原点的距离d, 两者相减的绝对值小于球半径那么存在相交

1. 胶囊与胶囊(球形扫掠体): 主要用于例如子弹检测的连续碰撞检测(CCD)情况. 胶囊体由球体上一帧的位置和当前帧的位置作为起点和终点, 判断思路和射线检测类似, 核心是判断能否找到一个合法的t(同一个)使得两个球心在t处的距离小于等于半径之和
   1. 首先球心由下式表示:

   

   1. 用平方简化距离计算得到下式

   

   1. 代入射线方程并提取公因式得到

   

   1. 用AB对式子进行简写

   

   1. 展开完全平方式并移项, 得到下面关于t的一元二次方程

   

   1. 以此提取abc后可以用方程判别式来判断是否存在合法的根

   

   1. 合法根有下面三种情况, 至此就能初步返回是否相交了. 但是要判断t是否合法和具体的t还需要完整解方程, 将[0, 1]之外的部分排除就能得到最终的相交结果

   

碰撞响应与优化

1. 刚体碰撞的响应结果一般是弹性碰撞, 也就是速度方向变为反射方向
2. 首先利用上面的扫掠体算法计算出碰撞的交点中t较小的那个时间点T, 那就是碰撞开始时的时间点, 用T计算出碰撞时的速度
3. 然后利用T时两个球的坐标, 按照其半径线性插值就能得到精确的碰撞点, 然后这两个球心的连线就是切平面的法向量线, 借助这个创建碰撞点上的切平面
4. 使用前面的算法, 对当前球, 按照速度和切平面求解出反射向量, 这个反射向量就是反射速度的方向
5. 具体碰撞后各自的速度会受到恢复系数的影响, 恢复系数为1时代表完全弹性碰撞. 定义恢复系数e为

1. 然后根据动量守恒可以推出碰撞后各自的速度, 合力分配给对应的方向即可

1. 碰撞检测和响应只能在一对物体间进行, 因此对于对象很多的场景复杂度就非常高, 一种效率优化方法是将场景使用八叉树(2D则是四叉树, 或使用更复杂的二进制空间分割BSP)进行分区, 递归分区直到一个叶子只保留一个对象, 然后从外到内以树的节点形成的包围体作为单位进行碰撞检测从而有序筛去大部分无用的对象

基于物理的运动

1. 游戏中的物理基本都是牛顿物理中的线性力学部分, 核心是牛顿三定律和对力/速度/加速度等物理量的积分和求导操作, 主要是积分.
2. 由于游戏是以帧为单位的离散模拟, 因此采用数值积分代替. 数值积分的最大问题是由于计算的不连续, 误差可能在计算中不断累积
3. 大多数游戏的物理模拟部分都采用固定时间步长(不可变帧)进行计算, 且很多时候物理部分的计算帧数比渲染帧数更高(例如120fps)
4. 游戏物理的基础计算: 通过a=F/m来求出加速度, 从而按帧数值积分改变速度, 进一步数值积分从而改变物体的位置
5. 欧拉积分, 最简单的算法, 由于速度不准确导致误差不断累加:

1. 半隐式欧拉积分, 使用了相对准确的速度, 整体更加稳定:

1. Verlet积分, 用中点速度作为当前帧的平均速度, 更稳定但需要用平均来计算中点速度:

1. Runge-Kutta方法: 使用四阶泰勒近似求解, 但是计算代价过大, 大部分游戏不适用
2. 部分游戏在描述旋转的时候会引入角力学和对应的积分, 也就是关于角的各种物理量的操作

8 摄像机

各种摄像机

1. 固定摄像机: 常见于带有恐怖元素的游戏, 比较早期, 随着玩家位置选择场景中某个固定的相机使用
2. 第一人称摄像机: 一般在眼睛处放置, 身体采用一个只有手臂或者特殊的部件组成的模型
3. 跟随摄像机: 就是常见的各种第三人称摄像机
4. 场景切换摄像机: 播片尤其是场景展示的片时, 放置在场景各处或者依照设定好的样条曲线移动的摄像机

摄像机的参数

1. 视场(FOV): 人眼共有最大180度的视野, 但是能够比较清晰使用的只有中间的120度
2. 显示器的推荐使用距离大约是对角线长度*1.2, 因此显示器通常是电视的主机游戏并不需要太大的视场, 而距离很近的PC游戏则需要更大的视场才不会让人感到难受. 家用机游戏大约需要40-65度, PC游戏需要90度

1. 视场太大时会有鱼眼效果, 不推荐太大的视场, 最大不要超过120度
2. 游戏的宽高比是射击之初就应该决定好的, 主要是4:3, 16:9, 16:10
3. 一般宽高比切换时都是以16:9作为基准, 切去左右部分来适配其它宽高比

摄像机的实现

1. 基础跟随摄像机: 相机eye始终在目标forward的后上方某个固定距离的位置, 相机forward是eye与目标的连线, 相机的forward与目标的up叉乘得到相机自己的left, 然后forward和left叉乘得到相机自己的up
2. 弹性跟随摄像机: 相机以弹性模拟的效果调整eye, 本身是基础跟随摄像机, 视觉效果舒服很多.

1. 旋转摄像机: eye记录的是相对于目标本身的偏移量, 从而将所有旋转处理为相对于原点的旋转. 通常变量是偏航yaw和俯仰pitch, 一般不桶滚.
2. 计算旋转摄像机有两种思路:
   1. 偏移旋转: 先将向量(0, 1, 0)进行yaw旋转得到forward, 然后配合up向量叉乘出正确的left向量, 再对这个left进行pitch旋转, 得到正确的forward向量, 叉乘得到正确的up向量, 在forward方向上实行和(0, 1, 0)相同的offset偏移即可.
   2. 球面坐标: 直接依据角度计算出球面坐标然后将球半径设置为偏移值即可
3. 第一人称摄像机: 摄像机位置总是角色位置加上某个偏移, 但使用旋转摄像机的思路将target在单位球上进行变换即可. 注意为了防止死锁pitch一般存在取值限制
4. 样条摄像机: 用下面经典的4点Catmull-Rom样条就可以了. 用一个很小的deltaTime来计算两点的差值就可以近似得到切线方向, 切线方向可以作为相机的forward, 很方便

摄像机算法

1. 最简单的解决摄像机碰撞的方法是从摄像机向目标位置发射射线, 如果碰撞到任何物体那么将摄像机移动到物体前面, 这种方法效果很突兀
2. 另一种方法是用一个物理对象表示摄像机
3. 还有一种流行的方法是让阻挡在中间的对象淡出或消去, 比较自然
4. 相机拣选: 鼠标选择画面中一个2D点, 然后将z补为0和1, 正好是前后投影面. 然后乘上反投影矩阵:

得到这两个点的三维坐标. 以这两个点作为射线的起点和终点, 计算t最接近近平面的交点就是相机拣选的结果

9 人工智能

寻路基础

1. 理想的寻路算法是求解最短路径, 合适的搜索空间是效率的关键, 但是搜索空间并不影响寻路算法的使用
2. 方格结构: 将世界构造为图数据结构, 世界划分为相等的格子(正方形/六边形), 然后用邻接表或邻接矩阵表示和寻路. 常见于策略游戏中
3. 寻路节点: 在世界中摆放一系列的节点表示可以到达的区域, 节点与节点之间有边连接, AI借助这个图数据进行寻路. 这种方法使得AI只能在边上游走, 显得不自然, 且必须给世界放置足够密集的节点才比较精确, 却又降低了效率
4. 导航网格: 用凸多边形将世界划分, 分为可行和不可行的多边形, 多边形内部都是完全可行的区域(支持任意行走), 多边形本身是寻路的节点(在多边形之间运行寻路算法). 导航网格可以完全自动生成, 且AI行走更加自然, 近年来比较常用

贪婪优先算法

1. 最简单的启发式搜索算法, 核心是利用估算的距离进行节点选择
2. 以正方形网格为例, 根据角色是否允许对角移动, 贪婪优先算法通常使用曼哈顿距离或欧几里得距离来在假定不存在障碍物的情况下对距离估算, 用h(x)表示

1. 在算法的每一刻, 查看目前路径中还没尝试的位置中, 往哪个位置前进后新的距离是最短的就选择哪一个.
2. 为了避开递归的使用, 对每个节点保存指向上一步的节点的指针prev和当前节点对应的距离值h
3. 然后还需要一个开放集合和一个封闭集合, 分别保存了目前需要考虑的节点和已经无法使用的节点. 其中开放集合通常用优先队列实现(为了快速取出h最小的节点), 封闭集合通常用BST实现(为了快速判断待测节点是否属于封闭集合)
4. 算法:
   1. 首先将起点加入开放集合
   2. 从开放集合中取出h最小的节点, 将这个节点加入封闭集合
   3. 将这个节点周围邻近的非封闭节点加入开放集合, 记入刚才那个封闭节点到这些节点的prev中
   4. 重复2~3直到到达终点, 如果还未到达终点开放集合就为空了, 返回寻路失败
   5. 到达终点后, 从终点节点开始利用prev形成的链表借助栈翻转追溯就能得到终点到起点的路径
   6. 如果将寻路算法改为从终点到起点的寻路就可以避开翻转计算

A*算法

1. A*, 读作A-Star算法, 在贪婪优先算法的基础上更改了寻路估价公式, 每次迭代都选择f(x)最小的节点

, 其中g(x)是当前路径的最小开销

1. A*的特点是在寻路过程中会根据附近封闭节点的g值来更新自己的g值和prev指针, 从而得到一条尽量短的路径. A*算法的缺点是计算量比贪心优先更大
2. 算法:
   1. 首先将起点加入开放集合, 设置好节点的g, h, f
   2. 从开放集合中取出f最小的节点
   3. 遍历这个节点的所有邻接节点, 排除掉所有处于封闭集合的节点
   4. 如果邻接节点不存在于开放集合中, 那么计算这个邻接节点的f, g, h, 其中g值为当前节点的g值加一, 然后压入开放集合
   5. 如果邻接节点存在于开放集合中, 那么比较邻接节点的g值与当前节点的g值, 如果邻接g小于当前g, 那么将当前prev指向这个邻接节点, 然后将当前节点的g设置为这个小邻接g加一
   6. 循环直到遍历完当前节点的所有邻接节点, 将当前节点加入封闭集合中
   7. 和贪心优先算法一样, 重复直到找到最终路径, 此时由于路径动态更新的原因可以得到比贪心优先更好的路径

Dijkstra算法

1. 不属于启发式搜索, 特点是代价函数f(x)只考虑当前路径开销g, 不考虑距离估计, 因此需要访问更多的节点, 速度较慢但是能确保得到最优路径
2. 历史: A*算法是对Dijkstra算法的改良
3. 这类最短路径算法主要用于在图中存在多个目标节点时, 返回最近的节点

状态机

现代游戏中的AI角色基本都是状态机驱动的, 例如下图的潜行游戏敌人状态机

最简单的状态机以一系列的枚举值作为标记, 在update中通过switch来实现不同状态下的AI行为, 通过设置枚举值来切换状态. 这种实现的缺陷是很不灵活, 会导致一个难读的update并难以实现状态代码的复用, 可能需要层层继承和多继承来节约代码, 除非AI非常简单否则不推荐

状态机设计模式: 通过类的组合来实现状态机. 每个对象有自己的状态, 所有状态都继承自AIState基类例如:

class AIState{
   // 有时候需要通知控制者做一些事
   AIController* Parent;
   // 下面是每个状态都需要的函数
   virtual void Update(float DeltaTime) = 0;
   virtual void Enter() = 0;
   virtual void Exit() = 0;
};

然后每个状态都依靠AIController类进行切换即可, 实现了状态和状态管理的解耦, 而且方便了代码复用

class AIController{
   AIState* CurrentState;
   void Update(float DeltaTime){
      CurrentState->Update(DeltaTime);
   }
   void SetState(AIState* NewState){
      CurrentState->Exit();
      CurrentState = NewState;
      CurrentState->Enter();
   }
};

AI的描述中, 策略一般指一系列特定的目标, 例如提高总体科技等级等, AI通常有一个优先级容器存放多个策略, 同时选择一个或者多个不冲突的策略作为当前的广泛目标

然后对于每个策略, 都应该能够生成一系列的计划, 也就是AI当前要进行的行为. 通常来说计划由状态机切换来实现, 计划中的每一步都可以是状态机的一个状态, 游戏AI就这样在策略和计划的调控下, 依据状态机来与玩家互动

10 用户界面

菜单系统

1. 典型的菜单系统需要实现: 菜单栈, 按钮, 打字输入
2. 菜单栈: 通常需要所有菜单继承自同一父类, 然后显示的时候只显示(或者堆叠显示)栈顶的菜单, 打开新菜单就是压栈, 关闭就是出栈. 为了方便使用, 菜单系统本身通常拥有栈中每个元素的引用
3. 按钮: 每个按钮应该有自己的感应区, 然后以类似链表的形式组织在菜单系统中, 并且拥有 未按下, 选择中, 按下 三个状态方便用户识别
4. 打字输入: 标准输入输出非常不适合游戏, 游戏需要图形效果. 游戏通常让画面渲染一个字符串, 每当我们按下一个键盘按键时, 将这个按键识别并转换为对应的字符, 再将这个新的字符连接到那个字符串的尾部, 然后将字符串渲染, 从而一方面实现了硬件输入与软件响应的分离, 又实现了可视化可订制的输出显示效果

HUD系统

1. HUD系统通常在游戏场景渲染之后再在顶层绘制一次
2. HUD中有很多元素, 例如场景路点箭头, 可能是渲染在3D空间中的, 那么这些元素要记得在相机之后再渲染, 且需要获取相机当前显示的信息, 从而保证HUD元素位置和结果的正确
3. 准心: 也就是鼠标拣选算法的延伸, 很多射击游戏有准星按拣选到的对象的信息进行变色/变形的功能
4. 雷达: 雷达通常是一个从游戏信息中额外渲染的2D场景, 雷达中的子场景的朝向通常和人物朝向相同, 且场景信息和其它对象信息都按所需进行不同的渲染

其它UI问题

1. UI最好能够支持多套分辨率, 解决方法是使用相对坐标进行UI设计, 使得相同比例而分辨率不同的屏幕也都能渲染出正确的结果
2. 如果无法使用相对坐标, 那么对UI按照分辨率进行缩放是一种可取方案
3. 本地化很重要, 支持本地化的关键在于将游戏中所有需要渲染出来的文字都保存在独立的类似JSON格式的外部文件中, 以Map的形式读写, 从而让渲染的时候能用key从文件中找出需要渲染的文字, 也就自然支持了本地化

11 脚本语言和数据格式

游戏中的脚本语言

1. 游戏中使用脚本语言是为了加快游戏逻辑开发的效率, 提高开发的灵活性
2. 需要快速迭代的部分(例如AI状态机和UI配置)应该用解释型的脚本语言快速实现和测试, 需要稳定且高效计算的部分(例如渲染和寻路算法)应该用C++等编译型的开发语言进行
3. 最好的选择方法就是从脚本语言开始开发, 直到遇到性能瓶颈和某些性能敏感的模块时再用编译语言
4. 常用的脚本语言有Lua, Python, 和例如UE4支持的可视化编程(蓝图)
5. Lua的优势是解释器非常轻量, 且非常容易与C/C++相互调用, 而且语法类似C语言方便学习

脚本语言的实现

1. 实现脚本解释器的原理与实现编译器类似, 整体流程大致如下
2. 标记化(词法分析): 通过正则表达式匹配之类的算法, 将代码进行扫描, 划分为大批关键词和标识符的顺序集合
3. 语法分析: 使用巴科斯范式(BNF)从划分的词语中按照定义好的语法规则生成对应的抽象语法树(AST). 语法树是一种树结构, 其叶节点是操作数, 中间节点是操作符, 可嵌套构造
4. 以后序遍历的形式遍历语法树, 将对应的每个子树的叶节点和中间节点翻译为底层开发语言进行计算, 或者作为解释型语言通过调用内置的函数来实现表达式的计算
5. 遍历语法树时, 所有运算结果保存在虚拟的栈中进行操作, 直到完全遍历完成就实现了解释

游戏数据的格式

1. 游戏外部数据主要有二进制文件和文本文件两种. 二进制文件用于表示携带大量信息的资源, 例如图像, 文本文件保存需要方便细节修改的资源, 例如场景配置文件
2. 二进制文件不支持版本管理, 且很难直接修改, 但文本文件过于方便编辑, 容易被玩家破解
3. 一种折中是在开发过程中使用文本文件, 直到发布的时候加入一个"烘焙"步骤, 将所有文本文件转为二进制文件压缩保存
4. 二进制文件通常没有固定格式, 将内部数据保存为二进制文件的过程称为序列化
5. INI: 最简单的文本文件, 文件内容都是键值对, 只适合简单数据, 一般用于配置文件
6. XML: 类似HTML的标记文件, 可以自定义标签和属性, 因此使用方便. 缺点是需要很多额外的字符进行控制, 可读性较差且生成的文件比较大
7. JSON: 游戏中常用的轻量级数据格式, 可读性好但生成的文件也比较大

12 网络游戏

各种协议

1. IP: 传输层协议. 将数据从一个IP地址传到另一个IP地址. 分为IPv4(32位地址)和IPv6(128位地址)两种
2. ICMP: 网络层协议. 不用于数据传输, 而主要用于发送回声包来测量两台机器间的延迟. 发送者将当前的时间戳放入数据帧, 然后接收者原样发回, 通过接收到的时间和之前放入的时间戳对比计算延迟时间. ICMP通过校验和来确保可靠
3. TCP: 网络层协议. 基于连接的, 可靠的, 保证顺序的协议. 两台计算机需要先握手建立连接, 然后传输中通过不断校验与重发保证数据包的可靠和有序. 对于高实时性要求的游戏来说, TCP的延迟太大了
4. UDP: 网络层协议. 无连接, 不可靠, 因此会出现丢包问题导致游戏体验变差. 而且为了在不可靠传输中保证一定的顺序性, 通常在UDP数据包中增加一些额外数据, 例如顺序号, 让接收者可以对顺序可靠性增加一定控制. UDP是大多数游戏所采用的网络层协议
5. 处于折中, 也可以对游戏关键数据用TCP传输, 其余数据用UDP传输

服务器/客户端模型

1. 由一台服务器和多台客户端组成, 也称为中心型结构
2. 服务器认为是游戏的权威判断者, 客户端的所有关键行为都需要发送给服务器, 由服务器计算, 验证行为是否合法并计算行为造成的后果, 然后通知给相关的其它客户端
3. 因此游戏的很多逻辑判断实际上处于服务器上, 需要实现单人模式的游戏应该设计将单人模式作为此模型中一种特殊的多人模式(服务器和客户端处于同台机器上)开发
4. 为了优化此模型的延迟, 一般会在客户端根据最近服务器返回的数据进行插值, 从而减少服务器延迟对用户体验的影响. 也就是在本地同样进行一部分服务器上的判断用于流畅地渲染, 一旦服务器返回的结果与当前客户端上模拟的结果冲突, 则将客户端的结果矫正
5. 当服务器和客户端在同台机器上时, 作为服务器的机器上的玩家会有主机优势, 因为延迟为0
6. 如果服务器崩溃那么所有客户端都会崩溃
7. 一般的解决方法是设立独立的专用服务器, 既平衡了延迟问题, 又减少了崩溃的可能性

点对点模型

1. 所有客户端都连接到其它客户端, 也称为帧同步模型, 常见于RTS等低实时要求的游戏
2. 点对点模型将网络更新划分为150ms-200ms的回合(帧)更新, 每个玩家的操作都保存在队列里, 等到回合结束时一起执行, 因此很多RTS网战会有操作延迟
3. 点对点模型的缺点是只要一个玩家计算出现延迟, 所有玩家都需要等待那个玩家的帧到达
4. 点对点模型的好处是需要传输的数据较少, 只有玩家自己的操作而已
5. 点对点模型需要保证每个玩家在获得相同的帧信息后, 都会模拟出完全相同的结果, 因此基于随机性的游戏逻辑比较难做

作弊

1. 信息作弊: 玩家通过读取内存得到本不应得到的信息. 对于服务器/客户端模型, 可以通过限制服务器下方的信息数量来减少作弊可能性. 点对点模型无法进行相应限制, 一种方法是额外安装反作弊程序监视其它读取内存的进程
2. 游戏状态作弊: 常见于玩家作为服务器的时候, 直接修改游戏数据来胜利. 对抗方法除了反作弊程序外, 还应该对客户端对服务器发送的指令进行检查
3. 中间人攻击: 通过拦截客户端与服务器间传输的信息并修改, 大多数上述反作弊方法都无效, 一种有效解决方法是对传输的数据包进行加密防止篡改. 但加密算法对大多数游戏来说都过重, 一般只保护游戏登入登出的部分