劉嘉昕，游 珍，黃捷文，陳家祥，胡洪文

(1．江西師范大學(xué)網(wǎng)絡(luò)化支撐軟件國家國際科技合作基地，江西 南昌 330022；2．江西師范大學(xué)軟件學(xué)院，江西 南昌 330022； 3．江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院，江西 南昌 330022)

0 引 言

虛擬現(xiàn)實(shí)(Virtual Reality， VR)是以計(jì)算機(jī)技術(shù)為核心并結(jié)合相關(guān)科學(xué)技術(shù)對現(xiàn)實(shí)世界或現(xiàn)實(shí)中實(shí)體進(jìn)行全方位仿真式模擬的數(shù)字化環(huán)境[1]。虛擬仿真系統(tǒng)是一種融合多源信息的可交互式三維動態(tài)實(shí)景和實(shí)體行為的系統(tǒng)，利用計(jì)算機(jī)結(jié)合顯示設(shè)備生成的沉浸和互動體驗(yàn)[1]。虛擬現(xiàn)實(shí)技術(shù)的3I特性，即Immersion(沉浸感)、Interaction(交互性)和Imagination(想象性)，使其在軍事、制造、醫(yī)療、娛樂、教育等領(lǐng)域具有無可比擬的潛力。因此，虛擬現(xiàn)實(shí)技術(shù)與理論分析、科學(xué)實(shí)驗(yàn)已經(jīng)成為人類探索客觀世界規(guī)律的3大手段[2]。目前,隨著5G這個通訊技術(shù)的誕生和商用，虛擬現(xiàn)實(shí)所涉及的全景視頻、立體3D、高分辨率畫質(zhì)等對網(wǎng)絡(luò)傳輸速度和帶寬需求較高的問題也順勢得到了解決[3],這將有效掃除分布式虛擬現(xiàn)實(shí)(Distributed Virtual Reality， DVR)中“交互延遲高”這一大障礙。

算法與數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程之一，它具有較高的抽象性，對教學(xué)有巨大的挑戰(zhàn)性。圖是這門課中具有代表性的一種數(shù)據(jù)結(jié)構(gòu)：圖是一些頂點(diǎn)(node)的集合，頂點(diǎn)通過一系列邊(edge)結(jié)對，頂點(diǎn)有時也稱為節(jié)點(diǎn)或者結(jié)點(diǎn)，邊有時也稱為鏈接。邊可以有權(quán)重(weight)，即每一條邊會被分配一個正數(shù)或者負(fù)數(shù)值。圖是現(xiàn)實(shí)世界大量問題的一個抽象表示，也為計(jì)算機(jī)程序和實(shí)際問題提供了一個卓越的研究與應(yīng)用模型。如果圖代表航線，各個城市就是頂點(diǎn)，航線就是邊。那么邊的權(quán)重可以是飛行時間或者機(jī)票價格。圖中結(jié)點(diǎn)與結(jié)點(diǎn)之間、結(jié)點(diǎn)與邊之間邏輯關(guān)系可以用圖的算法來刻畫。運(yùn)用圖中的最小生成樹、最短路徑、遍歷等算法就可以解決現(xiàn)實(shí)生活中的諸多問題，諸如航線規(guī)劃、最佳經(jīng)濟(jì)鋪路、衛(wèi)星導(dǎo)航等問題。

就當(dāng)前傳統(tǒng)算法的教學(xué)而言，多為線下講授(老師講解PPT，學(xué)生聽課編程)的教學(xué)方式為主。這種教學(xué)方式相對生硬，由于算法及其執(zhí)行過程十分抽象，學(xué)生普遍感覺學(xué)習(xí)難度大，并且除了寫代碼外，缺少對圖結(jié)構(gòu)及其算法執(zhí)行結(jié)果的可視化學(xué)習(xí)操作環(huán)境，使得一些學(xué)生在沒有理解知識點(diǎn)的基礎(chǔ)上直接進(jìn)行編碼，在這種情況下，學(xué)生很容易失去深入學(xué)習(xí)算法的興趣，更何談后續(xù)應(yīng)用算法解決實(shí)際問題。對于老師而言，盡管能夠在課堂上講得很詳細(xì)，但還是容易出現(xiàn)學(xué)生對理論和算法的掌握程度參差不齊的情況，老師理論授課和學(xué)生編碼實(shí)驗(yàn)的分離容易發(fā)生教學(xué)與實(shí)踐的脫節(jié)。因此，對于圖算法的傳統(tǒng)教學(xué)和實(shí)驗(yàn)中存在如下問題：1)算法的邏輯性強(qiáng)、晦澀難懂；2)算法實(shí)現(xiàn)過程抽象，難以理解；3)理論教學(xué)與學(xué)生實(shí)踐存在差別、脫節(jié)；4)教學(xué)中課堂展示與提供的PPT都是以平面為主，缺少交互性和沉浸感。

在虛擬現(xiàn)實(shí)技術(shù)的蓬勃發(fā)展下，教育領(lǐng)域也成為該技術(shù)運(yùn)用的主戰(zhàn)場之一。在算法與數(shù)據(jù)結(jié)構(gòu)教學(xué)中引入虛擬現(xiàn)實(shí)技術(shù)會成為擺脫傳統(tǒng)教學(xué)弊端的首選方案。本文就是利用虛擬現(xiàn)實(shí)技術(shù)對圖算法的教學(xué)和實(shí)驗(yàn)進(jìn)行革新，在VR輔助教學(xué)的情況下，學(xué)生可以脫離紙質(zhì)書本的限制，置身于虛擬算法世界中，可感知算法知識內(nèi)容，可交互操作，讓學(xué)生理解算法的執(zhí)行過程，進(jìn)而提高學(xué)生的學(xué)習(xí)興趣，增強(qiáng)其可視化思維能力和創(chuàng)新能力。

