基于Unity3D的数据结构算法交互式可视化平台

方子宁 曹正昊 孙瑞 郭清桐 朱玉晟

摘  要：文章重点研究数据结构算法交互式的可视化平台。由于数据结构的难点就是如何形象化其抽象的逻辑说明，并培养出完善的思维体系。团队致力于搭建交互式模型，利用Vue搭建网站，通过Unity3D这款软件编写算法底层逻辑代码，并且借助DoTweening等插件，达到算法动态的展示，通过Unity3D打包成WebGL和前端Vue交互，实现了数据结构算法的可视化互动学习。

关键词：交互式模型；Unity3D；Vue；数据结构算法；可视化演示

中图分类号：TP311.5  文献标识码：A  文章编号：2096-4706（2023）15-0006-06

Interactive Visualization Platform for Data Structure Algorithms Based on Unity3D

FANG Zining， CAO Zhenghao， SUN Rui， GUO Qingtong， ZHU Yusheng

（School of Electronics and Computer Engineering， Southeast University Chengxian College， Nanjing  210088， China）

Abstract： This paper focuses on researching an interactive visualization platform for data structure algorithms. The difficulty of data structure is how to visualize its abstract logical explanation and cultivate a sound thinking system. The team is committed to building interactive models， using Vue to build websites， using Unity3D software to write underlying logic code of algorithms， and utilizing pluggable units such as DoTweening to achieve dynamic display of algorithms. Through packaging Unity3D into webgl and interacting with front-end Vue， visualization and interactive learning of data structure algorithms are achieved.

Keywords： interactive model; Unity3D; Vue; data structure algorithm; visual demonstration

0  引  言

数据结构算法学习的一大难点[1]就是如何形象化其抽象的逻辑说明，并培养出一套完善的思维体系框架，而该过程是十分枯燥的。对算法的理解学习要求学习者不仅有深厚的数学功底，还要有良好的逻辑思维能力才能够理解书本上大量抽象的算法公式和枯燥烦琐的代码运算过程。而就目前的情况而言，课堂上教师们的授课大多也是采用口头讲述结合书本文字，辅以笔头绘图来进行授课，更遑论部分自学者只能通过钻研代码来理解算法，可见传统的学习方式对初学者来说并不是非常便捷。因此，现阶段很需要一个将数据结构算法动态可视化的平台，通过实例带入和交互式可视化演示技术[2]，来帮助用户用更加生动形象的方式来理解数据结构和其所拥有的各项算法。

在经过团队一系列的研究和搜索后，发现目前国内外有不少对于算法可视化的网站[3]和辅助工具，比较熟知的有VisuAlgo和Data Structure Visualizations[4]等，而这每个网站也各自有自己的独特之，例如Data Structure Visualizations网站特点为过程可以自己控制，VisuAlgo则是加入了文字讲解和复杂度的备注。但目前所使用的可视化网站[5]，大多都是2D的过程展示，较少有通过3D模型来进行演示的平台，且交互性也不够强。同时由于不是专门用于学习数据结构的工具，因此这些网站包含了较多其他逻辑类的算法，而有很多数据结构特有的算法没有得到展示。

在一系列权衡之后，项目组成员决定采用Unity平台，在基于在校期间学习的各类算法的学习基础上，再加上网站的制作和运行技术，来搭建一个基于Unity3D的数据結构算法交互式可视化网站。在充分研究了项目可行性后，团队成员进行了各项分析并逐渐完成了平台的设计与交互式可行性分析。Unity3D是一项对于动态模型搭建非常便捷的平台，但是还需要一个媒介将unity3D的动态演示给展现出来，因此在经过一系列了解后，团队选用了现在常用的网页制作工具Vue。

1  理论基础

1.1  开发工具介绍

1.1.1  Unity3D

Unity是由Unity Technologies公司开发的跨平台专业游戏引擎，也是实时互动内容创作和运营平台，其功能涵盖了包括游戏开发、美术、建筑、汽车设计、影视在内的多个领域。Unity平台提供一整套完善的软件解决方案，可用于创作、运营和变现任何实时互动的2D和3D内容，支持平台包括手机、平板电脑、PC、游戏主机、增强现实和虚拟现实设备。

