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

绪

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

全文6.6k字, 预计需要22分钟.

1 游戏编程概述

游戏主循环

1. 游戏循环: 整个游戏程序的核心流程控制, 不断执行直到退出
2. 帧: 循环的一次迭代. 一般一秒30-60帧, 也就是程序每帧耗时需要在33ms以下
3. 传统的游戏循环: 输入(控制器), 更新世界和逻辑, 输出(画面)
4. 多线程游戏循环: 最简单的方法是让线程做自己的事情, 例如一个线程负责图形以外的计算, 另一个线程负责渲染图形
5. 多线程合作的时候渲染线程需要等待主线程的数据, 因此为了提高利用率最好借用流水线的思路, 让渲染线程比主线程慢一帧
6. 多线程可能导致更高的输入延迟如下图: 第一帧进行了计算, 第二帧才会渲染出画面, 然后第三帧才能处理玩家的输入, 第四帧玩家才能看到输入的结果.

游戏中的时间

1. 真实时间: 真实世界流逝的时间, 用于记录
2. 游戏时间: 游戏内的时间, 用于游戏性设计使用, 例如制造时间减速效果, 加速效果, 倒退效果等等. 游戏可能内含多个时间
3. 增量时间(deltatime): 游戏从上一帧起流逝的时间, 游戏中与速度有关的设计都应该用这个时间来计算. 尽管我们无法得到当前帧的时间, 但是可以依据上一帧甚至之前的多帧来预测当前帧可能的耗时, 尽量保证游戏在各种帧率下都能正常运行, 而不是像早期游戏一样依赖于CPU频率或者显示器刷新率等
4. 与物理有关的游戏当帧率波动的时候按照不稳定的增量时间模拟出的结果可能产生很大的误差, 最简单的优化方法是限制物理模拟部分的帧率来使得数值积分过程尽量稳定
5. 遇到某帧绘制时间过长时, 程序可以选择丢弃过长的帧(跳帧)或者就正常表现(卡帧), 这方面的权衡应该视需求而定

游戏编程中的对象

1. 游戏对象可以大体分为三种: 需要更新状态也需要绘制的动态对象(如人物), 需绘制但是不需要更新状态的静态对象(如场景), 需要更新状态但无须绘制的工具对象(如摄像机和触发器)
2. 三大游戏对象的程序实现可以通过抽象出Drawable和Updateable接口然后通过继承(或组合)来配合得到
3. 游戏对象被创建出来后一般会加入游戏中维护的队列, 按照策略模式等设计进行更新和渲染

2 2D渲染基础

渲染时的帧刷新问题

1. 显示器有固定的刷新率, 按照显示-刷新-显示的循环进行. 如果程序在屏幕刷新的途中输入画面到屏幕的缓冲区的话会可能屏幕撕裂的现象, 也就是上半个画面是新内容, 下半个画面是旧内容, 虽然持续时间很短但是观感还是不好
2. 因此解决屏幕撕裂的关键在于必须在刷新之前就将所需的内容输入显示器缓冲, 但是帧率的不稳定导致这个过程可能过早或过晚
3. 为了最大化流水线效率, 游戏设计了双缓冲技术, 前缓冲是用于输入显示器的完整图像, 后缓冲是正在绘制的下一帧图像, 显示器按照周期从前缓冲获取内容, 程序渲染完画面就进行前后缓冲交换. 这会加大输入延迟但是让画面的渲染和显示独立开来, 从而一定程度上避免了由于渲染带来的帧率波动导致的画面撕裂
4. 如果帧率变化剧烈的话双缓冲依然可能出现显示器不得不取用目前正在绘制的图像的情况, 为了优化有些游戏引入了三缓冲技术, 进一步加大了延迟但是对特殊帧率的容忍性也更高了

2D精灵的绘制与动画

