Restoration Upgrade

存档升级

设计目标

• 在更新脚本时保持存档继续可用，目前如果更新脚本大部分情况会导致原存档没法用或者出现bug
• 避免引入额外存档或其他信息（如原脚本）
• 相同名字的节点视为同一个节点，不考虑逻辑上的bug
  • 比如，某个存档的状态在新脚本中是存在但是不可能到达的，但是在旧脚本中是可能到达的，这种存档会被升级并保留
  • 如果一条已读的旧对话在一条新对话之后，那么在存档升级后，新对话会变成已读
    • 特别地，如果一个节点在旧存档中已经读完并跳转到一个新的节点，那么新节点中的所有对话都会变成已读
  • 上述情况是因为存档的连续性，如果你已经经历过事件A，那么即使世界线发生变动，你逻辑上也应该经历过新的世界线的事件A之前的所有事件
• 其他的限制：
  • 如果在已读对话中添加或修改了小游戏（或者移动了小游戏的位置），由于我们无法模拟小游戏的交互，目前整个存档升级会失败
• 游戏制作者需要根据脚本修改的情况自行判断存档升级是否会导致逻辑问题
  • 如果只是增加了新的分支和节点，则不会有问题
  • 如果修改了已有节点，比如加入了新对话，调换对话位置等，在大部分情况下不会有问题，只是新对话可能会变成已读的
  • 如果修改了节点之间的逻辑关系，可能会导致逻辑bug
  • 如果在已有节点中添加了小游戏等功能，则有较大的风险会导致存档无法升级

存档中增加的信息

• GlobalSave中增加了每个节点的hash值（nodeHashes），用来比较节点是否发生改变
• ReachedDialogueData中增加了该已读节点的hash值（textHash），用来比较对话是否相同
  • 该hash会同时考虑脚本和对话文本，并且只考虑默认语言
  • 由于我们不存储原脚本，并且存档升级只需要考虑将目前已读部分的存档转换成新的脚本，所以只需要添加这个信息就可以进行存档升级

Differ

• 这个类用来比较新旧节点中不同的对话，原理类似于Linux的diff，输出结果包括：
  • 新旧节点的距离（distance），即最少需要增/删多少次才能使旧节点变为新节点
  • 需要增/删的对话编号（inserts表示新增对话在新节点中的编号，deletes表示删除对话在旧节点中的编号）
  • 新节点中的每一条对话在旧节点中的编号（remap，-1表示这是新增的对话）
  • 旧节点中的每一条对话在新节点中编号的下界（leftMap）和上界（rightMap），即其上一条（包括自己）和下一条（包括自己）未被删除的旧对话在新节点中的编号
• 算法参考：Myers, An O(N D) Difference Algorithm and Its Variations
  • 事实上只有leftMap和rightMap是最终用到的信息，但先计算上述结果实现起来比较方便，并且这些部分复杂度只有O(N)，相比核心部分可以忽略
  • 计算distance（以及数组V）是算法的核心，最坏复杂度是O(N D)，但期望复杂度是O(N + D^2)，其中N是两个节点的长度和，D是distance
  • 本质上来说这个算法和LCS（最长公共子序列）的原理类似，但是LCS的复杂度是O(N^2)
  • 由于旧节点并不一定包括所有的对话（因为有可能这个节点只读了一部分），并且在不引入其他信息的情况下也不知道旧节点一共有多少对话，因此我们对算法进行了修改，相当于是在匹配旧节点和新节点的一个前缀
    • 上述distance、inserts和deletes都是在这个含义下定义的
    • remap包含整个新节点，尾部新增的对话都map到-1
    • leftMap和rightMap在这个含义下定义不发生改变，不过由于distance定义不同，增/删的方式会不一样，因此结果不同

升级ReachedData

• 新增了一种IReachedData：NodeUpgradeMaker，用来表示某个节点经历过升级，如果有多次升级则会有多条这样的记录
• ReachedEndData不考虑升级，因为在新存档中即使有已被删除的结局，也不会有任何影响，并且我们不考虑逻辑上的bug
• 由于存档文件的设计，旧的ReachedDialogueData无法删除，而是插入一条NodeUpgradeMaker记录
• 当读到一条NodeUpgradeMaker记录时，会忽略这条记录之前所有对应节点的ReachedDialogueData
• 新的ReachedDialogueData会在升级NodeRecord时加入

升级NodeRecord

• 基本思路：从每个NodeRecord的开头出发，运行一遍整个NodeRecord，作为升级过后的NodeRecord
• 首先，确定这个NodeRecord覆盖的区间在新脚本中的区间，可以根据Differ得到
• 其次，恢复这个NodeRecord的第一个checkpoint，然后运行脚本来得到其他的checkpoint
• 如果一个NodeRecord需要删除，有两种情况：
  • 这个节点在新脚本中不存在了，这时我们会删除整个子树，因为没有其他信息将这个节点的孩子连接到其他节点上
  • 这个NodeRecord作为某个节点的一部分在新脚本中不存在了，这时我们必须要求：或者这个节点没有兄弟，或者这个节点只有一个孩子，否则也无法将这个节点的孩子连接到其他节点上
    • 这种情况只有可能发生小游戏中，会直接抛出异常
• 升级过后的NodeRecord作为新的记录加在整个checkpoint链表的末尾
  • 旧的NodeRecord无法删除，但是我们会更新所有NodeRecord中的引用以及Bookmark，以确保旧的存档不会被读取

升级checkpoint

• 如果新增了前端组件，在旧存档中没有数据，我们会使用GameState.initialCheckpoint中的初始值
  • 游戏制作者需要避免新的前端组件与某个旧版本重名
• 如果修改了前端组件，而没有更改restorableName，就要由游戏制作者在Restore中根据旧存档中的数据进行升级

升级过程（GameState.CheckScriptUpgrade）

• 遍历新的节点，对hash发生变化的节点运行Differ并记录结果
• 遍历旧的节点，记录需要删除的节点
• 对所有发生改变的节点，插入NodeUpgradeMaker记录
• 遍历所有NodeRecord，升级
• 修改Bookmark中的offset和dialogueIndex，dialogueIndex的对应关系可以通过Differ得到