4月27日，《星战前夜：无烬星河》主程张凯以《基于不可变数据结构的编辑器开发》为题，分享《星战前夜：无烬星河》团队如何利用不可变数据结构大幅提升编辑器的开发效率和运行稳定性。
以下为GameRes整理的演讲内容：
大家好我是来自网易《星战前夜：无烬星河》的张凯，很高兴今天来到这个峰会给大家分享我们项目的开发经验。我们今天的主题是洞见，所以我也希望带大家来看一看，在我们游戏的背后，我们项目是如何提高编辑器的开发效率，从而进一步提升游戏的开发效率。
不断增长的编辑器开发和维护成本
随着现在的游戏越来越复杂，定制化的编辑器成了一个项目开发过程中不可或缺的一部分。《星战前夜：无烬星河》的开发过程中，我们也是逐渐积累了越来越多的定制化的编辑器，随着编辑器越来越多，我们发现相关的开发和维护成本也变得越来越高。
这里有一个简单的例子，可以解释一下我们遇到了什么样的维护成本。
图中展示的是游戏编辑器当中一个非常常见的操作，通过鼠标点击拖拽一个物体在场景中移动，同时还有另一个非常常见的操作就是撤销。通常来说我们会封装一个编辑器框架，当你改变一个数据对象时，会自动触发事件去通知对应的UI控件更新。同时还会封装相应的命令，放到命令栈中供做撤销和重做。
在这个场景下我们遇到了什么问题呢，大家可以留意到，当我们撤销的时候，物体的位置总是直接回到了起点，毕竟在连续的拖拽过程中，会产生几十甚至上百个位移，我们肯定不希望美术同学执行这么多次撤销操作才能把它移回起点，所以这就意味着我们不能直接使用我们已经封装好的框架。
这也不是一个很复杂的问题，我们可以在移动过程中不产生真正的位移的数据修改，而是在松开鼠标按键之后才实际修改 。直到美术同学给我们提了这样一个需求：我在移动的过程中，我还想在控件上看到数字的变化。他们可以方便去做一些对齐，去感知这个数据到底是怎么变化的。
这个时候我们不得不在原有的框架下加入新的事件机制，来通知跟拖拽位移相关的UI控件进行更新。
类似这样的特殊事件，给我们的整个编辑器带来了更高的维护成本，因为不同的同学要为不同的特殊事件加入新的机制，其他同学接手的时候就有很高的学习成本；另一方面随着事件越来越复杂，整个编辑器的稳定性也在逐渐的下降，因为事件越多，你出错的机会就越大。一旦你出错，你debug的时间会非常的长。
另一方面，为每个新的操作封装撤销和重做的指令，过程也是非常繁琐的，使得我们难以提高编辑器的开发效率。所以我们想要解决这些问题。
回到编辑器的根本，我们到底在做一个什么事情呢？事实上我们在编辑器内部有一组数据，这个数据是我们的用户——美术同学、策划同学他们所想要编辑的，另一方面我们要为他们提供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，我们仍然需要找到另一个方案来解决撤销和重做的问题。
Immutable data：不可变数据结构
回到这个问题的根本，如果我们没有虚拟UI的帮助去直接对比界面的改变，我们为什么不直接对比新旧两份数据的改变，如果我知道数据在哪个部分发生了改变，我当然就可以非常简单的去改变我的UI。
背后的原因我相信大家也都清楚，比较操作实际上往往有着不小的开销，而且比较这个操作往往还需要复杂的代码，相信做过重载比较操作符的同学都会有体会。如果你想去比较前后两份数据的状态，你首先还得有copy ，而copy这个行为本身也是不高效的。这就是这种模式（从UI开发的一开始就采用通过数据比较去得出需要更新UI部分）的主要障碍。
但事实上并不是所有的数据结构都有这样的限制，这也就引出了我们今天要讲的主角：不可变数据结构，也就是我们常说的Immutable data。
什么是immutable data，从字面意义上来说，它指的是这个数据一旦生成之后再也不能改变，如果你想要改变它，你必须首先生成一份新的拷贝，然后在新的拷贝上去做改变。
举个例子。比如说我们有一个不可变的列表，这个列表里面有三个元素，当我们去向这个列表中插入一个新的元素时，它返回了一个新的列表。可以看到原有的列表是保持不变，而我们得到了一个被改变的新的列表，这个就是不可变的数据结构。
有了不可变的数据结构，就意味着每一次你需要去改变数据的时候，你一定要生成一份新的数据。在这种情况下，你只需要判断前后两份数据是不是同一个，就知道这部分数据是否发生了改变。所以说比较两份数据是不是同一个，这个操作是非常高效的。
同时由于Immutable data的特性，它的拷贝操作也是非常高效的。如何实现这一点，我们在最后会讲到。
回到刚才我们面临的问题，有了不可变数据结构的帮助，我们就可以从数据的源头上，对新旧两个状态进行比较，找到哪一个数据发生了真正的改变，从而去针对性的更新我们的UI表现。
到这里问题就解决了，今天的分享就可以结束了。但事实上还差一点点，我们看一下还差哪一点点？
这是新旧两个列表，列表是我们在编辑数据中非常常见的数据结构。比如说你有模型的列表、特效的列表等等，按照刚才的方式我们会对两个列表的数据进行比较，然后发现列表中的每一项都发生了改变，于是我们需要对整个列表的UI都进行相应的更新。
但事实上如果我们仔细去看这两份数据，我们会发现我们只是在前面插入了一个新的元素而已，我们不需要对后面所有的元素都进行更新。
在这里我们需要知道的是两个列表之间的最小编辑距离，从而尽可能的减少在列表发生变更时我们所需要的UI刷新操作。
经典的找到两个列表之间最小编辑距离的算法，也就是Levenshtein distance，它的时间复杂度是O（n*m），这个时间复杂度在当你的列表很大的时候，是不太可行、不太可以接受的。
在游戏开发领域，这个列表可能会非常大。比如说你在编辑一个大世界的场景，你的列表里面可能有成百上千个模型，所以我们不能用这个算法。
庆幸的是我们并不是在所有情况下都需要最优解，我们只需要一个足够好的结果就可以了。最后我们使用的方式是一个启发式的list diff算法，这个list diff实际上也是参考了React的实现，我们虽然没有使用声明式UI框架，但我们从声明式UI框架里面学到了很多东西。
list diff，你给定一个列表a和列表b，它会返回从列表a变到列表b所需要的操作，这个操作会尽可能的少，我们在这个算法基础上去做了两个特性，第一个是我们的list diff总会在以下的三种情况下返回最优解：
第一个是删除单个元素；
第二个是插入单个元素 ；
第三个是单个元素在列表中的位置发生了移动。
实际上在列表中的移动操作就是上面两个操作的组合。
为什么我们要对这样三个操作总是保证返回最优解？大家回想一下在美术和策划的同学去使用编辑器的时候，实际上数据往往是逐个变更的，这也是我们在整个编辑过程中列表最容易发生变更的情况。所以我们是在这种情况下让他们保持返回最优解。
然后我们保证的第二个特性是，我们永远让删除操作放在前面，插入操作放在后面，这是为了我们可以复用一些UI控件。
这里可以详细解释一下为什么。这是我们所有编辑器里面列表类的UI容器的基类，这个refresh函数是整个列表内容器进行刷新的关键的函数。
这里面其实做的事情非常简单，首先我们会使用list diff找出新旧两份数据发生了什么样的改变，我们需要做什么样的操作能让老的数据变成新的数据，然后我们会逐个执行这些操作，对于删除操作我们会取出对应的UI的元素，当然取出之后我们并不会直接将它销毁，而是把它放到cache里面保存起来。
我们在执行插入操作的时候，我们会检查如果目前cache中有UI元素可以用，我们就会直接从cache中取出对应的元素来减少元素的创建。
有了上面封装好的list view之后，我们在编辑器里面想用列表的形式去展示一组数据就变成非常简单。
首先你需要使用一个不可变的列表来保存你的数据，然后你只需要继承我们的 ListViewBase ，在这个类里面你只需要做一件事情，就是告诉这个列表容器里的每一个元素需要怎样渲染、需要怎么样的UI元素，然后你就只需要一个refresh函数的调用就可以刷新整个列表。
到这里为止，可能很多人会说对于像任务这样的数据，它天生很容易被表达成不可变的数据，如果编辑器编辑的是一个3D模型，那应该怎么办？
我们不太可能把引擎中像模型特效这样很核心的元素实现成不可变数据结构，即使可以实现，往往它也在开销上可能不会接受。所以说我们如果要编辑一个3D模型、编辑一个特效我们应该怎么做呢？
事实上3D模型本身就是一种UI元素，以这个小的编辑器为例，无论是通过数值类的UI控件，还是通过在场景里拖拽、旋转去操作这个模型，我们在这里面改变的永远是这一组抽象的基于不可变数据结构的数据，而不是去操作模型或者特效本身，所以说模型和特效本身就只是一种特殊的UI元素。
在使用基于不可变数据结构之后，处理这种复杂的模型特效的编辑反而变得更简单，原因是使用不可变数据结构使得我们能够将数据更新和UI更新解耦。
解耦带来什么样的好处呢？数据的更新往往都是同步的，它发生得非常快速，但是UI的更新有些时候是异步的。比如说我们刚刚提到的模型的加载，它往往是一个异步的过程，又或者说在UI界面上有动画，动画本身也是一个异步的过程 ，一个同步的事件去和一个异步的行为发生耦合的时候，往往就会带来很多复杂的事情。
有人问到当你的数据更新和UI更新都解耦之后，什么时候进行UI的更新？答案很简单，我们的UI总是以固定的帧率去做更新的，其实对于游戏开发的同学来说已经非常的熟悉了，因为我们的游戏通常都是以固定的帧率去做刷新的，我们只是把这个概念又带到了编辑器里面。
这里是一个例子，讲的是当数据的更新和UI的更新解耦之后带来的好处。举例来说，在一个场景编辑器中，我们有一个UI列表展示场景中所有的模型，同时有一个场景窗口提供场景的预览和编辑。
这个时候我们的美术同学在场景里面插入了一个新的模型，那么在下一个更新周期里面，我们的列表和场景都开始根据改变去做更新。列表里面显示出了一个新的模型，场景开始加载新的模型 ，这个时候突然美术意识到我选择了错误的模型，于是他立刻决定将这个模型删除掉，然后在列表里面这个模型也被删除掉了，可是在场景里面这个模型还在加载。
基于事件的更新的时候，我们就面临着我要删除一个正在加载中的模型，如果你直接删除编辑器crash了，如果你忘记去删除它你的场景里面会多出一个不受控制的模型，那会给美术同学的编辑带来困扰 ，所以这里面就引入了很复杂的逻辑。
但是在基于不可变数据结构的情况下，如果我们把数据的更新和UI的更新解耦，这个时候我们的处理会变得非常简单，我们只需要在模型加载期间忽略数据变化，让这个模型默默的加载完成就行。
这个时候场景里面会出现一个多余的模型，但是当下一次更新周期来到的时候，场景里面的模型和数据发生比较的时候，会发现一个多余的模型 ，于是我们删掉它。就这样逻辑会非常的清晰非常的简单，极大的降低了我们在这个过程中出错的可能。
现在我们解决了数据更新和UI更新的同步问题，我们刚才提到的撤销和重做应该怎么解决呢？
这段代码是目前《星战前夜：无烬星河》项目中所有编辑器里面撤销和重做的代码，我们常说天下没有免费的午餐，但是在使用不可变数据结构的时候，撤销和重做几乎就是免费的。
它的原理也非常简单，就是我们把每一次变更的数据，全部放到一个列表里面保存起来。当我们需要撤销的时候，我们只需要回退，找到历史的数据把它重新拿出来就可以了。
前面我们提到了连续拖拽的这样的一个特例，解决起来也非常的简单，我们只需要把一个很小的时间阈值之内连续发生的改变合并到一起，放到历史列表里面就可以了。
这就是目前整个星战前夜项目内编辑器的一个核心的框架。首先会有一个数据历史队列，保存了我们所有编辑过的历史状态，然后我们的编辑器会定期从历史当中选择当前我们最新的数据，然后把这个数据交给我们的UI界面去做刷新。
在UI界面上我们特意把所有的UI按照它的层级去做了划分，这里也是借鉴了React里面的基于component的UI设计，我们会把一个大的界面划分成更多小的抽象的界面的概念，每个界面只做自己所负责的事情，这样我们可以提高代码的复用率，同时也减少各个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的开发，同时使用不可变数据结构来保存你们实际所编辑的数据。
最后我们再简单的讲一下，不可变数据结构是怎么实现，他是怎么能够做到这么快速的去对数据做拷贝，然后再去做修改。
不可变数据结构的研究其实从很早以前就开始了，目前大部分不可变数据结构的实现都参考了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更新的解耦，使得我们在实现一个多人实时协作的编辑器的时候也会简单得多，我们也很想知道大家有没有在自己的项目中使用不可变数据结构，或者说在未来大家会如何在自己的项目中引入不可变的数据结构。
感谢大家今天来听我们的分享。
原文：https://mp.weixin.qq.com/s/UJMvec9QD4u86pTslw-Kuw