N.Game峰会系列持续上新中……
视频版课程已同步上线~

2021 N.Game网易游戏开发者峰会（以下简称峰会）技术论坛上，网易游戏《星战前夜：无烬星河》主程张凯发表了题为《基于不可变数据结构的编辑器开发》的演讲，就如何通过提高编辑器的效率，进而提高项目整体的开发效率的问题进行了探讨与分享。

以下是手游那点事整理的演讲全文，为提升阅读体验，内容有所删节：

大家好，我是来自网易《星战前夜：无烬星河》的张凯，很高兴今天来到这个峰会，给大家分享我们项目的开发经验。

我们今天的主题是「洞见」，所以我也希望带大家来看一看，在游戏的背后，我们项目是如何提高编辑器的开发效率，从而进一步提升游戏的开发效率。

随着现在的游戏越来越复杂，定制化编辑器成了项目开发过程中不可或缺的一部分。在《星战前夜：无烬星河》的开发过程中，我们也逐渐累积了越来越多的定制化编辑器。

随着编辑器越来越多，我们发现背后的维护成本也变得越来越高。这里有一个简单的例子，可以解释我们遇到了什么样的维护成本。

图中展示的是游戏编辑器中非常常见的操作，通过鼠标点击「拖拽」一个物体在场景中移动，同时还有另一个非常常见的操作「撤销」。

通常来说，我们会封装一个完善的编辑器框架，当你改变一个数据对象时，它会自动触发事件通知对应的UI控件做更新，同时还会封装相应的命令，放到命令栈中供撤销和重做。

1.在这个场景下，我们遇到了什么问题？

大家可以留意到，当我们撤销的时候，物体位置总是直接回到了起点。

毕竟在连续拖拽过程中，我们会产生20、30，甚至数百个位移，我们肯定不希望美术同学执行这么多次撤销操作才能把它移回起点，这就意味着我们不能直接重用已经封装好的框架。

这也不是一个很复杂的问题，我们可以在移动过程中并不产生真正的位移数据的修改，而是在放下鼠标之后才实际修改。

直到美术同学给我们提了这样一个需求：在移动的过程中，他还想在控件上看到数值变化，让他可以方便去做一些对齐，去感知这个数据到底是怎么变化的。

这个时候，我们不得不在原有框架下加入新的事件机制，来通知跟拖曳相关的UI控件进行更新。

随着这样的事件越来越复杂，整个编辑器的维护成本也越来越高。

比如「可维护性」方面，因为不同的同学要为不同的特殊事件加入新的机制，那么新的同学去接手的时候，就有很高的学习成本。

又比如「稳定性」方面，随着事件越来越复杂，整个编辑器的稳定性也在逐渐下降。因为事件越多，出错的机会越大，同时一旦你出错了，debug的时间会非常长。

最后是「撤销和重做」方面，即使不像刚才那么复杂，即使是简单的操作，在原有框架下，也意味着我们需要为每一个新的操作添加这个指令。这个过程是非常繁琐的，会降低编辑器的开发效率，所以我们想要解决这些问题。

回到编辑器的根本，我们到底在做一件什么事情呢？

一方面，我们在编辑器内部有一堆数据，是我们的美术同学、策划同学想要编辑的；另一方面，我们要为他们提供UI界面，用来展示、修改这些信息。

而常见的基于事件触发的框架，我们觉得太混乱、太复杂，它会带来较高的维护成本，我们想去掉它。

那我们能怎么做呢？

回到问题的根本，可以看到，我们现在有一组数据，有展示这个数据的界面。我们想做的是，当数据发生改变时，界面也发生对应的改变。

如果没有事件告诉我们什么样的数据发生了改变，我们怎么知道应该改变什么样的UI呢？最简单的方式，就是把整个UI都删掉，重建一个。

为什么这么多应用开发不采用这种方式呢？原因大家也知道，当你要完整地重建一个非常复杂的界面时，它的开销是很高的。

那有没有办法解决这个问题呢？事实上，我们发现问题并不只存在于游戏编辑器的开发领域，在传统应用程序的开发领域，人们也一直在试图解决这个问题。

而我们觉得目前最有希望的答案，就是「声明式UI」。

2.声明式UI是怎么解决这个问题的？

与我们常见的，直接根据数据创建整个UI不同。「声明式UI」往往依赖一个虚拟UI层，来抽象这个行为。

