张研

摘要　本文介绍了一种随机生成二维迷宫的方法，并用VC编程实现。
关键词　迷宫，VC
    玩过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表示了一条按此算法随机生成的通路，由图中的阴影方块表示，方块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　程序运行效果

四、结语
    本文介绍了一种随机生成二维迷宫的方法，并指出了该方法的几个关键点，即如何生成连接起点和终点的通路，如何实现强连通图，以及如何绘制迷宫和捕获键盘事件的编程技巧。虽然代码不多，却实现了一个较为完整的迷宫游戏，希望能为游戏编程爱好者们起到参考作用。

参考文献
[1]唐策善等.数据结构——用C语言描述.高等教育出版社，1995.