4月27日，在2021N.Game网易游戏开发者峰会程序论坛上，《银河前夜》总导演张凯发表了《基于不可变数据结构的编辑器开发》的主题演讲。
他表示，现代游戏的玩法设计和表现效果越来越复杂。 定制化的编辑器和工具链对于提高游戏开发效率至关重要。 为了在有限的开发时间内为团队提供尽可能多的稳定好用的编辑器和工具，《星战前夜》团队在工具链开发上进行了很多探索。 在本次演讲中，他分享了如何利用Immutable数据来大幅提升编辑器的开发效率和运行稳定性。
以下为演讲实录：
大家好，我是网易《星球大战前夜：无烬银河》的张凯。 很高兴今天来到这个峰会怎么制作游戏修改器，跟大家分享我们项目的发展经验。 我们今天的主题是“洞察”，所以我希望给大家带来看看如何提高我们游戏背后的编辑器的开发效率，从而进一步提高游戏的开发效率。
根据需求定制编辑器，开发维护成本不断增加
随着现代游戏变得越来越复杂，自定义编辑器已成为项目开发过程中不可或缺的一部分。 在《星战前夜：无烬银河》的开发过程中，我们逐渐积累了越来越多的定制编辑器。 随着编辑器越来越多，我们发现相关的开发和维护成本也越来越高。 下面通过一个简单的例子来说明一下我们遇到的是什么样的维护成本。
图为游戏编辑器中一个很常见的操作。 单击并拖动对象以在场景中移动它。 另一个非常常见的操作是撤消。 一般来说，我们会封装一个编辑器框架。 当你改变一个数据对象时，会自动触发一个事件来通知相应的UI控件进行更新。 相应的命令也会被封装并放置在命令栈中，用于undo和redo。 在这种场景下，我们会遇到什么问题呢？
你可以注意到，当我们取消时，对象的位置总是直接返回到起点。 毕竟在不断的拖动过程中，会发生几十甚至上百次的位移。 我们绝对不希望艺术生表演那么多次。 撤消操作可以将其移回到起始点，因此这意味着我们不能直接使用封装的帧。
这不是一个非常复杂的问题。 我们无法在移动过程中修改真实的位移数据，而是在释放鼠标按键后才真正修改。 直到一位美术同学给了我们这样一个要求：在移动的同时，我也想看到数控上数字的变化，这样我就可以方便地观察到数据是如何变化的。
这时候我们就得在原来的框架中添加新的事件机制来通知与拖动位移相关的UI控件进行更新。 像这样的特殊事件给我们整个编辑器带来了更高的维护成本，因为不同的学生要针对不同的特殊事件添加新的机制，而当其他学生接手时，就有很高的学习成本；
另一方面，随着事件变得越来越复杂，整个编辑器的稳定性也在逐渐下降，因为事件越多，出错的概率就越大，而一旦出错，调试时间就会很长。
每个新操作还封装了撤消和重做指令。 流程也非常繁琐，导致我们很难提高编辑器的开发效率，所以我们想解决这些问题。
回到编辑器，我们现在有了一组数据橙光游戏，并且我们有一个 UI 界面来显示这些数据。 我们要做的是当数据发生变化时，我们的界面也随之变化。 如果没有事件，告诉我们发生了什么样的数据变化，我们怎么知道应该改变什么样的UI？ 最简单的方法是删除整个 UI 并重建它。 为什么很多应用程序开发不使用这种方法？ 众所周知，当你想要完全重建一个非常复杂的界面时，开销是非常高的。 有什么办法可以解决这个问题吗？
声明式 UI 无法表达所有 UI 元素，并且没有撤消和重做选项
事实上，我们发现这个问题不仅仅存在于游戏编辑器开发领域。 在传统应用开发领域，人们也一直在尝试解决这个问题，我们觉得目前最有希望的答案是声明式UI。 声明式 UI 如何解决这个问题？
与我们直接基于数据创建整个 UI 的常见做法不同，声明式 UI 通常依赖于虚拟 UI 层来抽象此行为。 虚拟UI是指不实际渲染在屏幕上，但可以用来完整描述UI界面的内存数据。
它的创建非常高效，因此在声明式UI的框架中，当你的数据发生变化时，你总是可以重新创建一个完整的虚拟UI。 有了这个新的虚拟UI并与旧的虚拟UI进行比较，我们就可以得到真正需要修改的界面部分。
常见的声明式UI框架有Flutter、React、SwiftUI等，这些都是目前前端领域广泛使用且成熟的框架。 虚拟UI在Flutter中被称为蓝图，它就是React中著名的虚拟DOM。
那么为什么声明式 UI 这么好，我们为什么不直接采用声明式 UI 呢？
首先是声明式UI的虚拟层作为一般应用程序的框架，无法表达游戏编辑器中所需的所有“UI”元素，这一点我们稍后会提到。 理论上，我们可以自己维护一个虚拟UI解决方案，但这会带来非常大的开发成本；
第二是因为声明式UI仍然没有提供高效的撤消和重做解决方案，所以即使我们采用声明式UI，我们仍然需要寻找另一种解决方案来解决撤消和重做的问题，所以我们需要进一步寻找新的答案。
回到这个问题，如果没有虚拟UI的帮助，我们为什么不直接比较新旧数据呢？ 如果我们知道哪部分数据发生了变化，当然可以很简单地更新相应的UI。
但我相信每个人都会知道其背后的原因。 比较操作实际上常常有很大的开销，并且比较操作常常需要更复杂的代码。 相信重载过比较运算符的同学都会明白这一点。 ，甚至当你想要比较前后两条数据的状态时，你首先必须进行复制，而复制这个行为本身效率很低，所以这就阻碍了人们通过数据比较来更新UI。
不可变数据结构的3大优点
但其实并不是所有的数据结构都有这样的限制，所以这就是我们今天要讲的主角——不可变数据结构，也就是我们常说的不可变数据。
什么是不可变数据？ 从字面上理解，就是数据一旦生成，就无法再更改。 如果要更改，必须先制作新副本，然后对新副本进行更改。
例如，我们有一个包含三个元素的不可变列表。 当我们向列表中插入一个新元素时，它将返回一个新列表。 可以看到原来的列表没有变化。 这是一个不可变的数据结构。 对于不可变的数据结构，意味着每次数据发生变化都会生成新的数据。
这种情况下，只需判断两条数据是否相同，就可以知道这部分数据是否发生了变化。 比较两个数据是否相同的操作非常高效。 同时，由于Immutable数据的特性，其复制操作也非常高效。 稍后将讨论它如何实现这一点。
回到刚才我们面临的问题，我们可以从数据的源头对比新旧状态，找出哪些数据真正发生了变化，从而有针对性地更新我们的UI表现。 问题将会得到解决。 我们唯一需要额外注意的是列表的比较。
这是两个列表，旧的和新的。 列表是我们编辑数据时非常常见的数据结构。 比如你有一个模型列表，一个特效列表等等，按照刚才的方法，我们对比两个列表的数据，然后你会发现列表中的每一项都发生了变化。 所以我们需要相应地更新整个列表元素对应的UI。
但实际上，如果我们仔细看这两条数据，我们会发现我们只是在前面插入了一个新元素，并不需要更新所有后续元素。
这里需要的是知道两个列表之间的最小编辑距离，从而尽量减少列表变化时需要的UI更新操作。 寻找两个列表之间的最小编辑距离（即编辑距离）的算法的时间复杂度为 O(n*m)。 当你的列表非常大时，这个时间复杂度是不可行的，而在游戏开发领域，每个人都知道，当你编辑很多内容时，这个列表可能会非常大。
例如，如果您正在编辑一个大世界场景，您的列表中可能有数百或数千个模型，因此我们无法使用此算法。 但幸运的是，我们不需要在所有情况下都找到最佳解决方案。 我们所需要的只是一个足够好的结果。 我们使用的最后一种方法是启发式列表差异算法。 这个列表 diff 实际上指的是 React 的实现。 虽然我们没有使用声明式 UI 框架，但我们从声明式 UI 框架中学到了很多东西。
什么是列表差异？ 给定列表 a 和列表 b，该算法返回从列表 a 更改为列表 b 所需的操作。 我们基于这个算法做了两个功能。
第一个是我们的list diff在以下三种情况下总会返回最优解：第一种是删除单个元素； 第二种是插入单个元素； 第三个是列表中单个元素的位置。 感动了。 列表中的移动操作是前两个操作的组合。 为什么我们总是保证这三个操作返回最优解？ 回想一下，艺术和规划的学生在使用编辑器的时候，数据往往是一一改变的。 这也是整个编辑过程中列表最有可能发生变化的情况，所以我们希望让他们不断返回最优解。
第二个特点是我们总是把删除操作放在前面，插入操作放在最后。 这样我们就可以重用一些 UI 控件。
有了list diff算法，列表类的UI更新变得非常简单。 首先，我们会使用list diff来找出新旧数据发生了哪些变化，以及需要进行哪些操作才能使旧数据变成新数据。 然后我们将这些操作一一进行。 对于删除操作，我们会取出对应的UI元素。 取出来后，我们不会直接销毁它，而是放入缓存中保存。 当执行插入操作时，我们会进行检查。 如果缓存中当前有相关的UI元素可用，我们会直接从缓存中检索对应的元素，以减少元素的创建。
有了上面封装的列表视图怎么制作游戏修改器，我们在编辑器中以列表的形式展示一组数据就变得非常简单了。 首先，你需要使用一个不可变的列表来保存你的数据，然后你只需要继承ListViewBase即可。 在这个类中，你只需要做一件事情，就是告诉列表容器中的每个元素需要如何渲染以及需要如何渲染。 这样的UI元素，然后你只需要调用刷新函数就可以刷新整个列表。
对于像任务这样的数据，本质上很容易将其表达为不可变数据，这使得这个新框架看起来非常有用。 然而，我们有的同学问，如果编辑编辑的是3D模型，那我该怎么办？
因为我们不太可能将引擎中的核心元素（例如模型效果）实现为不可变的数据结构。 即使我们能够实现它，也可能会非常昂贵。 那么如果我们想要编辑一个3D模型，编辑一个特效，我们该怎么办呢？
事实上，3D模型本身就是一个UI元素。 以小编辑器为例。 无论是通过传统的数值UI控件，还是通过在场景中拖动和旋转模型，我们这里改变的始终是这组抽象的不可变的数据结构。 数据，而不是操作模型或特效本身，因此模型和特效本身只是特殊的 UI 元素。
事实上，使用不可变数据结构之后，处理如此复杂的模型效果的编辑变得更加容易，因为使用不可变数据结构可以让我们将数据更新和UI更新解耦。 这会带来什么好处？
数据更新通常是同步的并且发生得非常快。 但 UI 更新有时是异步的。 比如我们刚才提到的模型的加载往往是一个异步过程，或者UI界面上的动画本身也是一个异步过程。 如果一个同步事件与一个异步事件耦合在一起时，往往会导致很多复杂情况。
当数据更新和UI更新解耦后，我们什么时候应该更新UI呢？ 答案是固定帧率。 这对于游戏开发的同学来说已经很熟悉了，因为我们的游戏总是以固定的帧率刷新。 我们刚刚将这个概念带回到编辑器中。
下面通过一个具体的例子来说明解耦的好处。 在场景编辑器中，我们有一个显示场景中所有模型的 UI 列表，以及一个提供场景预览和编辑的场景窗口。 当美术同学向场景中插入新的模型时，那么在下一个更新周期中，我们的列表和场景就会根据变化开始更新。 列表中将显示一个新模型，场景将开始加载新模型。
但此时美术同学突然意识到我选错了模型，于是他立即决定删除该模型，然后模型就从列表中删除了，但场景中的模型仍在加载。 如果是基于事件的更新，您将面临删除加载模型的问题。 如果选择直接删除已卸载的模型，编辑器将会崩溃。 如果忘记删除它，场景中就会出现不受控制的模型。
基于不可变的数据结构，如果我们将数据更新和UI更新解耦，这时候我们的处理就会变得非常简单。 在加载过程中，我们只需要忽略数据变化，让模型静默加载即可。 这时场景中就会出现一个多余的模型。 我们会在下次更新的时候通过数据对比找到它，然后将其删除，这样就大大减少了我们在这个过程中出错的可能性。
当使用不可变数据结构时，撤消和重做几乎是免费的。 它的原理也很简单，就是我们把所有变化的数据放到一个列表中保存起来。 当我们需要撤销的时候，我们只需要回去找到历史数据，重新取出来就可以了。
前面我们提到了连续拖动的一个特例。 其实解决办法很简单。 我们只需要合并在一个很小的时间阈值内连续发生的变化，并将它们放入历史列表中。
所以这就是目前整个《夏娃：没有余烬的银河》项目中编辑器的核心框架3D道具，而且非常简单。
我们首先会有一个历史数据队列，里面保存了我们所有编辑过的历史状态，然后我们的编辑器会定期从历史中选取最新的数据，并将数据交给我们的UI界面进行刷新。
我们根据级别将所有UI分为不同的视图。 这里我们也借鉴了React中基于组件的UI设计。 我们将一个大的接口划分为更小的抽象接口的概念。 每个接口只做它负责的事情。 这样我们既可以提高代码复用率，也可以减少各种UI界面和UI控件之间的交互。 逻辑复杂性。
当视图修改数据时，会生成一条新数据，我们将这条新数据插入到历史队列中。 在下一个更新周期中，所有UI控件都将根据新数据进行更新。 当我们需要撤销一个操作时，我们只需回滚历史队列中的指针即可。
说完我们整个编辑框架，我们再回过头来和声明式 UI 进行比较。 Declarative UI主要基于一个虚拟的UI层来解决数据和UI之间的同步问题。 他们不提供对撤回或重做的直接支持。 毕竟，它是一个用于更通用的应用程序开发的框架。 它的UI代码会非常简单，但是整个框架会更多的依赖一个非常强大的开发团队来维护。
基于不可变数据结构的UI依赖于特殊的不可变数据结构。 它的优点是直接提供对undo和redo的支持。 UI代码会稍微复杂一些，因为我们依赖所有数据都表示为不可变的数据结构，但是它的框架代码会非常简单。
对于我们的应用场景来说，游戏开发团队通常只有一个小型的编辑器开发团队，而撤销和重做对于编辑器来说是非常关键的功能需求。 因此，基于不可变数据结构的UI解决方案自然成为了我们的选择。
但事实上，这两个UI框架并不冲突。 在React的实践中，也鼓励大家在使用声明式UI的同时，使用不可变的数据结构。
这是一个例子。 在一些非常复杂的界面中，即使使用声明式UI来创建完整的虚拟界面，开销仍然很高，所以这时候React提供了一个接口shouldComponentUpdate()，它会返回一个组件虚拟界面。 是否需要改变。 在不使用不可变数据的情况下，需要实现复杂的重载比较来做出判断。
如果你使用不可变数据结构来表达内部状态，这个比较就变得非常简单，所以声明式UI和不可变数据结构本身可以很好的结合起来，也许在你的项目中使用声明式UI进行UI开发时，使用不可变数据结构来保存数据你实际上是在编辑。
不可变数据结构的实现原理
最后简单说一下不可变数据结构是如何快速复制数据然后修改的。
不可变数据结构的研究其实很早以前就开始了。 目前大多数不可变数据结构的实现都参考了 Rich Hichkey 在 Clojure 语言中的实现。
在 Clojure 这种有趣的语言中，几乎所有本机数据结构都是不可变的。 Rich Hichkey 在该语言中使用的数据结构实际上是 Phil Begwell 发明的 Hash Array Mapped Trie。 Hash Array Mapped Trie本身并没有被设计成一种不可见的数据结构，但它的特性使得它很容易被用作不可变数据结构的实现。
在看到 Rich Hichkey 以如此有趣的方式使用其数据结构后，Begwell 也对这个领域非常感兴趣。 后来他写了一篇新论文，发明了一种更高效的不可变数据结构。
让我们举一个简单的例子。 这是我们对不可变列表的常见实现。 你可以看到它后面其实有一棵树。 这棵树中的所有节点都是等长数组，所有列表数据都存储在叶子节点上。
当我们要修改其中一条数据时，我们会先复制该数据所在的叶子节点，然后修改它的数据，然后复制它的所有祖先节点，得到一个新的链表。
可以看到新链表和旧链表共享很多内部节点，所以效率很高。 在经典实践中，节点数组的长度通常设置为32。大多数情况下，树的深度很浅，因此复制的复杂度可以近似视为恒定级别。
结论
在《夏娃前夜：没有余烬的银河》项目中，任务编辑器是我们第一个尝试使用不可变数据结构来重写的编辑器，因为它本身就有非常复杂的数据表达，但是它的UI逻辑却相对比较简单非常适合我们作为实验使用。 使用不可变数据结构修改后的编辑器减少了近30%的代码，而且我们在开发过程中几乎没有遇到严重的bug，因为整个框架和整个编辑器的结构都非常简单。
不可变数据结构还有许多其他优点和特性。 例如，因为不可变数据的特性决定了它天然是一种无锁的线程安全的数据结构，你可以将一些非常复杂的数据操作移到另一个线程，而不用担心你的UI线程和你的数据线程之间的任何竞争；
另一方面，由于不可变的数据结构实现了数据更新和UI更新的解耦，当我们实现多人实时协作的编辑器时会简单很多。 我们想知道您是否在自己的项目中使用过它。 使用不可变数据结构，或者说以后大家在自己的项目中会如何引入不可变数据结构。
