机器人是如何走出迷宫的
首先，我们要了解，机器人领域的视觉（Machine Vision）跟计算机领域（Computer Vision）的视觉有一些不同：机器视觉的目的是给机器人提供操作物体的信息。所以，机器视觉的研究大概有这几块： 物体识别（Object Recognition）：在图像中检测到物体类型等，这跟 CV 的研究有很大一部分交叉； 位姿估计（Pose Estimation）：计算出物体在摄像机坐标系下的位置和姿态，对于机器人而言，需要抓取东西，不仅要知道这是什么，也需要知道它具体在哪里； 相机标定（Camera Calibration）：因为上面做的只是计算了物体在相机坐标系下的坐标，我们还需要确定相机跟机器人的相对位置和姿态，这样才可以将物体位姿转换到机器人位姿。当然，我这里主要是讲物体定位领域的机器视觉；SLAM 等其他领域的就先不讲了。 算法肯定也是有的。 由于视觉是机器人感知的一块很重要内容，所以研究也非常多了，我就我了解的一些，按照由简入繁的顺序介绍吧： 1. 相机标定 这其实属于比较成熟的领域。由于我们所有物体识别都只是计算物体在相机坐标系下的位姿，但是，机器人操作物体需要知道物体在机器人坐标系下的位姿。所以，我们先需要对相机的位姿进行标定。 内参标定就不说了，参照张正友的论文，或者各种标定工具箱； 外参标定的话，根据相机安装位置，有两种方式： Eye to Hand：相机与机器人极坐标系固连，不随机械臂运动而运动Eye in Hand：相机固连在机械臂上，随机械臂运动而运动 两种方式的求解思路都类似，首先是眼在手外（Eye to Hand） 只需在机械臂末端固定一个棋盘格，在相机视野内运动几个姿态。由于相机可以计算出棋盘格相对于相机坐标系的位姿 、机器人运动学正解可以计算出机器人底座到末端抓手之间的位姿变化 、而末端爪手与棋盘格的位姿相对固定不变。 而对于眼在手上（Eye in Hand）的情况，也类似，在地上随便放一个棋盘格（与机器人基座固连），然后让机械臂带着相机走几个位姿，然后也可以形成一个 的坐标环。 2 平面物体检测 这是目前工业流水线上最常见的场景。目前来看，这一领域对视觉的要求是：快速、精确、稳定。所以，一般是采用最简单的边缘提取+边缘匹配/形状匹配的方法；而且，为了提高稳定性、一般会通过主要打光源、采用反差大的背景等手段，减少系统变量。目前，很多智能相机（如 cognex）都直接内嵌了这些功能；而且，物体一般都是放置在一个平面上，相机只需计算物体的 三自由度位姿即可。 另外，这种应用场景一般都是用于处理一种特定工件，相当于只有位姿估计，而没有物体识别。 当然，工业上追求稳定性无可厚非，但是随着生产自动化的要求越来越高，以及服务类机器人的兴起。对更复杂物体的完整位姿 估计也就成了机器视觉的研究热点。 3. 有纹理的物体 机器人视觉领域是最早开始研究有纹理的物体的，如饮料瓶、零食盒等表面带有丰富纹理的都属于这一类。 当然，这些物体也还是可以用类似边缘提取+模板匹配的方法。但是，实际机器人操作过程中，环境会更加复杂：光照条件不确定（光照）、物体距离相机距离不确定（尺度）、相机看物体的角度不确定（旋转、仿射）、甚至是被其他物体遮挡（遮挡）。幸好有一位叫做 Lowe 的大神，提出了一个叫做 SIFT （Scale-invariant feature transform）的超强局部特征点： Lowe, David G. "Distinctive image features from scale-invariant keypoints."International journal of computer vision 60.2 (2004): 91-110. 具体原理可以看上面这篇被引用 4万+ 的论文或各种博客，简单地说，这个方法提取的特征点只跟物体表面的某部分纹理有关，与光照变化、尺度变化、仿射变换、整个物体无关。 因此，利用 SIFT 特征点，可以直接在相机图像中寻找到与数据库中相同的特征点，这样，就可以确定相机中的物体是什么东西（物体识别）。对于不会变形的物体，特征点在物体坐标系下的位置是固定的。所以，我们在获取若干点对之后，就可以直接求解出相机中物体与数据库中物体之间的单应性矩阵。 如果我们用深度相机（如Kinect）或者双目视觉方法，确定出每个特征点的 3D 位置。那么，直接求解这个 PnP 问题，就可以计算出物体在当前相机坐标系下的位姿。 4. 无纹理的物体 好了，有问题的物体容易解决，那么生活中或者工业里还有很多物体是没有纹理的我们最容易想到的就是：是否有一种特征点，可以描述物体形状，同时具有跟 SIFT 相似的不变性？ 不幸的是，据我了解，目前没有这种特征点。 所以，之前一大类方法还是采用基于模板匹配的办法，但是，对匹配的特征进行了专门选择（不只是边缘等简单特征）。 这里，我介绍一个我们实验室之前使用和重现过的算法 LineMod： Hinterstoisser, Stefan, et al. "Multimodal templates for real-time detection of texture-less objects in heavily cluttered scenes." Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011. 简单而言，这篇论文同时利用了彩色图像的图像梯度和深度图像的表面法向作为特征，与数据库中的模板进行匹配。 由于数据库中的模板是从一个物体的多个视角拍摄后生成的，所以这样匹配得到的物体位姿只能算是初步估计，并不精确。 但是，只要有了这个初步估计的物体位姿，我们就可以直接采用 ICP 算法（Iterative closest point）匹配物体模型与 3D 点云，从而得到物体在相机坐标系下的精确位姿。当然，这个算法在具体实施过程中还是有很多细节的：如何建立模板、颜色梯度的表示等。另外，这种方法无法应对物体被遮挡的情况。（当然，通过降低匹配阈值，可以应对部分遮挡，但是会造成误识别）。 针对部分遮挡的情况，我们实验室的张博士去年对 LineMod 进行了改进，但由于论文尚未发表，所以就先不过多涉及了。 5. 深度学习 由于深度学习在计算机视觉领域得到了非常好的效果，我们做机器人的自然也会尝试把 DL 用到机器人的物体识别中。 首先，对于物体识别，这个就可以照搬 DL 的研究成果了，各种 CNN 拿过来用就好了。有没有将深度学习融入机器人领域的尝试？有哪些难点？ - 知乎 这个回答中，我提到 2016 年的『亚马逊抓取大赛』中，很多队伍都采用了 DL 作为物体识别算法。 然而， 在这个比赛中，虽然很多人采用 DL 进行物体识别，但在物体位姿估计方面都还是使用比较简单、或者传统的算法。似乎并未广泛采用 DL。 如 @周博磊 所说，一般是采用 semantic segmentation network 在彩色图像上进行物体分割，之后，将分割出的部分点云与物体 3D 模型进行 ICP 匹配。 当然，直接用神经网络做位姿估计的工作也是有的，如这篇： Doumanoglou, Andreas, et al. "Recovering 6d object pose and predicting next-best-view in the crowd." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.它的方法大概是这样：对于一个物体，取很多小块 RGB-D 数据（只关心一个patch，用局部特征可以应对遮挡）；每小块有一个坐标（相对于物体坐标系）；然后，首先用一个自编码器对数据进行降维；之后，用将降维后的特征用于训练Hough Forest。 6. 与任务/运动规划结合 这部分也是比较有意思的研究内容，由于机器视觉的目的是给机器人操作物体提供信息，所以，并不限于相机中的物体识别与定位，往往需要跟机器人的其他模块相结合。我们让机器人从冰箱中拿一瓶『雪碧』，但是这个 『雪碧』 被『美年达』挡住了。 我们人类的做法是这样的：先把 『美年达』 移开，再去取 『雪碧』 。 所以，对于机器人来说，它需要先通过视觉确定雪碧在『美年达』后面，同时，还需要确定『美年达』这个东西是可以移开的，而不是冰箱门之类固定不可拿开的物体。 当然，将视觉跟机器人结合后，会引出其他很多好玩的新东西。由于不是我自己的研究方向，所以也就不再班门弄斧了。更详细的图文解析可以到机器人家上去看，我这边就不贴出来了，希望对你有用
有一个小机器人闯关解谜游戏英文名的谁知道
是不是《机械迷城（Machinarium）》是由捷克独立开发小组Amanita Design开发的一款冒险游戏，于2009年10月16日发行。本游戏在2009年独立游戏节上获得了视觉艺术奖。《机械迷城》中每个人都是机器人，包括游戏中的主角。或者是《不机械城》不机械城是一款使用虚幻引擎开发横版解密类游戏，游戏中的主角颇似《机械迷城》中的那个小机器人。玩家将控制着它解开数层的难题。
走迷宫游戏算法
程序目的：
输入一个任意大小的迷宫，用栈求出一条走出迷宫的路径，并
显示在屏幕上。
程序实现：
可以实现载入迷宫和保存迷宫，附带文件中有4个测试迷宫路径的
文件test1~4.dd。请将这些文件拷贝到TC当前目录下，或者在载
入时写明完全路径。由于屏幕大小的限制，当用户自己输入迷宫
时一定要注意：迷宫大小是有限制的，不小于4*3,不大于30*20。
否则会出现错误信息。输入开始时全是墙，用上下左右键移动，
用Del键删除墙，形成通路，用Enter键添加墙。输入结束时可以
将迷宫保存下来，以dd为扩展名。输入完毕时用F9键来得到结果，
找到路径时，屏幕下方会出现Path found，否则出现Path not found。
程序经Turbo C 2.0编译调试成功。运行时不用添加任何运行库。
不可以在VC上编译。
下载DOS版和windows版的迷宫游戏全部代码
用户名：migong
----------------------------------------------------------------------------------
/*
MazePath Demo BY Turbo C 2.0
Copyright(c) RoverUnion. All right reserved.
Filename: Maze.c
Author Dongchengyu.
Ver 1.10
*/
#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define F9 0x43
#define Esc 0x1b
#define Del 0x53
#define Home 0x47
#define End 0x4f
#define Space 0x20
#define Up 0x48
#define Down 0x50
#define Left 0x4b
#define Right 0x4d
#define Enter 0x0d
#define F2 0x3c
#define F3 0x3d
#define STACK_INIT_SIZE 200
#define STACKINCREMENT 10
typedef int Boolean;
typedef int Status;
typedef struct {
int x;
int y;
} PosType;
typedef struct {
int ord;
PosType seat;
int di;
} SElemType;
typedef struct {
int td;
int foot;
int mark;
} MazeType;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} Stack;
int Maze[20][30];
MazeType maze[20][30];
PosType StartPlace;
PosType EndPlace;
int count;
int m,n;
Boolean b_start=FALSE,b_end=FALSE;
void CreatMaze(void);
Status SaveMaze(char *filename);
Status LoadMaze(char *filename);
void Error(char *message);
Status InitStack(Stack *s);
Status DestroyStack(Stack *s);
Status ClearStack(Stack *s);
Boolean StackEmpty(Stack *s);
int StackLength(Stack *s);
Status Push(Stack *s,SElemType e);
SElemType Pop(Stack *s,SElemType e);
Status GetTop(Stack *s,SElemType *e);
Status StackTraverse(Stack *s,Status (* visit)(SElemType *se));
Boolean Pass(PosType curpos);
void MarkPrint(PosType seat);
void FootPrint(PosType curpos);
PosType NextPos(PosType seat,int di);
Status MazePath(PosType start,PosType end);
void CreatMaze(void)
/* Form the maze. */
{
void Error(char *message);
Status SaveMaze(char *filename);
Status LoadMaze(char *filename);
int i,j;
int x,y;
char c;
char savename[12],loadname[12];
Boolean flag=FALSE,load=FALSE;
clrscr();
printf("Menu:\n\n");
printf("1.Load Mazefile:(*.dd)\n\n");
printf("2.Input Maze:\n\n");
printf("Input your choice: ");
do
{
c=getch();
switch(c)
{
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''); break;
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''); break;
case Esc: sleep(1); exit(1);
default: break;
}
}
while(c!=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''&&c!=''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''') ;
if(c==''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''')
{
printf("\n\nLoadName: ");
scanf("%s",loadname);
if(LoadMaze(loadname))
{
sleep(1); load=TRUE;
}
else { gotoxy(1,9); printf("Load fail! "); }
}
if(!load)
{
printf("\nInput the maze''''''''''''''''''''''''''''''''s size:\n");
printf("\nInput Length :\n");
scanf("%d",&m);
printf("\nInput Width :\n");
scanf("%d",&n);
if(m<4||n<4) Error("Input");
if(m>30||n>20) Error("Maze too large");
for(i=0;i<30;i++)
for(j=0;j<20;j++)
Maze[j][i]=2;
StartPlace.x=0;
StartPlace.y=0;
EndPlace.x=0;
EndPlace.y=0;
clrscr();
printf("\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf(" #");
Maze[i-1][j-1]=0;
}
printf("\n");
}
}
gotoxy(65,5);
printf("''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''':Wall");
gotoxy(65,7);
printf("Start:Home");
gotoxy(65,9);
printf("End:End");
gotoxy(65,11);
printf("Delete Wall:Del");
gotoxy(65,13);
printf("Enter Wall:Enter");
gotoxy(65,15);
printf("Save Maze:F2");
gotoxy(65,17);
printf("Complete:F9");
gotoxy(65,19);
printf("Exit:Esc");
gotoxy(4,3);
x=4;y=3;
do
{
c=getch();
switch(c)
{
case Up: if(y>3) { y--; gotoxy(x,y); }
break;
case Down: if(y<n) { y++; gotoxy(x,y); }
break;
case Left: if(x>4) { x-=2; gotoxy(x,y); }
break;
case Right: if(x<2*m-2) { x+=2; gotoxy(x,y); }
break;
case Del: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) b_start=FALSE;
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) b_end=FALSE;
putch('''''''''''''''''''''''''''''''' ''''''''''''''''''''''''''''''''); Maze[y-2][x/2-1]=1; gotoxy(x,y);
break;
case Enter: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) break;
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) break;
putch(''''''''''''''''''''''''''''''''#''''''''''''''''''''''''''''''''); Maze[y-2][x/2-1]=0; gotoxy(x,y);
break;
case Home: if(Maze[y-2][x/2-1]&&!b_start)
{
StartPlace.x=x/2-1;
StartPlace.y=y-2;
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''');
gotoxy(x,y);
b_start=TRUE;
}
break;
case End: if(Maze[y-2][x/2-1]&&!b_end)
{
EndPlace.x=x/2-1;
EndPlace.y=y-2;
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''');
gotoxy(x,y);
b_end=TRUE;
}
break;
case Esc: gotoxy(2,22); printf("exit"); sleep(1); exit(1);
case F9: if(b_start&&b_end) flag=TRUE; break;
case F2: gotoxy(2,22);
printf("Savename:");
scanf("%s",savename);
gotoxy(2,22);
if(SaveMaze(savename)) printf("Save OK! ");
else printf("Save fail! ");
sleep(1);
gotoxy(2,22);
printf(" ");
gotoxy(x,y);
break;
default: break;
}
}
while(!flag);
for(i=0;i<30;i++)
for(j=0;j<20;j++)
{
maze[j][i].td=Maze[j][i];
maze[j][i].mark=0;
maze[j][i].foot=0;
}
}
Status LoadMaze(char *file)
/* The maze has been loaded. */
{
FILE *fp;
char *buffer;
char ch;
int i=0,j,k;
Boolean len=FALSE,wid=FALSE;
if((fp=fopen(file,"r"))==NULL)
return ERROR;
buffer=(char *)malloc(600*sizeof(char));
ch=fgetc(fp);
while(ch!=EOF)
{
buffer[i]=ch;
i++;
ch=fgetc(fp);
}
m=30;n=20;
for(i=0;i<600;i++)
{
j=i/30; k=i%30;
if(buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!len){ m=i; len=TRUE; }
if(k==0&&buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!wid){ n=j; wid=TRUE; }
switch(buffer[i])
{
case ''''''''''''''''''''''''''''''''0'''''''''''''''''''''''''''''''': Maze[j][k]=0; break;
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': Maze[j][k]=1; break;
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': Maze[j][k]=2; break;
case ''''''''''''''''''''''''''''''''3'''''''''''''''''''''''''''''''': Maze[j][k]=1;
StartPlace.x=k;
StartPlace.y=j;
b_start=TRUE;
break;
case ''''''''''''''''''''''''''''''''4'''''''''''''''''''''''''''''''': Maze[j][k]=1;
EndPlace.x=k;
EndPlace.y=j;
b_end=TRUE;
break;
default : break;
}
}
fclose(fp);
clrscr();
for(i=0;i<30;i++)
for(j=0;j<20;j++)
{
maze[j][i].td=Maze[j][i];
maze[j][i].foot=0;
maze[j][i].mark=0;
if(Maze[j][i]==0)
{
gotoxy(2*i+2,j+2);
putch(''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''');
}
}
gotoxy(2*StartPlace.x+2,StartPlace.y+2);
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''');
gotoxy(2*EndPlace.x+2,EndPlace.y+2);
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''');
return OK;
}
Status SaveMaze(char *filename)
/* The maze has been saved. */
{
FILE *fp;
char *buffer;
int i,j,k;
fp=fopen(filename,"wb");
buffer=(char *)malloc(600*sizeof(char));
for(i=0;i<600;i++)
{
j=i/30; k=i%30;
switch(Maze[j][k])
{
case 0: buffer[i]=''''''''''''''''''''''''''''''''0''''''''''''''''''''''''''''''''; break;
case 1: buffer[i]=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''; break;
case 2: buffer[i]=''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''; break;
default : Error("Write"); break;
}
if(k==StartPlace.x&&j==StartPlace.y) buffer[i]=''''''''''''''''''''''''''''''''3'''''''''''''''''''''''''''''''';
if(k==EndPlace.x&&j==EndPlace.y) buffer[i]=''''''''''''''''''''''''''''''''4'''''''''''''''''''''''''''''''';
}
fwrite(buffer,600,1,fp);
free(buffer);
fclose(fp);
return OK;
}
void Error(char *message)
{
clrscr();
fprintf(stderr,"Error:%s\n",message);
exit(1);
} /* Error */
Status InitStack(Stack *s)
/* The stack s has been created and is initialized to be empty. */
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s->base) Error("Overflow");
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
return OK;
} /* InitStack */
Status DestroyStack(Stack *s)
/* The stack s has been destroyed. */
{
s->top=NULL;
s->stacksize=0;
free(s->base);
s->base=NULL;
return OK;
} /* DestroyStack */
Status ClearStack(Stack *s)
/* The stack has been clear to be maximum. */
{
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
return OK;
} /* ClearStack */
Boolean StackEmpty(Stack *s)
/* Check if the stack s is empty. */
{
if(s->top==s->base) return TRUE;
else return FALSE;
} /* StackEmpty */
int StackLength(Stack *s)
/* Gain the length of the stack s. */
{
if(s->top>s->base) return (int)(s->top-s->base);
else return 0;
} /* StackLength */
Status Push(Stack *s,SElemType e)
/* The element e has been pushed into the stack s. */
{
if(s->top-s->base>=s->stacksize)
{
s->base=(SElemType *)realloc(s->base,
(s->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!s->base) Error("Overflow");
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
return OK;
} /* Push */
SElemType Pop(Stack *s,SElemType e)
/* The element e has been removed from the stack s. */
{
if(s->top==s->base) Error("Pop");
e=*--s->top;
return e;
} /* Pop */
Status GetTop(Stack *s,SElemType *e)
/* The element e has got to the top of the stack s.*/
{
if(s->top==s->base) Error("GetTop");
*e=*(s->top-1);
return OK;
} /* GetTop */
/* Traverse the stack s using ''''''''''''''''''''''''''''''''visiting'''''''''''''''''''''''''''''''' function. */
/* Status StackTraverse(Stack *s,Status (* visit)(SElemType *se))
{
SElemType p;
int result;
if(s->top==s->base) return ERROR;
p=s->base;
while(!(p==s->top))
{
result=(*visit)(p);
p++;
}
return OK;
} */
Boolean Pass(PosType curpos)
/* Check if the current position can be passed. */
{
if(maze[curpos.x][curpos.y].td==1&&
maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0)
return TRUE;
else return FALSE;
} /* Pass */
void MarkPrint(PosType seat)
/* Mark the position seat. */
{
maze[seat.x][seat.y].mark=-1;
/* Marking ''''''''''''''''''''''''''''''''-1'''''''''''''''''''''''''''''''' symbolize the current position cannot be put. */
} /* MarkPrint */
void FootPrint(PosType curpos)
/* The foot of the curpos of the maze has been set ''''''''''''''''''''''''''''''''true''''''''''''''''''''''''''''''''. */
{
maze[curpos.x][curpos.y].foot=1;
} /* FootPrint */
PosType NextPos(PosType seat,int di)
{
switch(di)
{
case 1: seat.y++; return seat; /* Eastward */
case 2: seat.x++; return seat; /* Southward */
case 3: seat.y--; return seat; /* Westward */
case 4: seat.x--; return seat; /* Northward */
default: seat.x=0; seat.y=0; return seat;
}
} /* NextPos */
/* The key to the program. */
/* Pre: The maze array & the startplace & the endplace.
Post: Find the one traverse of the maze and perform the mazepath.
Uses: The ADT stack class.
*/
Status MazePath(PosType start,PosType end)
{
PosType curpos;
int curstep;
SElemType e;
Stack *s,stack;
stack.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!stack.base) Error("Overflow");
stack.top=stack.base;
stack.stacksize=STACK_INIT_SIZE;
s=&stack;
curpos=start;
curstep=1;
do
{
if(Pass(curpos))
{
FootPrint(curpos);
e.ord=curstep; e.seat=curpos; e.di=1;
gotoxy((curpos.y+1)*2,curpos.x+2);
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''');
delay(8000); /* pospone time. */
Push(s,e);
if(curpos.x==end.x&&curpos.y==end.y) /* Proceed recursively. */
{
DestroyStack(s);
return TRUE;
}
curpos=NextPos(curpos,1); /* Try next position. */
curstep++;
}
else
{
if(!StackEmpty(s))
{
e=Pop(s,e); /* Removed e from s. */
while(e.di==4&&!StackEmpty(s)) /* Four directions have been checked
and s is not empty. */
{
MarkPrint(e.seat);
gotoxy((e.seat.y+1)*2,e.seat.x+2);
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''');
delay(8000); /* Pospone time. */
gotoxy((e.seat.y+1)*2,e.seat.x+2);
putch('''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''');
e=Pop(s,e); /* Remove e from s. */
curstep--;
}
if(e.di<4) /* The current position hasnot been checked. */
{
e.di++;
Push(s,e); /* Insert e into s. */
curpos=NextPos(e.seat,e.di); /* Try next position. */
}
}
}
}
while(!StackEmpty(s));
DestroyStack(s);
return FALSE;
} /* MazePath */
void main()
{
PosType start,end;
CreatMaze();
start.x=StartPlace.y;
start.y=StartPlace.x;
end.x=EndPlace.y;
end.y=EndPlace.x;
if(MazePath(start,end))
{
gotoxy(2,22);
printf("Path found\n");
}
else
{
gotoxy(2,22);
printf("Path not found\n");
}
getch();
clrscr();
}