借助VR技術(shù)在教育領(lǐng)域的優(yōu)勢，針對以上傳統(tǒng)圖的算法教學(xué)和實(shí)驗(yàn)中存在的問題，本文基于搭建的廬山三維場景，設(shè)計(jì)并實(shí)現(xiàn)了圖算法虛擬仿真系統(tǒng)，首創(chuàng)性地將枯燥抽象、晦澀難懂的計(jì)算機(jī)圖結(jié)構(gòu)結(jié)合到廬山三維場景之中(每個景點(diǎn)對應(yīng)圖的結(jié)點(diǎn))，使其以直觀、形象、有趣的方式將圖算法的執(zhí)行過程展示給學(xué)生。對5種圖算法提供了“自動展示”和“用戶交互”這2種運(yùn)行模式。本文的主要貢獻(xiàn)是將圖的算法、算法教學(xué)與實(shí)驗(yàn)和虛擬現(xiàn)實(shí)技術(shù)進(jìn)行有機(jī)結(jié)合，研發(fā)的虛擬仿真系統(tǒng)使算法學(xué)習(xí)過程更加生動有趣，使學(xué)生在游玩廬山中理解算法思想和精髓，以激發(fā)學(xué)生對算法與數(shù)據(jù)結(jié)構(gòu)這門課的學(xué)習(xí)興趣，為編程實(shí)踐打下良好的基礎(chǔ)。

1 研究現(xiàn)狀

算法與數(shù)據(jù)結(jié)構(gòu)作為大學(xué)計(jì)算機(jī)及相關(guān)專業(yè)的一門必修課，對相關(guān)專業(yè)的后續(xù)學(xué)習(xí)具有極強(qiáng)的重要性。傳統(tǒng)算法教學(xué)和實(shí)驗(yàn)中的問題仍然存在，也日益凸顯。面臨諸多問題，在新時代下，需要對教學(xué)方式進(jìn)行改革，也需要引進(jìn)大量的現(xiàn)代新技術(shù)。

1.1 線下授課與編程實(shí)驗(yàn)的教學(xué)方式

在大學(xué)中，對于算法與數(shù)據(jù)結(jié)構(gòu)專門課程的教學(xué)多數(shù)采用線下講授和上機(jī)實(shí)驗(yàn)的教學(xué)方式。通過教師在課堂中對算法知識點(diǎn)的講解，只有一部分理解能力強(qiáng)的學(xué)生能很快掌握教學(xué)內(nèi)容，這是因?yàn)檎n程本身具有很高的抽象性，知識和內(nèi)容比較晦澀難懂，且大學(xué)對該課程設(shè)置的課時普遍不充足，盡管教師可以在課后布置相關(guān)任務(wù)來加強(qiáng)學(xué)習(xí)，但是由于理論知識的枯燥無味性，學(xué)生不大可能會在課后主動去深入探索，即使有些學(xué)生愿意主動通過編程驗(yàn)證所學(xué)理論知識，但仍沒有機(jī)會可視化地實(shí)際體驗(yàn)算法的執(zhí)行過程。因此，上述系列問題可能會把一些基礎(chǔ)差的學(xué)生推向失去耐心和興趣的深淵。

1.2 個性化問題驅(qū)動的教學(xué)方式

對算法與數(shù)據(jù)結(jié)構(gòu)采用個性化的、問題驅(qū)動的教學(xué)方式有助于改善傳統(tǒng)授課和編程方式的教學(xué)效果。通過指出引導(dǎo)性問題，借助畫圖、舉例與驗(yàn)證方式，解決教學(xué)效果不佳的問題[4]，但教學(xué)的本質(zhì)問題依然沒有得到解決，即枯燥的理論知識，容易使得學(xué)生失去學(xué)習(xí)的動力和興趣，而學(xué)習(xí)興趣對于學(xué)習(xí)新知識而言具有深遠(yuǎn)的影響。興趣促使學(xué)生不只是滿足于表面含義和結(jié)構(gòu)，而是積極地探尋深層含義[5]。興趣是創(chuàng)新的推動力，培育興趣是教師的職責(zé)[6]；興趣發(fā)生于好的“調(diào)動”和“滿足”[7]，計(jì)算機(jī)科學(xué)的深入必須要有自主探索的學(xué)習(xí)精神，假使喪失興趣，則很難在這條道路上走遠(yuǎn)。因此，教師在教學(xué)中要把學(xué)習(xí)興趣的誘發(fā)培養(yǎng)作為學(xué)生掌握知識的一個階段，作為一個重要教學(xué)原則來抓以有助于教學(xué)效果和質(zhì)量提高[8]。

1.3 虛擬現(xiàn)實(shí)在教育領(lǐng)域的應(yīng)用

2016年3月18日,北京師范大學(xué)舉辦了“智慧學(xué)習(xí)與VR教育應(yīng)用學(xué)術(shù)周”，以提高教育行業(yè)對虛擬現(xiàn)實(shí)技術(shù)的重視[9]。2019年12月，國家發(fā)展改革委、文化和旅游部、教育部、民政部、商務(wù)部、衛(wèi)生健康委、體育總局7個部門聯(lián)合印發(fā)《關(guān)于促進(jìn)“互聯(lián)網(wǎng)+社會服務(wù)”發(fā)展的意見》[10]，大力鼓勵虛擬現(xiàn)實(shí)等技術(shù)在教育、文旅等領(lǐng)域的應(yīng)用。在2019年10月在江西南昌召開的第二屆世界VR產(chǎn)業(yè)大會上[11],賽迪智庫電子信息研究所、虛擬現(xiàn)實(shí)產(chǎn)業(yè)聯(lián)盟發(fā)布《虛擬現(xiàn)實(shí)產(chǎn)業(yè)發(fā)展白皮書(2019年)》,將虛擬現(xiàn)實(shí)技術(shù)在教育領(lǐng)域中的應(yīng)用分成中小學(xué)教育、職業(yè)教育和高等教育3個方向[12]。而大會中簽約虛擬現(xiàn)實(shí)相關(guān)項(xiàng)目也達(dá)到104個，其總金額超過650億元[13]。

