研发设计

4月27日，在2021N.Game网易游戏开发者峰会的程序论坛上，《星战前夜：无烬星河》的主程张凯带来《基于不可变数据结构的编辑器开发》的主题演讲。

他表示，现代游戏的玩法设计、表现效果都越来越复杂。定制化的编辑器和工具链对于提高游戏的开发效率至关重要。为了在有限的开发时间内为团队提供尽可能多稳定好用的编辑器和工具，《星战前夜：无烬星河》团队对工具链开发进行了诸多探索。此次演讲，他分享了如何利用Immutable data大幅提升编辑器的开发效率和运行稳定性。

以下是演讲实录：

大家好，我是来自网易《星战前夜：无烬星河》的张凯，很高兴今天来到这个峰会给大家分享我们项目的开发经验，我们今天的主题是“洞见”，所以我希望带大家来看一看在我们游戏的背后，是如何提高编辑器的开发效率，从而进一步提升游戏的开发效率的。

针对需求做定制化编辑器，开发和维护成本不断堆高

随着现代游戏越来越复杂，定制化的编辑器成了一个项目开发过程中不可或缺的一部分。《星战前夜：无烬星河》的开发过程中，我们也是逐渐积累了越来越多的定制化编辑器。随着编辑器越来越多，我们发现相关的开发和维护成本，也变得越来越高，这里有一个简单的例子可以解释我们遇到了什么样的维护成本。

图中展示的是游戏编辑器当中一个非常常见的操作，通过鼠标点击拖拽一个物体在场景中移动，同时还有另一个非常常见的操作就是撤销。通常来说我们会封装一个编辑器框架，当你改变一个数据对象时，会自动触发事件去通知对应的UI控件更新。还会封装相应的命令放到命令栈中供撤销和重做。在这个场景下，我们遇到了什么问题呢？

大家可以留意到当我们撤销的时候，物体的位置总是直接回到了起点，毕竟在连续拖拽的过程中会产生几十甚至上百个位移，我们肯定不希望美术同学要执行这么多次的撤销操作才能把它移回起点，所以这就意味着我们不能直接使用已经封装好的框架。

这也不是一个很复杂的问题，我们可以在移动过程中不产生真正位移数据的修改，而是在松开鼠标按键之后才实际修改。直到美术同学给我们提了这样一个需求：我在移动的过程中，我还想在数值控件上看到数字的变化，方便观察数据是如何变化的。

这个时候我们不得不在原有的框架下，加入一套新的事件机制，来通知跟拖拽位移相关的UI控件进行更新。类似这样的特殊事件，给我们整个编辑器带来了更高的维护成本，因为不同的同学要为不同的特殊事件加入新的机制，其他同学接手的时候，就有很高的学习成本；

另一方面，随着事件越来越复杂，整个编辑器的稳定性，也在逐渐地下降，因为事件越多，出错的概率就越大，而且一旦出错，debug的时间会很长。

还有为每个新的操作封装撤销和重做的指令，过程也是非常繁琐的，使得我们难以提高编辑器的开发效率，所以我们想要解决这些问题。

回到编辑器，我们现在有一组数据，我们有展示这个数据的UI界面，我们想做的是当数据发生改变的时候，我们的界面也发生对应的改变，如果没有事件告诉我们什么样的数据发生了改变，我们怎么知道应该改变什么样的UI呢？最简单的方式就是把整个UI都删掉，然后重建一个。为什么这么多应用的开发不采用这种方式，原因大家也知道，当你要完整的重建一个非常复杂的界面时，他的开销是很高的，有没有办法解决这个问题呢？

声明式UI不能表达全部UI元素，没有撤销和重做方案

事实上我们发现这个问题并不只是存在于游戏编辑器的开发领域，在传统的应用开发领域，人们也一直试图在解决这个问题，而我们觉得目前最有希望的答案就是声明式UI。声明式UI是怎么解决这个问题的呢？

和我们常见的直接根据数据创建整个UI不同，声明式UI往往依赖虚拟UI层来抽象这个行为。虚拟UI指的是并不会在屏幕上真正渲染，但可以用来完整描述UI界面的内存数据。

它的创建是非常高效的，因此在声明式UI的框架中，当你的数据发生改变的时候，你总是可以重新创建一份完整的虚拟UI。有了这份新的虚拟UI，再和老的虚拟UI去做对比，我们就能得到真正需要去修改的界面部分。

常见的声明式UI框架包括Flutter、React和SwiftUI等。这些都是目前在前端领域用得非常多且成熟的框架。虚拟UI在Flutter里面被称之为blueprint，而在React里就是有名的virtual DOM。

