2008年（909）
分类：
2008-05-06 22:03:34
下载源代码
关键词：规则迷宫，映射，迷宫矩阵。
摘要
本文通过将规则迷宫映射为迷宫矩阵,在迷宫矩阵中搜索迷宫路径,最后再将迷宫矩阵中的标记的路径在迷宫图中画出来.本文给出了给出了详细的搜索算法和具体的图像实现方法,供大家参考.
前些天同学录上有同学上传了一个迷宫图（如图一所示），初看确是比较吓人，不放大是看不清路径的，但放大就看不到全图！要在图里手工走出很难想象的！当时有同学走出来了，以为是用程序就可以解决（后来才了解到同学是用Fireworks的Magic
Wind功能走出来的），但自己写程序时却一直没有想到比较理想的方法。
图一 迷宫原图
后来用Photoshop打开仔细观察发现迷宫非常规则，即可走的道路和障碍物的宽度都相同（此迷宫中为一个像素的宽度），而其长度则都是其宽度的整数倍，因此迷宫的主体部分为矩形，且迷宫边界除了出口和入口其他都是封闭的，我们不妨称其为规则迷宫。如果能够把迷宫主体转换为简单的数字矩阵，矩阵由0，1组成，0对应道路，1对应障碍物，迷宫中的最小单位（长宽为道路宽度的矩形）对应矩阵中的一个元素（此迷宫即为一个像素对应一个矩阵元素），这样的矩阵就和迷宫完全一一映射了，我们不妨称这样得到的矩阵为迷宫矩阵，而在迷宫矩阵中走出来就是搜索一条入口和出口元素之间的0元素通道，这样就容易多了！说做就做。
(一)、打开VC 6.0,为了简单起见建立一个基于Dialog的MFC程序mazes工程,并将迷宫的主体部分位图（只截取了主体部分，为601*401像素，因此迷宫矩阵大小也应为601*401）作为位图资源(IDB_
BITMAP1）选入工程，下面的代码是重载OnPaint()函数将迷宫显示在对话框上：
void CMazesDlg::OnPaint()
{
if (IsIconic())
{
//此处为VC 自动生成,在此省略.
......
}
else //以下为所加代码.
{
//类成员 bool first 表示初始化时将位图选入设备并显示。
if(!first){
m_bitmap.LoadBitmap(IDB_BITMAP1);
//在CmazesDlg.h中已经定义类成员
CBitmap m_bitmap;
memdc.CreateCompatibleDC(NULL);
//在CmazesDlg.h中已经定义类成员
CDC memdc;
memdc.SelectObject(&m_bitmap);
m_bitmap.GetObject(sizeof(bm),&bm);
//在CmazesDlg.h中已经定义类成员
BITMAP bm;
//hdc 取得memdc 的值供后面使用。
hdc=memdc;
//在CmazesDlg.h中已经定义类成员
HDC hdc;
//初始化完成.
first=true;
}
CClientDC clientdc(this); //此处为对话框初始化和重画时显示迷宫原图的代码。
clientdc.BitBlt(10,10,bm.bmWidth 10,bm.bmHeight 10,&memdc,0,0,SRCCOPY);
if(success) setcolor(XS,YS); //此处为重画迷宫路径,函数见后面.
CDialog::OnPaint();
}
}
(二)、下面的代码为迷宫映射为迷宫矩阵int mazelab[XM][YM](为公共变量矩阵)：//点击按钮进行转换.
void CMazesDlg::OnButget()
{
//类成员 bool success 表示是否成功搜索到迷宫路径。
success=false;
int x,y;
MessageBox("开始将迷宫转换为矩阵!","转化",MB_OK);
for(x=0;x<601;x )
for(y=0;y<401;y )
{
if(GetPixel(hdc,x,y)==0)
mazelab[x][y]=1;
// GetPixel ()取得像素颜色，为0表示黑色（障碍物），对应迷宫矩阵值1。
else
mazelab[x][y]=0;
//因为迷宫只有黑白两色，非黑即白,可走的道路对应迷宫矩阵值为0 。
flags[x][y]=0;
//公共变量矩阵flags[MX][MY]用于搜索迷宫路径时作标记，表示是否来过此处，
//现对其初始化，0表示未来过，1表示来过。
}
//将入口和出口缩小为一个元素,减少搜索量.
mazelab[0][200]=1,
//入口为mazelab[0][201],即mazelab[XS][YS],
mazelab[0][202]=1,
//出口为mazelab[600][201],即mazelab[XE][YE].
mazelab[600][200]=1,
//这些数据的取得是通过测试得到的,在此省略.
mazelab[600][202]=1;
MessageBox("成功将迷宫转换为矩阵!","成功转化",MB_OK);
}
这样迷宫图就被映射为迷宫矩阵。
bool search(int x,int y,int dir) //dir 表示搜索方向
{
bool subway=false,noway=false,east=false,west=false,north=false,south=false;
//subway 表示是否有左右方向的分杈子路，noway 表示是否可以继续往前走。
//east ,west, south, north 分别表示是否有往东，西，南，北的分叉子路
while(!subway && !noway)
{
switch(dir)
{
case E: //往东走，在图中即为往右走。
x ;
if(x==XM-1) noway=true;
//检测是否越界。以下三句为检测是否有往前，往右，往左分叉子路，下同。
if(x<(XM-1) && mazelab[x 1][y]){
noway=true,east=false;
} else
east=true;
if(y<(YM-1) && !(mazelab[x][y 1])){
south=true,subway=true;
}
if(y>0 && !(mazelab[x][y-1])){
north=true,subway=true;
}
break;
case W: //往西走，在图中即为往左走。
x--;
if(x==0) noway=true;
if(x>0 && mazelab[x-1][y]){
noway=true,west=false;
} else
west=true;
if(y<(YM-1) && !(mazelab[x][y 1])){
south=true,subway=true;
}
if(y>0 && !(mazelab[x][y-1])){
north=true,subway=true;
}
break;
case S: //往南走，在图中即为往下走。
y ;
if(y==YM-1) noway=true;
if(y<(YM-1) && mazelab[x][y 1]){
noway=true,south=false;
} else
south=true;
if(x<(XM-1) && !(mazelab[x 1][y])){
east=true,subway=true;
}
if(x>0 && !(mazelab[x-1][y])){
west=true,subway=true;
}
break;
case N: //往北走，在图中即为往上走。
y--;
if(y==0) noway=true;
if(y>0 && mazelab[x][y-1]){
noway=true,north=false;
} else
north=true;
if(x<(XM-1) && !(mazelab[x 1][y])){
east=true,subway=true;
}
if(x>0 && !(mazelab[x-1][y])){
west=true,subway=true;
}
break;
}
}
if(x==XE && y==YE) return true; //到达终点，成功返回。
if(!subway && noway) return false ;
//前进方向无路可走且没有左右分叉子路，返回失败，即此路不通。
if(!flags[x][y])
flags[x][y]=1;
//迷宫中往往有回路，在分叉路口作标记
//表示已经来过，防止程序在此转圈，无限迭代而失败。
else
return false ;
//标记为1，表示已经来过此处，返回失败，即此路不通。
if(subway) //存在分叉子路，迭代搜索。
{
if(east) east=search(x,y,E); //有往东的子路，继续往东搜索。
if(south) south=search(x,y,S); //有往南的子路，继续往南搜索。
if(west) west=search(x,y,W); //有往西的子路，继续往西搜索。
if(north) north=search(x,y,N); //有往北的子路，继续往北搜索。
}
//根据在分叉路口的是否成功迭代返回作标记方向，后面根据此标记方向画路径
if(east) mazelab[x][y]=-1; // -1表示在此分叉路口往东走可以走到出口，
if(south) mazelab[x][y]=-2; // -2 表示在此分叉路口往南走可以走到出口，
if(west) mazelab[x][y]=-3; // -3表示在此分叉路口往西走可以走到出口，
if(north) mazelab[x][y]=-4; // -4表示在此分叉路口往北走可以走到出口。
return (east||west||south||north) ; //返回此分叉路口的最终搜索结果。
}
(四)、下面是根据搜索结果在原迷宫图上画出迷宫图解。
void CMazesDlg::setcolor(int x,int y)
{
int dir;
CDC* cdc=GetDC();
CPen newPen;
newPen.CreatePen(PS_SOLID,1, RED); //选用红笔画出。
CPen *oldPen = cdc->SelectObject(&newPen);
cdc->MoveTo(x 5,y 10); //将起始点选在左边入口处。
while(x!=XE|| y!=YE){
if(mazelab[x][y]<0) //在分叉路口处，根据所标 方向画线。
{
cdc->LineTo(x 10,y 10);
cdc->MoveTo(x 10,y 10);
dir=mazelab[x][y];
} //画迷宫路径
if(dir==-1) x ; //在非分叉路口，根据上一个方向往继续前走。
if(dir==-2) y ;
if(dir==-3) x--;
if(dir==-4) y--;
}
cdc->LineTo(XE 15,YE 10); //画到出口处。
cdc->SelectObject(oldPen);
newPen.DeleteObject();
}
(五)、在按钮事件响应函数中调用search(),和setcolor()画出迷宫路径图解.
void CMazesDlg::OnOK()
{
MessageBox("开始搜索迷宫路径!","提示",MB_OK);
mazelab[XS][YS]=-1;
if(search(XS,YS,E)) //从左边入口开始往东进行搜索.
{
MessageBox("搜索迷宫路径成功,路径如红色所示!","成功提示",MB_OK);
CMazesDlg::setcolor(XS,YS); //从左边入口处开始画路线.
success=true; //搜索成功
}
}
至此,迷宫已经走了出来,最后运行结果如图二所示.