與此同時，虛擬現(xiàn)實(shí)在教育行業(yè)已有廣泛的應(yīng)用。在國外，有美國IBM開發(fā)的AWEDU(Active Worlds Educational Universe)系統(tǒng)[14]；有Merchant等在Second Life中搭建的供學(xué)生學(xué)習(xí)化學(xué)概念的3個化學(xué)虛擬學(xué)習(xí)場景[15]；還有谷歌與美國多所K-12學(xué)校合作推出的虛擬現(xiàn)實(shí)教育計(jì)劃Expeditions[16]。在國內(nèi)，有中學(xué)物理與虛擬現(xiàn)實(shí)結(jié)合[17]、基于虛擬現(xiàn)實(shí)技術(shù)的兒童交通安全教育系統(tǒng)[18]、運(yùn)動員體育素質(zhì)訓(xùn)練的虛擬環(huán)境[19]、虛擬現(xiàn)實(shí)導(dǎo)游系統(tǒng)[20]等。

1.4 基于虛擬現(xiàn)實(shí)技術(shù)的教學(xué)方式

傳統(tǒng)教學(xué)中使用PPT的教學(xué)更加擅長于記憶需要通過文本和圖片記憶的特定知識,這點(diǎn)對于VR教學(xué)較難完成。但虛擬現(xiàn)實(shí)對于原理或者方法的理解,以及對于問題的主觀感受上具有遠(yuǎn)超前者的效果[21]。目前，虛擬現(xiàn)實(shí)在教育行業(yè)已有廣泛的應(yīng)用，但是在計(jì)算機(jī)算法與數(shù)據(jù)結(jié)構(gòu)教學(xué)方面的應(yīng)用則是少之又少。基于虛擬現(xiàn)實(shí)的數(shù)據(jù)結(jié)構(gòu)三維動態(tài)教學(xué)系統(tǒng)[22]在將VR技術(shù)與算法教學(xué)結(jié)合方面進(jìn)行了初步嘗試，但是它只是簡單將2D內(nèi)容3D化，該教學(xué)系統(tǒng)提供了對重要參數(shù)的設(shè)置，但學(xué)生只能先設(shè)定好參數(shù)，然后觀察某種算法的運(yùn)行過程，這無異于當(dāng)今的微交互式視頻。

與上述傳統(tǒng)授課和問題驅(qū)動的教學(xué)方式相比，基于虛擬現(xiàn)實(shí)的數(shù)據(jù)結(jié)構(gòu)三維動態(tài)教學(xué)系統(tǒng)[22]增強(qiáng)了趣味性，但缺乏交互性。即學(xué)生沒有親自動手實(shí)踐的機(jī)會，并沒有體現(xiàn)到虛擬現(xiàn)實(shí)的交互性特征。

本文開發(fā)的圖算法虛擬仿真系統(tǒng)兼顧了“激發(fā)興趣”和“交互沉浸”的特征。該系統(tǒng)不僅將圖的結(jié)構(gòu)和算法的執(zhí)行過程三維化，還讓用戶擁有以第一人稱視角進(jìn)入結(jié)點(diǎn)分場景的沉浸性體驗(yàn)，用戶根據(jù)算法在多個景點(diǎn)中切換暢游和交互操作，感覺到自己就是算法需要執(zhí)行的實(shí)體，親身實(shí)境地觀察和理解算法每一步的執(zhí)行過程。

2 圖虛擬仿真系統(tǒng)設(shè)計(jì)

針對算法與數(shù)據(jù)結(jié)構(gòu)傳統(tǒng)教學(xué)方式缺乏動態(tài)性、趣味性、互動性等方面的不足，本文以圖算法作為研究對象，并實(shí)現(xiàn)一種基于虛擬現(xiàn)實(shí)技術(shù)的可交互的教學(xué)系統(tǒng)。

2.1 開發(fā)流程

如圖1所示，從圖虛擬仿真系統(tǒng)設(shè)想的提出到系統(tǒng)的成型經(jīng)過了需求分析、場景建設(shè)、編碼實(shí)現(xiàn)、虛擬設(shè)計(jì)等過程。下面將簡述系統(tǒng)實(shí)現(xiàn)的每個階段。

圖1 開發(fā)流程

2.1.1 需求分析

1.情景分析。

考慮到虛擬現(xiàn)實(shí)結(jié)合教育的同時又要體現(xiàn)江西特色，采用江西名勝廬山作為背景，以景點(diǎn)間旅游為情景，利用算法與數(shù)據(jù)結(jié)構(gòu)中的圖算法于廬山相關(guān)問題的求解中。例如：將不同的旅游景點(diǎn)模擬成路線中的一個節(jié)點(diǎn)，找出一條經(jīng)過廬山各景點(diǎn)一遍且僅一遍的最短路線，為游客縮短游覽時間和減少交通費(fèi)用[23]。

2.可行性分析。

廬山景點(diǎn)分布比較分散，完全符合圖結(jié)構(gòu)。如圖2所示，選取8個代表性景點(diǎn)(三疊泉、小天池、含鄱口、仙人洞、蘆林湖、三寶樹、天池塔和街心公園)表示為圖的結(jié)點(diǎn)，景點(diǎn)之間的13條路徑表示為圖結(jié)點(diǎn)之間的邊，邊上的數(shù)值表示權(quán)值，比如從一個景點(diǎn)到另一個景點(diǎn)的路徑長度或耗時。

