圖的遍歷迷宮算法淺析

1、圖的遍歷迷宮算法QQ:513696765作者：小牛1. 引言 在平常的游戲中，我們常常會碰到隨機生成的地圖。這里我們就來看看一個簡單的隨機迷宮是如何生成。2. 迷宮描述 隨機生成一個m * n的迷宮，可用一個矩陣mazemn來表示，如圖： 圖1.1 圖1.2這里是兩個迷宮的例子，其中“”表示障礙物(Obstacle block)。以圖1.1迷宮為例，我們可用一個9 * 9的矩陣來表示：1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 11 1 1 1 1 1 1 0 11 0 0 0 0 0 1 0 11 0 1 1 1 1 1 0 11 0 1 0 0 0 0 0 11 0

2、1 0 1 1 1 1 11 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 1(矩陣中1表示是障礙物，0表示可以行走)3、迷宮生成算法(藍(lán)色表示可以行走，棕色表示是墻壁) 圖3.1如圖3.1所示為迷宮的初始化情形，迷宮如果除去其迷宮的外圍框架就是一個7*7的矩陣，如果要生成一個完整的迷宮，那么就要遍歷完圖3.1所示的每一個可以行走的點，其中遍歷的點也包含了入口和出口，如果每一個點都遍歷完了就會生成一棵完整的遍歷樹，這棵遍歷樹包含了入口和出口所以這顆樹所描述的迷宮是有解的（即：入口到出口時連通的。）圖3.2就表示圖1.1迷宮遍歷所得到的遍歷樹，樹包含了入口和出口所以此迷宮有解。

3、圖3.2圖3.3圖3.3表示的是圖3.2進(jìn)一步的處理后得到的最終迷宮圖，就是在圖3.2的基礎(chǔ)上把遍歷樹上的是墻壁的元素置為可行走的元素。3.1元素的遍歷圖3.1.1描述了各個遍歷點的連接關(guān)系其中1元素為起始遍歷點，49元素為終點遍歷點我們聲明一個mazepoint類用來描述每一個遍歷點xtemp表示當(dāng)前點在數(shù)組中的x坐標(biāo)，ytemp表示當(dāng)前點在數(shù)組中的y坐標(biāo)，定義為mazepoint對象的next用來鏈表一個點的地址last用來鏈表上一個地址。圖3.1.1聲明了兩個mazepoint的變量head和tail用于存儲迷宮的鏈表的頭地址和尾地址由于在迷宮剛剛開始的時候初始化元素是第一個所以頭尾是相

4、同的在主函數(shù)中把head賦值給了p1，（p1是我們聲明的一個臨時存儲的變量；p1和p2用于新的鏈表元素生成）如圖3.1.2所示元素1它連接到元素3和元素15，所以它可以遍歷這兩個元素，假設(shè)遍歷的方向是隨機的，如果第一次現(xiàn)在向右遍歷那么元素3就被遍歷并把它標(biāo)志為flag（flag表示已經(jīng)遍歷過了不容許再次遍歷），所以元素1和元素3都標(biāo)志位flag說明在其它元素想遍歷它們的時候是不能再次被遍歷了。這就有可能會遍歷成一棵完整的樹。 圖3.1.2如圖3.1.3所示圖1.1迷宮在生成時前13步，據(jù)圖我們可知在第13步的時候遍歷到元素19，但是元素19周圍的點都已經(jīng)遍歷過但同時還有其它元素還沒有遍歷到，所

5、以要后退到上一個遍歷過的元素判斷是否有遍歷的方向，所以鏈表到元素17，但是此元素也沒有可遍歷的方向所以要一直往上鏈表直到鏈表到某一個可以重新遍歷的點為之。 圖3.1.3圖3.1.4是往上鏈表的示意圖直到鏈表到元素45發(fā)現(xiàn)此元素?fù)碛锌杀闅v的方向，所以又重新往下建立新的鏈表，即元素47 圖3.1.4圖3.1.5是最終遍歷完后的遍歷路徑，此時只要沿著遍歷的方向把相應(yīng)的“墻”拆掉就可以生成一個無外框的迷宮并且只能生成奇數(shù)行和奇數(shù)列的迷宮。 圖3.1.5圖3.1.6是程序生成得33*33的迷宮 圖3.1.64、編程思路結(jié) 束屏幕輸出迷宮鏈接到上一個點tail=tail->last下一個點是否有方向

