三維迷宮的設(shè)計(jì)與建模

王 康，吳文明，劉利剛

(中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 安徽 合肥 230026)

三維迷宮的設(shè)計(jì)與建模

王 康，吳文明，劉利剛*

(中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 安徽 合肥 230026)

三維迷宮在難度和趣味性上達(dá)到了一個(gè)更高的水平.通過(guò)改進(jìn)二維迷宮的生成算法，提出了循環(huán)迷宮的概念和迷宮復(fù)雜度公式.進(jìn)而，提出一種基于四邊形網(wǎng)格曲面的三維迷宮設(shè)計(jì)算法.該算法分3個(gè)步驟：首先，將給定的三維曲面四邊形網(wǎng)格化；再確定迷宮的起點(diǎn)和終點(diǎn)，采用基于生成樹(shù)的二維迷宮生成算法，在網(wǎng)格表面生成迷宮路徑；最后，將迷宮實(shí)體化為三維結(jié)構(gòu)，并與原始三維模型做布爾運(yùn)算，得到三維迷宮.通過(guò)3D打印機(jī)制造出個(gè)性化的三維迷宮玩具，大大增強(qiáng)了迷宮的趣味性，改善了用戶(hù)體驗(yàn).

三維迷宮；建模；生成樹(shù)；復(fù)雜度；三維打印

0 引 言

迷宮是一種古老的意象，在古代是完整的象征[1].迷宮建筑因其神秘性而令無(wú)數(shù)愛(ài)好者著迷；迷宮游戲亦因其趣味性強(qiáng)而廣受大眾喜愛(ài)；作為一種兒童學(xué)前教育的益智玩具，迷宮玩具備受家長(zhǎng)青睞.迷宮的相關(guān)研究與設(shè)計(jì)已取得了一些成果[2-5]，該領(lǐng)域具有廣闊的市場(chǎng)前景.

PHILLIPS[6]研究了羅馬馬賽克式迷宮拓?fù)?，提出一套用于破損迷宮重建和保存的迷宮重建理論.MCCLENDON[7]提出了一種計(jì)算曲線迷宮復(fù)雜度的方法：在迷宮的路徑曲線上定義連續(xù)函數(shù)，考慮路徑長(zhǎng)度、極值點(diǎn)等因素對(duì)復(fù)雜度的影響，利用連續(xù)化方法提出了曲線迷宮復(fù)雜度的計(jì)算公式.在迷宮設(shè)計(jì)方面，XU等[8]提出了一種帶有漩渦結(jié)構(gòu)的復(fù)雜迷宮生成算法，后又提出基于圖像的迷宮算法[9]，即通過(guò)擴(kuò)展傳統(tǒng)的迷宮生成算法建立適應(yīng)圖像風(fēng)格的迷宮.

將迷宮由二維空間推廣到三維空間，增加了迷宮的難度，同時(shí)也令其更具挑戰(zhàn)性、趣味性與可玩性，對(duì)玩家空間能力的培養(yǎng)大有裨益.雖然出現(xiàn)過(guò)一些三維迷宮的設(shè)計(jì)方案，但難以實(shí)現(xiàn)批量生產(chǎn)，也尚未出現(xiàn)相關(guān)的設(shè)計(jì)軟件.一方面，設(shè)計(jì)者要在三維空間中構(gòu)思迷宮的結(jié)構(gòu)，設(shè)計(jì)難度遠(yuǎn)遠(yuǎn)高于二維迷宮；另一方面，三維的設(shè)計(jì)也加大了迷宮游戲的難度，復(fù)雜的三維結(jié)構(gòu)超出玩家的能力范圍.

二維迷宮設(shè)計(jì)簡(jiǎn)單，而趣味性低；三維迷宮設(shè)計(jì)復(fù)雜，但操作性強(qiáng).自然的想法是結(jié)合二維迷宮與三維結(jié)構(gòu)得到三維迷宮.如圖1所示，通過(guò)將二維迷宮(a)嵌入到三維模型(b)表面，得到一個(gè)實(shí)體的三維迷宮(c).這樣的三維迷宮設(shè)計(jì)雖然簡(jiǎn)單，但具有很高的操作性和趣味性，主要需考慮以下問(wèn)題：(1)二維迷宮的約束條件，即二維迷宮滿(mǎn)足怎樣的條件才能設(shè)計(jì)成三維迷宮；(2)二維迷宮的生成算法，即如何在一般曲面上生成二維迷宮；(3)三維迷宮的生成算法，即如何將二維迷宮與三維模型合成得到三維迷宮.

