《星战前夜:无烬星河》主程:基于不可变数据结构的编辑器开发

张凯

2021-06-10506次浏览

1评论

4收藏

2点赞

分享

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
欢迎各位同学加群,与众多游戏爱好者一同学习交流~

评论 (1)

0/1000
网易游学APP
为热爱赋能
扫描二维码下载APP