4月27日，在2021 N.Game网易游戏开发者峰会程序论坛上，《星球大战前夜：永恒银河》主程序张凯就《基于不可变数据结构的编辑器开发》进行了主题演讲。
他表示，现代游戏的玩法设计和表现效果越来越复杂。 定制的编辑器和工具链对于提高游戏开发效率至关重要。 为了在有限的开发时间内为团队提供尽可能多的稳定易用的编辑器和工具，《EVE：永恒银河》团队在工具链开发上进行了诸多探索。 在本次演讲中，他分享了如何使用Immutable data大大提高编辑器的开发效率和运行稳定性。 以下为演讲实录： 大家好，我是来自网易《星战前夜：永恒银河》的张凯。 很高兴今天能来到本次峰会，与大家分享我们项目的开发经验。 我们今天的主题是“洞察力”。 所以希望给大家介绍一下如何提高我们游戏背后的编辑器的开发效率，从而进一步提高游戏的开发效率。 根据需要做一个定制化的编辑器，开发和维护成本不断堆积。 随着现代游戏变得越来越复杂，定制的编辑器已经成为项目开发过程中不可或缺的一部分。 在《星球大战前夕：无限银河》的开发过程中，我们逐渐积累了越来越多的定制编辑器。 随着编辑器越来越多，我们发现相关的开发和维护成本越来越高。 下面通过一个简单的例子来说明我们遇到过什么样的维护成本。 图为游戏编辑器中一个很常见的操作，点击并拖动物体在场景中移动，还有一个很常见的操作是撤销。 一般来说，我们会封装一个编辑器框架。 当你改变一个数据对象时，会自动触发一个事件来通知相应的UI控件进行更新。 它还会将相应的命令封装起来，放到命令栈中，用于undo和redo。 在这种情况下，我们会遇到什么问题？
你可以注意到当我们取消时，物体的位置总是直接回到起点。 毕竟在不断的拖动过程中，会产生几十个甚至上百个位移。 我们绝对不希望艺术生表演那么多次。 将其移回起点需要一个撤销操作，所以这意味着我们不能直接使用打包的框架。
这不是一个很复杂的问题。 我们不能在移动过程中修改实际的位移数据，而是在松开鼠标按键后才真正修改。 直到美术同学给了我们这样一个需求：我想边走边看数控上数字的变化，从而观察数据是如何变化的。 这时候我们就得在原有框架下增加一个新的事件机制来通知拖动位移相关的UI控件进行更新。 像这样的特殊事件给我们整个编辑器带来了更高的维护成本，因为不同的学生要为不同的特殊事件添加新的机制，而当其他学生接手时，有很高的学习成本；
另一方面，随着事件越来越复杂，整个编辑器的稳定性也在逐渐下降，因为事件越多，出错的概率就越大，一旦出错，调试的时间就会很长。
还有针对每个新操作封装撤消和重做的说明。 过程也很繁琐，让我们很难提高编辑器的开发效率，所以我们想解决这些问题。 回到编辑器，我们现在有一组数据，我们有一个UI界面来展示这些数据。 我们要做的是当数据发生变化时，我们的界面也随之变化。 如果没有事件告诉我们什么样的数据我们怎么知道应该改变什么样的UI呢？ 最简单的方法是删除整个 UI 并重建它。 为什么那么多应用不是这样开发的？ 大家都知道，当你想要完全重建一个非常复杂的界面时，它的开销是非常大的。 有没有办法解决这个问题？ 声明式 UI 无法表达所有的 UI 元素，也没有撤消和重做的解决方案。 事实上，我们发现这个问题不仅仅存在于游戏编辑器开发领域。 在传统应用开发领域，人们一直在尝试解决这个问题，我们觉得目前最有希望的答案是声明式 UI。 声明式 UI 如何解决这个问题？ 与我们直接从数据创建整个 UI 的常见方式不同，声明式 UI 通常依赖于虚拟 UI 层来抽象这种行为。 Virtual UI 指的是内存数据，实际上并没有呈现在屏幕上，但可以用来完整描述 UI 界面。
它的创建非常高效，因此在声明式 UI 框架中，当你的数据发生变化时，你总是可以重新创建一个完整的虚拟 UI。 有了这个新的虚拟UI，再和旧的虚拟UI对比，我们就可以得到真正需要修改的界面部分。 常见的声明式 UI 框架包括 Flutter、React 和 SwiftUI。 这些都是目前在前端领域使用的非常成熟的框架。 虚拟UI在Flutter中称为蓝图，在React中称为虚拟DOM。
那么为什么声明式 UI 这么好，我们不直接采用声明式 UI 呢？
首先是声明式 UI 的虚拟层作为一个通用的面向应用程序的框架，它不能表达游戏编辑器中需要的所有“UI”元素，我们将在后面提到。 理论上，我们可以自己维护一个虚拟UI方案，但这会带来非常大的开发成本；
二是因为声明式UI仍然没有提供高效的undo和redo解决方案，所以即使我们采用声明式UI，我们仍然需要寻找另一种解决方案来解决undo和redo的问题，所以我们需要更进一步去找到新的答案。
回到这个问题，如果我们没有虚拟UI的帮助，为什么不直接对比新旧数据呢？ 如果我们知道是哪部分数据发生了变化，当然可以很简单的更新相应的UI。
但是我相信每个人都会知道这背后的原因。 事实上，比较操作往往有很大的开销，而且比较操作往往需要更复杂的代码。 相信做过重载比较运算符的同学都会有一些体会。 ，甚至当你想比较前后两个数据的状态时，你必须先复制，而复制的行为本身是不高效的，所以这阻止了人们通过数据比较来更新UI。
不可变数据结构的三大优势 但其实并不是所有的数据结构都有这样的局限性，所以这就是我们今天要说的主角——不可变数据结构，也就是我们常说的Immutable data。
什么是不可变数据？ 字面意思是数据一旦生成，就不能再更改。 如果你想改变它，你必须先制作一个新的副本，然后在新的副本上进行更改。
例如，我们有一个包含三个元素的不可变列表。 当我们向这个列表中插入一个新元素时，它会返回一个新列表。 您可以看到原始列表保持不变。 这是一个不可变的数据结构。 使用不可变数据结构，意味着每次数据更改时，都会生成一个新的数据副本。
这种情况下，只需要判断前后两个数据是否相同，就可以知道这部分数据是否发生了变化。 比较两个数据是否相同的操作是非常高效的。 同时，由于Immutable数据的特性，其复制操作也非常高效。 它是如何做到这一点的，我们稍后会看到。
回到刚才我们面临的问题，我们可以从数据源头对比新旧状态，找出哪些数据真正发生了变化，从而有针对性地更新我们的UI性能。 问题已经解决了。 我们唯一需要关心的是列表的比较。 这是两个列表，旧的和新的。 列表是我们编辑数据时非常常用的一种数据结构。 比如你有一个模型列表，一个特效列表等等怎么制作游戏修改器，按照刚才的方法，我们比较两个列表的数据，然后你会发现列表中的每一项都发生了变化。 所以我们需要相应地更新整个列表元素对应的UI。
但实际上，如果我们仔细观察这两条数据，就会发现我们只是在前面插入了一个新的元素，并不需要更新后面的所有元素。
这里需要的是知道两个列表之间的最小编辑距离，从而尽可能减少列表变化时需要的UI更新操作。 找到两个列表之间的最小编辑距离的算法，即 Levenshtein 距离，时间复杂度为 O(n*m)。 这个时间复杂度在你的列表很大的时候是行不通的，而在游戏开发领域，大家都知道当你编辑很多内容的时候，这个列表可能会很大。
例如，如果你在编辑一个大的世界场景，你的列表中可能有成百上千个模型，所以我们不能使用这个算法，但幸运的是我们不需要所有情况下的最优解，我们 All it takes is a足够好的结果。 我们使用的最后一种方法是启发式列表差异算法。 这个list diff其实是参考了React的实现。 虽然我们没有使用声明式 UI 框架，但我们从声明式 UI 框架中学到了很多东西。
什么是列表差异？ 给定列表 a 和列表 b，此算法返回从列表 a 更改为列表 b 所需的操作。 我们基于这个算法做了两个特征。 首先是我们的list diff在以下三种情况下总会返回最优解：第一种是删除单个元素； 第二种是插入单个元素； 第三个是移动列表中单个元素的位置。 列表中的移动操作是前面两个操作的组合。 为什么我们总是保证返回这三个操作的最优解？ 回想一下，美术和策划同学在使用编辑器的时候，数据往往是一个一个的改。 这也是在整个编辑过程中列表最有可能发生变化的情况，所以我们希望让他们在这种情况下不断返回最优解。 第二个特点是我们总是把删除操作放在前面，然后插入操作。 这样我们就可以重用一些 UI 控件。 有了list diff算法，list类的UI更新变得非常简单。 首先，我们会使用list diff来找出新旧数据发生了哪些变化，需要做哪些操作才能让旧数据变成新数据。 然后我们将这些操作一一进行。 对于删除操作，我们会取出对应的UI元素。 取出来后，我们不会直接销毁，而是放在缓存中保存。 当执行插入操作时，我们会检查缓存中是否有可用的相关UI元素，我们会直接从缓存中获取相应的元素，以减少元素的创建。
有了上面封装的列表视图，我们在编辑器中以列表的形式展示一组数据就变得非常简单了。 首先，你需要使用一个不可变列表来保存你的数据，然后你只需要继承ListViewBase。 在这个类中，你只需要做一件事，就是告诉列表容器中的每个元素如何渲染，如何渲染这样的UI元素，然后你只需要调用刷新函数刷新整个列表即可。
对于任务这样的数据，本来就很容易被表示为不可变数据，这让这个新框架看起来不错，但是我们有同学问如果小编编辑的是3D模型，那应该怎么做呢？ 因为我们不太可能把模型效果等引擎的核心元素实现成不可变的数据结构，即使可以实现，开销也可能非常高，所以如果我们要编辑一个3D模型，编辑一个特效，我们应该做什么？
事实上，3D 模型本身就是一个 UI 元素。 以小编为例，无论是通过传统的数值UI控件，还是通过在场景中拖拽旋转来操作模型，我们这里改变的始终是这组抽象的不可变数据结构的数据，而不是去操作模型或特效本身，所以模型和特效本身只是一个特殊的 UI 元素。
其实在使用了不可变数据结构之后，处理这种复杂模型效果的编辑变得更加容易了，因为使用不可变数据结构可以让我们解耦数据更新和UI更新。 这会带来什么样的好处？
数据更新通常是同步的，而且发生得非常快。 但是，UI 更新有时是异步的。 比如我们刚刚提到的模型的加载往往是一个异步过程，或者UI界面上的动画本身也是一个异步过程。 如果一个同步事件与一个异步事件耦合时，往往会带来很多复杂的事情。
当数据更新和UI更新解耦后，我们应该什么时候更新UI呢？ 答案是固定的帧率。 这对于游戏开发的同学来说是非常熟悉的怎么制作游戏修改器，因为我们的游戏总是以固定的帧率刷新。 我们刚刚将这个概念带回了编辑器。 下面用一个具体的例子来说明解耦的好处。 在场景编辑器中，我们有一个 UI 列表来显示场景中的所有模型，以及一个场景窗口来提供场景的预览和编辑。 当一个美术生在场景中插入了一个新的模型，那么在下一个更新周期，我们的列表和场景就会开始根据变化进行更新，列表中会显示一个新的模型，并开始加载场景新模型。
但是这个时候美术生突然意识到我选错了模型，于是他立刻决定删除模型，然后列表中的模型也被删除了，但是场景中的模型还在加载中。 如果是基于事件的更新，则面临着删除一个正在加载的模型。 如果选择直接删除卸载的模型，编辑器会崩溃。 如果忘记删除，场景中就会多出一个不受控的模型。
基于不可变的数据结构，如果我们把数据的更新和UI的更新解耦，这时候我们的处理就会变得非常简单。 在加载过程中，我们只需要忽略数据变化，让模型静默加载即可。 这时候，场景中就会出现冗余模型。 我们会在下次更新时通过数据比对找到它，然后删除它，这大大减少了我们在这个过程中出错的可能性。
使用不可变数据结构时，撤消和重做几乎是免费的。 它的原理也很简单，就是我们把所有变化的数据放在一个列表中保存。 当我们需要撤销的时候，只需要回头找历史数据，重新取出即可。
前面我们提到了连续拖放的一个特例，其实解决起来很简单。 我们只需要合并在一个小的时间阈值内连续发生的变化，放到历史列表中。 所以这就是整个《星球大战前夜：永恒银河》项目中编辑器的核心框架，非常简单。
我们首先会有一个历史数据队列，里面保存着我们所有编辑过的历史状态，然后我们的编辑器会周期性的从历史中选择最新的当前数据，发送到我们的UI界面进行刷新。
我们把所有的UI按照层级划分成不同的View，这也是借鉴了React中基于组件的UI设计。 我们会将一个大的界面拆分成更多的小的抽象界面概念，每个界面只做自己负责的事情，这样可以提高代码复用率，减少各个UI界面和UI控件之间的差距。 逻辑复杂性。
当视图修改数据时，会产生一条新数据，我们将这条新数据插入到历史队列中。 在下一个更新周期，所有的UI控件都会根据新的数据进行更新。 当我们需要撤销操作时，只需要简单地回滚历史队列中的指针即可。
说完我们整个编辑框架，我们回过头来和声明式UI做个对比。 声明式UI主要是基于一个虚拟的UI层来解决数据和UI之间的同步问题。 它们不提供直接撤消或重做支持。 毕竟是更通用的应用开发框架。 它的UI代码会很简单3D交通工具，但是整个框架会更多的依赖非常强大的开发团队来维护。 基于不可变数据结构的 UI 依赖于特殊的不可变数据结构。 它的优点是直接提供了undo和redo的支持。 UI代码会稍微复杂一点，因为我们依赖所有的数据来表示为不可变的数据结构，但是它的框架代码会很简单。
对于我们的应用场景，游戏开发团队通常只有一个小的编辑器开发团队，undo和redo是编辑器非常关键的功能需求。 因此，基于不可变数据结构的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%的代码，我们在开发过程中几乎没有遇到任何严重的错误，因为整个编辑器的框架和结构非常简单。
不可变数据结构还有许多其他优点和特性。 例如，由于不可变数据的特性，它自然是一种无锁线程安全的数据结构，所以你可以将一些非常复杂的数据操作移到另一个线程游戏角色，而不用担心你的UI线程和你的数据线程之间有任何竞争;
另一方面，由于不可变数据结构实现了数据更新和UI更新的解耦，我们实现一个多人实时协作的编辑器也会容易很多。 我们想知道大家有没有在自己的项目中实现过使用不可变数据结构，或者以后大家在自己的项目中会如何引入不可变数据结构。 谢谢大家今天来听我们的分享！
合作请联系 商务合作/投融资对接(微信） 西瓜:18659030320 刘威:18948723460 文静:mutou_kiki 行业爆料/采访(微信） boq：boq270756 投稿邮箱： tougao@youxituoluo.com