圖1 三維迷宮的設(shè)計(jì)思路Fig.1 The design idea of 3D maze

本文提出一種三維迷宮設(shè)計(jì)與建模方法.結(jié)合二維迷宮生成和3D建模技術(shù)，將二維迷宮嵌入三維模型表面，得到三維迷宮.三維迷宮的設(shè)計(jì)有更多約束條件，如循環(huán)迷宮；出于用戶(hù)交互的需求，應(yīng)該為用戶(hù)提供迷宮路徑可控的生成算法，即定制迷宮；考慮生成迷宮的有效性，需要量化迷宮的復(fù)雜度，等等.

1 二維迷宮的設(shè)計(jì)

1.1 迷宮的表示及約束

如圖2所示，用二維數(shù)組表示二維迷宮.二維數(shù)組中的元素為0或1，0表示路徑，1表示墻壁.從入口到出口之間的最短路徑稱(chēng)為迷宮的主路徑.二維迷宮需要滿(mǎn)足以下約束條件才能設(shè)計(jì)成三維迷宮：

圖2 用二維數(shù)組表示迷宮Fig.2 A maze represented by 2D array

(1)二維迷宮有且僅有一條主路徑；

(2)路徑之間必須有墻壁阻隔；

(3)路徑中任意2個(gè)頂點(diǎn)之間連通；

(4)路徑之間不能形成回路.

如圖3所示，(a)中2條縱向路徑并列在一起，不滿(mǎn)足路徑約束條件(2)；(b)中路徑之間形成回路，不滿(mǎn)足路徑約束條件(4).

圖3 無(wú)法設(shè)計(jì)為三維迷宮的二維迷宮Fig.3 The 2D maze which can’t be designed as 3D maze

1.2 二維迷宮的生成

二維迷宮的生成可以通過(guò)生成樹(shù)算法實(shí)現(xiàn).從圖論的觀點(diǎn)看，迷宮可作某個(gè)圖的生成樹(shù)，反之，圖的生成樹(shù)也可表示為一個(gè)迷宮，如圖4所示.袁開(kāi)等[10]基于最小生成樹(shù)的Kruskal算法，用圖的連通子圖生成迷宮.田翠花等[11]采用圖的深度優(yōu)先遍歷生成規(guī)則的隨機(jī)迷宮.這些算法大同小異，主要步驟如下：

(1)初始化二維數(shù)組maze[m][n]；

(2)將二維數(shù)組maze[m][n]轉(zhuǎn)化成圖；

(3)基于某種生成樹(shù)算法生成迷宮；

(4)導(dǎo)出隨機(jī)迷宮.但存在以下問(wèn)題：(1)算法對(duì)圖進(jìn)行盲目搜索，生成迷宮的路徑是完全隨機(jī)的.(2)算法同時(shí)生成迷宮的主路徑和支路，不能定制迷宮.(3)生成的迷宮路徑局限在矩形區(qū)域，兩側(cè)不連通，迷宮是不可循環(huán)的.

圖4 迷宮與生成樹(shù)等價(jià)Fig.4 A maze is equivalent to a spanning tree

筆者希望系統(tǒng)既能生成隨機(jī)迷宮，也能定制迷宮，或者定制和隨機(jī)2種形式相互混合.由于傳統(tǒng)算法不能滿(mǎn)足此要求，于是提出了一種新的迷宮算法，將主路徑和支路的生成過(guò)程分為2個(gè)獨(dú)立的階段.

第1步 生成由指定起點(diǎn)到指定終點(diǎn)的迷宮主路徑.這里提出2種生成迷宮主路徑的方式：第1種通過(guò)用戶(hù)交互給出主路徑，此方式簡(jiǎn)單直接，亦能滿(mǎn)足用戶(hù)定制的需求.第2種基于生成樹(shù)算法生成主路徑，此方式能產(chǎn)生隨機(jī)主路徑.借鑒深度優(yōu)先遍歷算法[12]，用“窮舉求解”的思路：由指定起點(diǎn)開(kāi)始隨機(jī)搜索，如果走得通，則繼續(xù)搜索；否則沿原路后退一步或者多步，重新選擇其他路徑，至找到指定終點(diǎn)為止.

