基于庐山三维场景的图算法虚拟仿真系统研究

刘嘉昕，游 珍，黄捷文，陈家祥，胡洪文

(1．江西师范大学网络化支撑软件国家国际科技合作基地，江西 南昌 330022；2．江西师范大学软件学院，江西 南昌 330022； 3．江西师范大学计算机信息工程学院，江西 南昌 330022)

0 引 言

虚拟现实(Virtual Reality， VR)是以计算机技术为核心并结合相关科学技术对现实世界或现实中实体进行全方位仿真式模拟的数字化环境[1]。虚拟仿真系统是一种融合多源信息的可交互式三维动态实景和实体行为的系统，利用计算机结合显示设备生成的沉浸和互动体验[1]。虚拟现实技术的3I特性，即Immersion(沉浸感)、Interaction(交互性)和Imagination(想象性)，使其在军事、制造、医疗、娱乐、教育等领域具有无可比拟的潜力。因此，虚拟现实技术与理论分析、科学实验已经成为人类探索客观世界规律的3大手段[2]。目前,随着5G这个通讯技术的诞生和商用，虚拟现实所涉及的全景视频、立体3D、高分辨率画质等对网络传输速度和带宽需求较高的问题也顺势得到了解决[3],这将有效扫除分布式虚拟现实(Distributed Virtual Reality， DVR)中“交互延迟高”这一大障碍。

算法与数据结构是计算机专业的核心课程之一，它具有较高的抽象性，对教学有巨大的挑战性。图是这门课中具有代表性的一种数据结构：图是一些顶点(node)的集合，顶点通过一系列边(edge)结对，顶点有时也称为节点或者结点，边有时也称为链接。边可以有权重(weight)，即每一条边会被分配一个正数或者负数值。图是现实世界大量问题的一个抽象表示，也为计算机程序和实际问题提供了一个卓越的研究与应用模型。如果图代表航线，各个城市就是顶点，航线就是边。那么边的权重可以是飞行时间或者机票价格。图中结点与结点之间、结点与边之间逻辑关系可以用图的算法来刻画。运用图中的最小生成树、最短路径、遍历等算法就可以解决现实生活中的诸多问题，诸如航线规划、最佳经济铺路、卫星导航等问题。

就当前传统算法的教学而言，多为线下讲授(老师讲解PPT，学生听课编程)的教学方式为主。这种教学方式相对生硬，由于算法及其执行过程十分抽象，学生普遍感觉学习难度大，并且除了写代码外，缺少对图结构及其算法执行结果的可视化学习操作环境，使得一些学生在没有理解知识点的基础上直接进行编码，在这种情况下，学生很容易失去深入学习算法的兴趣，更何谈后续应用算法解决实际问题。对于老师而言，尽管能够在课堂上讲得很详细，但还是容易出现学生对理论和算法的掌握程度参差不齐的情况，老师理论授课和学生编码实验的分离容易发生教学与实践的脱节。因此，对于图算法的传统教学和实验中存在如下问题：1)算法的逻辑性强、晦涩难懂；2)算法实现过程抽象，难以理解；3)理论教学与学生实践存在差别、脱节；4)教学中课堂展示与提供的PPT都是以平面为主，缺少交互性和沉浸感。

在虚拟现实技术的蓬勃发展下，教育领域也成为该技术运用的主战场之一。在算法与数据结构教学中引入虚拟现实技术会成为摆脱传统教学弊端的首选方案。本文就是利用虚拟现实技术对图算法的教学和实验进行革新，在VR辅助教学的情况下，学生可以脱离纸质书本的限制，置身于虚拟算法世界中，可感知算法知识内容，可交互操作，让学生理解算法的执行过程，进而提高学生的学习兴趣，增强其可视化思维能力和创新能力。

借助VR技术在教育领域的优势，针对以上传统图的算法教学和实验中存在的问题，本文基于搭建的庐山三维场景，设计并实现了图算法虚拟仿真系统，首创性地将枯燥抽象、晦涩难懂的计算机图结构结合到庐山三维场景之中(每个景点对应图的结点)，使其以直观、形象、有趣的方式将图算法的执行过程展示给学生。对5种图算法提供了“自动展示”和“用户交互”这2种运行模式。本文的主要贡献是将图的算法、算法教学与实验和虚拟现实技术进行有机结合，研发的虚拟仿真系统使算法学习过程更加生动有趣，使学生在游玩庐山中理解算法思想和精髓，以激发学生对算法与数据结构这门课的学习兴趣，为编程实践打下良好的基础。

