规则迷宫的一种求解思想及算法
2009-10-29 11:58:51 来源:WEB开发网摘要
本文通过将规则迷宫映射为迷宫矩阵,在迷宫矩阵中搜索迷宫路径,最后再将迷宫矩阵中的标记的路径在迷宫图中画出来.本文给出了给出了详细的搜索算法和具体的图像实现方法,供大家参考.
前些天同学录上有同学上传了一个迷宫图(如图一所示),初看确是比较吓人,不放大是看不清路径的,但放大就看不到全图!要在图里手工走出很难想象的!当时有同学走出来了,以为是用程序就可以解决(后来才了解到同学是用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()
(二)、下面的代码为迷宫映射为迷宫矩阵int mazelab[XM][YM](为公共变量矩阵):
{
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();
}
}
//点击按钮进行转换.
这样迷宫图就被映射为迷宫矩阵。
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);
}
- ››规则迷宫的一种求解思想及算法
- ››迷宫
- ››迷宫探路II
- ››迷宫探路
- ››迷宫问题
- ››规则与自由:为何选择CORBA和Java技术
更多精彩
赞助商链接