如果當(dāng)前位置某個(gè)方向上的點(diǎn)及其四周的點(diǎn)都未被訪問(wèn)過(guò)，說(shuō)明該方向走得通.如圖5所示，黃色的點(diǎn)為當(dāng)前位置，紅色箭頭表示選擇右側(cè)為考察方向.為保證生成的迷宮是規(guī)則整齊的，在實(shí)際操作中均以2步為一個(gè)操作單位.于是考察紅色標(biāo)記的位置，若四周(圓圈標(biāo)記)的位置都未被訪問(wèn)過(guò)，則表示該方向走得通.

圖5 方向選擇Fig.5 The choice of the direction

當(dāng)所有方向都走不通時(shí)，就從路徑中刪除該位置并后退到前一位置，重新選擇路徑方向.如圖6所示，(a)圖中當(dāng)前位置(黃色標(biāo)記)的四周都走不通，此時(shí)后退到上一位置，(b)圖中當(dāng)前位置，然后再由此位置開(kāi)始，選擇其他路徑重新搜索，至找到指定終點(diǎn)為止.

圖6 回溯Fig.6 Backtrack

第2步 基于迷宮的主路徑生成迷宮的支路.算法流程是依次考察主路徑上的每個(gè)點(diǎn)，由該點(diǎn)開(kāi)始隨機(jī)搜索生成支路，其搜索不同于主路徑，當(dāng)四周都走不通時(shí)直接不再回溯停止搜索，繼續(xù)考察下一個(gè)點(diǎn)，如圖7所示：迷宮的主路徑在圖中用紅色標(biāo)記，沿著主路徑逐點(diǎn)生成迷宮的支路.在實(shí)際操作中，每次間隔1個(gè)點(diǎn)生成迷宮的支路，這樣可保證生成的迷宮路徑規(guī)整.當(dāng)前考察位置用黃色標(biāo)記，由此位置開(kāi)始隨機(jī)搜索，當(dāng)四周都走不通時(shí)停止搜索.這樣搜索過(guò)的路徑就構(gòu)成一條支路，在圖中用綠色標(biāo)記.接著間隔一個(gè)位置繼續(xù)考察下一個(gè).依此類(lèi)推，可以在生成的支路上繼續(xù)生成支路，進(jìn)一步完善迷宮至不能再生成支路為止.

圖7 支路的生成Fig.7 The generation of the branch

1.3 循環(huán)迷宮

循環(huán)迷宮指沒(méi)有邊界的迷宮.將平面迷宮映射到三維曲面時(shí)，平面迷宮因三維曲面結(jié)構(gòu)而發(fā)生拓?fù)涞木植扛淖?，使得迷宮路徑可循環(huán).循環(huán)迷宮可實(shí)現(xiàn)邊界間“無(wú)縫”拼接.圖8為非循環(huán)與循環(huán)迷宮圖.

圖8 非循環(huán)迷宮與循環(huán)迷宮Fig.8 Non-loop maze and loop maze

本文方法可以實(shí)現(xiàn)循環(huán)迷宮.如圖9所示，P在左側(cè)邊界上(黃色標(biāo)記)，與P相鄰的點(diǎn)為

{PU，PD，PR},

P的左側(cè)沒(méi)有點(diǎn)，因此，由P無(wú)法直接訪問(wèn)迷宮的右側(cè).解決辦法是在迷宮的邊界處重新定義邊界的拓?fù)?重新定義P的相鄰點(diǎn)為

{PU，PD，PR，PL},

其中,PL是迷宮的左側(cè)邊界點(diǎn).這樣，在P處，就可以自由訪問(wèn)4個(gè)方向的點(diǎn).對(duì)二維迷宮的所有邊界都重新定義類(lèi)似拓?fù)洌苯訉⑦@種拓?fù)潢P(guān)系應(yīng)用于迷宮的生成，則可設(shè)計(jì)出循環(huán)迷宮.