1 研究现状

算法与数据结构作为大学计算机及相关专业的一门必修课，对相关专业的后续学习具有极强的重要性。传统算法教学和实验中的问题仍然存在，也日益凸显。面临诸多问题，在新时代下，需要对教学方式进行改革，也需要引进大量的现代新技术。

1.1 线下授课与编程实验的教学方式

在大学中，对于算法与数据结构专门课程的教学多数采用线下讲授和上机实验的教学方式。通过教师在课堂中对算法知识点的讲解，只有一部分理解能力强的学生能很快掌握教学内容，这是因为课程本身具有很高的抽象性，知识和内容比较晦涩难懂，且大学对该课程设置的课时普遍不充足，尽管教师可以在课后布置相关任务来加强学习，但是由于理论知识的枯燥无味性，学生不大可能会在课后主动去深入探索，即使有些学生愿意主动通过编程验证所学理论知识，但仍没有机会可视化地实际体验算法的执行过程。因此，上述系列问题可能会把一些基础差的学生推向失去耐心和兴趣的深渊。

1.2 个性化问题驱动的教学方式

对算法与数据结构采用个性化的、问题驱动的教学方式有助于改善传统授课和编程方式的教学效果。通过指出引导性问题，借助画图、举例与验证方式，解决教学效果不佳的问题[4]，但教学的本质问题依然没有得到解决，即枯燥的理论知识，容易使得学生失去学习的动力和兴趣，而学习兴趣对于学习新知识而言具有深远的影响。兴趣促使学生不只是满足于表面含义和结构，而是积极地探寻深层含义[5]。兴趣是创新的推动力，培育兴趣是教师的职责[6]；兴趣发生于好的“调动”和“满足”[7]，计算机科学的深入必须要有自主探索的学习精神，假使丧失兴趣，则很难在这条道路上走远。因此，教师在教学中要把学习兴趣的诱发培养作为学生掌握知识的一个阶段，作为一个重要教学原则来抓以有助于教学效果和质量提高[8]。

1.3 虚拟现实在教育领域的应用

2016年3月18日,北京师范大学举办了“智慧学习与VR教育应用学术周”，以提高教育行业对虚拟现实技术的重视[9]。2019年12月，国家发展改革委、文化和旅游部、教育部、民政部、商务部、卫生健康委、体育总局7个部门联合印发《关于促进“互联网+社会服务”发展的意见》[10]，大力鼓励虚拟现实等技术在教育、文旅等领域的应用。在2019年10月在江西南昌召开的第二届世界VR产业大会上[11],赛迪智库电子信息研究所、虚拟现实产业联盟发布《虚拟现实产业发展白皮书(2019年)》,将虚拟现实技术在教育领域中的应用分成中小学教育、职业教育和高等教育3个方向[12]。而大会中签约虚拟现实相关项目也达到104个，其总金额超过650亿元[13]。

与此同时，虚拟现实在教育行业已有广泛的应用。在国外，有美国IBM开发的AWEDU(Active Worlds Educational Universe)系统[14]；有Merchant等在Second Life中搭建的供学生学习化学概念的3个化学虚拟学习场景[15]；还有谷歌与美国多所K-12学校合作推出的虚拟现实教育计划Expeditions[16]。在国内，有中学物理与虚拟现实结合[17]、基于虚拟现实技术的儿童交通安全教育系统[18]、运动员体育素质训练的虚拟环境[19]、虚拟现实导游系统[20]等。

1.4 基于虚拟现实技术的教学方式

