改進(jìn)的并查集迷宮地圖生成算法研究與設(shè)計(jì)

史寶明，賀元香，馬少斌

(蘭州文理學(xué)院數(shù)字媒體學(xué)院，甘肅 蘭州 730010)

0 引言

迷宮存在的歷史已經(jīng)有5 000多年，最早可以追溯到古希臘的神話傳說。迷宮不僅在現(xiàn)實(shí)生活中比較常見，而且在計(jì)算機(jī)游戲中也有很廣泛的應(yīng)用[1-3]，游戲中的迷宮可以通過手工繪制或建模的方式生成，也可以通過設(shè)計(jì)迷宮生成算法自動(dòng)生成，游戲中的迷宮地圖可以極大地增強(qiáng)游戲的趣味性，提升游戲的吸引力。一般而言，迷宮有單迷宮和復(fù)迷宮之分，單迷宮是指只有一種走法的迷宮，可沿著某一面墻壁走，用左(右)手始終摸著左(右)面的墻壁，就一定可以走出迷宮。復(fù)迷宮是指有多種走法的迷宮。在復(fù)迷宮中如果存在一些路徑可以不回頭地走回原點(diǎn)，則以這條閉合的回路為界，復(fù)迷宮可以被劃分為多個(gè)部分，因此復(fù)迷宮可看作由多個(gè)單迷宮組合而成。

迷宮地圖在計(jì)算機(jī)游戲中有著廣泛的應(yīng)用，可以通過特定的算法來隨機(jī)生成迷宮地圖，當(dāng)游戲角色在迷宮場景中隨機(jī)游走時(shí)[4]，可以極大地增強(qiáng)游戲的趣味性和吸引力。迷宮的生成算法多種多樣，典型的生成算法主要有深度優(yōu)先搜索算法[5]、隨機(jī)Prim算法[6]、遞歸分割算法[7]、并查集算法[8-11]等。并查集(Union-Find Sets)是一種樹型的數(shù)據(jù)結(jié)構(gòu)，主要用來處理不相交集合的合并及查詢問題，在任務(wù)規(guī)劃求解[8]、聚類分析[9]、機(jī)器視覺檢測[10-12]等領(lǐng)域有著廣泛的應(yīng)用，以下著重研究使用并查集算法生成迷宮地圖。

1 并查集

1.1 并查集算法

并查集是一種應(yīng)用廣泛的集合，由若干不相交的子集合組成，并查集算法主要包含并(Union)操作和查(Find)操作。

Find(a)：判斷元素a屬于哪一個(gè)子集，即在一個(gè)集合樹中不斷向上查找到它的根結(jié)點(diǎn)并返回。這個(gè)操作可以判斷兩個(gè)元素是否屬于同一個(gè)子集，即判斷根結(jié)點(diǎn)是否相同。

Union(a,b)：將元素a所在的集合和元素b所在的集合并為一個(gè)集合。

除了這兩個(gè)操作，還有建立單元素集合的操作(MakeSet)，通過這些操作可以解決實(shí)際中經(jīng)常碰到的規(guī)劃問題、聚類問題、迷宮生成問題等。并查集通常采用樹形結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，每個(gè)元素中都存儲(chǔ)其父元素的地址信息，下面通過圖1和圖2演示并查集的操作過程。

(a)子集一 (b)子集二圖1 兩個(gè)并查集子集

(a)C接A (b)A接C圖2 執(zhí)行并操作

在圖1中，對(duì)于D和G兩個(gè)元素，判斷它們是否連通，即是否屬于同一個(gè)集合，可按如下方法進(jìn)行：對(duì)于元素D和G執(zhí)行查操作Find(x)，返回對(duì)應(yīng)元素的根結(jié)點(diǎn)，即有Find(D)的值為A，F(xiàn)ind(G)的值為C，發(fā)現(xiàn)兩個(gè)根元素不相同，可知D和G屬于兩個(gè)不同的子集，此時(shí)表明這兩個(gè)子集是不連通的。若希望D和G連通時(shí)，就需要執(zhí)行并操作，即將G的根C接到D的根A上，如圖2(a)所示，此時(shí)樹的深度為3，或?qū)的根A接到G的根C上，如圖2(b)所示，此時(shí)樹的深度為4。子集連接的選擇，對(duì)整個(gè)算法的性能有很大的影響，可采取如下策略對(duì)并查集算法進(jìn)行優(yōu)化。

1.2 優(yōu)化方法

在執(zhí)行并操作時(shí)，如果不注意連接方式，就有可能導(dǎo)致連接后的樹出現(xiàn)不平衡的現(xiàn)象，如圖2(b)所示，進(jìn)而導(dǎo)致查找過程變慢。解決的辦法有兩鐘：一種方法是按秩合并；另一種方法是采用路徑壓縮來優(yōu)化集合樹。

