|
玩过RPG游戏的朋友一定遇到过各种各样的迷宫，迷宫道路错综复杂，千变万化，如《仙剑奇侠传》，那么这些迷宫是怎样生成的呢？生成迷宫的算法又是什么呢？下面就给出一个随机生成二维迷宫的方法，并用VC编程实现。
一、随机生成迷宫的方法
迷宫的本质就是一幅地图，因此程序的核心问题就是如何生成一幅二维地图。步骤如下：首先，生成地图的框架，即定义地图的大小，得到地图的外围边界；其次，在图中生成一条连接起点和终点的通路，保证玩家可以走出迷宫；然后，保证地图的强连通性，在图中尽可能多地生成一些围墙，构成多条“死”路，用于迷惑玩家；最后，用连线的方法画出迷宫。下面分别介绍各步骤的实现方法。
1.生成地图的框架
普通的地图都是按块来划分的，定义一个平面地图的大小其实只需定义一个二维数组即可，比如说定义一个6*4的地图，那么就得定义一个[4][6]的数组，数组的数据表示地图中的块，再加上地图的边界，所以一个ySize*xSize的地图由(xSize+2)*(ySize+2)个块构成，如图1所示。为图中每个块赋一个数值，表示块与块之间是否连通。外围的块赋值为-1，表示地图的边界，中间的块赋值为0，表示初始状态。
2.生成一条连接起点和终点的通路
如图2所示，编号为1的块表示迷宫的起点，编号为21的块表示迷宫的终点，即玩家需要从地图的右下方走到左上方。设起点的坐标是（x1,y1），终点的坐标是(x2,y2)，(x,y)表示一个在图中移动的点，(x,y)的初始值等于起点坐标，即x=x1，y=y1，s代表点(x,y)移动的步数，s初始值为1，然后点（x,y）就从迷宫的起点开始移动，上、下、左、右方向分别由数值0、1、2、3表示，每走一步的方向由随机数0、1、2、3决定。如果有路可走，即前进方向的块的数值为零，则前进到新的块，并令s=s+1，将s赋值给新块。如果四周均已无路可走(四周无数值为零的变量)，则退回到s-1处，寻找s-1四周的变量还有没有路可走(s-1代表来时的路)，如找到，则s=s-1，并且退回先前位置，继续找路前进，否则便结束算法。如果点(x,y)已经到达终点，同样会结束算法。图2表示了一条按此算法随机生成的通路，由图2中的阴影方块表示，方块1为起点（x1,y1），方块21为终点（x2,y2），数值相差为1的方块连通，按数值递增1的顺序，从编号为1的方块到编号为21的方块，恰好生成一条通路。
图2 随机生成的通路
3.保证地图的强连通性
当生成一条由起点到终点的随机路线后，地图上仍有封闭的区域，为了尽可能多地生成一些“死”路，用于迷惑玩家，需要生成强连通图。强连通图的概念是，在一个有向图G中，对于G的任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径。因此，需要遍历地图上所有未赋值的点，随机地为这些点赋值，生成更多的路线，注意赋值应大于1000，以便区分上一步得到的那些表示通路的块，如图3所示。
图3 生成强连通路
4.画出迷宫
现在，已经得到了表示迷宫的数据，下面的任务就是把迷宫画出来。在平面图中用线段表示迷宫中的围墙，因此迷宫可用画线的方法画出。首先，设置两个二维数组HWall[][]和VWall[][]，分别表示水平方向的线段和垂直方向的线段。例如，HWall[i][j]表示块（i-1,j）和块(i,j)之间是否有连线，然后，根据相邻块的数值决定HWall或VWall的值，以图3为例，块(3,1)的值为20，块(4,1)的值为19，两值相差1，两块连通，于是HWall[i][j]=0，表示不用画线，块(1,3)的值为8，块(2,3)的值为5，差值大于1，两块不通，于是HWall[i][j]=1，表示需要画线。
二、程序实现
下面给出迷宫的程序实现。选用VC++6.0作为程序开发平台，建立基于对话框的工程。程序设计的关键是，（1）编写迷宫类CMaze，用于实现生成迷宫的算法；（2）编写在对话框中显示迷宫的代码；（3）编写人机交互代码，即玩家可以使用方向键控制目标在迷宫中移动。
1.迷宫类CMaze
迷宫类CMaze的定义如下：
class CMaze : public CObject
{
public:
CMaze();
virtual ~CMaze();
int ** InitWall(int ,int); //初始化迷宫中的围墙
int SetMaze(int **Maze,int s,int x,int y); //设置迷宫中的路径
int **CreateMaze(); //创建迷宫
int DestroyMaze(); //销毁迷宫
BOOL InitMaze(); //初始化迷宫
public:
int current_y; //移动点的纵坐标
int current_x; //移动点的横坐标
int xSize; //迷宫水平方向的长度
int ySize; //迷宫垂直方向的长度
int **Maze; //表示迷宫的二维数组
int **HWall; //迷宫水平方向的围墙
int **VWall; //迷宫垂直方向的围墙
HENHMETAFILE hemf,hemf2; //emf文件的句柄
};
下面依次介绍CMaze类的成员函数。
函数int **CreateMaze()，用于创建迷宫，返回值表示迷宫的二维数组，实现的核心代码如下：
int ** CMaze::CreateMaze()
{
int x=xSize-1,y=ySize,s=1;
int r;
int i,j;
Maze=new int*[ySize+2]; // Maze是表示迷宫的二维数组，为Maze分配内存
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; //迷宫内部的块初始为0
for(i=0;i<ySize+2;i++)
Maze[i][xSize+1]=Maze[i][0]=-1; //迷宫的边界初始为-1
for(i=0;i<xSize+2;i++)
Maze[0][i]=Maze[ySize+1][i]=-1;
Maze[y][x]=s; //s表示可以走出迷宫的步数，在起点处s=1
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; /*随机赋值，值应大于1000*/
SetMaze(Maze,s,x,y);
}
}
}
return Maze;
}
函数int SetMaze(int **Maze,int s,int x,int y)，用于设置迷宫中的路径，实现的核心代码如下：
int CMaze::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)
/*如果点(x,y)的四方有连通点*/
{
r=rand()%4; /*随机产生r的值，r=0、1、2或3分别表示右、下、左、上*/
xx=x+(r==0)-(r==2);
yy=y+(r==1)-(r==3);
/*得到新点（xx,yy），该点是随机产生的，不一定是连通点*/
while(Maze[yy][xx]!=0) /*当（xx,yy）走不通时，继续找可以连通的点*/
{
r=rand()%4;
xx=x+(r==0)-(r==2);
yy=y+(r==1)-(r==3);
}
x=xx;y=yy;s++; /*更新移动点的坐标，增加步数s的值*/
Maze[y][x]=s; /*将s赋值于新位置*/
}
else /*如果没有连通点，则退回到s-1处，寻找s-1四周的变量还有没有路可走*/
{
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) /*s-1处也无路可走，便结束算法*/
break;
}
}
return 0;
}
函数int ** InitWall(int ,int)，用于初始化迷宫中的围墙，代码如下：
int ** CMaze::InitWall(int xSize, int ySize)
{
int **Wall;
int i,j;
Wall=new int*[ySize+1];
for(i=0;i<ySize+1;i++)
Wall[i]=new int[xSize+1]; /*为二维数组Wall分配内存*/
for(i=0;i<ySize+1;i++)
for(j=0;j<xSize+1;j++)
Wall[i][j]=0; /*数组Wall初始值为0，表示尚无围墙*/
return Wall;
}
函数BOOL InitMaze()，用于初始化迷宫，为迷宫中水平方向和垂直方向的围墙赋值。生成迷宫后，把表示迷宫的图形存储为emf类型的文件，emf(Enhanced Metafile)文件是微软公司开发的一种Windows 32位扩展图元文件格式，扩展名为.emf。本程序用到的操作emf文件的API函数有CreateEnhMetaFile()，MoveToEx()，LineTo()，PlayEnhMetaFile()，关于这些函数的用法请参考《MSDN》，在此不再详述。实现的代码如下。
BOOL CMaze::InitMaze()
{
current_x = xSize-2 ;
current_y = ySize-1 ; / *(current_x , current_y )是起点坐标*/
HDC hdcEmf=CreateEnhMetaFile(NULL,"emf.emf",NULL,NULL);
/*得到emf文件的句柄，"emf.emf"保存迷宫的图形*/
HWall=InitWall(ySize, xSize); /*初始化水平方向的围墙*/
VWall=InitWall(ySize, xSize); /*初始化垂直方向的围墙*/
int i,j;
for (i=0;i<xSize;i++)
HWall[i][0]=1;
for (i=0;i<ySize;i++)
VWall[0][i]=1; /*迷宫的边缘要画线，表示有围墙*/
Rectangle(hdcEmf,0,0,STEP*xSize+1,STEP*ySize+1);
SelectObject(hdcEmf,GetStockObject(BLACK_PEN));
MoveToEx(hdcEmf,0,0,NULL);
LineTo(hdcEmf,STEP*xSize+1,0);
MoveToEx(hdcEmf,0,0,NULL);
LineTo(hdcEmf,0,STEP*ySize+1);
MoveToEx(hdcEmf,STEP*xSize+1,0,NULL);
LineTo(hdcEmf,STEP*xSize+1,STEP*ySize+1);
MoveToEx(hdcEmf,0,STEP*ySize+1,NULL);
LineTo(hdcEmf,STEP*xSize+1,STEP*ySize+1); /*以上几句画出迷宫的外围*/
/*下面的二重循环根据Maze数组表示的迷宫中各块的连通情况，画出迷宫内部的围墙*/
for(i=1;i<ySize+1;i++)
for(j=1;j<xSize+1;j++)
{
int 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*STEP,i*STEP-STEP,NULL);
LineTo(hdcEmf,j*STEP,i*STEP);
if (!VWall[j][i-1]) VWall[j][i-1]=1;
}
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*STEP-STEP,i*STEP,NULL);
LineTo(hdcEmf,j*STEP,i*STEP);
if (!HWall[j-1][i]) HWall[j-1][i]=1;
}
}
DeleteObject(SelectObject(hdcEmf,GetStockObject(BLACK_PEN)));
SelectObject(hdcEmf,GetStockObject(WHITE_PEN));
MoveToEx(hdcEmf,STEP,0,NULL);
LineTo(hdcEmf,2*STEP,0);
MoveToEx(hdcEmf,STEP*(xSize-2),STEP*ySize,NULL);
LineTo(hdcEmf,STEP*(xSize-1),STEP*ySize);
DeleteObject(SelectObject(hdcEmf,GetStockObject(WHITE_PEN)));
hemf=CloseEnhMetaFile(hdcEmf); /*释放emf文件的句柄*/
return TRUE;
}
函数int DestroyMaze()，用于销毁迷宫，释放内存，代码如下：
int CMaze::DestroyMaze()
{
int i;
for(i=0;i<ySize+2;i++)
{
delete []Maze[i];
}
for(i=0;i<ySize+1;i++)
{
delete []HWall[i];
}
for(i=0;i<ySize+1;i++)
{
delete []VWall[i];
}
return 0;
}
2.在对话框中显示迷宫
显示迷宫需要在WM_PAINT消息的处理函数中添加代码，在程序中走迷宫的主角是一个小动物，如图4所示，这也是一个emf类型的文件，实现的代码如下：
图4 游戏主角
void CMyDlg::OnPaint()
{
…… /*省略部分是工程自动生成的代码*/
this->GetClientRect(&rect); /*获得对话框的客户区参数，赋值给CRect变量rect*/
rect.left=rect.right/8;
rect.right=7*rect.right/8;
rect.top=rect.bottom/8;
rect.bottom=7*rect.bottom/8;
PlayEnhMetaFile(dc.m_hDC,maze.hemf,&rect); /*按比例画出在迷宫中移动的图标*/
nLeft=rect.left;
nTop=rect.top;
nWidth=rect.Width();
nHeight=rect.Height();
/*以下根据图标移动的路线，在迷宫中显示图标*/
HDC hdcEmf1=CreateEnhMetaFile(NULL,"emf2.emf",NULL,NULL);
DrawIcon(hdcEmf1,0,0,HIcon);
rect2.left=rect.left + nWidth*(maze.current_x)/maze.xSize;
rect2.right=rect2.left + nWidth/maze.xSize;
rect2.top=rect.top + nHeight*(maze.current_y)/maze.ySize ;
rect2.bottom=rect2.top + nHeight/maze.ySize;
maze.hemf2=CloseEnhMetaFile(hdcEmf1);
PlayEnhMetaFile(dc.m_hDC,maze.hemf2,&rect2);
}
3.实现人机交互
玩家利用键盘的四个方向键操纵小动物在迷宫中移动，为了捕获玩家对键盘的操作，需要在对话框中重载PreTranslateMessage函数，函数只对上、下、左、右四个按键进行处理，根据前进方向是否有围墙来移动小动物，移动小动物的函数为MoveIcon()。实现的代码如下：
BOOL CMyDlg::PreTranslateMessage(MSG* pMsg)
{
// TODO: Add your specialized code here and/or call the base class
if (pMsg->message == WM_KEYDOWN) /*如果玩家按下按键*/
{
switch (pMsg->wParam)
{
case VK_UP: /*按“上”键，如上方无围墙，则调用MoveIcon移动小动物*/
if ( !maze.HWall[int(maze.current_x)][int(maze.current_y)] )
MoveIcon(VK_UP);
break;
case VK_DOWN: /*向下*/
if ( !maze.HWall[int(maze.current_x)][int(maze.current_y+1)] )
MoveIcon(VK_DOWN);
break;
case VK_LEFT: /*向左*/
if ( !maze.VWall[int(maze.current_x)][int(maze.current_y)] )
MoveIcon(VK_LEFT);
break;
case VK_RIGHT: /*向右*/
if ( !maze.VWall[int(maze.current_x+1)][int(maze.current_y)] )
MoveIcon(VK_RIGHT);
break;
default:
break;
}
}
return CDialog::PreTranslateMessage(pMsg);
}
void CMyDlg::MoveIcon(UINT Direction) /*实现图形的移动*/
{
CClientDC dc(this);
PlayEnhMetaFile(dc.m_hDC,maze.hemf,&rect);
switch (Direction)
{
case VK_UP: /*在新位置重画小动物*/
maze.current_y--;
rect2.top=rect.top + nHeight*maze.current_y/maze.ySize;
rect2.bottom = rect2.top + nHeight/maze.ySize;
PlayEnhMetaFile(dc.m_hDC,maze.hemf2,&rect2);
break;
case VK_DOWN:
maze.current_y++;
rect2.top=rect.top + nHeight*maze.current_y/maze.ySize;
rect2.bottom = rect2.top + nHeight/maze.ySize;
PlayEnhMetaFile(dc.m_hDC,maze.hemf2,&rect2);
break;
case VK_LEFT:
maze.current_x--;
rect2.left=rect.left + nWidth*maze.current_x/maze.xSize;
rect2.right = rect2.left + nWidth/maze.xSize;
PlayEnhMetaFile(dc.m_hDC,maze.hemf2,&rect2);
break;
case VK_RIGHT:
maze.current_x++;
rect2.left=rect.left + nWidth*maze.current_x/maze.xSize;
rect2.right = rect2.left + nWidth/maze.xSize;
PlayEnhMetaFile(dc.m_hDC,maze.hemf2,&rect2);
break;
default:
break;
}
if (maze.current_x==1 && maze.current_y==0)/*如果走到终点，则弹出消息框表示祝贺*/
MessageBox("恭喜!","",MB_OK);
}
4.结束程序
添加一个按钮，单击按钮可释放资源，结束程序。编写响应按钮的函数OnCancel()，代码如下：
void CMyDlg::OnCancel()
{
maze.DestroyMaze(); /*释放CMaze类的资源*/
DeleteEnhMetaFile(maze.hemf);
DeleteEnhMetaFile(maze.hemf2);
CDialog::OnCancel();
}
至此，完成了自动生成迷宫的程序设计。由于迷宫是随机生成的，每次画出的图形不同。程序运行情况如图5所示。
图5 程序运行效果
三、结语
本文介绍了一种随机生成二维迷宫的方法，并指出了该方法的几个关键点，即如何生成连接起点和终点的通路，如何实现强连通图，以及如何绘制迷宫和捕获键盘事件的编程技巧。虽然代码不多，却实现了一个较为完整的迷宫游戏，希望能为游戏编程爱好者们起到参考作用。
|