传统教学中使用PPT的教学更加擅长于记忆需要通过文本和图片记忆的特定知识,这点对于VR教学较难完成。但虚拟现实对于原理或者方法的理解,以及对于问题的主观感受上具有远超前者的效果[21]。目前，虚拟现实在教育行业已有广泛的应用，但是在计算机算法与数据结构教学方面的应用则是少之又少。基于虚拟现实的数据结构三维动态教学系统[22]在将VR技术与算法教学结合方面进行了初步尝试，但是它只是简单将2D内容3D化，该教学系统提供了对重要参数的设置，但学生只能先设定好参数，然后观察某种算法的运行过程，这无异于当今的微交互式视频。

与上述传统授课和问题驱动的教学方式相比，基于虚拟现实的数据结构三维动态教学系统[22]增强了趣味性，但缺乏交互性。即学生没有亲自动手实践的机会，并没有体现到虚拟现实的交互性特征。

本文开发的图算法虚拟仿真系统兼顾了“激发兴趣”和“交互沉浸”的特征。该系统不仅将图的结构和算法的执行过程三维化，还让用户拥有以第一人称视角进入结点分场景的沉浸性体验，用户根据算法在多个景点中切换畅游和交互操作，感觉到自己就是算法需要执行的实体，亲身实境地观察和理解算法每一步的执行过程。

2 图虚拟仿真系统设计

针对算法与数据结构传统教学方式缺乏动态性、趣味性、互动性等方面的不足，本文以图算法作为研究对象，并实现一种基于虚拟现实技术的可交互的教学系统。

2.1 开发流程

如图1所示，从图虚拟仿真系统设想的提出到系统的成型经过了需求分析、场景建设、编码实现、虚拟设计等过程。下面将简述系统实现的每个阶段。

图1 开发流程

2.1.1 需求分析

1.情景分析。

考虑到虚拟现实结合教育的同时又要体现江西特色，采用江西名胜庐山作为背景，以景点间旅游为情景，利用算法与数据结构中的图算法于庐山相关问题的求解中。例如：将不同的旅游景点模拟成路线中的一个节点，找出一条经过庐山各景点一遍且仅一遍的最短路线，为游客缩短游览时间和减少交通费用[23]。

2.可行性分析。

庐山景点分布比较分散，完全符合图结构。如图2所示，选取8个代表性景点(三叠泉、小天池、含鄱口、仙人洞、芦林湖、三宝树、天池塔和街心公园)表示为图的结点，景点之间的13条路径表示为图结点之间的边，边上的数值表示权值，比如从一个景点到另一个景点的路径长度或耗时。

图2 庐山景点的图结构

3.功能结构。

获取当下图结构的算法教学需求后，通过分析各个部分的功能需要，初步规划系统的功能结构。作为教学系统，实现2种算法执行模式：

1)自动展示模式。

通过系统控制运动实体自动演示算法执行过程，自动规划行走路径，并自动生成图对应算法的正确运行结果。

2)用户交互模式。

通过电脑或借助VR设备的控制，用户化身为虚拟角色，进入虚拟场景，参与算法的交互式互动，并实时观察实验结果。

如图3所示，自动展示和用户交互2个模块都包含了图的5类算法：Dijkstra最短路径算法、Kruskal最小生成树算法、Prim最小生成树算法、DFS深度优先搜索算法和BFS广度优先搜索算法。

图3 系统功能结构

4.工具选择。

在一系列初期准备工作完成以后，开始着手调研该系统的开发环境和建模工具，最后确认使用Unity3D可视化编辑器作为开发工具，使用3DsMax作为主要建模工具。

2.1.2 场景搭建

使用建模系统对庐山场景进行3D建模，将已经建好的模型和场景导入到新建的Project的asset文件夹中，导入场景切换动画，设置好全局主场景，编辑好各个景点分场景。如图4所示，将需要的模型摆放在合适且符合程序功能逻辑的地方，进行比例的调节，构建全局主场景小地图；图5是搭建好的庐山仙人洞景点的三维场景。

图4 全局主场景

图5 庐山仙人洞景点分场景

2.1.3 编码实现

基于庐山映射到图的三维场景，着手实现算法的执行和交互功能。首先需要研究上述5类图算法的思想和策略，使用C#脚本语言加以实现。编码实现是图算法虚拟仿真系统最为核心的设计部分，涉及很多技术难题和理论问题，本文将在第4章进行详细描述。

2.1.4 虚拟设置