1. 精灵: 使用图片的一个方块绘制的2D图像游戏对象. 可能是动态也可能是静态, 2D游戏需要大量的精灵对象
2. 绘制2D画面大多使用画家算法(遍历排序好的场景进行渲染, 这样无须深度测试). 因此2D游戏中每个精灵都应该有自己的坐标和绘制序号, 然后程序按照这个序号列表按顺序渲染, 前景覆盖背景
3. 一些图形库支持按层次组合一组图像的绘制顺序, 方便美术人员设计场景
4. 动画精灵: 也就是带有自己动画的2D游戏对象, 动画一般用一组图片来表现, 类似现实中的帧动画.
5. 组织动画一个简单的方法是包装一个帧动画结构体, 内含当前需要显示的动画的索引, 当前动画需要显示的图像, 每帧图像的时间, 动画播放的帧率, 和对应的init, update, change接口. 其中update是最重要的, 因为需要利用当前的增量时间(deltatime)来决定是否需要切换下一帧动画, 并按照当前游戏的状态决定是否需要切换到不同的动画上
6. 更加复杂的动画应该用状态机来实现
7. 将每帧的图像作为一张图片进行保存会产生很多读取和传输开销, 且图像的空白区域也会产生很多浪费的空间. 比较好的方法是用一张(少数张)来保存多个精灵所需的内容, 称为精灵表单. 然后按照设置好的索引位置和区域大小来从表单中读取所需的图像, 这样能消除图像切换的消耗
8. 下图左边是分离的图像, 右图是整合后的精灵表单:

常见的2D游戏

1. 单轴滚屏: 游戏世界只按照x轴或y轴滚动, 典型的是跑酷类游戏. 其背景的实现方法一般是按照屏幕大小进行背景切割, 然后以片段为单位组成链表放在游戏世界中, 摄像机始终追随玩家只要范围不要超过第一张和最后一张背景即可. 通常同时只需要绘制两张背景图
2. 无限滚屏: 通常是多张背景以随机的方式组成序列来显示
3. 平行滚屏: 这种技术将背景分为多层, 每层都有自己的滚动速度的因子, 设定越远的背景滚动速度越慢从而产生深度感
4. 四向滚屏: 游戏世界会同时在xy上滚动, 类似单轴滚屏, 需要同时准备四张背景图像用于显示, 而且背景不再使用链表来组建, 而是改为二维数组来决定目前需要显示哪些背景图像
5. 砖块地图: 将背景切分为等分的方块, 方块可以集合在一张表单里然后按照索引进行查找, 此时游戏世界由精度更高的二维索引数组构建, 一般储存为外部文件然后按需读入. 这种组建形式可以制作随机产生的地图, 且方便美术人员调整, 而且可以让一个砖块ID对应多张不同的图片从而实现常见的"季节性皮肤"功能
6. 斜视砖块地图: 视角通过旋转来让常见更有深度感的砖块地图, 需要支持多层次渲染和成组的砖块绑定设计来保证前后景效果和一些遮挡效果, 砖块一般是正方形(竖放)或者平行四边形.

3 游戏中的线性代数

向量点乘

1. 向量长度需要开方, 代价比较大, 应该避免. 比较向量长度和比较向量长度的平方是一样的, 所以尽量不要开方
2. "卡马克快速平方根"是通过概率估算牛顿法第一次迭代的结果加速了求开方的速度
3. 点乘得到标量, 叉乘得到向量
4. 两个向量的夹角向量夹角:

.

1. 非单位向量投影到单位向量方向上的投影长度投影长度:

1. 单位向量点乘为0时两个向量垂直, 为1时两个向量平行且同向, -1时平行且反向. 结合原始的向量乘法公式来记忆即可
2. 向量长度的平方就是用自己与自己点乘

求反射向量

1. 与向量有关的问题画图会比较好理解, 求反射向量需要有入射向量本身与反射点的法线
2. 首先将入射向量反向然后与法线点乘, 得到入射向量在法线方向上的投影长度
3. 将这个投影长度乘在法线上后, 将入射向量与投影法线相加能得到平行于切面的半向量
4. 将反向的入射向量与两倍的半向量相加就得到反射向量了

1. 反推一下得到反射向量的直接计算公式:

向量叉乘与顶点序