Unity的3D[6]开发平台是行业内领先的，Unity引擎的灵活性和实时互动性，为创作者提供了极大的便利，完善的技术和丰富的个性化功能可以满足开发者在使用时几乎所有的要求。同时Unity也密切关注着教育行业的发展，为学生使用Unity平台时提供了较多的便捷[7]。Unity提供易用实时平台，开发者可以在平台上构建各种3D互动模型。

1.1.2  Vue

Vue是一种渐进式的Web前端开发框架[8]，它基于标准HTML、CSS和JavaScript构建，提供容易上手的API和一流的文档。它拥有丰富的、可渐进式集成的生态系统，可以根据应用规模在库和框架间切换自如。Vue采用自底向上的增量开发设计，且它的核心库只关注视图层，非常容易学习，并且很易于与其他库或已有项目整合。

Vue出色的性能和丰富的场景对于本团队这种初学开发者来说实用性高[9]，上手度快。并且根据团队成员所查到的文献资料可知，Unity平台可以和Vue进行交互式的联动，实现两者数据的传参，通过这个特性，可以将这个平台的功能进一步完善。

1.2  设计思路

在进行项目统筹设计时，团队采用了渐增模型来设计，将网站所需要的一系列组成部分拆分为每项单独的增量构件，每个增量构件都是项目系统的一个子集，能够完成特定的功能。从最初进行网站的页面设计，而后在Vue搭建时进行算法展示窗口设计，完成这一部分时团队成员又开始研究窗口内动态模型所需要的交互部分，以此类推，逐步完善项目的网站系统，本系统的功能结构图如图1所示。

在设计网站时，团队初步构思了如下几个组成页面，包括主页的算法分类维护，算法展示和算法查找。其中，主页面会呈现该平台所有的算法并进行归类，用户可以根据自己的需求下拉找到想看的算法或者使用搜索栏进行关键字搜索，如果没有对应的算法系统会让用户重新输入，同时，用户输入的关键字，系统也会自动补齐相关算法并显示在搜索框的下方供用户选择。

当用户点击对应的算法图片后，会弹出该算法的展示界面，此时的界面共有三个部分，左边为Unity3D平台的动态实例展示窗口，右侧上半部分为该算法的文字介绍部分，下面则是用C++语言展示出来的主要逻辑代码。同时在展示实例的下方会有交互输入窗口，用户可以输入自定义数据，而后上方的动态实例展示窗口会根据数据生成对应的模型。模型建立好后用户可以点击对应的开始和暂停按钮，以观察模型的变化，流程如图2所示。

2  需求分析

数据结构算法[10]是计算机的中心思想课程，让程序员更好地了解程序之间的结构关系，因此结构的可视化非常重要。更重要的是要让人们对这门课的学习有更加轻松的体验，因此选取合适的3D模型进行交互式可视化演示就极其重要。本网站不仅适用于教师进行授课使用，也适用于希望初步自学数据结构的学生或者工作者，在对某一算法概念不清晰时，可以通过对本网站的使用加深自己的概念理解，模型的可交互性也增加了用户的使用体验。

该平台基于其他网站的优点，结合3D模型的具体化演示，通过搭建可交互式模型，网站实现算法如下：

1）线性表：顺序表和链表的基本操作，循环链表，双向链表。

2）栈和队列的基本操作，循环队列。

3）字符串的模式匹配。

4）矩阵的压缩存储和广义表的存储。

5）树：线索二叉树，前中后遍历二叉树，赫夫曼树。

6）图：DFS，BFS，普利姆算法，克鲁斯卡尔算法，拓扑排序，关键路径，最短路径。

7）查找：静态查找：顺序查找，折半查找，索引顺序查找。

8）动态查找：二叉排序树，二叉平衡树，B-树，哈希表。

9）排序：直接插入，希尔排序，直接选择，堆排序，冒泡排序，快速排序，归并排序，基数排序。

3  系统实现

3.1  Unity3D模型搭建

在经过研究后，为保证组内各位成员所制作的工程不会产生版本误差导致无法互通，团队在Unity Hub中选择了同一版本2020.1.01f1来进行制作，而后通过多种渠道的自主学习，成员们初步了解了该如何使用Unity中的自带模型来完成初步的动态建模。