本虚拟仿真系统既支持电脑控制(键盘、鼠标控制交互，屏幕终端显示)，也可以借助VR设备(三维显示屏、头盔、手柄等)实现算法的交互操作，还可以使用分布式虚拟现实技术实现多人协作。在满足教学效果的基础上，真正实现虚拟现实技术的3大特性。

2.2 虚拟仿真系统与图结构的映射

在虚拟现实技术与算法教学结合时，要考虑诸多方面的因素，本节将讨论在虚拟现实中以何种方式展示图的结构，以及如何模拟算法的执行过程。

2.2.1 图结构的定义

庐山场景的图结构包含了8个结点和13条边(如图2所示)，在Unity3D的C#脚本代码中定义一个8×8的二维矩阵Graph[8][8]来表示结点之间的边，即结点到结点之间的邻接关系。行代表边的起点，列代表边的终点，行列对应的值表示的是从起点到终点所经过的边的权值。

当邻接矩阵中Graph[i][j]=0时，表示的是终点和起点都是同一个点，需要排除；若Graph[i][j]=-1，表示2个结点之间无路可达。

2.2.2 边的选取

在自动展示模式下程序通过控制虚拟角色在场景中的运动，将结点与结点连接起来，以表示2个结点之间的边被选择。在用户交互模式下，用户点击小地图上的结点，在此过程中用户要先点击一个起始结点，然后再点击选择一个终止结点，表示选择了对应的边(其中每一选择步骤系统都会给予人性化高亮显示提醒)，选择完成后，系统将会根据用户的选择移动虚拟角色。

2.2.3 过程的存储

对用户交互过程的存储是为了系统在判断用户操作过程的正确性的同时，还能找出首次出错的位置。由于本系统中判断程序是根据用户当前操作产生的结果并结合历史步骤的单个迭代数据来判断用户目前操作的准确性。若系统正在根据用户操作实时判断用户某一步骤正确性，则代表用户之前的每一步都是正确的，若出现错误，则系统会停止后续正确性判断。

因此，对于用户过程数据，只存储判断程序需要的数据，不存储用户过程中每一步骤的数据，但用户每一次操作过程的文字描述会存储在Unity中TipCanvasText的text中，并使用它在前端展示。根据不同图算法定义了不同名称或不同类型的变量，例如：Kruskal算法中定义的gradeSum变量，以存储用户已选边权值的累计；Prim算法和Dijkstra算法中定义的newGrade，以存储用户当前选择的权值；DFS算法和BFS算法中定义的start与end,以记录用户当前选择的边。

2.2.4 结果的存储

在图算法执行完毕后，系统需要展示系统主动或用户手动交互的结果，本系统代码中定义一个8×8的二维矩阵ResultGraph[8][8]来表示生成的结果图中结点之间的边，即结点到结点之间的邻接情况，并将所有值初始化为0,用户或系统每次选择后，会将二维矩阵中对应的值修改为1，表示结果中增加了一条边；在自动展示模式的程序中还定义了一个存储选边的route集合，存储着系统选边的结果。

2.3 虚拟仿真系统的实现和使用

本节介绍图算法虚拟仿真系统的2种运行模式和2个发布版本，并从用户角度，给出使用系统的活动流程。

2.3.1 2种算法运行模式

1.自动展示。

自动展示过程中，用户可以修改各个边的权值以观察在不同组合的边权值条件下对应的算法执行过程。如图6所示，用户可在左下角的小地图的文本框内修改边权值。

图6 边权值修改

用户通过以“上帝视角”观察整个庐山地貌和景点，以及对应算法对景点的连接过程，这个功能使抽象的算法执行过程具体化、动态化。如图7所示，系统实时地提供展示系统每一步控制的过程，并以文字显示在左上角，方便用户观察。

图7 自动展示过程

2.用户交互。

本系统还提供一种由用户互动性地手动控制方式，让学生自己手动操作相应算法的执行过程，将每一步操作交由用户自主完成。除了上述的自定义边权值之外，还实现这些交互功能：

1)选择边功能。用户通过在小地图上点击一个起始结点，和一个终止结点，选择相应的边来控制实现算法的每一步。当用户选择了某2个不存在边的结点时，系统会给予提示，并让用户重新选择。若用户已经选择了某个起始结点可以再次点击该结点以取消选择。

