Restoration

存档系统的设计

设计目标

• 保存和读取各种前端组件（对话框、图片、BGM等）的状态
• 在对话中设置变量，根据变量跳转剧情分支，在读档时恢复变量
• 在小游戏中设置变量，此时变量取决于玩家的输入
• 在章节选择界面中从任一个开始节点开始游戏
• 在文本回顾界面、流程图界面中跳转到一条已经到达过的对话
• 读档、回跳时，恢复文本回顾界面的内容
• 根据变量改变文本（插值）
• 存档占用的硬盘空间足够小
• 存档、读档的速度足够快

游戏状态

• 本文所说的游戏状态（GameState）只包括游戏流程层面上的状态（当前在哪条对话，这条对话结束时各个前端组件的状态），而不包括一条对话之内的状态（比如当前是不是在自动播放、对话内动画播放到了哪一秒）
• 游戏状态由全局变量、节点历史、当前节点中的对话序号唯一确定
  • 一个节点可以执行多次（流程图可以有环），而节点里的脚本可以增量地改变游戏状态（比如变量加1、立绘向左移一格），所以节点每次执行的结果可能不同，不能只用当前节点的名称确定游戏状态，必须用所有节点的历史
• 绝大多数对话无论什么时候读档，只要在相同的初始状态下执行脚本，都会得到相同的结果
  • 例外的情况包括小游戏（结果取决于玩家的输入）、随机数、根据当前日期给角色过生日等，这些情况会在节点历史中增加一条记录
• Nova管理的变量分为局部变量和全局变量
  • 局部变量是指一次游戏过程中，被存档记录、在读档时恢复的数据，存档之间的局部变量是相互独立的
  • 与之相对的全局变量是可以在多次游戏过程中更新，存档之间共享的数据
  • 举例而言，游戏过程中立flag、好感度等是局部变量（除非你想搞meta），而几周目、是否通关过某些结局等是全局变量
• 由于读档时不改变全局变量，可以出现只能通过读档达到，而无法通过从头开始游戏达到的状态
  • 比如一个节点只有一周目选一个选项才能进，二周目这个选项就没有了，但是如果一周目在这个节点里存档，二周目再读档，就会达到全局变量是二周目，节点历史是这个节点的状态
  • 这是一个feature，游戏制作者可以使用它或者避免它
• 任何对话的语音只由当前的节点名称和对话序号确定，不会因为变量或节点历史而改变
  • 这是为了方便在读档时恢复log界面中的语音
  • 如果需要改变，可以分成不同的节点
  • TODO：允许根据变量改变语音（可能会与文本插值一起使用）

存档文件的块结构

• 存档文件（global.nsav）按固定长度分块（CheckpointBlock，默认为4 kB）
  • 这是为了提高存读档的速度，避免每次都把所有东西序列化一遍，而且因为文件系统的随机读写不一定靠谱，我们需要自己做分块
• 块的更新缓存在内存中（CheckpointSerializer.cachedBlocks），只在特定时候回写到硬盘（CheckpointSerializer.Flush）
• 块与块之间以单链表连接，一条链表表示一段连续数据
• 一条链表内有若干条顺序存储、不定长的记录（record）
  • 支持在链表的尾部追加记录，不支持删除（除非清空所有存档）
  • 如果更新已有的记录，必须保持长度不变，或者整个链表只有一条记录，因为我们由存档文件中的offset来读取记录
  • 一个块中可以存储多条记录，一条记录也可以跨越多个块
• 每条记录一般会实现ISerializedData，先序列化成JSON，再用DeflateStream压缩
  • 但是某些记录（NodeRecord）需要更新，在更新时必须保持序列化后的长度不变，所以由我们手动序列化
  • 前端组件实际用到的状态在可能的状态空间中是很稀疏的（比如有些作品中的立绘只会出现在左中右三个位置，而不用把位置当作实数来存储），所以应该压缩
  • 我们没有提供存档加密功能，因为代码是开源的，如果需要加密请自行解决

存档文件的逻辑结构

所有的块组成三条链表，分别存储以下内容：

• Global save header：只包含一条记录（GlobalSave），存储存档版本、下面两条链表的metadata、全局变量等信息
  • 这些信息需要更新，由于整条链表只有一条记录，即使不是定长的也可以更新
• Reached链表：包含两种记录
  • ReachedDialogueData：一条已读对话的信息，包括该对话的语音信息（voices）、文本是否需要插值（needInterpolate）
    • 用于在快进时判断是否已读，以及在读档时恢复log界面
    • 这些信息是全局的，不依赖于变量
  • ReachedEndData：一个已读结局的名称，同样是全局的