但由于大多数的教程都着重于如何使用Unity来设计一个游戏，因此都比较看终于动态模型的导入与动作的产生。而动作控制与本平台所需要的算法可视化并无太多关联，因此成员们在学习时主要选择通过讲解视频来了解并学习Unity中C#语言的应用和掌握，考虑重心在物体的材质、移动、旋转及多物体间的联动反应。在完成常用功能的学习后看，团队的研究重点在Unity模型的与Vue输入数据的交互性上。

为了实现交互式功能，团队并没有直接将物体排布在展示窗口中间，而是设置了预设体，这样可以让物体按照用户输入的数据自动生成对应的物体在窗口中。

3.2  Vue搭建

负责界面设计的成员照着设计时所画的界面设计图，如圖3所示，插入对应的标签、文本框和图片插件，网页的图片也已经设置了跳转链接，用户点击后就可以进入对应分类详细查看该类别中的算法，再点击单个算法的图片缩略图就可以进入该算法的动态模型演示页面。进入页面后，网页右半部分设置了文字注释部分以及代码注释部分，结合所用的动态模型，可以更直观地让大家理解这个算法。同时，手动输入数据进行交互式演示可以让抽象的算法变得具体。该网页在演示中也设置了暂停与开始按钮，方便用户暂停演示时可以查看该步骤所对应的代码。

3.3  服务器搭建

在比较了网络上各类云服务器的优劣性后，结合该项目的运行内存大小，团队成员选择了阿里云服务器。阿里云是创立于2009年的全球领先的云计算及人工智能科技公司，致力于以在线公共服务的方式，提供安全可靠的计算和数据处理能力。阿里云服务器是简单高效、安全可靠、处理能力弹性伸缩的计算服务器，常适用于开发者将完成的个人网站部署到云服务器上，较为轻松便捷。

在购买了云服务器之后，负责服务器搭建的成员按照操作流程设置好了端口，再设置好管理员的账号密码等内容，就可以开始上传文件，而后进行环境变量的配置。配置完成后就可以开始上传网站的源码，再部署Web项目包，最后经过调试就可将该平台成功放置在云服务器上。

3.4  功能实现

打开链接跳转后，会首先进入该网站的首页。经过讨论，本团队将首页设计成了算法缩略图加上简易文字说明的组合，将所有算法分为几类，而后进入每个分类可以再看到该类别中的几种详细算法首页Vue界面与算法分类Vue界面如图4、图5所示。

这里就用冒泡算法的实现过程来进行简单介绍。冒泡排序是简单的排序算法，它的基本原理就是比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这个比较的步骤要不停地重复，直到没有任何一对数字需要比较，而最后完成的数列应是按照从左到右从小到大的顺序排列整齐的。

所以在本模型中，团队成员采用了柱体来表示数字大小的不同，将每个元素比较大小转换为多个柱体比较高度的模型，更为直观。

为了做到交互式，通过在Vue的文本输入框输入数字，在进行数据传参传递到Unity中，这样就可以让每个柱体根据输入数据的不同改变自身的高低。而后通过对底层逻辑的编写和位置转换函数的研究，成功實现了点击界面Start按钮即可让生成的柱体依照冒泡排序的逻辑顺序开始自动交换位置的，同时会生成一个对应的有序数列。

在实现动态变化的同时，模型变换中还结合了Unity3D中物体材质的改变，让柱体在位置转换时可以实现颜色的转变，将每次需要交换的两个物体用亮色标记，交换完成后回到原来的颜色，而后过程都重复这一步骤，这样使得整个流程更加完善更加清晰。

3.5  代码思路阐述

3.5.1  Unity3D系统

算法演示动态模型的搭建步骤大致相同，这里选取冒泡算法的制作过程来进行简单阐述。首先搭建好预设体的模型并分类命名，例如Obj[0]为柱体，Obj1[0]为文本等，第二步设置类型转换函数numberString将文本转换为数字，并设置数字的有效读取范围为0～9。其次这是数据类型转换函数将转换后的数字设置为int型。数字读取部分就基本完成了。

然后是预设体的模型部分。第一步先确认在镜头中三维坐标，第二步设置参数x，x是获取到的数字进行处理后得到的数字。设GetComponent函数中localScale参数来实现自身的缩放，得到的新物体缩放比例为（1，numberInt，1），设置position参数将预设体的位置移动到镜头中合适的地方。物体移动至对英文之后，再次使用GetComponent函数中的text参数部分将物体对应的数字文本进行显示，并使用position参数移动至该物体前方便于观察。至此模型的生成部分就基本完成。