圖2 廬山景點(diǎn)的圖結(jié)構(gòu)

3.功能結(jié)構(gòu)。

獲取當(dāng)下圖結(jié)構(gòu)的算法教學(xué)需求后，通過分析各個部分的功能需要，初步規(guī)劃系統(tǒng)的功能結(jié)構(gòu)。作為教學(xué)系統(tǒng)，實(shí)現(xiàn)2種算法執(zhí)行模式：

1)自動展示模式。

通過系統(tǒng)控制運(yùn)動實(shí)體自動演示算法執(zhí)行過程，自動規(guī)劃行走路徑，并自動生成圖對應(yīng)算法的正確運(yùn)行結(jié)果。

2)用戶交互模式。

通過電腦或借助VR設(shè)備的控制，用戶化身為虛擬角色，進(jìn)入虛擬場景，參與算法的交互式互動，并實(shí)時觀察實(shí)驗(yàn)結(jié)果。

如圖3所示，自動展示和用戶交互2個模塊都包含了圖的5類算法：Dijkstra最短路徑算法、Kruskal最小生成樹算法、Prim最小生成樹算法、DFS深度優(yōu)先搜索算法和BFS廣度優(yōu)先搜索算法。

圖3 系統(tǒng)功能結(jié)構(gòu)

4.工具選擇。

在一系列初期準(zhǔn)備工作完成以后，開始著手調(diào)研該系統(tǒng)的開發(fā)環(huán)境和建模工具，最后確認(rèn)使用Unity3D可視化編輯器作為開發(fā)工具，使用3DsMax作為主要建模工具。

2.1.2 場景搭建

使用建模系統(tǒng)對廬山場景進(jìn)行3D建模，將已經(jīng)建好的模型和場景導(dǎo)入到新建的Project的asset文件夾中，導(dǎo)入場景切換動畫，設(shè)置好全局主場景，編輯好各個景點(diǎn)分場景。如圖4所示，將需要的模型擺放在合適且符合程序功能邏輯的地方，進(jìn)行比例的調(diào)節(jié)，構(gòu)建全局主場景小地圖；圖5是搭建好的廬山仙人洞景點(diǎn)的三維場景。

圖4 全局主場景

圖5 廬山仙人洞景點(diǎn)分場景

2.1.3 編碼實(shí)現(xiàn)

基于廬山映射到圖的三維場景，著手實(shí)現(xiàn)算法的執(zhí)行和交互功能。首先需要研究上述5類圖算法的思想和策略，使用C#腳本語言加以實(shí)現(xiàn)。編碼實(shí)現(xiàn)是圖算法虛擬仿真系統(tǒng)最為核心的設(shè)計(jì)部分，涉及很多技術(shù)難題和理論問題，本文將在第4章進(jìn)行詳細(xì)描述。

2.1.4 虛擬設(shè)置

本虛擬仿真系統(tǒng)既支持電腦控制(鍵盤、鼠標(biāo)控制交互，屏幕終端顯示)，也可以借助VR設(shè)備(三維顯示屏、頭盔、手柄等)實(shí)現(xiàn)算法的交互操作，還可以使用分布式虛擬現(xiàn)實(shí)技術(shù)實(shí)現(xiàn)多人協(xié)作。在滿足教學(xué)效果的基礎(chǔ)上，真正實(shí)現(xiàn)虛擬現(xiàn)實(shí)技術(shù)的3大特性。

2.2 虛擬仿真系統(tǒng)與圖結(jié)構(gòu)的映射

在虛擬現(xiàn)實(shí)技術(shù)與算法教學(xué)結(jié)合時，要考慮諸多方面的因素，本節(jié)將討論在虛擬現(xiàn)實(shí)中以何種方式展示圖的結(jié)構(gòu)，以及如何模擬算法的執(zhí)行過程。

2.2.1 圖結(jié)構(gòu)的定義

廬山場景的圖結(jié)構(gòu)包含了8個結(jié)點(diǎn)和13條邊(如圖2所示)，在Unity3D的C#腳本代碼中定義一個8×8的二維矩陣Graph[8][8]來表示結(jié)點(diǎn)之間的邊，即結(jié)點(diǎn)到結(jié)點(diǎn)之間的鄰接關(guān)系。行代表邊的起點(diǎn)，列代表邊的終點(diǎn)，行列對應(yīng)的值表示的是從起點(diǎn)到終點(diǎn)所經(jīng)過的邊的權(quán)值。

當(dāng)鄰接矩陣中Graph[i][j]=0時，表示的是終點(diǎn)和起點(diǎn)都是同一個點(diǎn)，需要排除；若Graph[i][j]=-1，表示2個結(jié)點(diǎn)之間無路可達(dá)。

2.2.2 邊的選取

在自動展示模式下程序通過控制虛擬角色在場景中的運(yùn)動，將結(jié)點(diǎn)與結(jié)點(diǎn)連接起來，以表示2個結(jié)點(diǎn)之間的邊被選擇。在用戶交互模式下，用戶點(diǎn)擊小地圖上的結(jié)點(diǎn)，在此過程中用戶要先點(diǎn)擊一個起始結(jié)點(diǎn)，然后再點(diǎn)擊選擇一個終止結(jié)點(diǎn)，表示選擇了對應(yīng)的邊(其中每一選擇步驟系統(tǒng)都會給予人性化高亮顯示提醒)，選擇完成后，系統(tǒng)將會根據(jù)用戶的選擇移動虛擬角色。

2.2.3 過程的存儲