所以为什么声明式UI这么好，我们不直接采用声明式UI？

首先是声明式UI的虚拟层作为一个面向通用应用程序的框架，它不能表达在游戏编辑器中需要的所有“UI”元素，后面我们会提到。理论上我们可以自己维护一个虚拟UI方案，但这会带来非常大的开发成本；

第二个是因为声明式UI仍然没有提供高效的撤销和重做的解决方案，所以即使我们采用了声明式UI，仍需要找到另一个方案来解决撤销和重做的问题，所以我们还需要进一步去找新的答案。

回到这个问题，如果我们没有虚拟UI的帮助，我们为什么不直接对比新旧两份数据？如果我们知道数据在哪个部分发生了改变，当然就可以非常简单地去更新相应的UI。

但背后的原因我相信大家也都会清楚，比较操作实际上往往是有着不小的开销的，而且比较这个操作往往还需要比较复杂的代码，相信做过重载比较操作符的同学都会有所体会，甚至你想去比较前后两份数据的状态时，你首先得copy，而copy这个行为本身是不高效的，所以这阻止了人们采用通过数据比较的方式更新UI。

不可变数据结构的3大优势

但事实上并不是所有的数据结构都有这样的限制，所以这就是我们今天要讲的主角——不可变数据结构，也就是我们常说的Immutable data。

• 快速判断前后两份数据的异同，实现高效操作

什么是immutable data？从字面意义上理解它指的是这个数据一旦生成之后，再也不能改变。如果你想要改变它，你必须首先生成一份新的拷贝，然后在新的拷贝上做改变。

比如我们有一个不可变的列表，这个列表里面有三个元素，当我们向这个列表中插入一个新的元素时，它会返回一个新的列表，可以看到原有的列表是保持不变的。这个就是不可变的数据结构。有了不可变的数据结构，就意味着每一次数据改变时都会生成一份新的数据。

在这种情况下，你只需要判断前后两份数据是不是同一个，就知道这部分数据是否发生了改变。而比较两份数据是不是同一个的操作是非常高效的。同时由于Immutable data的特性，它的copy操作也是非常高效的。它是如何实现这一点，我们在后面会讲到。

回到刚才我们面临的问题，我们可以从数据的源头上对新旧两个状态进行比较，找到哪一个数据发生了真正的改变，从而去针对性的更新我们的UI表现。问题也就迎刃而解。唯一需要我们额外关心的，是列表的对比。

这是新旧两个列表，列表是我们在编辑数据时非常常见的数据结构，比如说你有模型的列表、特效的列表等等，按照刚才的方式，我们对两个列表的数据进行比较，然后会发现列表中的每一项，都发生了改变。于是我们需要对整个列表元素对应的UI都进行相应的更新。

但事实上如果我们仔细去看这两份数据，就会发现我们只是在前面插入了一个新的元素而已，我们不需要对后面所有的元素都进行更新。

这里需要的是要知道两个列表之间的最小编辑距离，从而尽可能的减少在列表发生变更时所需要的UI更新操作。找到两个列表之间最小编辑距离的算法，也就是Levenshtein distance，它的时间复杂度是O（n*m）。这个时间复杂度当你的列表很大的时候是不太可行的，而在游戏开发领域，大家都知道当你编辑的内容非常多的时候，这个列表可能会非常大。

比如你在编辑一个大世界的场景，你的列表里面可能有成百上千个模型，所以我们不能用这个算法，但庆幸的是我们也并不是在所有情况下都需要一个最优解，我们只需要一个足够好的结果就可以了。最后我们使用的方式是一个启发式的list diff算法。这个list diff实际上也是参考了React的实现。我们虽然没有使用声明式UI框架，但我们从声明式UI框架里面学到了很多东西。

什么是list diff?给定一个列表a和列表b，这个算法会返回从列表a变到列表b所需要的操作。我们在这个算法基础上去做了两个特性。

第一个是我们的list diff总会在以下的三种情况下返回最优解：第一个是删除单个元素；第二个是插入单个元素；第三个是单个元素在列表中的位置发生了移动。在列表中的移动操作就是前面两个操作的组合，为什么我们要对这样三个操作总是保证返回最优解？大家回想一下在美术和策划的同学去使用编辑器的时候，数据往往是逐个变更的，这也是我们在整个编辑过程中，列表最容易发生变更的情况，所以我们希望在这种情况下让他们保持返回最优解。

第二个特性是我们永远让删除操作放在前面，插入操作放在后面。这是为了我们可以复用一些UI控件。

