写这个程序的原因是在某论坛上看到一个据称走出了这个迷宫就能让“I服了U”的帖子，迷宫如图：
这个图片是GIF格式的文件，所以像素比较清晰，便于用程序读点，所以开始考虑用程序写出这个迷宫算法。
在书写本程序时参考了VC知识库的相关文章（http://www.vckbase.com/document/viewdoc/?id=1219），在此表示感谢。
本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。
栈节点类型说明：
struct StackNode
{
POINT Point;
struct StackNode *Next, *Prev;//双向链表形式
};
栈结构用一个类（CPointStack）实现，声明如下：
class CPointStack
{
public:
void ClearStack();//清空栈
void InitStack();//初始化栈
bool Pop(POINT &pt);//弹出顶端元素，并给出该点的坐标，返回是否弹出成功
bool Push(POINT pt);//将pt点的信息压入栈，返回是否压入成功
CPointStack();
virtual ~CPointStack();
protected:
StackNode *m_psnTop;//栈顶指针
StackNode m_snBottom;//栈底，不保存点信息
};
以下为成员函数实现，都是一些数据结构的操作，应该没什么好说的：
//构造时初始化栈
CPointStack::CPointStack()
{
InitStack();
}
//析构时清空栈
CPointStack::~CPointStack()
{
ClearStack();
}
//将点压入栈(成功返回true,失败返回false)
bool CPointStack::Push(POINT pt)
{
StackNode* NewNode = new StackNode;
//是否返回true主要看这里申请内存是否成功
if(!NewNode)
return false;
NewNode->Point = pt;
NewNode->Prev = m_psnTop;
NewNode->Next = NULL;
m_psnTop->Next = NewNode;
m_psnTop = NewNode;
return true;
}
//将点弹出栈(成功返回true,栈为空则返回false)
bool CPointStack::Pop(POINT &pt)
{
if(m_psnTop == &m_snBottom)//是否返回true主要看这里栈是否为空
return false;
StackNode *p;
p = m_psnTop;
m_psnTop = m_psnTop->Prev;
pt = p->Point;
delete p;
m_psnTop->Next = NULL;
return true;
}
//初始化栈
void CPointStack::InitStack()
{
m_psnTop = &m_snBottom;
m_snBottom.Next = NULL;
m_snBottom.Prev = NULL;
}
//清空栈
void CPointStack::ClearStack()
{
StackNode *p;
while(m_psnTop != &m_snBottom)
{
p = m_psnTop;
m_psnTop = m_psnTop->Prev;
delete p;
}
}
接下来设计怎样走出这个迷宫，也就是迷宫算法的主体部分。再次用一个类实现。
在设计这个类时，我考虑到以下几点：
1、迷宫入口和出口的坐标
2、保存迷宫的2维数组
3、获得路径的函数
但是实际设计时由于没有考虑太多问题，只是以设计迷宫算法和解决一个具体迷宫为目的，所以没有考虑动态大小的迷宫，而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识（在保存迷宫数据的表中设置经过的点为2而将死路点设置为3）。
这样迷宫类（CGoMaze）的声明为：
class CGoMaze
{
public:
void Go();//寻找路径的函数
POINT m_ptIn;//入口坐标
POINT m_ptOut;//出口坐标
BYTE m_btArrMaze[401][601];//保存迷宫的二维表
CGoMaze();
virtual ~CGoMaze();
};
最后让我们来看一下CGoMaze::Go()这个函数：
我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。
在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。
Go函数的具体实现如下，其实挺简单的^_^：
void CGoMaze::Go()
{
CPointStack psPath;//保存路径的栈
POINT ptCur = m_ptIn, ptNext;//设置当前点为入口
while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出
{
ptNext = ptCur;//设置目标点为当前点，便于下面偏移
if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)
ptNext.y --;//如果上方是空的，则目标点向上偏移
else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)
ptNext.x --;//如果左边是空的，则目标点向左偏移
else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)
ptNext.y ++;//如果下方是空的，则目标点向下偏移
else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)
ptNext.x ++;//如果右边是空的，则目标点向右偏移
else
{//这里是没有路的状态
m_btArrMaze[ptCur.y][ptCur.x] = 3;//标记为死路
psPath.Pop(ptCur);//弹出上一次的点
continue;//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2;//标记当前点为路径上的点
psPath.Push(ptCur);//当前点压入栈中
ptCur = ptNext;//移动当前点
}
}
其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：
psPath.ClearStack();
这样就可以用Timer来演示走迷宫的过程了
程序在Windows2000sp4，VC6.0环境下通过
完整代码的其余部分因为使用了MFC的向导，比较复杂，没有列出，需要的请E-Mail至：[email protected]
但是我个人认为应该没有必要了，呵呵，算法了解了，这个程序没有别的什么值得看的了^_^
累啦～不知道这东西对初学者有没有帮助，随便写写～HOHO
也希望各位高手也给予批评指导 
|
本类阅读TOP10