對用戶交互過程的存儲是為了系統(tǒng)在判斷用戶操作過程的正確性的同時，還能找出首次出錯的位置。由于本系統(tǒng)中判斷程序是根據(jù)用戶當(dāng)前操作產(chǎn)生的結(jié)果并結(jié)合歷史步驟的單個迭代數(shù)據(jù)來判斷用戶目前操作的準(zhǔn)確性。若系統(tǒng)正在根據(jù)用戶操作實(shí)時判斷用戶某一步驟正確性，則代表用戶之前的每一步都是正確的，若出現(xiàn)錯誤，則系統(tǒng)會停止后續(xù)正確性判斷。

因此，對于用戶過程數(shù)據(jù)，只存儲判斷程序需要的數(shù)據(jù)，不存儲用戶過程中每一步驟的數(shù)據(jù)，但用戶每一次操作過程的文字描述會存儲在Unity中TipCanvasText的text中，并使用它在前端展示。根據(jù)不同圖算法定義了不同名稱或不同類型的變量，例如：Kruskal算法中定義的gradeSum變量，以存儲用戶已選邊權(quán)值的累計(jì)；Prim算法和Dijkstra算法中定義的newGrade，以存儲用戶當(dāng)前選擇的權(quán)值；DFS算法和BFS算法中定義的start與end,以記錄用戶當(dāng)前選擇的邊。

2.2.4 結(jié)果的存儲

在圖算法執(zhí)行完畢后，系統(tǒng)需要展示系統(tǒng)主動或用戶手動交互的結(jié)果，本系統(tǒng)代碼中定義一個8×8的二維矩陣ResultGraph[8][8]來表示生成的結(jié)果圖中結(jié)點(diǎn)之間的邊，即結(jié)點(diǎn)到結(jié)點(diǎn)之間的鄰接情況，并將所有值初始化為0,用戶或系統(tǒng)每次選擇后，會將二維矩陣中對應(yīng)的值修改為1，表示結(jié)果中增加了一條邊；在自動展示模式的程序中還定義了一個存儲選邊的route集合，存儲著系統(tǒng)選邊的結(jié)果。

2.3 虛擬仿真系統(tǒng)的實(shí)現(xiàn)和使用

本節(jié)介紹圖算法虛擬仿真系統(tǒng)的2種運(yùn)行模式和2個發(fā)布版本，并從用戶角度，給出使用系統(tǒng)的活動流程。

2.3.1 2種算法運(yùn)行模式

1.自動展示。

自動展示過程中，用戶可以修改各個邊的權(quán)值以觀察在不同組合的邊權(quán)值條件下對應(yīng)的算法執(zhí)行過程。如圖6所示，用戶可在左下角的小地圖的文本框內(nèi)修改邊權(quán)值。

圖6 邊權(quán)值修改

用戶通過以“上帝視角”觀察整個廬山地貌和景點(diǎn)，以及對應(yīng)算法對景點(diǎn)的連接過程，這個功能使抽象的算法執(zhí)行過程具體化、動態(tài)化。如圖7所示，系統(tǒng)實(shí)時地提供展示系統(tǒng)每一步控制的過程，并以文字顯示在左上角，方便用戶觀察。

圖7 自動展示過程

2.用戶交互。

本系統(tǒng)還提供一種由用戶互動性地手動控制方式，讓學(xué)生自己手動操作相應(yīng)算法的執(zhí)行過程，將每一步操作交由用戶自主完成。除了上述的自定義邊權(quán)值之外，還實(shí)現(xiàn)這些交互功能：

1)選擇邊功能。用戶通過在小地圖上點(diǎn)擊一個起始結(jié)點(diǎn)，和一個終止結(jié)點(diǎn)，選擇相應(yīng)的邊來控制實(shí)現(xiàn)算法的每一步。當(dāng)用戶選擇了某2個不存在邊的結(jié)點(diǎn)時，系統(tǒng)會給予提示，并讓用戶重新選擇。若用戶已經(jīng)選擇了某個起始結(jié)點(diǎn)可以再次點(diǎn)擊該結(jié)點(diǎn)以取消選擇。

2)主場景和分場景之間切換功能。當(dāng)用戶處于主場景時，可以點(diǎn)擊“進(jìn)入場景”按鈕進(jìn)入到某景點(diǎn)的分場景，隨后用戶可以點(diǎn)擊“退出場景”按鈕回到主場景。

3)角色移動。進(jìn)入某個景點(diǎn)的分場景之后，用戶可以通過鍵盤的“上”“下”“左”“右”或“W”“S”“A”“D”來控制虛擬角色的行走，并游覽景觀。

2.3.2 2種發(fā)布版本

本系統(tǒng)最終發(fā)布了2個版本：WebGL版和PC版。WebGL版可通過瀏覽網(wǎng)站https://nss.jxnu.edu.cn/VRExperiment/index.html，在網(wǎng)站首頁點(diǎn)擊“進(jìn)入無向圖算法虛擬仿真實(shí)驗(yàn)”進(jìn)行訪問，其運(yùn)行界面如圖8所示。PC版則需要用戶下載客戶端應(yīng)用程序。

圖8 WebGL運(yùn)行界面圖

2.3.3 用戶使用流程

基于廬山三維場景的圖虛擬仿真系統(tǒng)的運(yùn)行流程如圖9所示。

圖9 系統(tǒng)運(yùn)行流程圖

用戶進(jìn)入系統(tǒng)后點(diǎn)擊開始實(shí)驗(yàn)進(jìn)入到實(shí)驗(yàn)選擇環(huán)節(jié)，在此環(huán)節(jié)中，用戶可以直接選擇算法開始實(shí)驗(yàn)，也可以在邊對應(yīng)的文本框中寫入需要的值以修改圖中邊的權(quán)值，然后再選擇算法和起始結(jié)點(diǎn)開始實(shí)驗(yàn)。