1. 两个不共线的向量确定一个平面, 它们的叉乘就是垂直于这个平面的法向量
2. 如果想要对二维向量进行叉乘, 只需要将z分量设置为0
3. 叉乘后的向量指向遵循右手法则如下图: 食指对准第一个向量, 中指对准第二个向量, 此时右手拇指的方向就是叉乘的方向

1. 因此向量不满足交换律, 但是满足反交换律

1. 叉乘公式的记忆口诀: xyzzy. 即如下图, 叉乘后的向量的三个分离是基于ab-ab结构, 然后按照xyzzy字符进1的顺序进行推导的

1. 叉乘得到的0向量代表前两个向量共线
2. 可以通过计算三角形的法线与当前向量的叉乘来判断当前向量与目标三角形是否垂直(垂直时当前向量与三角形法向量共线)
3. 由于反交换律, 两个向量可以得到两种方向的叉乘结果, 因此需要在游戏中规定全局的三角性顶点的顺序(称为顶点缠绕顺序: Vertex Winding Order)来统一叉乘后法向量的方向.
4. 大多数图形库都可以自己指定所需的顺序, DirectX的默认顺序是顺时针, 也就是如下图三角形, A作为核心顶点, B-A是第一条向量, C-A是第二条向量, 叉乘得到的法向量朝屏幕内

二维向量旋转与三维坐标系

1. 两个向量间的夹角可以由两个向量点乘后arccos得到
2. 二维向量可以简单判断旋转的方向, 先将向量的z设为0扩展为3维, 然后起点向量叉乘终点向量, 得到的叉乘向量z为正时代表顺时针, z为逆代表逆时针
3. 常见的三维坐标系有两种, 左手系和右手系. 其都是y轴向上的, 区别在于z轴向屏幕内侧(左手系)或屏幕外侧(右手系). DirectX是左手系, OpenGL是右手系
4. 坐标系的手系可以通过计算基向量组的行列式得到(区别只在于z轴基向量的方向), 行列式为正的是右手系, 否则是左手系

4 3D图形

矩阵与仿射变换

1. 矩阵相乘只要行列对应得上即可
2. 但因此3D图形向量也有行和列两种等价的表示方式, 对应的变换矩阵是转置与左乘右乘的区别. 大多数3D图形库都是以行向量表示的, OpenGL使用列向量表示. 这里都按照行向量表示
3. 3D中3x3矩阵只能表示向量的线性变换(旋转, 缩放, 错切), 但是无法表示非常常用的平移变换(非线性), 因此引入了一维(w)表示平移, 称为仿射变换. 对应的4x4矩阵称为仿射变换矩阵, 此时扩展出来的4维向量坐标称为齐次坐标. 注意运算最后的齐次坐标的w分量应该总保持为0或1
4. w为0的向量表示3D方向, w为1的向量表示3D的点
5. 四种最基本的三维变换:
   1. 缩放: 只在需要缩放的轴对应的对角线上设置倍率, 其他位置保持0. 缩放倍率为负时称为反射:

   

   1. 错切: 保持对角线上的值不变, 改变另一个轴的偏移量. 或看为坐标系变换, 这里原本是(0, 1)的y轴变换为了(1, 1), 因此整个图形发生了倾斜:

   

   1. 平移: 借助了齐次坐标的特性, 行向量左乘下面的矩阵后, 如果w为1也就是3D的点的话, 矩阵最下面一行就会起到平移点的作用, w为0的时候则不生效, 符合向量的性质

   

   1. 旋转: 二维旋转用手就能很容易从向量中推导出来, 要注意默认的旋转角度指朝向旋转轴负方向方向, 逆时针旋转的角度. 大多数时候三维旋转使用xyz三个轴固定下的轴对齐欧拉角旋转矩阵连乘得到. 同样按照坐标系基底变换的思路理解: 对物体的旋转相当于进行将原本的单位坐标系改为旋转后的坐标系, 因此我们只要手推xyz坐标轴旋转后的新坐标并以列向量的方式排列即可

   

   1. 注意这里的y轴的旋转角度发生了反向, 这个特性动手推一下就能够得到, 本质是因为与x和z轴的时候不同, 绕y轴旋转时, z的初始位置是(0, -1), 本质是手性带来的不对称性.

