这是我刚刚在文曲星pc1000a下载的GVBASIC代码,可以自动生成迷宫,很有趣的.
说实话,这个代码除了算法思想值得一提,其层次结构真的很糟糕.我把它改成win32程序了.
gvbasic代码如下:
10 l=8:mx=160/l:my=80/l:dim a(mx+1,my+1):goto 110
20 while not(x=2 and y=1)
30 if a(x-1,y)*a(x,y-1)*a(x,y+1)*a(x+1,y)=0 then 70
40 for i=0 to 3:xx=x+(i=0)-(i=2):yy=y+(i=1)-(i=3):if a(xx,yy)=s-1 then 60
50 next : return
60 x=xx:y=yy:s=a(x,y):goto 90
70 r=int(rnd(1)*4):xx=x+(r=0)-(r=2):yy=y+(r=1)-(r=3):if a(xx,yy)<>0 then 70
80 x=xx:y=yy:s=s+1:a(x,y)=s
90 wend:return
110 for i=0 to mx+1:a(i,0)=-1:a(i,my+1)=-1:next:for i=0 to my+1:a(0,i)=-1:a(mx+1,i)=-1:next
120 x=mx-1:y=my:s=1:a(x,y)=s:gosub 20
130 for q=my to 1 step -1:for p=mx to 1 step -1:if a(p,q)>0 then 160
140 r=int(rnd(1)*4):pp=p+(r=0)-(r=2)::qq=q+(r=1)-(r=3):if a(pp,qq)<1 then 140
150 x=p:y=q:s=a(pp,qq)*2+1000:a(x,y)=s:gosub 20:f=1
160 next p,q:if f then f=0:goto 130
200 graph
210 for x=1 to mx:for y=1 to my
220 t=abx(a(x,y)-a(x+1,y)):if t<=1 or t-1000=a(x,y) or t-1000=a(x+1,y) then 230
225 line x*l,y*l-l,x*l,y*l
230 t=abx(a(x,y)-a(x,y+1)):if t<=1 or t-1000=a(x,y) or t-1000=a(x,y+1) then 240
235 linex*l-l,y*l,x*l,y*l
240 next y,x
250 box 1,0,160,80:line l,0,l+l,0,0:line 160-l,80,160-l-l,80,0
260 end
400 while not (x=2 and y=1)
1000 for i=1 to 4:for j=1 to 8:print a(j,i);" ";:next: print inkey$:next:return
我改的win32代码如下:
int SetMaze(int **Maze,int s,int x,int y)
{
int r,xx,yy;
int i;
while(x!=2||y!=1)
{
if(Maze[y][x-1]*Maze[y][x+1]*Maze[y+1][x]*Maze[y-1][x]==0)
{
r=rand()%4;
xx=x+(r==0)-(r==2);
yy=y+(r==1)-(r==3);
while(Maze[yy][xx]!=0)
{
r=rand()%4;
xx=x+(r==0)-(r==2);
yy=y+(r==1)-(r==3);
}
x=xx;y=yy;s++;
Maze[y][x]=s;
}
else
{
for(i=0;i<4;i++)
{
xx=x+(i==0)-(i==2);
yy=y+(i==1)-(i==3);
if(Maze[yy][xx]==s-1)
{
x=xx;y=yy;s=Maze[y][x];
break;
}
}
if(i==4)
break;
}
}
return 0;
}
int **CreateMaze(int xSize,int ySize)
{
int x=xSize-1,y=ySize,s=1;
int r;
int i,j;
int **Maze=new int*[ySize+2];
for(i=0;i<ySize+2;i++)
Maze[i]=new int[xSize+2];
for(i=0;i<ySize+2;i++)
for(j=0;j<xSize+2;j++)
Maze[i][j]=0;
for(i=0;i<ySize+2;i++)
Maze[i][xSize+1]=Maze[i][0]=-1;
for(i=0;i<xSize+2;i++)
Maze[0][i]=Maze[ySize+1][i]=-1;
Maze[y][x]=s;
srand((unsigned)time(NULL));
SetMaze(Maze,s,x,y);
for(i=ySize;i>0;i--)
{
for(j=xSize;j>0;j--)
{
if(Maze[i][j]<=0)
{
r=rand()%4;
while(Maze[i+(r==1)-(r==3)][j+(r==0)-(r==2)]<1)
r=rand()%4;
x=j;y=i;s=Maze[i+(r==1)-(r==3)][j+(r==0)-(r==2)]*2+1000;
Maze[y][x]=s;
SetMaze(Maze,s,x,y);
CheckOver=false;
}
}
}
return Maze;
}
int DestroyMaze(int **Maze,int ySize)
{
for(int i=0;i<ySize+2;i++)
{
delete []Maze[i];
}
return 0;
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
PAINTSTRUCT ps;
HDC hdc,hdcEmf;
static HENHMETAFILE hemf;
RECT rect;
static int **Maze;
int t;
static int xSize=20;
static int ySize=16;
switch (message)
{
case WM_COMMAND:
break;
case WM_CREATE:
Maze=CreateMaze(xSize,ySize);
hdcEmf=CreateEnhMetaFile(NULL,"emf.emf",NULL,NULL);
Rectangle(hdcEmf,0,0,20*xSize+1,20*ySize+1);
for(int i=1;i<ySize+1;i++)
for(int j=1;j<xSize+1;j++)
{
t=abs(Maze[i][j]-Maze[i][j+1]);
if(!(t<=1||(t-1000)==Maze[i][j]||t-1000==Maze[i][j+1]))
{
MoveToEx(hdcEmf,j*20,i*20-20,NULL);
LineTo(hdcEmf,j*20,i*20);
}
t=abs(Maze[i][j]-Maze[i+1][j]);
if(!(t<=1||(t-1000)==Maze[i][j]||t-1000==Maze[i+1][j]))
{
MoveToEx(hdcEmf,j*20-20,i*20,NULL);
LineTo(hdcEmf,j*20,i*20);
}
}
SelectObject(hdcEmf,GetStockObject(WHITE_PEN));
MoveToEx(hdcEmf,20,0,NULL);
LineTo(hdcEmf,40,0);
MoveToEx(hdcEmf,20*(xSize-2),20*ySize,NULL);
LineTo(hdcEmf,20*(xSize-1),20*ySize);
DeleteObject(SelectObject(hdcEmf,GetStockObject(BLACK_PEN)));
hemf=CloseEnhMetaFile(hdcEmf);
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
// TODO: 在此添加任意绘图代码...
GetClientRect(hWnd,&rect);
rect.left=rect.right/4;
rect.right=3*rect.right/4;
rect.top=rect.bottom/4;
rect.bottom=3*rect.bottom/4;
PlayEnhMetaFile(hdc,hemf,&rect);
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
DeleteEnhMetaFile(hemf);
DestroyMaze(Maze,ySize);
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
那些创建窗口的程序我就省略了,反正大家都会.
普通的地图都是以块来划分的,定义一个地图也就只需要定义一个二维数组
比如说我定义一个8*6的地图,就得定义一个[6][8]的数组,其中用0代表障碍,
1代表可行即可,但这样设计未免太过于偷懒.
这个随机迷宫依然是以块来划分,所不同的是定义地图用的是点阵,划分地图的
任个块都有4个顶点,再加上地图边界的概念,所以一个xSize*ySize的地图由
(xSize+2)*(ySize+2)个点构成.这样地图中不再有障碍的概念,而变为块于
块之间是否连通的关系.
基本概念介绍完了,现在说说我对这个生成算法的理解.
我定义了两个变量
static int xSize=20;
static int ySize=16;
来表示生成20*16的地图,可以更改数值.
在CreateMaze(int,int)函数中,首先要定义一个Maze[ySize+2][xSize+2],
然后将数组赋初值,将数组边界均赋值为-1,非边界赋值0.
地图数据直观感觉如下:
-1 -1 -1 -1 -1
-1 0 0 0 -1
-1 0 0 0 -1
-1 0 0 0 -1
-1 -1 -1 -1 -1
注意这三个变量,int x=xSize-1,y=ySize,s=1;形象点说,x,y表示一个不存在的精
灵此刻在迷宫顶点阵列中的位置,而s代表这是它走的第几步.
然后这个精灵就在迷宫的右下位置开始走动了,每走一步的方向由随机数决定(随机迷
宫呗,但要注意,精灵并非在迷宫中走动,而是在构成迷宫方块的点中走动),如果路可
走(即前方位置数组值为零),则前进,s=s+1并将s赋值于新位置,如果四周均已无路
可走(四周无数值为零的变量),则寻找四周s-1的变量(代表来时的路,如找到,则
s=s-1,并且退回先前位置).否则便结束函数.还需注意,如果精灵已经到达组成出口的
点坐标(1,2),同样会结束函数.
看看CreateMaze的后半段代码,为什么要加上这么一段呢,因为原先的SetMaze虽然已经给出了一条由顶点到终点的随机路线,
但地图上仍有封闭的区域,不符合随机迷宫的强连通性,这段代码则检测那些未被赋值的顶点,
将精灵放置在这些顶点上,再进行一次SetMaze走出一条道路.
s=Maze[i+(r==1)-(r==3)][j+(r==0)-(r==2)]*2+1000;
代表将这些未赋值的点和已经存在的通路相关.
一切准备工作已经做完了,然后就是最关键的绘图了.
看看WM_PAINT:
Rectangle(hdcEmf,0,0,20*xSize+1,20*ySize+1);
for(int i=1;i<ySize+1;i++)
for(int j=1;j<xSize+1;j++)
{
t=abs(Maze[i][j]-Maze[i][j+1]);
if(!(t<=1||(t-1000)==Maze[i][j]||t-1000==Maze[i][j+1]))
{
MoveToEx(hdcEmf,j*20,i*20-20,NULL);
LineTo(hdcEmf,j*20,i*20);
}
t=abs(Maze[i][j]-Maze[i+1][j]);
if(!(t<=1||(t-1000)==Maze[i][j]||t-1000==Maze[i+1][j]))
{
MoveToEx(hdcEmf,j*20-20,i*20,NULL);
LineTo(hdcEmf,j*20,i*20);
}
}
很感谢您耐着性子看到这里,呵呵,估计你看到这里仍还是一头雾水吧,对这个地图数据赋那么多乱
七八糟的值到底有什么用,其实我也不太清楚代码原作者的意思,现在还没有精确的结论
过几天等我的猜想验证了再发贴吧.
大家也请说说自己的想法.^_^