虚拟UI指的是并不会在屏幕上真正渲染，但是用来描述UI界面该长成什么样的一组内存数据。因为它是纯内存数据，创建是非常高效的。

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

常见的「声明式UI」的框架有Flutter、React和SwiftUI等，这些都是目前在前端领域非常成熟的框架。

虚拟UI在Flutter里面被称之为blueprint，而在React里就是有名的virtual DOM。

3.声明式UI这么好，我们为什么不直接采用它？

第一个原因是，「声明式UI」的虚拟层作为面向通用应用程序的框架，它无法表达在游戏编辑器中需要的所有“UI”元素，这个后面会讲到。理论上，我们可以自己补充完善虚拟UI层，但这样会带来非常大的开发成本，我们没有拥有这样的条件。

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

回到问题的根本。

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

背后的原因，相信大家也都会清楚。

比较这个操作，往往实际有着不小的开销，而且还需要比较复杂的代码，相信大家做过重载比较操作符的同学，都会有体会。

甚至，如果想去比较前后两份数据的状态，你首先得有copy，而这个行为本身也是不高效的。所以，这阻止了人们从UI开发的一开始，就采用通过数据比较得出需要更新UI的部分。

但事实上，并不是所有的数据结构都有这样的限制。

这就是我们今天要讲的主角「不可变数据结构」，也就是我们常说的「Immutable data」。

4.什么是不可变数据结构？

很简单，从字面意义可以知道，它指的是数据一旦形成之后再也不能改变。如果你想要改变它，你必须先生成一份新拷贝，然后在上面去做改变。

这是一个例子：比如有一个「不可变的列表a」，里面有[1，2，3]三个元素，当我向列表插入一个新元素(4)时，它返回了一个「新的列表b」。

可以看到，原有列表保持不变，而我得到了一个被改变的新列表，这就是「不可变数据结构」。

有了「不可变数据结构」，就意味着每一次你需要去改变数据时，一定要生成一份新的数据。

在这种情况下，你只需要判断前后的两份数据是否为同一个，就知道这部分数据是否发生了改变。比较两个元素是否为同一个，这个操作是非常高效的。同时，由于「Immutable data」的特性，它的拷贝操作也是非常高效的，这一点我们在最后会讲到。

回到刚才我们面临的问题，有了「不可变数据结构」的帮助，我们就可以从数据的源头，对新旧两种状态进行比较，找到真正发生了改变的那部分数据，从而针对性地更新UI表现。

所以到这里问题就解决了，今天的分享可以结束了（笑）。

但事实上还差一点点，我们看一下还差哪一点点？

这是新旧两个列表，列表是数据编辑中非常常见的数据结构，比如说模型的列表、特效的列表等。

按照刚才的方式，我们会比较两个列表的数据，然后会发现每一项都发生了改变，于是我们需要对整个列表的UI都进行相应的更新。最后，我们还发现新的列表多插入了一个新的元素。

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

所以我们需要知道两个列表之间的「最小编辑距离」，从而尽可能地减少在列表发生变更时，我们所需要的UI刷新操作。

经典的求两个列表之间「最小编辑距离」的算法，也就是「Levenshtein distance」，它的时间复杂度是O（n*m）。

在游戏开发领域，这个列表可能会非常大。比如说你在编辑一个大世界的场景，你的列表里面可能有成百上千个模型，所以我们不能用这个算法。

但庆幸的是，我们也并不是在所有情况下都需要最优解，只需要一个足够好的结果就可以了。

最后我们使用的方式是「启发式list diff」，这个list diff实际上也参考了React的实现，我们虽然没有使用「声明式UI」框架，但我们从它里面学到了很多东西。

5.什么是list diff？

这个算法是，你给定一个“列表A”和“列表B”，它会返回从A到B所需的操作，同时操作会尽可能的少。我们在这个算法的基础上做了两个特性：

第一个特性是我们的「list diff」总会在以下的三种情况下返回最优解：第一，删除单个元素；第二，插入单个元素；第三，单个元素在列表中的位置发生了移动。实际上，列表中的移动操作就是上面两个操作的组合。

为什么我们要对这样三种操作总是保证返回最优解呢？

大家回想一下，在美术和策划的同学使用编辑器时，数据往往是逐个变更的。这也是我们在编辑过程中，列表最容易发生变更的情况，所以我们总是在这种情况下让它们保持返回最优解。

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

我们再详细解释一下：

这是我们所有编辑器里面，列表类的UI容器的基类，refresh函数是整个列表容器进行刷新的关键函数。