1.2.1 按秩合并

這里的秩指的就是樹的深度，按秩合并即記錄每個(gè)子集樹的深度，當(dāng)執(zhí)行兩個(gè)子集樹的并操作時(shí)，選擇始終將深度小的樹的樹根接到深度大的樹的樹根上，如圖2(a)所示，即將深度小的樹C接到深度大的樹A上，樹的深度不變；若兩個(gè)樹的深度大小一樣，則可任意合并，合并后的樹的深度加1。按秩合并可以讓集合樹盡可能地保持相對(duì)平衡，進(jìn)而可以提升查找效率。

1.2.2 路徑壓縮

路徑壓縮是一種在執(zhí)行“查”操作時(shí)扁平化樹結(jié)構(gòu)的方法，即在遞歸的查找樹的過程中，將每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)直接設(shè)置為根結(jié)點(diǎn)(圖3)，這樣可讓查找效率大大提升。路徑壓縮的思想著重關(guān)注每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，而無需關(guān)注樹的結(jié)構(gòu)，這個(gè)方法不僅極大地優(yōu)化了“查”操作，同時(shí)也優(yōu)化了“并”操作，可使并查集算法的效率大大提高。

圖3 路徑壓縮

2 改進(jìn)的并查集迷宮生成算法

2.1 迷宮初始化

當(dāng)設(shè)定好一個(gè)m行n列的迷宮時(shí)，考慮墻體在內(nèi)則需要一個(gè)2m+1行2n+1列的矩陣Maze[2m+1,2n+1]來進(jìn)行迷宮的初始化。假設(shè)行列的序號(hào)都從0開始，則一個(gè)迷宮空間可被偶數(shù)行和偶數(shù)列墻體劃分為一個(gè)一個(gè)的小單元。一個(gè)2m+1行2n+1列迷宮矩陣的初始化過程如下：

for (i = 0; i < 2*m+1; i++)

for (j = 0; j < 2*n+1; j++)

{

if (i == 0 || i ==2*m || j == 0 || j ==2*n)

maze[i,j] = 1; //迷宮外墻設(shè)置

else if (i % 2 == 0 || j % 2 == 0)

maze[i,j] = 1; //迷宮中間墻設(shè)置

else

maze[i,j] = 0; //迷宮單元格設(shè)置

}

Maze[i,j]的值為1表示墻體單元格，為0表示迷宮單元格。一個(gè)3×3迷宮的初始化狀態(tài)如圖4(a)所示，其中，黑色單元格為永久性墻體，網(wǎng)格狀單元格和斜線單元格為可拆除墻體，白色單元格為迷宮單元格。如果墻體單元格用1表示，迷宮單元格用0表示，則可得到圖4(b)所示的一個(gè)二維01矩陣。將墻體簡化為線條后的迷宮如圖4(c)所示。

(a)初始化 (b)數(shù)據(jù)化 (c)墻體簡化為線條

2.2 迷宮生成

迷宮生成的基本思路是在已初始化的迷宮矩陣中先設(shè)定起點(diǎn)和終點(diǎn)，并將可拆除的墻(即圖4(a)中的網(wǎng)格墻和斜線墻)放入一個(gè)列表，然后循環(huán)從列表中不斷隨機(jī)選擇一面墻，判斷被墻分隔的兩個(gè)迷宮單元是否連通，若不連通就拆掉該墻，并將該墻從列表中移除，重復(fù)此過程直到起點(diǎn)和終點(diǎn)連通為止。在迷宮生成的過程中，執(zhí)行并查集算法中的并操作時(shí)，采用按秩合并的策略進(jìn)行，在執(zhí)行查操作之前，先對(duì)集合樹進(jìn)行路徑壓縮處理。整個(gè)迷宮生成的算法設(shè)計(jì)如下：

Step1 在迷宮中選定起點(diǎn)a和終點(diǎn)b；

Step2 將網(wǎng)格墻和斜線墻單元格結(jié)點(diǎn)信息放入列表list中；

Step3 隨機(jī)從list中取出一面墻，對(duì)該墻兩側(cè)的單元格結(jié)點(diǎn)分別執(zhí)行“查”操作，查找其根結(jié)點(diǎn)；

Step4 判斷兩個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)是否相同，若不相同，執(zhí)行“并”操作，打通墻，并將此墻移出對(duì)應(yīng)列表；

Step5 對(duì)起點(diǎn)a和終點(diǎn)b分別執(zhí)行“查”操作，判斷其是否連通，若不連通，跳轉(zhuǎn)到Step3繼續(xù)，否則算法終止。

