Restoration

存档系统

设计目标

• 保存和读取各种前端组件（图片、BGM等）的状态
• 在对话中设置变量，用变量控制剧情分支，在读档时恢复变量
• 在小游戏中设置变量，此时变量取决于玩家输入
• 在章节选择界面、文本回顾界面、流程图界面中跳转到一条已经到达过的对话
• 读档时恢复文本回顾界面的内容
• 在文本回顾界面中回跳时，恢复更早的文本
• 根据变量或全局变量改变文本（插值）
• 变量是指一次游戏过程被存档记录在读档时恢复的数据，存档之间的变量是相互独立的，与之相对的全局变量是整个游戏过程中实时更新，存档之间共享的数据
  • 举例而言：游戏过程中选选项立flag、好感度等是变量，而几周目、是否通关过某些结局等是全局变量
• 同一个Node内的对话脚本在绝大多数时候是可重复执行的，即相同的初始状态执行相同的脚本会得到相同的结果，例外的情况有：
  • 小游戏，取决于玩家的输入
  • 这些例外情况需要调用特定函数（GameState.AppendSameNode），目前仅支持小游戏
• 上述初始状态仅包括变量和全局变量，不包括前端组件的状态
  • 举例而言，对话不会因为图片位置或BGM发生变化，如果需要存储这些状态请放到变量或全局变量中
• 同一个Node同一条对话的语音不会因为变量或全局变量而改变
  • 如果需要改变，可以考虑分开放到不同的Node
• 占用的硬盘空间足够小
• 读写文件的速度足够快

序列化

• 一个Checkpoint为一个特定时刻（一条对话脚本执行前）全部游戏状态，包括变量和所有前端组件状态，不包括全局变量的状态，可以根据Checkpoint完全恢复出该游戏时刻
• 每个有状态的前端组件实现IRestorable，它的状态表示成IRestoreData
• 一个Checkpoint存储在GameStateCheckpoint中，GameStateCheckpoint由BinaryFormatter序列化后再用DeflateStream压缩
  • BinaryFormatter有比较大的Overhead，所以需要压缩
  • 我们没有提供存档加密功能，因为代码是开源的，如果需要加密请自行解决
• 并不是每条对话都会存储Checkpoint，大部分对话在读档的时候会先恢复到之前最近的Checkpoint，然后再重新执行一遍脚本。默认情况下经过一定对话数量自动做Checkpoint，在某些时候会强制启用（NodeRecord开始，小游戏）或禁用（持续动画）Checkpoint
• 除此之外，还有一部分存档中的内容也是用BinaryFormatter进行序列化的，如果更换序列化方式也会同步更换

存档文件格式

• 为了提高读写效率，存档文件按固定大小（默认为4K）分块（CheckpointBlock），块与块之间以单链表连接，一个链表表示一段连续数据
• 块会缓存，只在特定时候回写（CheckpointManager.UpdateGlobalSave）
• 块内为多个顺序存储的不定长记录（Record），并且由于是顺序存储，记录只支持尾部插入，不支持删除，并且保证需要更新的记录长度不变。由于不能保证序列化的长度（取决于序列化方式），因此这一部分定长记录不会使用序列化而是手动转化为二进制数据

目前所有的块组成三个单链表，分别存储以下内容：

• GlobalSave：只包含一条记录（GlobalSave），用来存储所有全局变量、存档版本、块的MetaData等信息，由于只包含一条记录，所以即使不是定长的也可以更新，在回写的时候更新该记录
• Reached：包含2种记录，这2种记录都是序列化的：
  • ReachedDialogueData：已读对话，其中已读对话还存储该对话的语音信息和该文本是否需要插值（needInterpolate）
    • 这里存储的是全局共享的已读信息，不依赖于存档，这个数据用于在快进时判断是否已读以及构建文本回顾界面
  • ReachedEnd（string）：已读结局，同样是全局的