若用戶進(jìn)入“自動展示”模式，算法執(zhí)行與運(yùn)動邏輯完全交由實(shí)驗(yàn)系統(tǒng)完成，用戶在該模式下觀看算法運(yùn)行的每一個步驟來理解算法的中間執(zhí)行過程，同時在系統(tǒng)的左上部分會根據(jù)系統(tǒng)算法控制的步驟實(shí)時給出過程記錄，方便用戶回顧之前的運(yùn)行步驟。

若用戶進(jìn)入“用戶交互”模式，虛擬角色和算法執(zhí)行過程將交由用戶控制。在開始實(shí)驗(yàn)后，用戶需要根據(jù)自己對相應(yīng)算法的思考在系統(tǒng)小地圖上選擇一個起始結(jié)點(diǎn)和一個終止結(jié)點(diǎn)，以表示虛擬角色從起始結(jié)點(diǎn)的位置運(yùn)動到終止結(jié)點(diǎn)的位置，同時2點(diǎn)之間的邊將被置為被選狀態(tài)。在任意時刻里，若箭頭位置在結(jié)點(diǎn)位置，用戶可以點(diǎn)擊進(jìn)入場景，在播放完一段切換動畫后，系統(tǒng)將進(jìn)入到結(jié)點(diǎn)名稱所表示的場景之中，用戶在場景中可以使用鍵盤上的方向鍵控制虛擬角色的移動，以游覽廬山景點(diǎn)中優(yōu)美壯觀的景色，在此過程中，用戶不僅可以學(xué)習(xí)相關(guān)算法，還可以游覽江西知名旅游景區(qū)，這也是學(xué)習(xí)加放松的完美結(jié)合。實(shí)驗(yàn)交互完畢后，系統(tǒng)界面將會顯示實(shí)驗(yàn)的執(zhí)行過程和用戶交互的判斷結(jié)果，若用戶的交互結(jié)果不符合對應(yīng)算法的規(guī)則,系統(tǒng)會給出錯誤發(fā)生的位置。在結(jié)果展示的整個過程中，用戶可以清晰了解到自己操作實(shí)驗(yàn)的步驟，了解自己在實(shí)驗(yàn)過程中出現(xiàn)的問題，并及時糾正錯誤。

3 理論問題和關(guān)鍵技術(shù)

本系統(tǒng)在開發(fā)過程中存在各類理論問題和技術(shù)難點(diǎn)，本章將詳細(xì)介紹這些問題的解決方案。

3.1 大小地圖映射

本系統(tǒng)是以在廬山三維場景景點(diǎn)為背景。主場景中各個結(jié)點(diǎn)之間沒有設(shè)置可見路徑以表示各個結(jié)點(diǎn)之間是否有邊連接，路徑的邊連接情況僅在小地圖中展示。在用戶交互模式下，使用相關(guān)圖的算法時，需要通過系統(tǒng)窗口右上角的小地圖來了解結(jié)點(diǎn)與結(jié)點(diǎn)之間的權(quán)值以及連接情況。同時，虛擬角色在主場景中的位置會對應(yīng)到小地圖上的箭頭，用戶可以參考箭頭在小地圖上的位置來確認(rèn)角色在場景中的位置。

問題描述如何將主場景中的景點(diǎn)位置與小地圖小圓點(diǎn)一一對應(yīng)？如何在主場景俯視視角下隱藏可見邊？

解決方案本系統(tǒng)利用Unity3D的Camera下的Culling Mask實(shí)現(xiàn)了全景圖與小地圖的映射。具體實(shí)現(xiàn)過程如下：

1)在項(xiàng)目文件中創(chuàng)建一個Texture，并在主場景中創(chuàng)建一個Camera，調(diào)整Camera的位置，使其能夠觀察到完整的場景。

2)為Camera設(shè)置Target Texture，即第一步創(chuàng)建的Texture。

3)在場景中每一個結(jié)點(diǎn)位置創(chuàng)建一個sprite，為其加上圓形遮罩，并在它上面創(chuàng)建3D Text來顯示結(jié)點(diǎn)名稱；每個相鄰邊之間的直線位置頂部都設(shè)置一個Quad；并為本步中創(chuàng)建的物體都設(shè)置Layer為waymap。調(diào)整所創(chuàng)建的新物體的位置，確保在攝像機(jī)中所展示的效果能與實(shí)際場景中的位置保持一致。

4)設(shè)置2個用戶Camera(對應(yīng)于用戶在主場景視角和用戶在分場景中的角色第一人稱視角)的Culling Mask屬性，取消選擇waymap，并設(shè)置第一步中創(chuàng)建的Camera的Culling Mask屬性，僅選擇waymap。使得用戶在系統(tǒng)主場景中不會看見新創(chuàng)建的物體，而小地圖僅顯示新創(chuàng)建的物體。

5)創(chuàng)建小地圖的Canvas，將其位置調(diào)整為界面右上角，并在Canvas中創(chuàng)建RowImage，將Texture設(shè)置為第一步創(chuàng)建的Texture，并調(diào)整RowImage的位置。

3.2 被選邊的高亮設(shè)置

對已被選的邊進(jìn)行高亮或者變色處理，有利于用戶清晰地獲得圖中生成的最小生成樹、最短路徑或遍歷路徑，使用戶更為透徹地了解算法的執(zhí)行過程。

問題描述當(dāng)在自動展示模式或用戶交互模式下，系統(tǒng)或用戶選定了某條邊后，系統(tǒng)是如何在場景模型中找到該條邊？如何對找到的邊進(jìn)行高亮處理的？