圖9 循環(huán)迷宮的實(shí)現(xiàn)Fig.9 The implement of the loop maze

1.4 迷宮的復(fù)雜度

保證迷宮的有效性是檢驗(yàn)迷宮設(shè)計(jì)質(zhì)量的標(biāo)準(zhǔn)之一，控制復(fù)雜度是保證迷宮設(shè)計(jì)有效性的良好方法.因此，有必要引入迷宮的復(fù)雜度來(lái)指導(dǎo)迷宮設(shè)計(jì).MCCLENDON[7]提出了一種計(jì)算迷宮復(fù)雜度的方法，但所討論的迷宮是一類(lèi)曲線迷宮，計(jì)算比較復(fù)雜.考慮到矩形迷宮自身離散的特點(diǎn)，借鑒MCCLENDON的方法，本文提出一種計(jì)算矩形迷宮復(fù)雜度的離散化方法.

當(dāng)迷宮中沒(méi)有支路時(shí)，則認(rèn)為迷宮復(fù)雜度為0.一般來(lái)說(shuō)，支路越多，支路的深度越深，迷宮就越復(fù)雜.引起支路路徑方向改變的點(diǎn)稱(chēng)為支路的拐點(diǎn)，拐點(diǎn)的數(shù)量在一定程度上反映了迷宮的復(fù)雜程度.綜上所述，支路的數(shù)目、長(zhǎng)度，支路上的拐點(diǎn)數(shù)都是影響迷宮復(fù)雜度的因素，如圖10所示.

圖10 影響迷宮復(fù)雜度的因素Fig.10 The influence factors of the maze complexity

設(shè)B是基于迷宮主路徑生成的某條支路，稱(chēng)為一階支路，在一階支路上可以生成高階支路.設(shè)B上的支路數(shù)為n.設(shè)Li是i階支路的長(zhǎng)度，

{Ci,1,Ci,2,Ci,3,…,Ci,j}

表示i階支路的拐點(diǎn)集合，其中i=1,2,…，n.顯然，隨著支路階數(shù)的增加，迷宮的復(fù)雜度也增大.根據(jù)用戶(hù)習(xí)慣，定義迷宮支路B的復(fù)雜度為

對(duì)于給定的迷宮，特別是存在高階支路的迷宮，支路的劃分不唯一.例如圖10中的支路存在2種劃分，見(jiàn)圖11.于是定義：

Branchmax(B)=Max{Branch(B)|B的所有劃分},

Branchmin(B)=Min{Branch(B)|B的所有劃分},

平均復(fù)雜度Branchave(B)能更好地反映迷宮支路的復(fù)雜情況.簡(jiǎn)單計(jì)算圖11中支路的3種復(fù)雜度.(a)圖對(duì)應(yīng)的是最大復(fù)雜度：

(b)圖對(duì)應(yīng)的是最小復(fù)雜度：

于是平均復(fù)雜度為

圖11 支路的不同劃分Fig.11 Different division of the branch

設(shè){B1,B2,B3,…，Bn}表示迷宮主路徑上的n條一階支路，迷宮的復(fù)雜度定義為所有支路的復(fù)雜度之和.因此，迷宮的復(fù)雜度為

2 三維迷宮的設(shè)計(jì)

2.1 算法概述

三維模型最常見(jiàn)的表示方式是網(wǎng)格，網(wǎng)格所表達(dá)的三維模型具有點(diǎn)、線、面等基本的數(shù)據(jù)結(jié)構(gòu).三維模型的網(wǎng)格具有圖的特征，可以看作三維空間中的圖.因此，通過(guò)圖導(dǎo)出生成樹(shù)，就能在三維模型對(duì)應(yīng)的網(wǎng)格上生成迷宮.

對(duì)于給定的三維模型，三維迷宮的設(shè)計(jì)算法如圖12所示.二維迷宮實(shí)體化即將迷宮由二維結(jié)構(gòu)轉(zhuǎn)化為三維結(jié)構(gòu)，如圖13(b)所示，其目的是將二維迷宮通過(guò)三維模型合成三維迷宮.通過(guò)迷宮與三維模型之間的布爾差運(yùn)算實(shí)現(xiàn)三維迷宮的合成.布爾差運(yùn)算實(shí)際上就是從原始三維模型中減去二維迷宮，得到三維迷宮，如圖13(c)所示.

