maze.cpp

迷宫算法,一个利用堆栈和回溯算法实现的自动寻路程序

// Maze.cpp: implementation of the CMaze class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "zty.h"
#include "Maze.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMaze::CMaze()
{
	for(int i=0;i<28;i++)
		for(int j=0;j<20;j++)
			map[i][j]=0;

	curdi=0;		//一个方向也没试
	top=-1;			//栈顶指向空
}

CMaze::~CMaze()
{

}

void CMaze::Init()
{
	for(int i=0;i<28;i++)
		for(int j=0;j<20;j++)
			map[i][j]=0;
}

int CMaze::Go()
{
	if(CanGo())
	{
		//留下足迹
		map[curpos.x][curpos.y]=2;
		//压入栈
		e.point=curpos;
		e.di=curdi;
		top+=1;
		s[top]=e;
		//判断
		if(curpos.x==end.x&&curpos.y==end.y)
			return 2;
		else
		{
			prepos=curpos;
			//curpos=nextpos(curpos,curdi);
			switch(curdi)
			{
			case 1:
				curpos.y--;
				break;
			case 2:
				curpos.x++;
				break;
			case 3:
				curpos.y++;
				break;
			case 4:
				curpos.x--;
				break;
			}
			return 1;
		}
	}

	else			//curdi=0
	{
		if(top!=-1)
		{
			//出栈
			e=s[top];
			top--;
			//设定当前位置为栈顶位置的坐标

			map[curpos.x][curpos.y]=2;

			prepos=curpos;
			curpos=e.point;

			return 1;
		/*	while(e.di==4&&top!=0)
			{
				map[e.point.x][e.point.y]=2;
				top--;
				e=s[top];
			}
			if(e.di<4)
			{
				e.di++;
				top++;
				s[top]=e;

				//curpos=nextpos(e.point,e.di);
				switch(e.di)
				{
				case 1:
					curpos.x=e.point.x+1;
					curpos.y=e.point.y;
					break;
				case 2:
					curpos.x=e.point.x;
					curpos.y=e.point.y+1;
					break;
				case 3:
					curpos.x=e.point.x-1;
					curpos.y=e.point.y;
					break;
				case 4:
					curpos.x=e.point.x;
					curpos.y=e.point.y-1;
					break;
				}
				return 1;
			}
			else
				return 0;		//回到起点了

			*/
		}
		else
				return 0;		//回到起点了	

	}

}

BOOL CMaze::CanGo()
{
	int x=curpos.x;
	int y=curpos.y;

	//判断条件有：1.无障碍2.没走过3.没到边界
	if(map[x][y-1]!=1&&map[x][y-1]!=2&&(y-1)!=-1)		//向上走
	{
		curdi=1;
		return TRUE;
	}
	else
	{
		if(map[x+1][y]!=1&&map[x+1][y]!=2&&(x+1)!=28)
		{
			curdi=2;
			return TRUE;
		}
		else
		{
			if(map[x][y+1]!=1&&map[x][y+1]!=2&&(y+1)!=20)
			{
				curdi=3;
				return TRUE;
			}
			else
			{
				if(map[x-1][y]!=1&&map[x-1][y]!=2&&(x-1)!=-1)
				{
					curdi=4;
					return TRUE;
				}
				else			//无路可走
					curdi=0;
					return FALSE;
			}
		}
	}
}

int* CMaze::GetPath()
{

	int *a;
	return a;
}