解決方案要實(shí)現(xiàn)這種效果，首先必須要能在hierarchy中找到小地圖上的路徑。對每條邊進(jìn)行規(guī)則性命名，即將相關(guān)邊的預(yù)制件放在2個結(jié)點(diǎn)中名稱值較小的結(jié)點(diǎn)模型下，邊命名中使用符號“-”連接2個結(jié)點(diǎn)的名字，且命名總是以左小右大的方式命名。在算法腳本每次從鄰接矩陣中找到下一條邊后，都可以先從更小值結(jié)點(diǎn)模型下，根據(jù)命名規(guī)則方式找到相應(yīng)的邊。

找到邊后就需要對該邊進(jìn)行處理，借助以邊更換Material材質(zhì)的方式為其改變顏色使得相應(yīng)的邊高亮顯示，這種方式與使用shader效果相當(dāng)，但更為節(jié)省系統(tǒng)資源。具體涉及的代碼如下：

int low=row>col?col:row;

int high=row>col?row:col;

string NowSucWayName=low+"-"+high;

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

用戶不會根據(jù)大小順序選擇結(jié)點(diǎn)，根據(jù)上述規(guī)則性命名的選邊原理，需要區(qū)分用戶選擇結(jié)點(diǎn)編號的大小順序，在代碼中定義一個low和high的變量分別獲取兩者較大編號與較小編號，然后根據(jù)規(guī)定的命名規(guī)則用“-”將他們拼接成邊模型的名稱形式保存在NowSucWayName變量中，然后根據(jù)NowSucWayName找到對應(yīng)模型,并為它更換材質(zhì)球。

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

由于在圖的各類算法中，經(jīng)常會出現(xiàn)執(zhí)行到某個結(jié)點(diǎn)后，無法繼續(xù)再從該結(jié)點(diǎn)繼續(xù)執(zhí)行下去，而需要從其它結(jié)點(diǎn)開始執(zhí)行的狀況。

問題描述在用戶交互模式下，需要讓用戶完全控制邊的選擇過程，這種操作是以何種形態(tài)為用戶提供合適的交互接口？

解決方案系統(tǒng)為用戶提供了一種簡潔的交互機(jī)制，即用戶先選擇邊的開始結(jié)點(diǎn)(點(diǎn)擊小地圖上圓點(diǎn)按鈕)，此時，系統(tǒng)將虛擬角色立即跳轉(zhuǎn)到起始結(jié)點(diǎn)的位置；之后，用戶再選擇邊的終止結(jié)點(diǎn)，如果選擇無誤系統(tǒng)將會調(diào)用運(yùn)動腳本并對對應(yīng)邊進(jìn)行著色和高亮顯示。

由于圖中某些部分可能不存在邊，且用戶操作存在失誤的情況，系統(tǒng)中提供如下檢查與判斷機(jī)制：

1)取消選擇。即當(dāng)用戶已經(jīng)選擇了一個起始結(jié)點(diǎn)A后，需要重新選擇另外一個起始結(jié)點(diǎn)B，系統(tǒng)提供對已選結(jié)點(diǎn)A再次點(diǎn)擊的方式取消上一次選擇。

2)邊不存在或重復(fù)選擇。即當(dāng)用戶已經(jīng)選擇起始結(jié)點(diǎn)和終止結(jié)點(diǎn)后，系統(tǒng)會立刻在后臺判斷是否存在對應(yīng)的邊，或者該邊是否已經(jīng)被選擇，若這種情況發(fā)生，系統(tǒng)將會取消用戶的本次操作，并給予用戶錯誤提示，提醒用戶重新選擇另一條邊，如圖10所示。

圖10 邊選擇錯誤提示

3.4 用戶交互模式下的結(jié)果正確性判定

問題描述有些圖算法的結(jié)果可能不是唯一的。由于計(jì)算機(jī)不具有人腦的靈活性，如何將用戶交互模式下的操作結(jié)果與圖算法的多結(jié)果進(jìn)行比對，并判定正確？

解決方案通過深入研究探討算法的原理以及結(jié)果的共性，系統(tǒng)采用以下方案解決，分別對5種算法進(jìn)行描述：

1)Prim算法。

由于該算法是從某個起點(diǎn)開始，無論下一條選的是哪一條邊，被選邊的權(quán)值一定都是確定的。因此本系統(tǒng)采用程序?qū)崟r跟蹤用戶的每一次選擇，在用戶做出選擇前，系統(tǒng)會提前計(jì)算得到下一次應(yīng)該被選的邊的權(quán)值，在用戶選擇結(jié)束后，只需要比對兩者結(jié)果，便可以判斷用戶本輪交互的正誤，并給出發(fā)生錯誤的步驟。

2)Kruskal算法。

該算法的每一步同樣具有共同特性，即其每一步選擇的邊的權(quán)值與先前的權(quán)值的累積是固定的，且考慮圖的權(quán)值可以交由用戶設(shè)定，因此系統(tǒng)中也將該部分的判斷設(shè)定為與Prim算法類似的實(shí)時跟蹤方式。

3)Dijkstra算法。

此算法判斷方式與Prim算法極為類似，只需在Prim算法實(shí)現(xiàn)的前提下完成。

4)DFS算法。

從第一個起點(diǎn)開始程序會在用戶每次選擇終止結(jié)點(diǎn)后，將終止結(jié)點(diǎn)進(jìn)棧，程序始終會保證棧頂所代表的結(jié)點(diǎn)有未被選擇的相鄰結(jié)點(diǎn)。在用戶每一步選擇后，程序判斷用戶的起點(diǎn)是否是從棧頂元素所代表的結(jié)點(diǎn)出發(fā)，并同時判斷終止結(jié)點(diǎn)是否被選擇。

5)BFS算法。

