三維迷宮的設計與建模

王 康，吳文明，劉利剛

(中國科學技術大學 數學科學學院， 安徽 合肥 230026)

三維迷宮的設計與建模

王 康，吳文明，劉利剛*

(中國科學技術大學 數學科學學院， 安徽 合肥 230026)

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

三維迷宮；建模；生成樹；復雜度；三維打印

0 引 言

迷宮是一種古老的意象，在古代是完整的象征[1].迷宮建筑因其神秘性而令無數愛好者著迷；迷宮游戲亦因其趣味性強而廣受大眾喜愛；作為一種兒童學前教育的益智玩具，迷宮玩具備受家長青睞.迷宮的相關研究與設計已取得了一些成果[2-5]，該領域具有廣闊的市場前景.

PHILLIPS[6]研究了羅馬馬賽克式迷宮拓撲，提出一套用于破損迷宮重建和保存的迷宮重建理論.MCCLENDON[7]提出了一種計算曲線迷宮復雜度的方法：在迷宮的路徑曲線上定義連續函數，考慮路徑長度、極值點等因素對復雜度的影響，利用連續化方法提出了曲線迷宮復雜度的計算公式.在迷宮設計方面，XU等[8]提出了一種帶有漩渦結構的復雜迷宮生成算法，后又提出基于圖像的迷宮算法[9]，即通過擴展傳統的迷宮生成算法建立適應圖像風格的迷宮.

將迷宮由二維空間推廣到三維空間，增加了迷宮的難度，同時也令其更具挑戰性、趣味性與可玩性，對玩家空間能力的培養大有裨益.雖然出現過一些三維迷宮的設計方案，但難以實現批量生產，也尚未出現相關的設計軟件.一方面，設計者要在三維空間中構思迷宮的結構，設計難度遠遠高于二維迷宮；另一方面，三維的設計也加大了迷宮游戲的難度，復雜的三維結構超出玩家的能力范圍.

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

圖1 三維迷宮的設計思路Fig.1 The design idea of 3D maze

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

1 二維迷宮的設計

1.1 迷宮的表示及約束

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

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

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

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

(3)路徑中任意2個頂點之間連通；

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

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

圖3 無法設計為三維迷宮的二維迷宮Fig.3 The 2D maze which can’t be designed as 3D maze

1.2 二維迷宮的生成

二維迷宮的生成可以通過生成樹算法實現.從圖論的觀點看，迷宮可作某個圖的生成樹，反之，圖的生成樹也可表示為一個迷宮，如圖4所示.袁開等[10]基于最小生成樹的Kruskal算法，用圖的連通子圖生成迷宮.田翠花等[11]采用圖的深度優先遍歷生成規則的隨機迷宮.這些算法大同小異，主要步驟如下：

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

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

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

(4)導出隨機迷宮.但存在以下問題：(1)算法對圖進行盲目搜索，生成迷宮的路徑是完全隨機的.(2)算法同時生成迷宮的主路徑和支路，不能定制迷宮.(3)生成的迷宮路徑局限在矩形區域，兩側不連通，迷宮是不可循環的.

圖4 迷宮與生成樹等價Fig.4 A maze is equivalent to a spanning tree

筆者希望系統既能生成隨機迷宮，也能定制迷宮，或者定制和隨機2種形式相互混合.由于傳統算法不能滿足此要求，于是提出了一種新的迷宮算法，將主路徑和支路的生成過程分為2個獨立的階段.

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

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

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

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

圖6 回溯Fig.6 Backtrack

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

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

1.3 循環迷宮

循環迷宮指沒有邊界的迷宮.將平面迷宮映射到三維曲面時，平面迷宮因三維曲面結構而發生拓撲的局部改變，使得迷宮路徑可循環.循環迷宮可實現邊界間“無縫”拼接.圖8為非循環與循環迷宮圖.

圖8 非循環迷宮與循環迷宮Fig.8 Non-loop maze and loop maze

本文方法可以實現循環迷宮.如圖9所示，P在左側邊界上(黃色標記)，與P相鄰的點為

{PU，PD，PR},

P的左側沒有點，因此，由P無法直接訪問迷宮的右側.解決辦法是在迷宮的邊界處重新定義邊界的拓撲.重新定義P的相鄰點為

{PU，PD，PR，PL},

其中,PL是迷宮的左側邊界點.這樣，在P處，就可以自由訪問4個方向的點.對二維迷宮的所有邊界都重新定義類似拓撲，直接將這種拓撲關系應用于迷宮的生成，則可設計出循環迷宮.

圖9 循環迷宮的實現Fig.9 The implement of the loop maze

1.4 迷宮的復雜度

保證迷宮的有效性是檢驗迷宮設計質量的標準之一，控制復雜度是保證迷宮設計有效性的良好方法.因此，有必要引入迷宮的復雜度來指導迷宮設計.MCCLENDON[7]提出了一種計算迷宮復雜度的方法，但所討論的迷宮是一類曲線迷宮，計算比較復雜.考慮到矩形迷宮自身離散的特點，借鑒MCCLENDON的方法，本文提出一種計算矩形迷宮復雜度的離散化方法.

