# 前言
说实话，关于正经游戏模式的书还是有点少，这本算是少数中的其中之一。
整本书看下来，发现书里并没有按照类似常规 “23 种设计模式” 这种概念来讲述，有不少其实都不存在于常规设计模式当中：
比如双缓冲、空间分区、脏标记等... 确实跟书名更符一点，讲的是 “游戏编程模式”，而不是单纯的设计模式。
不过，要说是是游戏程序设计方面的书籍，本书肯定是算的。总之值得一看。
# 介绍
设计模式相关的书籍，主要是为了做到如何更好组织程序
- 编写超出大脑思考范围的程序，需要更好的设计与组织。
- 宝藏埋在代码深处，而许多人正在它们之上路过。
作者将其描述的模式分为：序列型、行为型、解藕型、优化型
# 架构、性能和游戏
解藕
- 解藕符合最少知识原则：如果两块代码耦合，意味着必须同时搞清楚两者，而如果解藕，只需要了解其一
维护设计
- 一个良好的设计必须在实现新需求时优雅地融入，否则就会死于一个又一个『小补丁』
- 在项目生命周期维护一个良好的架构需要很大努力
许多模式会让代码更加灵活，但是依赖于一些运行时成本的机制 (如接口、消息、虚函数等)。
# 寻求平衡
- 良好架构：在项目生命周期内更容易理解代码
- 快速的运行时性能
- 快速完成所需功能
它们一部分是冲突的，需要权衡
# 要点
- 抽象和解藕能够使程序开发变得更快和简单，但不必浪费时间来做，除非确信存在问题的代码需要这种灵活性
- 在开发周期中要对性能进行思考和设计，但要推迟会降低灵活性、底层的、详尽的优化
- 尽快探索游戏设计空间，但不要走得太快留下烂摊子
- 如果将要删除代码，那么不需要浪费时间将其整理得很整洁
- 乐在其中
# 再探设计模式
# 命令模式
『命令就是一个对象化 (实例化) 的方法调用』
- 将某个概念转化为一块数据、一个对象 (或者可以认为是传入函数的变量等)
- 支持 undo、redo 的命令模式与备忘录模式有点类似，但区别在于备忘录模式是记录所有数据，而命令模式仅需记录该条命令改变的数据
示例：关卡编辑、角色 (包括 AI) 控制
# 享元模式
一般用于太多对象并考虑对其进行轻量化时
享元模式通过将对象数据切分成两种类型解决共同数据问题
- 不属于单一实例对象并且能够被所有对象共享的数据 (内部状态)
- 单一对象实例特有数据 (外部状态)
示例：地图绘制，地块类型等数据
# 森林之树
『迷雾升起，一片雄伟、古老而茂密的森林在眼前展现。数不尽的远古铁杉铺面而来，宛如一座绿色的大教堂。漫天树叶像是褪色的巨大玻璃穹顶，将阳光滤碎成细密的水雾，透过高大树干的间隙，你能感到这庞大的森林往远方渐逝。』
# 观察者模式
MVC 一般必然都会用到。
C# event 亦是。
分为『容器』方式和链表方式
链式观察者
- 避免动态容器扩容导致的内存分配
- 链表节点池 (指向观察者及下一个链表)，可以使得多个链表节点指向同一个观察者，使得一个观察者可以同时观察多个被观察对象。
注：观察者模式非常适合于一些不相干的模块之间的通信问题，但并不适合于单个紧凑的模块内部的通信。
目的：解藕
示例：成就系统、数据绑定
# 原型模式
如 prefab
原型数据建模
- 如 BOSS 或某些特殊物品，通常是游戏中某一对象的重定义版本
- 即可定义：原型 + 额外数据
# 单例模式
谨慎使用，避免使用、避免滥用。
单例会尽可能将初始化延后 (懒汉)，所以到那时它们所需信息一般都可获得。
- 只要不是循环依赖，一个单例甚至可以在其初始化时引用另一个单例。
- 可以继承单例，例如使用简单的编译跳转，实现不同平台绑定到具体类型
不推荐单例的原因：单例模式就是一个全局状态，只是被封装到类中了而已
- 全局变量有害，令代码晦涩难懂
- 全局变量促进耦合，控制对实例的访问才能控制耦合
- 并发不友好
注：不访问或不修改全局状态的函数称为『纯函数』，纯函数易于理解、利于编译器优化，并能使用诸如记忆缓存、重用调用结果等技巧。
为实例提供便捷访问方式
- 传递参数
- 在基类获取
- 通过其它全局对象访问
- 通过 服务定位器访问 (定义一个类专门用来给对象做全局访问)
# 状态模式
# 有限状态机
- 借鉴了计算机科学里的自动机理论中的一种数据结构 (图灵机) 思想。
- FSMs 可以看作最简单的图灵机
表达的是：
- 拥有一组状态，且可以在这组状态之间进行切换
- 状态机同一时刻只能处于一种状态
- 状态机会接收一组输入或事件
- 每一个状态有一组转换，每一个转换都关联着一个输入并指向另一个状态
整个状态机可以分为：状态、输入和转换
注：部分状态机实例 (没有内部状态) 可通过享元模式复用
# 并发状态机
角色在持枪过程中可以跑、跳和躲避，并能在过程中开火，若执着于传统的有限状态机，那么之前的状态可能都需要加倍：对于已存在状态，需要定另一个 (附加额外操作的) 状态。
- 并发状态机即另外定义一个状态机，与基础状态机同时运行
- 适用于两个状态没什么关系的时候 (也许还需要加点额外判断)，但至少比单层有限状态机更能完成任务
# 层次状态机
比如有一个『on ground』状态用于处理跳跃状态和躲避状态，站立、走路、跑步状态则可以从这个『on ground』状态继承而来。
- 一个状态有一个父状态，当一个事件进来时，如果子状态不处理则沿继承链传给父状态处理。
- 或使用状态栈实现状态链
# 下推自动机
解决有限状态机没有历史记录问题。
- 下推自动机有一个状态栈
- 在一个有限状态机里，当有一个状态切进来时，则替换之前状态
- 下推状态机除此之外还提供额外选择：
- 可以把新状态放入栈中 (当前状态即存在栈顶)
- 可以弹出栈顶状态 (上一个状态变成新的栈顶状态)
# 序列型模式
# 双缓冲
当今多数游戏中，每个像素占 32 位：红、绿、蓝 各占 8 位，剩余 8 位保留做其它各种用途。
显示器从左至右，从上至下绘制显示器像素，会从帧缓冲区获知这些像素该是何种颜色。
- 各种高级图形算法，本质上都是为了向这个帧缓冲数组写东西
撕裂
- 显示器访问速度 (屏幕刷新率) 比显卡写入速度 (帧率) 更快
- GPU 的帧率超过显示器后、或在帧率较低的时候都可能会出现撕裂的情况：其本质是帧率和屏幕刷新率的不一致导致
适用双缓冲情景：
- 需要维护一些被逐步改变着的状态量
- 同个状态可能会在其被修改的同时被访问到
- 希望避免访问状态的代码能看到具体的工作过程
- 希望能够读取状态但不希望等待写入操作完成
注意
- 双缓冲需要在写入完成后进行一次交换操作，操作必须是原子性的
- 双缓冲意味着增加了内存使用
双缓冲模式所解决的核心问题是对状态同时进行修改和访问的冲突 (并非只针对图形)
- 状态被另一个线程或中断代码直接访问
- 进行状态修改的代码访问到了其正在修改的那个状态
例如：战斗中事件状态？
做法
- 交换缓冲区指针或引用 (需要注意外部不能缓冲这个引用，因为引用指向地址可能错误)
- 在两个缓冲区之间进行数据拷贝
# 游戏循环
实现用户输入和处理器速度在游戏行进时间上的解藕。
一个游戏循环在游戏过程中持续运转，每循环一次，非阻塞地处理用户的输入、更新游戏状态并渲染游戏。它跟踪流逝的时间并控制游戏的速率。
关键部分：
- 非阻塞用户输入
- 帧时间适配
- 非同步的固定时间步长 (尽可能快执行更新循环)
- 同步的固定时长 (让循环以固定时间步长运行：增加延时或追赶帧时间)
- 变时步长 (使游戏变得不确定)
- 定时更新迭代，变时渲染 (最复杂且最具适配性)
# 更新方法
通过对所有对象实例同时进行帧更新来模拟一系列相互独立的游戏对象。
注 1：所有对象都在每帧进行模拟，但并非真正同步。且对象更新顺序亦有很大影响，因为 A 更新时，看到的 B 的状态是前一帧的。(除非借助双缓冲模式)
注 2：在更新期间修改对象列表必须谨慎
- 更新期间删除列表对象可能导致某项被跳过
- 添加新对象则会导致新对象提前一帧更新
update 依存：
- 实体类中
- 组件类中
- 代理类中
处理非激活对象
- 过多无需被更新的对象会导致 CPU 浪费额外时间来遍历，并破坏缓存。若非激活对象较多，可考虑单独一个列表维护
# 行为型模式
# 字节码
# 解释器模式
缺点
- 从磁盘加载它需要进行实例化并串联成堆的小对象
- 这些对象与它们之间的指针占用大量内存
- 遍历子表达式、虚函数调用均对缓存不友好
# 虚拟机器码
由虚拟机 (VM) 执行
- 高密度
- 线性
- 底层
- 迅速
字节码模式
- 指令集定义了一套可以执行的底层操作，一系列指令被编码为字节序列，虚拟机逐条执行指令栈上的这些指令
- 通过组合指令，即可完成很多高级行为
# 堆栈机
指令
字面值指令 + 数据
指令分类
- 外部基本操作：虚拟机之外，引擎内部，做一些玩家能看到的事情，决定字节码能够表达的真正行为
- 内部基本操作：操作虚拟机内部的值 —— 字面值、算数运算符、操作栈的指令等
- 控制流：让指令有选择执行或循环重复执行，即跳转
- 抽象化：复用，方法调用
# 语法转换工具
一个图形界面以让用户定义行为，随后转换为字节码
注 1：用户其实可以绕过编译器，手动编写一些恶意字节码
注 2：ANTLR 或 Bison 解析器生成器
# 设计决策
基于栈虚拟机
- 指令较小
- 代码生成简单
- 指令数更多
基于寄存器虚拟机
- 指令更大：需要记录参数在栈中偏移量
- 指令更少：每个指令能做更多的事
# 子类沙盒
使用基类提供的操作集合来定义子类中的行为。
- 基类定义保护的方法供给子类调用
- 基类可能会与许多不同游戏系统耦合，而子类不会
注：它去掉了继承类的耦合，但这是通过把耦合聚集到基类自身来实现的。（基类可能会变得更大且越难以维护）
适用情景：
- 有一个带有大量子类的基类
- 基类能够提供所有子类可能需要执行的操作集合
- 在子类之间有重叠代码，使它们之间更简便共享代码
- 希望使这些继承类与其它代码之间耦合最小化
# 类型对象
通过创建一个类来支持新类型的灵活创建，其每个实例都代表一个不同的对象类型。
继承树实现 (is-a 关系)
- 游戏中每只怪物实例都将属于某一种派生的怪物种族，种族越多继承树就越庞大
包含 (has-a 种类) 实现
- 每个怪物包含种族数据 (初始生命值、攻击等)
『定义一个类型对象类和一个持有类型对象类，每个类型对象表示一个不同的逻辑类型。每个持有类型对象类的实例引用一个描述其类型的类型对象。』
使用情景：
- 需要定义一系列不同『种类』的东西，又不想硬编码进类型系统
- 不知道将来会有什么类型
- 需要在不重新编译或修改代码的情况下，修改或添加新的类型
注：在 C++ 内部，虚方法通过 虚函数表 (vtable) 实现，一个虚函数表是包含了函数指针集合的简单结构体，每个函数指针指向类里一个虚方法。每个类在内存驻存一张虚函数表。每个实例都有一个指向其类虚函数表的指针。当调用虚函数时，代码首先从对象虚函数表中查找，通过存储在表里的函数指针进行函数调用。
缺点
- 通过类型对象去定义类型相关的数据非常容易，但是定义类型相关的行为却很难
- 解决方式：
- 简单方式：是创建一个固定的预定义行为集合，让类型对象中数据从中任选其一
- 复杂方式：支持在数据中定义行为 (解释器模式或字节码模式)
通过继承共享数据
- 没错，数据之间也可以通过继承共享
- 分为动态继承 (基类可能会动态变更) 或静态 (基类属性不变) 直接复制给子类
类型对象应该封装还是暴露
- 如果封装
- 类型对象模式的复杂性对代码库其它部分不可见，成为持有类型对象才关心的实现细节
- 持有类型对象可以选择性重写类型对象的行为
- 需要给类型对象暴露的所有内容提供转发函数
- 如果公开类型对象
- 外部代码在没有持有类型对象类实例的情况下就能访问类型对象
- 类型对象现在是对象公共 API 的一部分
# 解藕型模式
我们几乎没有可能不去更改程序的功能或特性，而解藕能够让变化变得简单点。
某块代码中的变化通常不会影响到另一块代码
- 组件将游戏中不同域相互解藕成单一实体
- 事件队列能够静态而且及时地将两个通信中的对象解藕开来
- 服务器定位器允许代码访问功能却不需要被绑定到提供服务的代码上
# 组件模式
『允许一个单一的实体跨越多个不同域而不会导致耦合』
- 软件设计的趋势是尽可能使用组合而不是继承
- 为实现两个类之间的代码共享，应该让它们拥有同一个类的实例而不是继承同一个类
单一实体横跨了多个域，为保持域之间的相互隔离，每个域的代码都独立地放在自己的组件类中。实体本身则简化为这些组件的容器。
使用情景：
- 有一个涉及多个域的类，但也能够用在别的地方
- 一个类越来越庞大、难以开发
- 希望定义许多共享不同能力的对象，但采用继承方式却无法精确重用代码
注 1：组件模式相较直接在类中实现，引入了更多复杂性：每个概念上的对象成为一系列必须被同时实例化、初始化，并正确关联的集群。不同组件间通信也变得更具挑战性。
注 2：组件指针属于二级引用，在循环代码中可能导致更低性能
# 组件之间传递信息
- 通过修改容器对象的状态 (状态共享)
- 使组件间可以保持解藕
- 要求组件间任何需要共享的数据都由容器对象进行共享
- 使得信息传递变得隐秘，同时对组件执行的顺序产生依赖
- 直接相互引用 (组件之间会有耦合)
- 通过传递信息的方式 (最复杂)
# 事件队列
『对消息或事件的发送与受理进行时间上的解藕』
事件队列是一个按照先进先出顺序存储一系列通知或请求的队列。请求可由处理直接处理或转交给对其感兴趣模块，使消息的处理变得动态且非实时。
- 在很多方面，可以看作是观察者模式的异步版本
使用情景：
- 相比观察者模式的直接 『派发 - 处理』模式，队列提供给拉取请求的代码块一些控制权：接收者可以延迟处理，聚合请求或完全废弃它们
- 使得队列在发送端需要实时反馈时显得不适用
- 如播放音效：解藕播放与受理，并避免两个同类音效同时叠加播放
注 1：队列事件视图比同步系统中的事件具有更重量级的数据结构：后者只需通知然后接收者可以通过检查系统环境获知，而队列则需要在事件发生时记录以便稍后处理消息时使用。
注 2：当消息系统是同步时，注意可能导致消息循环的情景，如避免在处理事件端代码中发送事件。
# 环形缓冲区
# 设计决策
入队的是什么
- 事件：就有点类似异步观察者模式
- 消息：一个『消息』或『请求』描述一种期望发生在『将来』的行为，或者可以认为是一种异步 API 服务
读取者
- 单播队列：当一个队列是一个类 API 本身的一部分时
- 广播队列：类似事件系统
- 工作队列：可以有多个处理者，不过队列中一项只能投递给一个处理者
写入者
- 一个写入者：类似同步观察者模式
- 隐式知道事件来源
- 通常允许多个读取者
- 多个写入者：类似『全局』或『中央』事件总线工作原理
同步消息提醒模式下，调用执行只有在所有接收者都处理完消息后才会返回到发送者。
# 服务定位器
『为某服务提供一个全局访问入口来避免使用者与该服务具体实现类之间产生耦合』
- 一个服务类为一系列操作定义了一个抽象接口
- 一个具体的服务提供器实现这个接口
- 一个单独的服务定位器通过查找一个合适的提供器来提供这个服务的访问，同时屏蔽了提供器的具体类型和定位这个服务的过程
- 注：由于使用接口抽象，因此可以方便地使用装饰器模式额外为服务提供器附加额外功能
注：注意处理服务不能被定位器使用时的处理
# 优化型模式
# 数据局部性
『通过合理组织数据利用 CPU 的缓存机制来加快内存访问速度』
我们能更快地处理数据，但不能更快地获取数据
- CPU 进行运算时需要从主存取出数据并置入寄存器
- RAM 的存取速度远远跟不上 CPU 的速度，甚至从未接近
数据获取 (缓存)
- 利用数据的时空局部性，获取数据时同时缓存数据及相关数据。
数据即性能
- 缓存失效与面向数据局部性的代码，性能相差可能几十倍，由于缓存机制，组织数据的方式会直接影响性能 (包括代码也是在内存中，需要载入 CPU 执行)
- 缓存行：优化的目标在于尽量将数据结构组织，使其在内存中两两相邻
使用情景
- 找到出现性能热点的地方
- 不需要在不常执行之处：结果会更加复杂笨拙
使用须知
- 抽象化意味着要通过指针或引用访问对象，导致在内存中来回跳转，引发缓存未命中的现象
- 越是在数据局部性上下功夫，就越要牺牲继承、接口及这些手段带来的好处
CPU 流水线
- 免分支预测，导致 CPU 预测失准和流水线停顿
- 现代 CPU 单条指令需要多个时钟周期来完成，为了让 CPU 保持忙碌，因此引入流水线以便多条指令并行执行
- 流水线模式：CPU 猜测哪些指令接下来会被执行，顺序结构很简单，控制流结构很麻烦，需要分支猜测：分析前面代码走向，预测下一次代码执行流（因此出现控制流代码会降低面向数据设计的性能，因此关键代码最好避开控制流）
冷 / 热代码分解
- 每帧需要检查和修改的变量 (如位置)
- 非每帧需要用到的处理意外情况的变量 (如怪物掉落数据)
# 设计决策
- 避开继承
- 或者至少在进行缓存优化之处避开
- 为不同的对象类型使用相互独立的数组
游戏实体的定义 (主要指配合组件模式)
- 假如游戏实体通过类中的指针索引其组件
- 可以将组件存于相邻数组中，游戏实体并不关心组件存储，这样组织可以对迭代过程进行优化
- 对于给定实体，很容易通过其指针获取对应组件
- 在内存中移动组件较困难：启用禁用组件，对其移动 (排序) 时，可能一不小心就破坏了指针关联，必须确保对实体相应指针进行更新
- 假如游戏实体通过一系列 ID 进行索引更新
- 更加复杂 (相比指针)
- 速度更慢：不大可能比遍历原始指针更快，通过 ID 获取组件可能也涉及到哈希查找问题
- 需要访问组件管理器：存储组件数组的管理类来提供 ID 获取组件的对应接口
- 假如游戏实体本身就只是个 ID
- 若将游戏实体所有行为和状态都从主类移动到组件中，游戏实体唯一要做的就是将自己与其组件绑定
- 实体类变得很小，只是个数值包装
- 实体类本身为空
- 无需管理其生命周期 (现在实体只是某些内置类型的值)
- 检索一个实体的所有组件会很慢：与前一个方案问题类似，为某个实体寻找对应组件需要进行 ID 映射带来开销 (或者将实体 ID 对应为其组件所在数组索引，但这样所有组件必须保持平行，导致不能排序)
# 脏标记模式
『将工作推迟到必要时进行以避免不必要的工作』
一组原始数据随时间变化，一组衍生数据经过一些代价昂贵的操作由这些数据确定。一个脏标记跟踪这个衍生数据是否和原始数据同步，它在原始数据改变时被设置。如果它被设置，那么当需要衍生数据时，它们就会被重新计算并清除标记，否则仅使用缓存数据。
使用情景
- 这个模式解决一个相当特定的问题
- 仅当性能问题严重到值得增加代码复杂度时才使用
其它要求
- 原始数据修改次数比衍生数据的使用次数多
- 递增更新数据十分困难
- 例如在容器里放东西，更新容器总量，每当增加或减少时重新统计 —— 这样还不如使用动态总重量：增加或减少物品时直接在总量上进行操作（例如属性系统）
注意
- 延时太长会有代价
- 这个模式将某些耗时工作推迟到真正需要时才执行
- 而真正需要时，往往刻不容缓
- 必须保证每次状态改动时都设置脏标记
- 必须在内存中保存上次的衍生数据
# 对象池
内存碎片化
- 如同乱停的车和规矩停放的车，可停数量差异一样。
- 即使碎片化情况很少，它也依然在削减着堆内存并使其成为一个千疮百孔而不可用的泡沫块。
使用情景
- 需要频繁创建和销毁对象
- 对象的大小一致
- 在堆上进行对象内存分配较慢或会产生内存碎片时
- 每个对象封装着获取代价昂贵且可重用的资源
注意
- 每个对象的内存大小是固定的 (应当是一个类型)
- 重用对象不会被自动清理 (若没有适当重设，可能保留上一次的数据)
- 未使用的对象将占用内存 (并会阻碍垃圾回收释放它指向的对象)
空闲表
- O (1) 的时间复杂度
- 一个头指针，依次指向形成链表
- 使用时取出当前头指针，并重置当前头指针为其指向的下一个空闲对象
- 回收时将回收对象指向当前头指针，然后重置当前头指针为回收对象
# 空间分区
『将对象存储在根据位置组织的数据结构中来高效地定位它们。』
基本要求是有一组对象，每个对象都具备某种位置信息。
- 普通 (方格) 空间分区
- 四叉树 (二维)
- 八叉树 (三维)