这里做的事情非常简单。首先我们会使用「list diff」找出新旧两份数据发生的改变，计算我们需要做什么操作，能让老的数据变成新的数据；然后我们会逐个执行操作，对于删除操作，我们会取出对应的UI元素，取出后我们不会直接销毁，而是把它放到cache里保存。

那我们在执行插入操作的时候，我们就会检查，如果目前cache中有UI元素可用，我们会直接从cache中取出对应的元素来减少元素的创建。

有了上面封装好的list view之后，我们在编辑器里想用列表的形式展示一组数据，就会变成非常简单。

首先你需要使用一个「不可变的列表」来保存数据，然后继承我们的List View Base。在这个类里面你只需要做一件事情，就是告诉这个列表容器，每一个元素需要怎样渲染，需要怎样的UI元素，然后你只需调用一个refresh函数，就可以刷新整个列表。

到这里为止，可能很多人会说，对于像任务这样的数据，它天生很容易被表达成「不可变数据」的时候，这新的框架看起来很好用。

如果我们要编辑的是一个3D模型，那应该怎么办？

我们不太可能把引擎中，像模型特效这样很核心的元素实现成「不可变数据结构」，即使可以实现，往往它在开销上也不会被接受。

所以我们如果要编辑一个3D模型、编辑一个特效，我们应该怎么做呢？

事实上，3D模型本身就是一种UI元素。

以这个小的编辑器为例，无论是通过传统的、数值类的UI控件，还是通过场景里面、通过拖拽、旋转去操作这个模型，我们改变的永远是这一组抽象的、基于「不可变数据结构」的数据，而不是去操作模型或者特效本身。

所以说模型和特效本身只是一种特殊的UI元素。事实上，在使用基于「不可变数据结构」这种模式之后，处理这种复杂的模型特效的编辑，反而变得更简单。原因是因为使用「不可变数据结构」，使得我们能够将数据更新和UI更新解耦。

6.为什么要解耦，解耦带来什么好处？

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

有人可能就问到，当数据更新和UI更新都解耦之后，那什么时候进行UI的更新呢？

答案很简单，UI总是以固定帧率去做更新。其实对于游戏开发的同学来说已经非常的熟悉了，因为游戏通常都是以固定帧率做刷新的，我们只是把这个概念又带到了编辑器里。

这是一个例子，讲的是当数据的更新和UI的更新解耦之后带来的好处。举例来说，在一个场景编辑器中，我们有一个UI列表展示场景中所有的模型，同时有一个场景窗口提供场景的预览和编辑。

这时候美术同学在场景里插入了一个新的模型，那么在下一个更新周期里，列表和场景都开始根据改变去做更新，列表里显示出了一个新的模型，场景开始加载新的模型。

这时候美术同学突然意识到选择了错误的模型，于是他立刻决定把这个模型删除掉，然后列表里这个模型也被删除了，可场景里这个模型还在加载。

基于传统事件的更新时，我们就面临着要删除一个正在加载中的模型的问题。如果你直接删除，编辑器crash了，如果你忘记删除，场景里会多出一个不受控制的模型，会给美术同学的编辑带来困扰。

所以这里面引入了很复杂的逻辑，但是在基于「不可变数据结构」的情况下，如果把数据的更新和UI的更新解耦，我们的处理会变得非常简单。我们只需要在加载过程中忽略掉这样的数据变化，让这个模型默默加载完成就行了。

这时候场景里会出现一个多余的模型，但是当下一次更新周期来到时，当场景里的模型和数据发生比较时，会发现有一个多余的模型，于是删掉它。

就这样，逻辑非常清晰简单，极大的降低了在过程中出错的可能。

我们现在解决了数据更新和UI更新的同步问题，那刚才提到的撤销和重做应该怎么解决呢？

这是目前《星战前夜：无烬星河》所有编辑器里撤销和重做运行的所有代码。

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

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

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

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

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

有一点目前我们还没有讲到的，这个编辑器如何更新数据？

我们的策略是所有的view，负责维护自己数据的更新。

当数据在更新时，首先view会创建一份新的数据，因为我们是「不可变数据结构」，当要改变数据的时候，你永远要创建一份新的数据。

这份新的数据会交给它的父亲节点，父亲节点会拿着新的数据创建出另一份新的数据。

直到交给最后的根节点，根节点会把这份数据交给编辑器，然后编辑器会把它插入到历史队列当中。