常见坐标系

1. 模型坐标系: 相对于模型自身的坐标系, 通常坐标系的原点置于模型中心或者角色脚下
2. 世界坐标系: 将所有对象按照设定的对象坐标进行偏移, 放置到同一个坐标空间中成为世界坐标系, 此时的坐标系原点是世界中心
3. 相机坐标系: 将整个场景(世界)移动到以相机坐标为原点的坐标系上, 相机的上方朝向为y轴, 前向和其二的叉乘为z(或-z)和x轴. 将场景变换到相机坐标系所用的变换矩阵称为观察矩阵
4. 投影坐标系: 有时称视口坐标系. 将自定义的视体变为标准视体的过程, 变换后的原本自定义视体中的内容会变换到标准视体中. 基于OpenGL的书中常见的标准视体的是比较符合数学规则的三个轴都在(-1, 1)的立方体, 而基于DirectX的标准视口则为了表达方便将z映射到(0, 1)上, 这会使得投影变换矩阵产生差别, 具体查看对应文档即可
5. 屏幕坐标系: 将投影后的坐标系(-1, 1)进一步移动和缩放到对应屏幕像素分辨率的坐标系上, 供给像素着色器的处理

投影变换

1. 正交投影: 最简单的投影矩阵, 由右侧的平移部分和左侧的缩放部分组成, 注意这里是基于列向量的DirectX版本, 因此投影后视体的z处于(0, 1)

1. 透视投影: 同样是将整个场景缩放, 但是透视投影的原始视体是锥形的, 所以推导上相对复杂一些. 基础的思路是先绘制一个二维的透视示意图, 可以看到xy上的投影结果可以依据相似三角形得到. 但是由于投影的分母是深度z, 需要利用透视除法将深度值带到xy上. 而z分量本身则需要保持近似线性插值, 联立方程将近平面和远平面的深度投影到0-1从而求解出第三行的两个矩阵系数. 最后将这个视体进行一次正交投影映射到(1, -1)即可. 下图是通用的DirectX版本投影矩阵, 实际DirectX使用的时候并没有第三列上面的两个系数

1. 透视投影变换只能保证深度投影后前后顺序不变, 但是并不能保持线性关系, 整体的深度值会向后挤压, 也就是大多数深度投影后分布在较后的比例. 近平面越接近相机则向后分布越严重, 有些时候这会引起精度问题.
2. 为了优化这个精度问题, 一种方法是将深度取反处理从而让靠近近平面的场景分配到更多的浮点空间, 还有一种方法是对深度按照对数储存, 对数精度能让深度值得到更均匀的分布

光照

1. Phong光照属于一种简单的BRDF模型, 且属于一种局部光照模型(不考虑光线的二次反射)
2. Phong光照由环境光项 漫反射项 高光项得到
3. 环境光项是直接附加的一个常数
4. 漫反射项是颜色乘上一个权重, 权重是法线方向与光照方向的点乘
5. 高光项也是颜色乘权重, 权重是视线方向与光照方向的半程向量(相加然后单位化)与法线方向的点乘, 然后经过一个指数幂处理来控制得到的高光范围大小, 幂次越大高光范围越小

四元数

1. 目的是避免欧拉角表示旋转会有的万向节死锁问题, 并优化旋转插值的效果, 且用四元数来表示多个旋转的合成可以减少计算量
2. 表示旋转的四元数是一个由四个浮点数组成的四维向量, 写为q=[q_v, q_s]或[x, y, z, w]的形式. 其中q_v中的a是旋转轴, theta是旋转角

1. 四元数在使用前要记得将向量分量q_v归一化后才能正常使用, 否则旋转会表现出奇怪的缩放效果
2. 四元数也可连续使用, 但需要以下式进行相乘, 且顺序相反, 即物体是先q后p旋转时, 乘法四元数是pq