2)主场景和分场景之间切换功能。当用户处于主场景时，可以点击“进入场景”按钮进入到某景点的分场景，随后用户可以点击“退出场景”按钮回到主场景。

3)角色移动。进入某个景点的分场景之后，用户可以通过键盘的“上”“下”“左”“右”或“W”“S”“A”“D”来控制虚拟角色的行走，并游览景观。

2.3.2 2种发布版本

本系统最终发布了2个版本：WebGL版和PC版。WebGL版可通过浏览网站https://nss.jxnu.edu.cn/VRExperiment/index.html，在网站首页点击“进入无向图算法虚拟仿真实验”进行访问，其运行界面如图8所示。PC版则需要用户下载客户端应用程序。

图8 WebGL运行界面图

2.3.3 用户使用流程

基于庐山三维场景的图虚拟仿真系统的运行流程如图9所示。

图9 系统运行流程图

用户进入系统后点击开始实验进入到实验选择环节，在此环节中，用户可以直接选择算法开始实验，也可以在边对应的文本框中写入需要的值以修改图中边的权值，然后再选择算法和起始结点开始实验。

若用户进入“自动展示”模式，算法执行与运动逻辑完全交由实验系统完成，用户在该模式下观看算法运行的每一个步骤来理解算法的中间执行过程，同时在系统的左上部分会根据系统算法控制的步骤实时给出过程记录，方便用户回顾之前的运行步骤。

若用户进入“用户交互”模式，虚拟角色和算法执行过程将交由用户控制。在开始实验后，用户需要根据自己对相应算法的思考在系统小地图上选择一个起始结点和一个终止结点，以表示虚拟角色从起始结点的位置运动到终止结点的位置，同时2点之间的边将被置为被选状态。在任意时刻里，若箭头位置在结点位置，用户可以点击进入场景，在播放完一段切换动画后，系统将进入到结点名称所表示的场景之中，用户在场景中可以使用键盘上的方向键控制虚拟角色的移动，以游览庐山景点中优美壮观的景色，在此过程中，用户不仅可以学习相关算法，还可以游览江西知名旅游景区，这也是学习加放松的完美结合。实验交互完毕后，系统界面将会显示实验的执行过程和用户交互的判断结果，若用户的交互结果不符合对应算法的规则,系统会给出错误发生的位置。在结果展示的整个过程中，用户可以清晰了解到自己操作实验的步骤，了解自己在实验过程中出现的问题，并及时纠正错误。

3 理论问题和关键技术

本系统在开发过程中存在各类理论问题和技术难点，本章将详细介绍这些问题的解决方案。

3.1 大小地图映射

本系统是以在庐山三维场景景点为背景。主场景中各个结点之间没有设置可见路径以表示各个结点之间是否有边连接，路径的边连接情况仅在小地图中展示。在用户交互模式下，使用相关图的算法时，需要通过系统窗口右上角的小地图来了解结点与结点之间的权值以及连接情况。同时，虚拟角色在主场景中的位置会对应到小地图上的箭头，用户可以参考箭头在小地图上的位置来确认角色在场景中的位置。

问题描述如何将主场景中的景点位置与小地图小圆点一一对应？如何在主场景俯视视角下隐藏可见边？

解决方案本系统利用Unity3D的Camera下的Culling Mask实现了全景图与小地图的映射。具体实现过程如下：

1)在项目文件中创建一个Texture，并在主场景中创建一个Camera，调整Camera的位置，使其能够观察到完整的场景。

2)为Camera设置Target Texture，即第一步创建的Texture。

3)在场景中每一个结点位置创建一个sprite，为其加上圆形遮罩，并在它上面创建3D Text来显示结点名称；每个相邻边之间的直线位置顶部都设置一个Quad；并为本步中创建的物体都设置Layer为waymap。调整所创建的新物体的位置，确保在摄像机中所展示的效果能与实际场景中的位置保持一致。