注意这个时候我们的UI界面，还没有更新成新的数据形态，因为数据更新和UI更新是解耦的。

那么在来到下一个UI更新周期时，编辑器会取出这份数据交给所有的UI逻辑，UI逻辑会顺势做更新。

这个时候如果发生了撤销操作，我们只需要简单把数据历史队列里面的指针往回退，然后在下一个更新周期，所有界面都会更新回退到新的数据状态。

讲完整个编辑框架之后，我们回过头来和「声明式UI」做一次对比。

「声明式UI」主要基于虚拟UI层，来解决数据和UI之间同步的问题。它没有提供直接的撤回或重做的支持，毕竟它是面向更通用的应用程序开发的框架，它的UI代码会非常简单，缺点是整个框架相对来说比较复杂，依赖一个强大的框架开发团队去维护。

基于「不可变数据结构」的UI，依赖这样一种特殊的数据结构，它的好处是直接提供了撤回和重做的支持，它的UI代码会复杂一点点，因为所有的数据都必须表达成「不可变数据结构」，但是它的框架代码会非常简单。结合到游戏团队实际的开发项目，我们往往只拥有一个比较小的工具开发团队，又需要表达类似于“模型特效”这样复杂的引擎中的对象，所以我们很自然地选择了基于「不可变数据结构」的UI。

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

这是一个例子，在某些很复杂的界面情况下，即使使用「声明式UI」创建一个完整的虚拟界面，仍然是开销非常大、难以接受的。这时候React提供了一个接口，它会返回一个值，来表达某一部分UI结构是否应该发生改变。

在传统情况下，这时候会依赖重载比较来判断界面是否需要更新。但如果你使用「不可变数据结构」来表达内部的状态，这个比较就变得非常简单了。

所以「声明式UI」和「不可变数据结构」本身可以很好地组合在一起，或许在你们的项目中，就可以使用「声明式UI」做UI的开发，同时使用「不可变数据结构」保存实际所编辑的数据。

7.不可变数据结构是怎么实现的？

最后我们简单讲一下，「不可变数据结构」是怎么做到快速对数据做拷贝，再去做修改的？

「不可变数据结构」的研究其实从很早以前就开始了，目前绝大部分「不可变数据结构」的实现，都参考了Rich Hichkey在Clojure这门语言中的实现，在Clojure里面，几乎所有原生的数据结构都是不可变的。

而Rich Hichkey在语言中使用的数据结构，实际上是Phil Begwell所发明的Hash Array Mapped Trie。但Hash Array Mapped Trie本身并不是设计成「不可变数据结构」的，是它的特性，使它很容易用来作为「不可变数据结构」的实现。

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

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

当我们要修改其中一个数据时，首先会复制数据所在的叶节点，修改它的数据，然后再复制一份它的父亲节点，因为里面的数据也发生了变化。然后一直不断往上，直到复制到根节点，最后我们得到了一个新的列表。

可以看到，新的列表和老的列表之间共用了非常多的内部节点，它是非常高效的。

在经典的实现当中，节点的数组长度通常会被定到32，在大部分情况下，这棵树的深度都是很浅的，它的复制操作可以近似看成一个常数级的操作。

在《星战前夜：无烬星河》的项目中，任务编辑器是我们第一个尝试使用「不可变数据结构」改写的编辑器，因为它本身有着非常复杂的数据表达，但是它的UI逻辑又相对比较简单，非常适合拿来作为试验。

使用「不可变数据结构」修改后，我们的任务编辑器减少了将近30%的代码，而且在开发中几乎没有遇到严重的bug，因为整个框架、整个编辑器的结构非常简单。

「不可变数据结构」还有很多其他的优点和特性，我们今天没有讲到。例如，一方面由于不可变数据的特性，决定了它天然是一个无锁的线程安全的数据结构，你可以把非常复杂的数据操作移到另外一个线程去，而不用担心UI线程和数据线程产生任何竞争。另一方面，由于「不可变数据结构」实现了数据更新和UI更新的解耦，使得我们在实现多人实时协作的编辑器时，也会简单非常多。

所以我们也很想知道，大家有没有在自己的项目中使用「不可变数据结构」，或者说在未来大家会如何在项目中引入「不可变数据结构」。感谢大家来听我的分享。

---

网易游戏学院官方讨论QQ群：1034322830
欢迎各位同学加群，与众多游戏爱好者一同学习交流~