• Checkpoint：包含3种记录，组织成一棵树，存储所有游戏历史
  • NodeRecord：表示一个树结点，每个NodeRecord覆盖同一个Node内的若干条对话和若干个Checkpoint
    • NodeRecord覆盖的第一条对话（beginDialogue）前会强制做Checkpoint（也就是第一个Checkpoint一定对应beginDialogue），但结尾不需要，所以需要分开存储endDialogue和lastCheckpointDialogue
    • 由于某些原因，endDialogue表示最后一条对话的编号+1（左闭右开），但lastCheckpointDialogue不+1
    • NodeRecord的连接关系通过child-sibling表示法存储，子女间的分歧仅由跳转到的Node和跳转时的变量决定
      • 举例而言，如果两次跳转到同一个Node且变量完全相同，即使是不同的分支，也不会记录新的NodeRecord
    • NodeRecord由于需要更新，为定长记录
    • 同一个Node可能会产生多个NodeRecord，目前有两种情况会造成这个结果，这两种情况都会调用GameState.AppendSameNode增加一条新的NodeRecord：
      • 同一Node内的脚本需要在不同条件下产生不同的结果，比如小游戏
      • 当前正在写的NodeRecord不处于顺序表末尾但是需要添加新的Checkpoint
  • CheckpointHeader：目前只存储该Checkpoint对应的对话编号，主要是考虑性能在遍历的时候不需要读取和反序列化整个Checkpoint就能得到这个信息
  • Checkpoint：即序列化的GameStateCheckpoint，和CheckpointHeader成对出现

游戏状态

• 一个特定时刻的游戏状态由：NodeRecord（或nodeOffset，对应存档内记录offset）、checkpointOffset（存档内CheckpointHeader记录offset）和对话序号（dialogueIndex）唯一确定
  • Checkpoint和对话必须是NodeRecord所覆盖的
  • 该时刻的全部历史记录由该NodeRecord到树根结点的路径所覆盖，目前GameState.GetDialogueHistory会返回这个迭代器
• 读档时先恢复Checkpoint，然后再快进脚本直到目标对话前
• 可能的节点历史的数量随着分支选项和小游戏结果的数量增加而指数增长，但是我们只会记录玩家遇到过的节点历史。在最坏情况下，Checkpoint占用的硬盘随着游玩时间而线性增长

书签

• 存档/读档界面中的每个存档称为书签（Bookmark），记录nodeOffset、checkpointOffset和dialogueIndex
  • 读档时，提供这些信息就能恢复checkpoint
• 自动存档、快速存档与手动存档的格式是一样的

文本回顾界面

• LogEntry：当前历史对话的nodeOffset、checkpointOffset和dialogueIndex
  • 在Log界面中回跳时，提供这些信息就能恢复该历史对话
• LogEntryRestoreData：只存储需要插值的历史对话，LogEntry不需要全部存储到Checkpoint中
  • 全部历史对话可以通过遍历当前NodeRecord的祖先得到（GameState.GetDialogueHistory）
  • 不需要插值的文本通过FlowChartTree得到
  • 语音通过ReachedDialogueData得到
  • 出于性能考虑，需要避免反序列化太多的Checkpoint，因此在每个Checkpoint中都存储全部的LogEntryRestoreData，这样只需要反序列化一个Checkpoint，但相应的需要O(N^2)的存储空间

TODO List

• 随机数
• BinaryFormatter已经被微软官方deprecate了，并且效率不高，考虑换成JSON或者其他格式，目前存档文件的设计和序列化方式无关
• NodeRecord存储完整的变量信息不要只存储Hash
• 可以考虑仿照文本在LogEntryRestoreData中加入需要插值的语音信息，但和文本不同，无法判断两次运行的语音会不会改变
• LogEntryRestoreData使用树状数组可以降低到O(NlogN)的存储空间，但需要反序列化O(logN)个Checkpoint