4)设置2个用户Camera(对应于用户在主场景视角和用户在分场景中的角色第一人称视角)的Culling Mask属性，取消选择waymap，并设置第一步中创建的Camera的Culling Mask属性，仅选择waymap。使得用户在系统主场景中不会看见新创建的物体，而小地图仅显示新创建的物体。

5)创建小地图的Canvas，将其位置调整为界面右上角，并在Canvas中创建RowImage，将Texture设置为第一步创建的Texture，并调整RowImage的位置。

3.2 被选边的高亮设置

对已被选的边进行高亮或者变色处理，有利于用户清晰地获得图中生成的最小生成树、最短路径或遍历路径，使用户更为透彻地了解算法的执行过程。

问题描述当在自动展示模式或用户交互模式下，系统或用户选定了某条边后，系统是如何在场景模型中找到该条边？如何对找到的边进行高亮处理的？

解决方案要实现这种效果，首先必须要能在hierarchy中找到小地图上的路径。对每条边进行规则性命名，即将相关边的预制件放在2个结点中名称值较小的结点模型下，边命名中使用符号“-”连接2个结点的名字，且命名总是以左小右大的方式命名。在算法脚本每次从邻接矩阵中找到下一条边后，都可以先从更小值结点模型下，根据命名规则方式找到相应的边。

找到边后就需要对该边进行处理，借助以边更换Material材质的方式为其改变颜色使得相应的边高亮显示，这种方式与使用shader效果相当，但更为节省系统资源。具体涉及的代码如下：

int low=row>col?col:row;

int high=row>col?row:col;

string NowSucWayName=low+"-"+high;

GameObject.Find(NowSucWayName).GetComponent().material=changeMaterialT;

用户不会根据大小顺序选择结点，根据上述规则性命名的选边原理，需要区分用户选择结点编号的大小顺序，在代码中定义一个low和high的变量分别获取两者较大编号与较小编号，然后根据规定的命名规则用“-”将他们拼接成边模型的名称形式保存在NowSucWayName变量中，然后根据NowSucWayName找到对应模型,并为它更换材质球。

3.3 用户交互模式下算法交互方式

由于在图的各类算法中，经常会出现执行到某个结点后，无法继续再从该结点继续执行下去，而需要从其它结点开始执行的状况。

问题描述在用户交互模式下，需要让用户完全控制边的选择过程，这种操作是以何种形态为用户提供合适的交互接口？

解决方案系统为用户提供了一种简洁的交互机制，即用户先选择边的开始结点(点击小地图上圆点按钮)，此时，系统将虚拟角色立即跳转到起始结点的位置；之后，用户再选择边的终止结点，如果选择无误系统将会调用运动脚本并对对应边进行着色和高亮显示。

由于图中某些部分可能不存在边，且用户操作存在失误的情况，系统中提供如下检查与判断机制：

1)取消选择。即当用户已经选择了一个起始结点A后，需要重新选择另外一个起始结点B，系统提供对已选结点A再次点击的方式取消上一次选择。

2)边不存在或重复选择。即当用户已经选择起始结点和终止结点后，系统会立刻在后台判断是否存在对应的边，或者该边是否已经被选择，若这种情况发生，系统将会取消用户的本次操作，并给予用户错误提示，提醒用户重新选择另一条边，如图10所示。

图10 边选择错误提示

3.4 用户交互模式下的结果正确性判定

问题描述有些图算法的结果可能不是唯一的。由于计算机不具有人脑的灵活性，如何将用户交互模式下的操作结果与图算法的多结果进行比对，并判定正确？

解决方案通过深入研究探讨算法的原理以及结果的共性，系统采用以下方案解决，分别对5种算法进行描述：

1)Prim算法。

由于该算法是从某个起点开始，无论下一条选的是哪一条边，被选边的权值一定都是确定的。因此本系统采用程序实时跟踪用户的每一次选择，在用户做出选择前，系统会提前计算得到下一次应该被选的边的权值，在用户选择结束后，只需要比对两者结果，便可以判断用户本轮交互的正误，并给出发生错误的步骤。

2)Kruskal算法。

该算法的每一步同样具有共同特性，即其每一步选择的边的权值与先前的权值的累积是固定的，且考虑图的权值可以交由用户设定，因此系统中也将该部分的判断设定为与Prim算法类似的实时跟踪方式。