6、可遍歷把p1的地址賦給p2，同時把當(dāng)前點的x，y坐標(biāo)賦給p1，新建一個鏈表元素并且把其地址賦給p1，把p2的next連接到p1的地址，p1的last鏈接到p2，p1的next鏈接到NULL，這樣就生成了一個雙向的動態(tài)鏈表每一個點是否遍歷完 即：pointcount=0？聲明和初始化mazepoint變量P1，p2，head，teil初始化p1變量成員變量并且把p1的地址傳遞給head開 始在可以遍歷的方向中隨機選擇一個方向遍歷并且把選擇的元素標(biāo)志為flag同時把x，y的坐標(biāo)更新到和當(dāng)前點的坐標(biāo)，說明當(dāng)前點不可再一次遍歷了pointcount-1說明有一個點已經(jīng)遍歷過了，再把tail賦值為p1的

7、地址5、源代碼#include<iostream>#include <time.h>using std:cout;using std:cin;using std:endl;#define Row 33/用于定義迷宮的行必須為奇數(shù)，否則不能遍歷到所以的點#define Col 33/用于定義迷宮的列必須為奇數(shù)，否則不能遍歷到所以的點#define flag 1/點的標(biāo)志位，如果找到符合條件的點就把它置為flag，只要某一個點置位為flag就不能再次被訪問；int x_row=0;/迷宮的起始點位置的x坐標(biāo)int y_col=0;/迷宮的起始點位置的y坐標(biāo)int Left=

8、0;/初始化向左的方向標(biāo)志位Leftint Right=0;/初始化向右的方向標(biāo)志位Rightint Up=0;/初始化向上的方向標(biāo)志位Upint Dwon=0;/初始化向下的方向標(biāo)志位Dwonint pointcount=(Row+1)*(Col+1)/4-1);/初始化要遍歷的點數(shù)，(因為第一個點不要遍歷了，所以總點數(shù)要減去1)int get_count();/定義可以獲得某一個點可以行走的方向數(shù)的函數(shù)class mazepoint/定義一個類用于存放每一個遍歷點的坐標(biāo)public:int xtemp; /用于存放一個遍歷點的x坐標(biāo)int ytemp;/用于存放一個遍歷點的y坐標(biāo)mazep

9、oint *next;/用于存放一個遍歷點的下一個遍歷點的地址mazepoint *last;/用于存放一個遍歷點的上一個遍歷點的地址;mazepoint *p1;mazepoint *p2;mazepoint *head=NULL;/初始化頭由于沒有指向如何位置所以賦值為NULLmazepoint *tail=NULL;/初始化尾由于沒有指向如何位置所以賦值為NULLint mazemapRowCol=/初始化迷宮地圖數(shù)組1;int main()p1=new mazepoint;/聲明一片內(nèi)存空間p1->xtemp=0;/初始化類元素x坐標(biāo)p1->ytemp=0;/初始化類元素y