圖12 三維迷宮設(shè)計(jì)流程Fig.12 The pipeline design of 3D maze

圖13 三維迷宮設(shè)計(jì)Fig.13 The design of 3D maze

2.2 四邊形網(wǎng)格化

網(wǎng)格是表示三維模型最簡(jiǎn)單、最有效的方式，網(wǎng)格化也是三維模型研究的基礎(chǔ).針對(duì)不同的問(wèn)題需選擇不同的網(wǎng)格化方式.本文選擇三維模型的四邊形網(wǎng)格化，如圖14所示，主要基于以下考慮：

(1)高質(zhì)量的四邊形網(wǎng)格相對(duì)于自由度相同的三角形網(wǎng)格，具有更精確的解和較好的收斂性;

(2)四邊形網(wǎng)格更符合二維迷宮的特征，因此生成的二維迷宮也具有較好的外觀.

圖14 三維模型的四邊形網(wǎng)格Fig.14 The quadrilateral mesh of the 3D model

20世紀(jì)80年代，四邊形網(wǎng)格化成為研究的熱點(diǎn).根據(jù)生成原理，四邊形網(wǎng)格化大致可分為直接法和間接法.直接法是在給定的幾何區(qū)域上直接生成四邊形網(wǎng)格；間接法就是將三角網(wǎng)格轉(zhuǎn)化為四邊形網(wǎng)格.即將1個(gè)四邊形沿對(duì)角線分成2個(gè)三角形.因此四邊形網(wǎng)格可看作特殊的三角網(wǎng)格,反之不成立.通過(guò)移除三角網(wǎng)格之間的對(duì)角線，將2個(gè)三角形變成一個(gè)四邊形，可得到一個(gè)既有三角形網(wǎng)格又有四邊形網(wǎng)格的混合網(wǎng)格.

2.3 基于四邊形網(wǎng)格的三維迷宮設(shè)計(jì)

四邊形網(wǎng)格的結(jié)構(gòu)為迷宮的生成提供了便利.首先，獲取四邊形網(wǎng)格中所有頂點(diǎn)的領(lǐng)域信息.除邊界外，四邊形網(wǎng)格頂點(diǎn)的鄰接點(diǎn)數(shù)都為4.為簡(jiǎn)便，本文僅考慮在四邊形網(wǎng)格內(nèi)部生成迷宮，即頂點(diǎn)的鄰接點(diǎn)個(gè)數(shù)都為4.

然后，指定迷宮的起點(diǎn)和終點(diǎn)，采用基于生成樹(shù)的二維迷宮生成算法，在四邊形網(wǎng)格表面生成二維迷宮，如圖15所示.其中，(a)表示在四邊形網(wǎng)格上選取2點(diǎn)作為起點(diǎn)和終點(diǎn)；(b)表示隨機(jī)生成連接起點(diǎn)和終點(diǎn)的一條主路徑；(c)表示在主路徑基礎(chǔ)上生成迷宮的其他支路；(d)表示不斷重復(fù)此過(guò)程最終得到完整的迷宮.算法的具體過(guò)程已在前文詳述，不再重復(fù).

圖15 基于四邊形網(wǎng)格的三維迷宮設(shè)計(jì)Fig.15 The design of 3D maze based on the quadrilateral mesh

為建立三維迷宮，需將二維迷宮實(shí)體化.這里實(shí)體化指用圓柱替代迷宮中的路徑.圓柱需滿(mǎn)足以下條件：

(1)高度等于兩頂點(diǎn)之間的距離；

(2)上下2個(gè)底面分別以相鄰2個(gè)頂點(diǎn)為圓心；

(3)圓柱之間按照頂點(diǎn)順序依次連接.

最后，將實(shí)體化的迷宮與原始的三維模型做布爾差運(yùn)算，得到基于三維結(jié)構(gòu)的三維迷宮模型.

3 結(jié) 果

