走迷宫算法v1.0
N 迷宫行数
M 迷宫列数
V 分割块占总空间比例
ElemType 迷宫元素类型
MazeType 迷宫类型
函数MazePath 走迷宫算法
函数Pass 判断当前位置是否可通过
函数FootPrint 留下足迹
函数MarkPrint 留下不能再走的标记
函数NextPos 计算下一位置
-------------------------------------------------*/
#include "MazePath.h"
Status MazePath（MazeType &maze, PosType start, PosType End）
{
// 算法3.3
// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中
// （从栈底到栈顶），并返回TRUE;否则返回FALSE
Stack stack; //定义一个栈
InitStack（stack）； //初始化该栈
int count = 0 ; //用来记录通道块的序号
PosType nextPos = start,curPos = start;
SElemType e,pe;
pe.di = 0;
int di = 0 ;
bool judger = true ;
bool uu = true;
while（true）
{
for（int i = 1 ; i <= 4 ; i++ ）
{
nextPos = NextPos（curPos,i）；
if（Pass（maze,nextPos））
{
count++;
e.seat = curPos ;
e.ord = count;
e.di = i ;
FootPrint（maze,curPos）；
Push（stack, e）；
curPos = nextPos ;
judger = true ;
if（curPos.c==End.c&&curPos.r==End.r）
{
count++;
e.seat = curPos ;
e.ord = count;
e.di = i ;
FootPrint（maze,curPos）；
Push（stack, e）；
return true ;
}
break;
}
if（i == 4）
{
if（judger） //走投无路时将最后一个通道块压入栈
{
count++;
e.seat = curPos ;
e.ord = count;
e.di = i ;
FootPrint（maze,curPos）；
Push（stack, e）；
judger = false;
if（curPos.c==End.c&&curPos.r==End.r）
return true ;
}
Pop（stack , pe）； //出栈
curPos = pe.seat ;
MarkPrint（maze , pe.seat）； //标记为走过且不可走
if（stack.top == 0）
return false;
break;
}
}
}
} //MazePath
Status Pass（ MazeType &MyMaze,PosType CurPos）
{
if （MyMaze.arr[CurPos.r][CurPos.c].c==' '）
return 1; // 如果当前位置是可以通过，返回1
else return 0; // 其它情况返回0
}
void FootPrint（MazeType &MyMaze,PosType CurPos）
{
//循环是判断全局线程互斥变量的值，等待走步，
//值为false,迷宫走步，并重新设为true,交给
//主线程绘制，子线程等待
while（drawflag）
;
drawflag=true;
MyMaze.arr[CurPos.r][CurPos.c].c='*';
}
void MarkPrint（MazeType &MyMaze,PosType CurPos）
{
//循环是判断全局线程互斥变量的值，等待走步，
//值为false,迷宫走步，并重新设为true,交给
//主线程绘制，子线程等待
while（drawflag）
;
drawflag=true;
MyMaze.arr[CurPos.r][CurPos.c].c='!';
}
PosType NextPos（PosType CurPos, int Dir）
{
PosType ReturnPos;
switch （Dir）
{
case 1:
ReturnPos.r=CurPos.r;
ReturnPos.c=CurPos.c+1;
break;
case 2:
ReturnPos.r=CurPos.r+1;
ReturnPos.c=CurPos.c;
break;
case 3:
ReturnPos.r=CurPos.r;
ReturnPos.c=CurPos.c-1;
break;
case 4:
ReturnPos.r=CurPos.r-1;
ReturnPos.c=CurPos.c;
break;
}
return ReturnPos;
}
[cpp] view plaincopy
selemtype.h
#pragma once
#define Status bool
#define TRUE true
#define FALSE false
struct PosType
{
int r,c; //行列 or xy
};
typedef struct
{
int ord; //通道块在路径上的序号
PosType seat; //通道块在迷宫中的坐标位置
int di; //从此通道块走向下一通道块的方向
}SElemType;
extern bool drawflag; //全局变量外部声明
[cpp]
main.cpp
#include <iostream>
using namespace std;
#include "graphics.h"
#include <time.h>
#include "mazepath.h"
/*------------------------------------------------
走迷宫游戏v1.0
屏幕大小： 640*480
Width 每个小方块宽度
Space 每个小方块间隔
Step 每块占据象素
drawflag 线程互斥全局变量，为true画图，
为false走迷宫
threadflag 判断线程是否结束的全局变量，为false
线程结束，程序结束
maze; 迷宫全局对象
start,end 迷宫起终点全局变量
函数InitMaze 初始化迷宫
函数RandmMaze 随机生成迷宫
函数DrawMaze 绘制迷宫
函数ThreadMazePath 子线程函数，调用走迷宫函数修
改迷宫对象数据
算法设计思想
数据结构： 迷宫每个元素由位置坐标x,y和是否可走
的状态c构成，x、y代表画块的左上角坐
标，c为#是障碍，为空格是空位，为！
是已走过且不能再走，为*是走过且还有
选择；
基本操作： 栈的初始化、销毁、入栈、出栈等；
绘制迷宫操作： 在主线程中绘制，根据元素值c选择不同
颜色绘制，根据元素值x、y,确定绘制
位置；
走迷宫操作： 在子线程中计算迷宫对象走动的每一步，
修改迷宫对象的值，但不绘制迷宫，通
过修改互斥变量drawflag的值，在两个
线程中交替进行绘制和走步。
-------------------------------------------------*/
#define Width 24
#define Space 2
#define Step （Width + Space）
bool drawflag=true;
MazeType maze;
PosType start,End;
bool threadflag=true;
void InitMaze（MazeType &maze）
{
//初始化迷宫，将二维数组的每个元素计算出屏幕坐标
int i,j;
for（i=0;i<N;i++）
for（j=0;j<M;j++）
{
maze.arr[i][j].x=30+j*Step;
maze.arr[i][j].y=30+i*Step;
}
}
void RandmMaze（MazeType &maze,PosType start,PosType end）
{
//随机生成迷宫，在二维数组内除起终点外其余位置随
//机生成障碍，障碍数量按比例V计算
int i,j,k,num;
//边界和空位初始化
for（i=0;i<N;i++）
{
maze.arr[i][0].c='#';
maze.arr[i][M-1].c='#';
if（i!=0&&i!=N-1）
{
for（j=1;j<M-1;j++）
{
maze.arr[i][j].c=' ';
}
}
}
for（i=1;i<M-1;i++）
{
maze.arr[0][i].c='#';
maze.arr[N-1][i].c='#';
}