1. 四元数可以很轻松地取逆, 只要将向量分量取反即可, 这两个四元数互为共轭
2. 两个旋转间的插值可以直接用四元数线性插值或球面插值等其他插值得到, 计算方便效果好
3. 应用到图形库时可以用下面的式子将四元数转换为变换矩阵

5 游戏输入

输入设备

1. 输入可以简单分为数字和模拟两大类, 数字意味着只有0和1两种状态的输入(例如普通的按键), 模拟是浮点输入(例如摇杆)
2. 游戏常常需要对同时按键和序列按键进行处理, 同时按键就是那些需要同时按下的操作, 序列按键则是很多格斗游戏中有的按键表操作. 这种处理一般可以用状态机来实现
3. 图形游戏一般都禁止系统的标准输入, 直接对输入设备进行设备级别的查询, 并维护一个数组跟踪设备对应所有按键的当前状态和上一帧状态等信息, 再利用这些信息进行状态的转换
4. 例如摇杆设备带来的模拟输入经常会有设备误差, 因此需要设置无效区域(死区), 一般通过计算设备返回的2D向量长度来进行过滤, 然后计算死区之外的向量长度与最大值之间的百分比乘上向量方向来得到过滤后的向量结果

输入事件系统

1. 得到输入设备的结果后游戏通常实现一个单例模式的输入管理器来管理各种输入事件, 减少事件轮询的开销
2. 一般这个输入管理器对象是全局可见的, 对象内部在每一帧对所有输入操作进行基础的处理, 而其他需要被输入调用的对象将自己的函数指针传入管理器的链表/映射表中(这种操作称为注册或绑定), 管理器在判断某输入操作发生时, 就依次调用链表中的对应函数通知需要响应事件的对象

移动设备输入

1. 移动设备一般面对轻度玩家, 所以最好不要采用过于复杂的操作
2. 移动设备的核心是触摸屏, 主要由模拟家用机游戏的虚拟手柄和手势操作组成
3. 一种流行的手势检测算法是Rubine算法, 其将手势线条划分出14个属性, 例如时长, 距离, 区域, 中点, 起点, 包围盒大小 等等. 绝大多数手势都可以用这套属性进行描述并判断, 响应速度也很快
4. 加速器: 检测设备轴向上的加速度, 用于甩动等玩法
5. 陀螺仪: 检测设备轴向的旋转角度, 用于瞄准等玩法

6 声音

声音系统

1. 游戏一般会设置声音事件, 将游戏中的一个事件映射到一个或多个声音文件上进行播放
2. 声音文件的播放一般会经由场景预加载节省时间, 并为了节省内存采用流式加载(只按需加载一部分)
3. 声音事件常常由较复杂的场景设计, 最常见的就是脚步事件在角色不同状态, 不同地面环境, 不同周边环境, 当前事件不同优先级下, 播放不同的音频. 因此实现声音系统关键是提供足够的信息去判断所需播放什么声音

3D声音

1. 2D游戏一般声音与方向无关, 一部分会考虑音源距离
2. 3D游戏考虑得很多, 需要设置虚拟监听者和虚拟发射者. 第一人称游戏的情况最简单, 监听者就是相机的方向和相机朝向即可
3. 第三人称动作游戏的监听者比较难设置, 比较好的设置是监听者的位置在相机与角色之间中点附近的位置, 朝向等于相机的朝向, 具体视需求而定
4. 发射者最基础的设置是音量大小和衰减半径, 超出半径距离的时候就按照衰减函数减少音量, 直到音量为0
5. 大多数设备只支持立体声, 对应环绕声的开发可能不是很划算

声音处理

1. 常见的声音处理效果有:
   1. 回声: 模拟狭窄空间的回声
   2. 音高偏移: 模拟多普勒效应, 常见于竞速游戏, 靠近频率上升, 远离频率下降
   3. 频率压缩: 统一不同大小的声音
   4. 低通滤波: 模拟爆炸的轰鸣声和音量遮挡效果
2. 音量遮挡: 最简单的遮挡效果通过判断监听者到发射者之间有无阻挡并应用低通滤波即可, 复杂的遮挡可以使用Fresnel声学衍射模拟音波的传播效果