3)Dijkstra算法。

此算法判断方式与Prim算法极为类似，只需在Prim算法实现的前提下完成。

4)DFS算法。

从第一个起点开始程序会在用户每次选择终止结点后，将终止结点进栈，程序始终会保证栈顶所代表的结点有未被选择的相邻结点。在用户每一步选择后，程序判断用户的起点是否是从栈顶元素所代表的结点出发，并同时判断终止结点是否被选择。

5)BFS算法。

该实现过程较为复杂，简单来说，即是后台程序在用户每一步选择后，都会更新图中每个结点的相对层次，程序始终可以保证用户可正确交互结点的层次是正确的，系统只需根据后台获得的层次判断用户交互的正确性。

4 实例演示

Prim算法是图中最小生成树算法的一种，可在加权连通图里搜索最小生成树，由该算法所得的边子集所构成的树中，包含了连通图里的所有结点，且其边集的权值之和亦为最小。本章从“用户交互”和“自动展示”2个模式展示Prim算法的功能的实现和运行过程．

1)自动展示模式。

点击进入虚拟仿真系统后进入主界面，首先根据需要修改某些边的权值，随后依次点击“Prim”算法和“三叠泉”起始结点，选择“自动展示”开始实验。此时，在主场景中都能观察到箭头的运动轨迹，虚拟角色首先从“三叠泉”结点出发，根据Prim算法策略，从与“三叠泉”相邻的3条边(权值为6、8、12)中选择权值最小的边，即“街心公园”作为目标结点，系统控制虚拟角色从“三叠泉”向“街心公园”移动。当到达“街心公园”后，系统将继续根据Prim算法策略挑选下一对结点，以相同的方式向目标结点移动，其后续过程如图11所示。系统自动展示停止后给出完整的执行结果。

图11 自动展示模式执行结果

2)用户交互模式。

与自动展示模式类似，用户交互模式先根据需要修改边的权值，然后依次点击算法和“三叠泉”起始结点，选择“用户交互”开始实验。用户需要根据Prim算法策略自主选择边，用户通过点击小地图上的起始结点和终止结点选择一条边，选中边对应的路径会以高亮在小地图上显示，与此同时主场景中心位置2个景点之间也会出现该条路径。在用户交互模式下，用户依次选取其它边。当所有结点都连通，交互式实验结束，左上角显示用户的实验过程。如果用户的实验流程有误，在左上角提示中显示实验结果错误，同时还给出了错误的步骤，如图12所示。在用户交互模式下，可以在主场景和8个景点分场景中进行切换。如图13所示，虚拟角色现在的位置是“天池塔”，用户可以点击“进入场景”按钮，进入到“天池塔”三维场景中，可以通过键盘控制虚拟角色移动。

图12 用户交互模式实验结果

图13 进入分场景

5 结束语

本文从教学和虚拟现实2个维度开展研究和讨论，通过搭建的庐山三维场景来模拟图结构，利用Unity3D引擎设计并实现了图算法虚拟仿真系统，并围绕着该虚拟仿真系统的理论问题和关键技术进行研究和探讨。本虚拟仿真系统的特点概述如下：

1)系统将图的结构和算法的执行过程以具象化、可交互的游戏形式呈现给用户，并调动学生学习算法与数据结构的积极性，使其更有动力和信心对算法的分析和应用进行更深入学习和探索。

2)系统提供了自动演示和用户交互2种模式，使学生摆脱抽象枯燥的传统理论讲授方式，让学生以交互方式参与实验，见证和控制算法执行过程，进而到达“知其然也知其所以然”的目标。

3)系统操作简单易懂，情景切合现实，可以作为算法与数据结构教学的一种新方法。

本文所研发的系统融合游戏化的特征，贯彻“寓学于乐”的教育理念，提高学生学习的内在动机[24]。目前系统仍然在升级与维护中，已经搭建还原了江西庐山的8个场景，但场景模型还有完善空间，UI也有待优化。后期，还将引入分布式虚拟现实技术，使得不同的人可以在世界各地通过网络进入图虚拟仿真系统的同一个三维场景，虚拟角色既可以独立执行算法，又可以实现多角色的协同工作。