當迷宮中沒有支路時，則認為迷宮復雜度為0.一般來說，支路越多，支路的深度越深，迷宮就越復雜.引起支路路徑方向改變的點稱為支路的拐點，拐點的數量在一定程度上反映了迷宮的復雜程度.綜上所述，支路的數目、長度，支路上的拐點數都是影響迷宮復雜度的因素，如圖10所示.

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

設B是基于迷宮主路徑生成的某條支路，稱為一階支路，在一階支路上可以生成高階支路.設B上的支路數為n.設Li是i階支路的長度，

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

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

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

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

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

平均復雜度Branchave(B)能更好地反映迷宮支路的復雜情況.簡單計算圖11中支路的3種復雜度.(a)圖對應的是最大復雜度：

(b)圖對應的是最小復雜度：

于是平均復雜度為

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

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

2 三維迷宮的設計

2.1 算法概述

三維模型最常見的表示方式是網格，網格所表達的三維模型具有點、線、面等基本的數據結構.三維模型的網格具有圖的特征，可以看作三維空間中的圖.因此，通過圖導出生成樹，就能在三維模型對應的網格上生成迷宮.

對于給定的三維模型，三維迷宮的設計算法如圖12所示.二維迷宮實體化即將迷宮由二維結構轉化為三維結構，如圖13(b)所示，其目的是將二維迷宮通過三維模型合成三維迷宮.通過迷宮與三維模型之間的布爾差運算實現三維迷宮的合成.布爾差運算實際上就是從原始三維模型中減去二維迷宮，得到三維迷宮，如圖13(c)所示.

圖12 三維迷宮設計流程Fig.12 The pipeline design of 3D maze

圖13 三維迷宮設計Fig.13 The design of 3D maze

2.2 四邊形網格化

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

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

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

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

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

2.3 基于四邊形網格的三維迷宮設計

四邊形網格的結構為迷宮的生成提供了便利.首先，獲取四邊形網格中所有頂點的領域信息.除邊界外，四邊形網格頂點的鄰接點數都為4.為簡便，本文僅考慮在四邊形網格內部生成迷宮，即頂點的鄰接點個數都為4.

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

圖15 基于四邊形網格的三維迷宮設計Fig.15 The design of 3D maze based on the quadrilateral mesh

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

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

(2)上下2個底面分別以相鄰2個頂點為圓心；

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

最后，將實體化的迷宮與原始的三維模型做布爾差運算，得到基于三維結構的三維迷宮模型.

3 結 果

圖16顯示了3種設計風格的二維迷宮.隨機迷宮通過傳統迷宮算法實現，循環迷宮通過本文提出的迷宮生成算法實現，定制迷宮是系統結合用戶交互生成，用戶可以自行設計迷宮的主路徑，支路部分由系統隨機生成.通過對比可以看出，定制迷宮能夠產生較好的路徑形狀，循環迷宮左右兩側可相互連通.

圖16 3種風格的二維迷宮Fig.16 Three kinds of 2D mazes

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

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

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

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

圖18 三維迷宮模型及其實物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 結 論

結合二維迷宮設計與三維模型結構，提出了一種三維迷宮設計與建模方法，設計了一種基于立體結構的三維迷宮.作為玩具，三維迷宮在平面迷宮的基礎上增加了難度，同時也賦予迷宮更多的可操作性，從而大大增強了迷宮游戲的趣味性與可玩性.

首先，改進了基于生成樹的傳統迷宮生成算法.將迷宮的生成分為先主路徑、后支路2個過程，為設計隨機迷宮、循環迷宮及定制迷宮等不同風格的二維迷宮提供了便利.然后，基于生成的二維迷宮，嘗試利用圓柱體和球體設計三維迷宮，通過OpenSCAD建模軟件設計了基于圓柱造型、球造型的三維迷宮，并用FDM 3D打印機打印了成品.最后，將三維迷宮推廣到一般曲面，經四邊形網格化、網格表面設計二維迷宮、求布爾差等步驟，成功實現了一般曲面上的三維迷宮設計.

本文算法還有待進一步改進.首先，只能定制主路徑迷宮，尚無法實現迷宮的完整定制.其次，在一般曲面上設計的三維迷宮的質量依賴于四邊形網格化算法的質量.

[1] 余洋，張伶伶，楊曉軍.“迷宮”——景觀的神秘體驗[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] 袁開，友楊勇.平面迷宮地圖隨機生成樹算法設計與實現[J].科學咨詢，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] 田翠花，許衛平，陳玉明.深度優先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應用[J].河北北方學院學報，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] 嚴蔚敏，吳偉民.數據結構(C語言版)[M].北京：清華大學出版社，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.

國家自然科學基金資助項目(61222206，11526212)；中科院“百人”計劃項目.

王 康(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