有了list diff算法，列表类的UI更新就变得非常简单，首先我们会使用list diff找出新旧两份数据发生了什么样的改变，我们需要做什么样的操作能让老的数据变成新的数据。然后我们会逐个执行这些操作。对于删除操作我们会取出对应的UI元素，取出之后我们并不会直接将它销毁，而是把它放到cache里面保存起来。在执行插入操作的时候我们会检查，如果目前cache中有相关UI元素可以用，我们就会直接从cache中取出对应的元素来减少元素的创建。

有了上面封装好的list view之后，我们在编辑器里面想用列表的形式去展示一组数据就变得非常简单。首先你需要使用一个不可变的列表来保存你的数据，然后只需要继承ListViewBase，在这个类里面你只需要做一件事情，就是告诉这个列表容器里的每一个元素，需要怎样渲染，需要怎么样的UI元素，然后你就只需要调用refresh函数就可以刷新整个列表。

• 将数据更新和UI更新解耦，轻松处理复杂的UI更新

对于像任务这样的数据，它天生就很容易被表达成不可变的数据，让这新的框架看起来很好用，但是我们有的同学就问到了如果编辑器编辑的是一个3D模型，那应该怎么办？

因为我们不太可能把引擎中像模型特效这样很核心的元素实现成不可变的数据结构，即使可以实现它也在开销上可能也很大，所以说我们如果要编辑一个3D模型，编辑一个特效，我们应该怎么做呢？

事实上3D模型本身就是一种UI元素。以小的编辑器为例，无论是通过传统的数值类的UI控件，还是场景里面通过拖拽、旋转去操作这个模型，我们在这里面改变的永远是这一组抽象的基于不可变数据结构的数据，而不是去操作模型或者特效本身，所以说模型和特效本身就只是一种特殊的UI元素。

事实上，在使用不可变数据结构之后，处理这种复杂的模型特效的编辑反而变得更简单，原因是使用不可变数据结构能让我们将数据更新和UI更新解耦。这会带来什么样的好处呢？

数据的更新往往都是同步的，它发生得非常快速。但是UI的更新有些时候是异步的，比如说我们刚刚提到的模型的加载，它往往是一个异步的过程，又或者说在UI界面上的动画本身也是一个异步的过程，如果一个同步的事件去和一个异步的事件发生耦合的时候，往往就会带来很多复杂的事情。

当数据更新和UI更新解耦之后，我们该在什么时候进行UI的更新呢？答案是固定的帧率。这对于游戏开发的同学来说已经非常的熟悉了，因为我们的游戏总是以固定的帧率去做刷新的。我们只是把这个概念又带到了编辑器里面。

这里有一个具体的例子来解释解耦带来的好处。在一个场景编辑器中，我们有一个UI列表展示场景中所有的模型，同时有一个场景窗口提供场景的预览和编辑。当美术同学在场景里面插入了一个新的模型，那么在下一个更新周期里，我们的列表和场景都开始根据改变去做更新，列表里显示出一个新的模型，场景开始加载新的模型。

但是这个时候美术同学突然意识到我选择了错误的模型，于是他立刻决定将这个模型删除，然后在列表里面这个模型也就被删除掉了，可是在场景里的这个模型还在加载中。如果是基于事件的更新，就要面临着删除一个正在加载中的模型。选择直接删除一个未加载完的模型，编辑器会崩溃。如果你忘记去删除它，场景中会多出一个不受控制的模型。

基于不可变数据结构的情况下，如果我们把数据的更新和UI的更新解耦，这个时候我们的处理会变得非常简单。在加载过程中我们只需要忽略掉数据变化，让这个模型默默地加载完成就行。这个时候场景里面会出现一个多余的模型，在下一次更新的时候通过数据对比会被我们发现，然后删掉它就行，极大地降低了我们在这个过程中出错的可能。

• 支持撤销和重做

在使用不可变数据结构的时候，撤销和重做几乎就是免费的。它的原理也非常简单，就是我们把每一次变更的数据全部放到一个列表里面保存起来，当我们需要撤销的时候只需要回退找到历史的数据，把它重新拿出来就可以了。

前面我们提到了连续拖拽的这样一个特例，其实解决起来也非常的简单，我们只需要把在一个很小的时间阈值之内连续发生的改变合并到一起放到历史列表里面就可以了。

所以这就是目前整个《星战前夜：无烬星河》项目内编辑器的一个核心框架，非常的简单。

我们首先会有一个历史数据队列，它保存了我们所有编辑过的历史状态，然后我们的编辑器会定期从历史当中选择当前最新的数据，把数据交给我们的UI界面去做刷新。

我们把所有的UI按照它的层级划分成不同的View，这里也是借鉴了React里面的基于component的UI设计。我们会把一个大的界面划分成更多小的抽象界面的概念，每个界面只做自己所负责的事情，这样我们可以提高代码的复用率，同时也减少各个UI界面和UI控件之间逻辑的复杂度。