圖16顯示了3種設(shè)計(jì)風(fēng)格的二維迷宮.隨機(jī)迷宮通過(guò)傳統(tǒng)迷宮算法實(shí)現(xiàn)，循環(huán)迷宮通過(guò)本文提出的迷宮生成算法實(shí)現(xiàn)，定制迷宮是系統(tǒng)結(jié)合用戶(hù)交互生成，用戶(hù)可以自行設(shè)計(jì)迷宮的主路徑，支路部分由系統(tǒng)隨機(jī)生成.通過(guò)對(duì)比可以看出，定制迷宮能夠產(chǎn)生較好的路徑形狀，循環(huán)迷宮左右兩側(cè)可相互連通.

圖16 3種風(fēng)格的二維迷宮Fig.16 Three kinds of 2D mazes

圖17展示了3種復(fù)雜度的二維迷宮，根據(jù)復(fù)雜度公式，(a)圖的復(fù)雜度為0，(b)圖的為25.2，(c)圖的為33.5.

OpenSCAD是一款編程式建模工具，可以方便地生成三維模型，本文使用該工具生成迷宮模型.3D打印作為一種個(gè)性化定制的制造工具，制造三維模型非常方便.本文使用FDM 3D打印機(jī)制造了基于圓柱面的迷宮盒，包括迷宮芯和障礙殼兩部分，障礙殼中有一個(gè)小球，恰好可沿著迷宮芯中的凹槽滑動(dòng)，玩家通過(guò)旋轉(zhuǎn)和前后運(yùn)動(dòng)可將迷宮芯和障礙殼分離和合并.

圖17 不同復(fù)雜度的二維迷宮Fig.17 2D mazes with different complexities

圖18(a)是生成的迷宮芯和障礙殼的三維模型，圖18(b)是3D打印的迷宮盒實(shí)物.筆者還設(shè)計(jì)了基于球面的三維迷宮，如圖18(c)和(d)所示.圖19展示了將障礙殼與迷宮盒分離的操作過(guò)程，可以看出三維迷宮具有良好的可操作性和趣味性.本文算法可直接應(yīng)用于任意網(wǎng)格曲面，設(shè)計(jì)曲面造型趣味十足的三維迷宮，如圖20所示.

圖18 三維迷宮模型及其實(shí)物Fig.18 3D maze models and material objects

圖19 迷宮盒操作Fig.19 Operations of 3D maze box

圖20 任意曲面的三維迷宮Fig.20 3D mazes of arbitrary surfaces

4 結(jié) 論

結(jié)合二維迷宮設(shè)計(jì)與三維模型結(jié)構(gòu)，提出了一種三維迷宮設(shè)計(jì)與建模方法，設(shè)計(jì)了一種基于立體結(jié)構(gòu)的三維迷宮.作為玩具，三維迷宮在平面迷宮的基礎(chǔ)上增加了難度，同時(shí)也賦予迷宮更多的可操作性，從而大大增強(qiáng)了迷宮游戲的趣味性與可玩性.

首先，改進(jìn)了基于生成樹(shù)的傳統(tǒng)迷宮生成算法.將迷宮的生成分為先主路徑、后支路2個(gè)過(guò)程，為設(shè)計(jì)隨機(jī)迷宮、循環(huán)迷宮及定制迷宮等不同風(fēng)格的二維迷宮提供了便利.然后，基于生成的二維迷宮，嘗試?yán)脠A柱體和球體設(shè)計(jì)三維迷宮，通過(guò)OpenSCAD建模軟件設(shè)計(jì)了基于圓柱造型、球造型的三維迷宮，并用FDM 3D打印機(jī)打印了成品.最后，將三維迷宮推廣到一般曲面，經(jīng)四邊形網(wǎng)格化、網(wǎng)格表面設(shè)計(jì)二維迷宮、求布爾差等步驟，成功實(shí)現(xiàn)了一般曲面上的三維迷宮設(shè)計(jì).

本文算法還有待進(jìn)一步改進(jìn).首先，只能定制主路徑迷宮，尚無(wú)法實(shí)現(xiàn)迷宮的完整定制.其次，在一般曲面上設(shè)計(jì)的三維迷宮的質(zhì)量依賴(lài)于四邊形網(wǎng)格化算法的質(zhì)量.

[1] 余洋，張伶伶，楊曉軍.“迷宮”——景觀的神秘體驗(yàn)[J].華中建筑，2010(2):29-31. YU Y, ZHANG L L, YANG X J. “Labyrinth”: The landscape mystical experience [J]. Huazhong Architecture,2010(2):29-31.