10、坐標(biāo)p1->last=NULL;/初始類只有一個元素沒有前一個元素，鏈接到別的元素所以它的的上一個遍歷點位空NULLhead=p1;/把鏈表的頭地址賦值給p1tail=p1;/剛剛開始沒有其它元素所以把鏈表的尾地址也是p1int mazenum=0;/用于統(tǒng)計遍歷的次數(shù)srand(time(0);/用當(dāng)前時間做隨機種子數(shù)while(pointcount)/如果沒有遍歷完所有的點就繼續(xù)遍歷，以確保每一次的隨機數(shù)都不一樣int rdNo=rand();/獲得隨機數(shù)int Randtemp;/定義一個變量，用于存儲處理后的隨機數(shù)int tempflag;/定義一個變量，用于存儲某一個點可以行走

11、的方向數(shù)tempflag=get_count();/獲得某一個點可以行走的方向數(shù)if(tempflag!=0) /如果某一個點可以行走就處理隨機數(shù)然后隨機選擇行走的方向Randtemp=rdNo%tempflag;/根據(jù)返回的可以行走的方向提供行走方向數(shù)elseRandtemp=NULL;/如果不能行走就賦值為NULLcout<<"電腦隨機數(shù)為:" << rdNo<<endl;/輸出電腦產(chǎn)生的隨機數(shù)Randtemp+=1;/加1是為了和定義的方向Left,Right,Up,Dwon相匹配cout<<"隨機數(shù)為:&qu

12、ot; << Randtemp<<endl;/輸出處理后的隨機數(shù)if(tempflag!=0)/如果可以行走p2=p1;p1->xtemp=x_row;/保存當(dāng)前點的x坐標(biāo)p1->ytemp=y_col;/保存當(dāng)前點的y坐標(biāo)p1=new mazepoint;/聲明內(nèi)存p2->next=p1;/前一個遍歷點鏈表到下一個點的地址p1->last=p2;/后一個遍歷點鏈表到上一個點的地址p1->next=NULL;/新生產(chǎn)的點沒有鏈表到下一個點所以設(shè)為NULL。(新產(chǎn)生的點是鏈表的最后一個點)if(Randtemp=Left &&

13、 mazemapx_rowy_col-2!=flag)/判斷左邊是否可以走如果可以走就不為；flagRandtemp=Left表示隨機數(shù)等于Left/*/mazemapx_rowy_col；新遍歷到的位置*/上一次確定的位置*/ mazemapx_rowy_col+1；新遍歷到位置的相同方向的臨近元素*/*y_col-=2;/如果可以左走就要把對應(yīng)的坐標(biāo)也要改變；也就是行值減2mazemapx_rowy_col=flag;/把遍歷到的新的迷宮地圖元素也要置flagmazemapx_rowy_col+1=flag;/把遍歷到的新的迷宮地圖元素相同方向的臨近元素也要置flag-pointcount

14、;/遍歷到新的一個點，那么遍歷點的總數(shù)pointcount減1cout<<"I choice Left"<<endl;else if(Randtemp=Right && mazemapx_rowy_col+2!=flag)/判斷右邊是否可以走如果可以走就不為；flagRandtemp=Right表示隨機數(shù)等于Right/*/ mazemapx_rowy_col；新遍歷到的位置*/上一次確定的位置*/mazemapx_rowy_col-1；新遍歷到位置的相同方向的臨近元素*/*y_col+=2;/如果可以右走就要把對應(yīng)的坐標(biāo)也要改變；也

15、就是行值加2mazemapx_rowy_col=flag;/把遍歷到的新的迷宮地圖元素也要置flagmazemapx_rowy_col-1=flag;/把遍歷到的新的迷宮地圖元素相同方向的臨近元素也要置flag-pointcount;/遍歷到新的一個點，那么遍歷點的總數(shù)pointcount減1cout<<"I choice Right"<<endl;else if(Randtemp=Up && mazemapx_row-2y_col!=flag)/判斷上邊是否可以走如果可以走就不為；flagRandtemp=Up表示隨機數(shù)等于Up/*

16、/ mazemapx_rowy_col；新遍歷到的位置*/ mazemapx_row+1y_col；新遍歷到位置的相同方向的臨近元素*/上一次確定的位置*/*x_row-=2;/如果可以上走就要把對應(yīng)的坐標(biāo)也要改變；也就是列值減2mazemapx_rowy_col=flag;/把遍歷到的新的迷宮地圖元素也要置flagmazemapx_row+1y_col=flag;/把遍歷到的新的迷宮地圖元素相同方向的臨近元素也要置flag-pointcount;/遍歷到新的一個點，那么遍歷點的總數(shù)pointcount減1cout<<"I choice Up"<<e

17、ndl;else if(Randtemp=Dwon && mazemapx_row+2y_col!=flag)/判斷下邊是否可以走如果可以走就不為；flagRandtemp=Dwon表示隨機數(shù)等于Dwon/*/上一次確定的位置*/ mazemapx_row-1y_col；新遍歷到位置的相同方向的臨近元素*/ mazemapx_rowy_col；新遍歷到的位置*/*x_row+=2;/如果可以下走就要把對應(yīng)的坐標(biāo)也要改變；也就是列值加2mazemapx_rowy_col=flag;/把遍歷到的新的迷宮地圖元素也要置flagmazemapx_row-1y_col=flag;/把遍歷

18、到的新的迷宮地圖元素相同方向的臨近元素也要置flag-pointcount;/遍歷到新的一個點，那么遍歷點的總數(shù)pointcount減1cout<<"I choice Dwon"<<endl;tail=p1;/把鏈表的尾巴賦值給新產(chǎn)生的點。(新產(chǎn)生的點是鏈表的最后一個點)else/如果不可以行走就鏈表到上一個點直到鏈表到的某一個點可以行走為止cout<<"Pop To Last Point."<<endl;if(tail=head)/如果是第一個遍歷點那么鏈表的頭和尾巴重合tail=head;return

19、0;elsetail=tail->last;/鏈表到上一個點地址if(tail->last =NULL)tail=head;x_row=tail->xtemp;/讀取上一個遍歷點的x坐標(biāo)y_col=tail->ytemp;/讀取上一個遍歷點的y坐標(biāo)+mazenum;/執(zhí)行次數(shù)加1cout<<"Step is:"<<" "<<mazenum<<endl;/統(tǒng)計執(zhí)行的步數(shù)cout<<"Last Point coordinate is"<<&qu

20、ot; x is:"<<tail->xtemp<<" y is:"<<tail->ytemp<<endl;/輸出上一個點的X坐標(biāo)和Y坐標(biāo)cout<<"Now Point coordinate is"<<" x is:"<<x_row<<" y is:"<<y_col<<endl;/輸出當(dāng)前點的X坐標(biāo)和Y坐標(biāo)if(pointcount=0)/如果每一個遍歷點都遍歷到了就打印地圖

21、，生成得迷宮是沒有邊界，即：沒有外圍墻的迷宮for(int C=0;C<Col+2;+C)/輸出迷宮最上面的的圍墻即：上邊界cout<<""cout<<endl;for(int R=0;R<Row;+R)if(R=0)/入口不能輸出圍墻cout<<"IN" /打印入口elsecout<<""/輸出迷宮最左面的的圍墻即：左邊界for(int C=0;C<Col;+C)/打印各迷宮數(shù)組的元素if(mazemapRC=flag)/如果迷宮數(shù)組的元素是路的話就打印空白cout&

22、lt;<" "else /如果迷宮數(shù)組的元素是墻壁（flag）的話就打印墻cout<<""if(R=Row-1)/打印出口cout<<"OUT"elsecout<<""/輸出迷宮最右面的的圍墻即：右邊界cout<<endl;for( C=0;C<Col+2;+C)/輸出迷宮最下面的的圍墻即：下邊界cout<<""cout<<endl;return 0;int get_count()int count=0;/初始化

23、用于某一個點可以行走的方向數(shù)，(count用于統(tǒng)計某一個點可以行走的方向數(shù))count=0;if(y_col-2<0)/判斷往左是否越界；即：是否超出迷宮數(shù)組if(y_col<0)y_col=0;Left=0;cout<<"Left not is Direction "<<"count is:"<<count<<endl;/輸出往左不能走elseif(mazemapx_rowy_col-2!=flag)/判斷往左是否可以走+count;Left=count;elsecout<<&qu

24、ot;Left not is Direction "<<"count is:"<<count<<endl;/輸出往左不能走if(y_col+2>Col)/判斷往右是否越界；即：是否超出迷宮數(shù)組if(y_col>Col)y_col=Col;Right=0;cout<<"Right not is Direction "<<"count is:"<<count<<endl;/輸出往右不能走elseif(mazemapx_rowy_col+2!=flag)/判斷往右是否可以走+count;Right=count;elsecout<<&quo