第三部分则是物体的动态部分，主要包括物体的位置移动，物体的材质变化（当前进行移动的物体会改变颜色来重点说明），以及文本对应的下挪。当前物体移动完成后，执行waitForSecond函数来等待，而后在执行下一个物体的移动。此处团队选用if函数来实现物体的动态演示，通过大小的自动比对来实现物体间的交换。

3.5.2  Vue代码

在主页以及算法选择页面部分团队成员插入了文本框、按钮、图片等部分，通过参数设置将各个部分大小调整为比例显示，以达到在不同的设备上都可以得到恰当大小的展示的目的。通过点击图片或对应文字就可以通过设置的跳转参数自动进入对应界面，流程如图6所示。

而后在动态模型展示界面主要设置了与Unity相关联的函数，例如querySelector函数可用于进行查询筛选，获取单个元素。navigator.userAgent函数可用于判断当前浏览器所处的环境，筛选用户所使用的设备，createElement函数用于创建数据节点。

最后比较重要的部分就是sendMsgToUnity函数，该函数用于实现Vue和Unity之间的参数传递，通过Unity中GameObject自带的SendMessage函数实现输入文本的传输，同时注意与Unity代码中的receiveMsgFromVue函数实现一一对应，这样才能保证输入的数据可以准确地在模型中展示出来，部分代码如图7所示。

4  项目创新点

相比较其他数据结构算法可视化网站，该平台实现了与用户动态交互，可以按照用户需求进行算法演示。在目前的市场中有很多关于数据结构算法可视化的网站，但是很多网站的可视化均是基于后台固定的数据进行算法的展示，用户无法自主的更改数据，丧失了算法的动态性。而本网站的一大亮点便是通过Unity平台与Vue框架进行交互处理，用户可以在Vue的界面中自主定义数据，然后通过Vue进行传递参数，同时Unity平台则会接收到这些参数，并提取到用户传递的数据，于是该算法便会基于用户所给予的数据进行动态的演示，增强了用户的使用体验，而不是仅仅观看了一次静态的动画演示，从而使用户更能理解到算法的本质。

5  结  论

数据结构算法学习对计算机本专业的学生已是一门较为困难的学科，其他没有经过系统学习的却想自学的开发者或学生就更难了。相比其他的算法2D展示网站，基于Unity3D完成的动态建模更为直观清晰。

今后该平台也会在现有这么多算法的基础上不断完善，加入现实中的实例来帮助使用者理解各算法的逻辑步骤，通过不同的可视化提高工具的适用性与推广性，让数据结构的算法不再那么困难。

参考文献：

[1] JUNAIDU S. Effectiveness of multimedia in learning & teaching data structures online [J].The Turkish Online Journal of Distance Education，2008，9（4）：97.

[2] 张一驰.大数据十大经典算法可视化实例教学系统研究与实现 [D].西安：西安石油大学，2021.

[3] 刘丛.针对数据结构的命令式算法可视化系统设计与开发 [D].长沙：湖南大学，2015.

[4] 胡珊.程序可视化方法在程序设计课程教学中的应用 [J].电脑知识与技术，2021，17（7）：104-105.

[5] WIBAWA P A，DWIYANTO A F，WIDIYANINGTIYAS T，et al. Utilization visualgo.net as a data structure learning media based on cdio [C]//2nd International Conference on Statistics，Mathematics，Teaching，and Research.Makassar：IOPscience，2018：012064[2023-01-06].https：//iopscience.iop.org/article/10.1088/1742-6596/1028/1/012064.

[6] 顾笑迎，吴瑨，李硕.基于Unity3D的自引查找工具设计与实现 [J].图书馆研究与工作，2022（12）：74-78+82.

[7] 朱青.基于项目驱动的Unity3D开发基础教学分析 [J].科技视界，2021（35）：125-126.

[8] 刘亚茹，张军.Vue.js框架在网站前端开发中的研究 [J].电脑编程技巧与维护，2022（1）：18-19+39.

[9] 赵龙，王风硕.基于Vue的图书销售系统设计与实现 [J].电脑知识与技术，2021，17（36）：81-82+85.

[10] 严蔚敏.数据结构：C语言版 [M].北京：清华大学出版社，2007.