深度遍歷實現迷宮生成(純C語言)
迷宮就是一個二維數組，可以給數組元素賦不同的值來表示路和牆。這裡我用0表示路，1表示牆。生成迷宮的過程就是先把數組所有元素都置為1(即為牆),然後通過賦值為0(即打破這些牆)來生成迷宮。
一、迷宮的初始化(我使用迷宮大小為7)
首先生成一個n*n(我這裡n=7)的二維數組maze，使其全部元素都為1，然後再選取裡面一些特殊的元素使其賦值為0，即下圖中藍色的點。該過程的輸出就是圖中黑色部分的值為1，藍色部分的值為0。
其次再生成一個k*k(k=n/2,即k為3)的二維數組smaze，剛好對應圖中所有的藍色點。該數組中所有的值全部置為FALSE，表示這些位置都沒有被訪問。
最後還需要一個結構體一維數組，其大小為3*3=9.該結構體內存儲子數組(即圖中藍色的數組)的坐標值。比如struct Point[2]中就存儲行數 x = 0; 列數 y = 2
結構體數組與二維數組的關係即二維數組映射到一維數組的關係。P[i]對應的坐標為(i/k,i%k);
倒過來就有smaze[i][j]==r[i*k + 1]
這樣迷宮的所有初始化就完成了，接下來就是遍歷smaze這個數組來實現迷宮的生成。
二、通過棧實現深度遍歷
壓棧一個結構體數組元素，我選擇的是P[0]
循環彈棧，彈出一個，則將其二維數組中的FALSE改為TURE表示該元素已經被訪問了。然後尋找其上下左右沒有被訪問的元素，找到一個，則將夾在兩個藍色圈中的牆打破，使其變成路，然後找到的未訪問的元素入棧。
我這裡選擇的順序是上右下左，因此生成的迷宮具有規律性。可以通過選擇不同順序來生成不一樣的迷宮，當然若每次循環時順序都是隨機的，那麼就實現了一個真正的隨機迷宮。
下面為代碼：
Push(&s,r[0]); //壓棧r[0]
while(Pop(&s,&e)) //棧不空時，進行循環
{
if(e.x-1>=0 && smaze[e.x-1][e.y]!=TURE) //上
{
smaze[e.x-1][e.y] = TURE;
maze[2*e.x][2*e.y+1] = a; //打牆
Push(&s,r[(e.x-1)*k+e.y]);
}
if(e.y+1<k && smaze[e.x][e.y+1]!=TURE) //右
{
smaze[e.x][e.y+1] = TURE;
maze[2*e.x+1][2*(e.y+1)] = a;
Push(&s,r[(e.x)*k+e.y+1]);
}
if(e.x+1<k && smaze[e.x+1][e.y]!=TURE) //下
{
smaze[e.x+1][e.y] = TURE;
maze[2*(e.x+1)][2*e.y+1] = a;
Push(&s,r[(e.x+1)*k+e.y]);
}
if(e.y-1>=0 && smaze[e.x][e.y-1]!=TURE) //左
{
smaze[e.x][e.y-1] = TURE;
maze[2*e.x+1][2*e.y] = a;
Push(&s,r[(e.x)*k+e.y-1]);
}
}
三、生成結果展示：
為了便於直觀，用visual studio做了貼圖，結果如下：
下面是可以直接運行的所有代碼。因為貼圖需要編譯器支持graphics包，沒有安裝VS的不能運行，故我放的是沒有做貼圖的。
//深度遍歷 18-11-3
#include <stdio.h>
#include <stdlib.h>
#define IN_MAXSIZE 100
#define INCREASE 10
#define SElemType Point
#define FALSE 0
#define TURE 1
#define n 7 //迷宮大小
#define k 3 // K = n/2
#define N 9 // N = K*K
#define a 0 //a表示路
#define b 1 //b表示牆
typedef struct
{
int x; //行坐標
int y; //列坐標
}Point;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int main()
{
int i,j;
int Init_Stack(SqStack *);
int Push(SqStack *,SElemType);
int Pop(SqStack *,SElemType *);
void DFSmaze(Point [],int [][n],int [][k]) ;
int maze[n][n];
int smaze[k][k];
Point r[(k)*(k)]; //結構體數組
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
maze[i][j] = b;
}
for(i=1;i<n-1;i=i+2)
for(j=1;j<n-1;j=j+2)
{
maze[i][j] = a;
}
maze[1][0]=maze[n-2][n-1]=a;
for(i=0;i<k;i++)
for(j=0;j<k;j++)
{
smaze[i][j] = FALSE;
}
for(i=0;i<k*k;i++) //結構體數組賦初值
{
r[i].x = i/k;
r[i].y = i%k;
}
for(i=0;i<k;i++) //smaze數組賦值
for(j=0;j<k;j++)
smaze[i][j] = FALSE;
smaze[0][0] = TURE; //初始節點
DFSmaze(r,maze,smaze);
for(i=0;i<n;i++) //列印生成迷宮
{
for(j=0;j<n;j++)
{
printf("%d ",maze[i][j]);
}
printf("
");
}
return 0;
}
int Init_Stack(SqStack *t) //初始棧
{
t->base = (SElemType *)malloc(IN_MAXSIZE*sizeof(SElemType));
if(!(t->base))
return 0;
t->top = t->base;
t->stacksize = IN_MAXSIZE;
return 1;
}
int Push(SqStack *t,SElemType e) //入棧
{
if(t->top-t->base>=t->stacksize)
{
t->base = (SElemType *)realloc(t->base,(t->stacksize+INCREASE)*sizeof(SElemType));
if(!t->base)
return 0;
t->top = t->base + t->stacksize;
t->stacksize += INCREASE;
}
*(t->top++) = e;
return 1;
}
int Pop(SqStack *t,SElemType *e) //出棧
{
if(t->top==t->base)
return 0;
*e = *(--t->top);
return 1;
}
void DFSmaze(Point r[N],int maze[n][n],int smaze[k][k]) //深度優先演算法
{
SElemType e; //結構體變數e
SqStack s;
if(Init_Stack(&s)==1) //初始棧
printf("OK
");
else
printf("Fail
");
Push(&s,r[0]); //壓棧r[0]
while(Pop(&s,&e)) //棧不空時，進行循環
{
if(e.x-1>=0 && smaze[e.x-1][e.y]!=TURE) //上
{
smaze[e.x-1][e.y] = TURE;
maze[2*e.x][2*e.y+1] = a; //打牆
Push(&s,r[(e.x-1)*k+e.y]);
}
if(e.y+1<k && smaze[e.x][e.y+1]!=TURE) //右
{
smaze[e.x][e.y+1] = TURE;
maze[2*e.x+1][2*(e.y+1)] = a;
Push(&s,r[(e.x)*k+e.y+1]);
}
if(e.x+1<k && smaze[e.x+1][e.y]!=TURE) //下
{
smaze[e.x+1][e.y] = TURE;
maze[2*(e.x+1)][2*e.y+1] = a;
Push(&s,r[(e.x+1)*k+e.y]);
}
if(e.y-1>=0 && smaze[e.x][e.y-1]!=TURE) //左
{
smaze[e.x][e.y-1] = TURE;
maze[2*e.x+1][2*e.y] = a;
Push(&s,r[(e.x)*k+e.y-1]);
}
}
}
推薦閱讀：