• Checkpoint链表：包含三种记录，存储游戏历史中的所有状态
  • NodeRecord：表示节点历史中的一段
  • Checkpoint header：一个int，表示一个checkpoint对应的对话序号
    • 这是为了便于查找某条对话的上一个checkpoint，避免在遍历链表时反序列化整个checkpoint
  • Checkpoint：即序列化的GameStateCheckpoint，和checkpoint header成对出现
• 可能的节点历史的数量随着分支和小游戏结果的数量增加而指数增长，但是我们只会记录玩家遇到过的节点历史，因此在最坏情况下，存档文件的体积随着游玩时间而线性增长

Node record

• 每个NodeRecord覆盖一个流程图节点内的若干条对话和若干个checkpoint
  • NodeRecord覆盖的第一条对话（beginDialogue）会强制创建checkpoint（也就是覆盖的第一个checkpoint一定对应beginDialogue）
  • 但结尾不一定是checkpoint，所以需要分开存储endDialogue和lastCheckpointDialogue
  • 为了使用方便，endDialogue为最后一条对话的序号加1（左闭右开），但lastCheckpointDialogue不加1
• 所有NodeRecord组成一棵树，通过child-sibling表示法存储
  • 跳转到一个新的节点时，创建一个NodeRecord，作为当前NodeRecord的child
  • 在剧情分支处，跳转到不同的节点时，创建不同的NodeRecord
    • 如果跳转到同一个节点，即使是不同的分支，也不会创建新的NodeRecord
• 同一个节点内也可能会产生多个NodeRecord，目前有两种情况：
  • 一条对话的脚本可能在相同的初始状态下产生不同的结果，比如小游戏
    • 这时根据不同的variablesHash创建不同的NodeRecord
  • 当前NodeRecord所覆盖的checkpoint范围不处于链表末尾，但是需要添加新的checkpoint
  • 这两种情况都会调用GameState.AppendSameNode增加一个新的NodeRecord，作为当前NodeRecord的child
• 一个时刻的全部节点历史由树根到当前NodeRecord的路径所覆盖，GameState.GetDialogueHistory返回这个迭代器
• 存档文件中的NodeRecord需要更新，必须保持长度不变，所以由我们手动序列化

Checkpoint

• 每个有状态的前端组件实现IRestorable，它的状态表示成IRestoreData
• 一个checkpoint（GameStateCheckpoint）包括一个时刻（一条对话的default代码块执行前）的局部变量和所有前端组件的状态，不包括全局变量
• 并不是每条对话都会创建checkpoint，读档时会先恢复到之前最近的checkpoint，然后重新执行到那条对话为止的脚本
  • 默认情况下，每经过一定对话数量（GameState.maxStepNumFromLastCheckpoint），创建一个checkpoint
  • 某些情况下会强制创建checkpoint（NodeRecord开始、小游戏），或禁用checkpoint（持续动画）
• 读档时，需要提供nodeRecord（或nodeOffset，即NodeRecord在存档文件中的offset）、checkpointOffset（checkpoint header在存档文件中的offset）、dialogueIndex
  • Checkpoint和对话必须是nodeRecord所覆盖的

书签

• 存档/读档界面中的每个存档称为书签（Bookmark），记录nodeOffset、checkpointOffset、dialogueIndex
• 自动存档、快速存档与手动存档的格式是一样的

文本回顾界面

• LogEntry：记录一条历史对话的nodeOffset、checkpointOffset、dialogueIndex
  • 在log界面中回跳时，提供这些信息就能恢复该历史对话
• LogEntryRestoreData：记录一条历史对话插值后的文本
  • 不需要插值的文本通过FlowChartGraph得到
  • 每个checkpoint中存储当前log界面中全部的LogEntryRestoreData，这是为了避免在读档时反序列化太多的checkpoint，但相应地需要O(n^2)的存储空间
• 历史对话中的语音通过ReachedDialogueData得到

TODO List

• 完成对随机数的支持
• 对存档数据去重
  • 比如对每个restorable分别去重，如果总共有一万条对话，但是某个角色只有几条对话会出现，其他时候都是默认状态，就不要在全局存档文件中把“默认状态”重复一万遍，而是用指针之类的办法来去重
• 固实压缩一条链表内的多条记录
• 在某些时候清理存档，删除因为随机数、存档升级等原因而不会再被读取的对话
• LogEntryRestoreData使用树状数组可以降低到O(n log n)的存储空间，但需要反序列化O(log n)个checkpoint