該實(shí)現(xiàn)過程較為復(fù)雜，簡單來說，即是后臺程序在用戶每一步選擇后，都會更新圖中每個結(jié)點(diǎn)的相對層次，程序始終可以保證用戶可正確交互結(jié)點(diǎn)的層次是正確的，系統(tǒng)只需根據(jù)后臺獲得的層次判斷用戶交互的正確性。

4 實(shí)例演示

Prim算法是圖中最小生成樹算法的一種，可在加權(quán)連通圖里搜索最小生成樹，由該算法所得的邊子集所構(gòu)成的樹中，包含了連通圖里的所有結(jié)點(diǎn)，且其邊集的權(quán)值之和亦為最小。本章從“用戶交互”和“自動展示”2個模式展示Prim算法的功能的實(shí)現(xiàn)和運(yùn)行過程．

1)自動展示模式。

點(diǎn)擊進(jìn)入虛擬仿真系統(tǒng)后進(jìn)入主界面，首先根據(jù)需要修改某些邊的權(quán)值，隨后依次點(diǎn)擊“Prim”算法和“三疊泉”起始結(jié)點(diǎn)，選擇“自動展示”開始實(shí)驗(yàn)。此時，在主場景中都能觀察到箭頭的運(yùn)動軌跡，虛擬角色首先從“三疊泉”結(jié)點(diǎn)出發(fā)，根據(jù)Prim算法策略，從與“三疊泉”相鄰的3條邊(權(quán)值為6、8、12)中選擇權(quán)值最小的邊，即“街心公園”作為目標(biāo)結(jié)點(diǎn)，系統(tǒng)控制虛擬角色從“三疊泉”向“街心公園”移動。當(dāng)?shù)竭_(dá)“街心公園”后，系統(tǒng)將繼續(xù)根據(jù)Prim算法策略挑選下一對結(jié)點(diǎn)，以相同的方式向目標(biāo)結(jié)點(diǎn)移動，其后續(xù)過程如圖11所示。系統(tǒng)自動展示停止后給出完整的執(zhí)行結(jié)果。

圖11 自動展示模式執(zhí)行結(jié)果

2)用戶交互模式。

與自動展示模式類似，用戶交互模式先根據(jù)需要修改邊的權(quán)值，然后依次點(diǎn)擊算法和“三疊泉”起始結(jié)點(diǎn)，選擇“用戶交互”開始實(shí)驗(yàn)。用戶需要根據(jù)Prim算法策略自主選擇邊，用戶通過點(diǎn)擊小地圖上的起始結(jié)點(diǎn)和終止結(jié)點(diǎn)選擇一條邊，選中邊對應(yīng)的路徑會以高亮在小地圖上顯示，與此同時主場景中心位置2個景點(diǎn)之間也會出現(xiàn)該條路徑。在用戶交互模式下，用戶依次選取其它邊。當(dāng)所有結(jié)點(diǎn)都連通，交互式實(shí)驗(yàn)結(jié)束，左上角顯示用戶的實(shí)驗(yàn)過程。如果用戶的實(shí)驗(yàn)流程有誤，在左上角提示中顯示實(shí)驗(yàn)結(jié)果錯誤，同時還給出了錯誤的步驟，如圖12所示。在用戶交互模式下，可以在主場景和8個景點(diǎn)分場景中進(jìn)行切換。如圖13所示，虛擬角色現(xiàn)在的位置是“天池塔”，用戶可以點(diǎn)擊“進(jìn)入場景”按鈕，進(jìn)入到“天池塔”三維場景中，可以通過鍵盤控制虛擬角色移動。

圖12 用戶交互模式實(shí)驗(yàn)結(jié)果

圖13 進(jìn)入分場景

5 結(jié)束語

本文從教學(xué)和虛擬現(xiàn)實(shí)2個維度開展研究和討論，通過搭建的廬山三維場景來模擬圖結(jié)構(gòu)，利用Unity3D引擎設(shè)計(jì)并實(shí)現(xiàn)了圖算法虛擬仿真系統(tǒng)，并圍繞著該虛擬仿真系統(tǒng)的理論問題和關(guān)鍵技術(shù)進(jìn)行研究和探討。本虛擬仿真系統(tǒng)的特點(diǎn)概述如下：

1)系統(tǒng)將圖的結(jié)構(gòu)和算法的執(zhí)行過程以具象化、可交互的游戲形式呈現(xiàn)給用戶，并調(diào)動學(xué)生學(xué)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)的積極性，使其更有動力和信心對算法的分析和應(yīng)用進(jìn)行更深入學(xué)習(xí)和探索。

2)系統(tǒng)提供了自動演示和用戶交互2種模式，使學(xué)生擺脫抽象枯燥的傳統(tǒng)理論講授方式，讓學(xué)生以交互方式參與實(shí)驗(yàn)，見證和控制算法執(zhí)行過程，進(jìn)而到達(dá)“知其然也知其所以然”的目標(biāo)。

3)系統(tǒng)操作簡單易懂，情景切合現(xiàn)實(shí)，可以作為算法與數(shù)據(jù)結(jié)構(gòu)教學(xué)的一種新方法。

本文所研發(fā)的系統(tǒng)融合游戲化的特征，貫徹“寓學(xué)于樂”的教育理念，提高學(xué)生學(xué)習(xí)的內(nèi)在動機(jī)[24]。目前系統(tǒng)仍然在升級與維護(hù)中，已經(jīng)搭建還原了江西廬山的8個場景，但場景模型還有完善空間，UI也有待優(yōu)化。后期，還將引入分布式虛擬現(xiàn)實(shí)技術(shù)，使得不同的人可以在世界各地通過網(wǎng)絡(luò)進(jìn)入圖虛擬仿真系統(tǒng)的同一個三維場景，虛擬角色既可以獨(dú)立執(zhí)行算法，又可以實(shí)現(xiàn)多角色的協(xié)同工作。