在每次執(zhí)行“并”操作時(shí)，使用按秩合并的方法進(jìn)行集合樹的合并，在執(zhí)行“查”操作時(shí)，先采用路徑壓縮的方式對(duì)集合樹進(jìn)行扁平化處理，再進(jìn)行查找，可以極大地提高查找效率。上述算法結(jié)束的條件是起點(diǎn)和終點(diǎn)連通，此時(shí)迷宮中有些單元格可能還未訪問到，這會(huì)導(dǎo)致有些迷宮單元格永遠(yuǎn)都到達(dá)不了的情形出現(xiàn)，若希望能夠到達(dá)迷宮的任意單元格，則只需將算法結(jié)束的條件更改為列表list為空即可。

3 算法仿真及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)仿真的計(jì)算機(jī)型號(hào)為Lenovo啟天M6600，操作系統(tǒng)為Window10(64位)，處理器為Intel?CoreTMi5-6500 CPU@3.20 GHz，測試軟件為Visual Studio 2017，算法用C#編程實(shí)現(xiàn)。

3.2 迷宮地圖生成仿真

迷宮生成程序使用C#語言實(shí)現(xiàn)，使用并查集算法思想先生成迷宮矩陣，再根據(jù)迷宮矩陣來繪制迷宮地圖。

設(shè)定迷宮格為15×15，則對(duì)應(yīng)的迷宮矩陣為31×31，迷宮單元格之間的墻體采用線條來進(jìn)行繪制，設(shè)定迷宮的起點(diǎn)為最左上的單元格，終點(diǎn)為最右下的單元格，則當(dāng)起點(diǎn)連通終點(diǎn)時(shí)，運(yùn)行3次程序生成的迷宮，如圖5所示。

(a)第1次 (b)第2次 (c)第3次圖5 起點(diǎn)連通終點(diǎn)時(shí)生成的迷宮

由圖5可以看出，每一次運(yùn)行生成的迷宮均不相同，在3次生成的迷宮地圖中，均存在一些封閉的迷宮單元格,四面都有墻體，在這樣的迷宮中行走時(shí)，這些封閉的迷宮單元格是無法訪問到的。將迷宮生成的終止條件變更為遍歷到每一個(gè)迷宮單元格，再運(yùn)行程序，運(yùn)行3次后得到的結(jié)果如圖6所示。

(a)第1次 (b)第2次 (c)第3次圖6 遍歷所有單元格后生成的迷宮

由圖6可以看出，3次運(yùn)行結(jié)果中均不存在不可訪問的迷宮單元格，此時(shí)從迷宮中任意一點(diǎn)出發(fā)，都可以遍歷所有的迷宮單元格，這也是在實(shí)際中應(yīng)用較為廣泛的一種迷宮。

3.3 算法結(jié)果分析

以上使用并查集思想設(shè)計(jì)的迷宮生成算法在生成迷宮時(shí)，只需要控制一個(gè)二維矩陣中矩陣元素的01變化即可，在迷宮初始化時(shí)，通過雙重循環(huán)來設(shè)置矩陣元素，時(shí)間復(fù)雜度為O(n2)，使用并查集算法生成迷宮時(shí)，時(shí)間主要消耗在“查”操作上，如果對(duì)查找的樹采用了路徑壓縮，則可將“查”操作的時(shí)間復(fù)雜度由O(n)提升為O(1)。在遍歷迷宮單元格時(shí)，只需一個(gè)while循環(huán)作為遍歷結(jié)束的終止條件，其時(shí)間復(fù)雜度為O(n)，并且可通過控制結(jié)束條件來生成不同類型的迷宮。總地來看，使用改進(jìn)的并查集算法生成迷宮地圖時(shí)效率較高，生成的迷宮地圖結(jié)構(gòu)布局合理，適合在各種迷宮探索游戲中進(jìn)行部署和應(yīng)用。

4 結(jié)語

本文設(shè)計(jì)并實(shí)現(xiàn)了基于并查集思想的迷宮地圖自動(dòng)生成算法，通過按秩合并、路徑壓縮等方式對(duì)迷宮生成算法進(jìn)行了優(yōu)化，算法設(shè)計(jì)高效，可以應(yīng)用在各類游戲開發(fā)中。除了文中探討的并查集迷宮自動(dòng)生成算法外，研究如何將深度優(yōu)先搜索算法、Prim算法、遞歸切割算法應(yīng)用在迷宮地圖的生成中并加以改進(jìn)，如何在生成好的迷宮地圖中進(jìn)行高效的智能尋路，是今后課題研究的重點(diǎn)方向。