当view对数据做了修改时，会产生一份新的数据，我们把这份新的数据插入到历史队列中。在下一个更新周期，所有的UI控件都会根据新的数据做更新。当我们需要撤销操作时，我们只需要简单的回退历史队列中的指针即可。

在讲完我们的整个编辑的框架之后，我们回过头来和声明式UI做一个对比。声明式UI主要是基于一个虚拟UI层来解决数据和UI之间同步的问题。他们没有提供直接的撤回或重做的支持，毕竟它是面向更通用的应用程序开发的一个框架，它的UI代码会非常的简单，但整个框架会更依赖一个很强大的开发团队去维护。

而基于不可变数据结构的UI，依赖的是特殊的不可变数据结构。它的好处是直接提供了撤回和重做的支持， UI代码会复杂一点，因为我们依赖所有的数据都必须表达成不可变数据结构，但是它的框架代码会非常的简单。

对于我们的应用场景，游戏开发团队通常只有一个较小的编辑器开发团队，撤销和重做又是编辑器非常关键的功能需求。因此基于不可变数据结构的UI方案很自然成为了我们的选择。

但事实上这两种UI框架并不是冲突的，在React的实践里，也鼓励大家在使用声明式UI的同时使用不可变数据结构的。

这里是一个例子。在某些很复杂的界面之中，即使使用声明式UI创建一个完整的虚拟界面，开销仍然是非常大的，所以这个时候React提供了一个接口shouldComponentUpdate()，这个接口会返回一个component的虚拟界面是否需要变更。在不使用immutable data的情况下，这个时候就需要去实现复杂的重载比较来做判断。

如果你使用不可变数据结构来表达内部的状态，这个比较就会变得非常简单了，所以声明式UI和不可变数据结构本身就是可以很好地组合在一起，或许在你们的项目中就可以使用声明式UI去做UI开发的同时，使用不可变数据结构来保存你们实际所编辑的数据。

不可变数据结构的实现原理

最后我们再简单地讲一下不可变数据结构是怎么实现快速地去对数据做copy后，然后再去做修改的。

对于不可变数据结构的研究，其实从很早以前就开始了。目前大部分不可变数据结构的实现都参考了Rich Hichkey在Clojure这门语言当中的实现。

在Clojure这门很有意思的语言中，几乎所有原生的数据结构都是不可变的，Rich Hichkey在语言中使用的数据结构实际上是Phil Begwell所发明的Hash Array Mapped Trie。Hash Array Mapped Trie本身并不是设计成一个不可见的数据结构，但是它的特性让它很容易被用来作为一个不变的数据结构的实现。

Begwell在看到Rich Hichkey用这么有趣的方式去使用它的数据结构之后，也对这个领域非常有兴趣。后来他又写了一篇新的论文发明了一个更高效的不可变数据结构。

我们简单举个例子。这是我们常见的一个不可变列表的实现。可以看到它背后实际上是一棵树，这个树里面所有的节点都是一个等长的数组，然后所有的列表的数据都保存在叶子节点上。

当我们要修改其中的一个数据的时候，我们首先会复制数据所在的叶节点，然后修改它的数据，再将他所有的祖先节点复制一份，就得到了一个新的列表。

可以看到新的列表和老的列表之间共用了非常多的内部节点，所以说它是非常高效的。在经典的实践当中，节点数组的长度通常会被定到32，在大部分情况下，这个树的深度都是很浅的，所以复制的复杂度可以近似看成常数级。

结语

在《星战前夜：无烬星河》的项目当中，任务编辑器是我们第一个尝试使用不可变数据结构改写的编辑器，因为它本身有着非常复杂的数据表达，但是它的UI逻辑又相对来说比较简单，非常适合我们拿来作为一个试验。使用不可变数据结构修改后的编辑器，减少了将近30%的代码，而且在开发中我们几乎没有遇到什么严重的bug，因为整个框架，整个编辑器的结构非常的简单。

不可变数据结构还有很多其他的优点和特性，例如由于不可变数据的特性决定了它天然是一个无锁的线程安全的数据结构，所以说你可以把一些非常复杂的数据操作移到另外一个线程去，而不用担心你的UI线程和你的数据线程产生任何的竞争；

另一方面由于不可变数据结构实现了数据更新和UI更新的解耦，使得我们在实现一个多人实时协作的编辑器时，也会简单很多，我们很想知道大家有没有在自己的项目中去使用不可变数据结构，或者说在未来大家会如何在自己的项目中引入不可变的数据结构。

感谢大家今天来听我们的分享！