[2] CHENG T K, XIANG L M, LYN T Y, et al. To?: journey or destination?[C]//Proceedings of the 12th International Conference on Advances in Computer Entertainment Technology. New York： ACM,2015:37.

[3] WANG D, ZHANG C, WANG H. T-maze: A tangible programming tool for children[C]//Proceedings of the 10th International Conference on Interaction Design and Children. Now York：ACM,2011:127-135.

[4] LLOTET J, KIRTON T. The maze EV: A two player installation game[C]//Proceedings of the 8th International Conference on Advances in Computer Entertainment Technology. New York：ACM,2011:1-2.

[5] HUANG T W, WU P C, WONG M D F. UI-route: An ultra-fast incremental maze routing algorithm[C]//Proceedings of SLIP (System Level Interconnect Prediction) on System Level Interconnect Prediction Workshop. New York： ACM,2014:1-8.

[6] PHILLIPS A. The topology of Roman mosaic mazes [J]. Leonardo,1993,25(3/4):65-73.

[7] MCCLENDON M S. The complexity and difficulty of a maze[C]//Bridges: Mathematical Connections in Art, Music, and Science. Bridges Conference,2001:213-222. http//archive.bridges mathart.org/2001/bridges2001-213pdf.

[8] XU J, KAPLAN C S. Vortex maze construction [J]. Journal of Mathematics and the Arts,2007,1(1):7-20.

[9] XU J, KAPLAN C S. Image-guided maze construction[J]. ACM Transactions on Graphics,2007,26(3):Article No.29.

[10] 袁開(kāi)，友楊勇.平面迷宮地圖隨機(jī)生成樹(shù)算法設(shè)計(jì)與實(shí)現(xiàn)[J].科學(xué)咨詢(xún)，2013(1):138-139. YUAN K, YOU Y Y. Plane random tree algorithm design and implementation of maze map [J]. Scientific Consult,2013(1):138-139.

[11] 田翠花，許衛(wèi)平，陳玉明.深度優(yōu)先遍歷算法、隨機(jī)布點(diǎn)法及回溯法在迷宮游戲中的應(yīng)用[J].河北北方學(xué)院學(xué)報(bào)，2013,29(3):19-24. TIAN C H, XU W P, CHEN Y M. Application of depth-first traversal, randomly distributed point algorithm and backtracking method to maze game [J]. Journal of Hebei North University: Natural Science Edition,2013,29(3):19-24.

[12] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京：清華大學(xué)出版社，2007. YAN W M, WU W M. Data Structure (C Language Version) [M]. Beijing: Tsinghua University Press,2007.

WANG Kang, WU Wenming, LIU Ligang

(SchoolofMathematicalSciences,UniversityofScienceandTechnologyofChina,Hefei230026,China)

3D maze has reached a high level in terms of complexity and fun. By improving the algorithm of generating a 2D maze, we propose the concept of loop maze and the complexity formula of the maze. Then, an algorithm for designing a 3D maze is presented based on the quadrilateral mesh surface. This approach mainly consists of three steps: Firstly, the quadrilateral mesh is generated on the given 3D surface; Secondly, the start point and end point of the maze are chosen alternatively, and the maze on the quadrilateral mesh surface is obtained by the algorithm of generating a 2D maze which is based on a spanning tree algorithm; At last, the maze is turned into 3D structure, and 3D maze is generated by Boolean operation between the 3D structure and the original 3D model. Several personalized 3D maze toys are produced by 3D printer, which consumedly enhances fun and user experience.

3D maze; modeling; spanning tree; complexity; 3D printing

2016-07-05.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61222206，11526212)；中科院“百人”計(jì)劃項(xiàng)目.

王 康(1991-)，ORCID:http://orcid.org/0000-0002-6667-3131,男,碩士研究生，主要從事3D打印研究.

*通信作者，ORCID:http://orcid.org/0000-0002-2118-3016,E-mail：ligang.liu@gmail.com.

10.3785/j.issn.1008-9497.2017.02.001

TP 391

A

1008-9497(2017)02-127-07

3D maze design and modeling.Journal of Zhejiang University(Science Edition), 2017,44(2):127-133