maze.cpp

迷宫探险算法

void Maze::GenerateMaze()
{
	int w,n,e,s;
	direction dir;
	Point pos(rand()%width,rand()%height);
	TwoDimensionArray temp(width,height);
	temp.Set(pos.x,pos.y,1); /* mark the position */
	for (;;)
	{
		pos=FindExtendablePosition(temp);

		if (pos.x==-1&&pos.y==-1) break; /* constructing maze complete */
		for (;;)
		{

			w=ExtendableInDir(temp,pos, west);
			n=ExtendableInDir(temp,pos,north);
			e=ExtendableInDir(temp,pos, east);
			s=ExtendableInDir(temp,pos,south);
			dir=RandDirection(w,n,e,s);

			switch(dir)
			{
			case  west:
				pos.x-=1;
				maze.Set(pos.x,pos.y,2);
				break;
			case north:
				pos.y-=1;
				maze.Set(pos.x,pos.y,1);
				break;
			case  east:
				if (maze.Get(pos.x,pos.y)==0)
					maze.Set(pos.x,pos.y,2);
				else
					maze.Set(pos.x,pos.y,3);
					pos.x+=1;
				break;
			case south:

				if (maze.Get(pos.x,pos.y)==0)
					maze.Set(pos.x,pos.y,1);
				else
					maze.Set(pos.x,pos.y,3);
				pos.y+=1;
			}
			temp.Set(pos.x,pos.y,1); /* mark the position */
			if (!Extendable(temp,pos))
				break;
		}
	}
}

void Maze::GeneratePath()
{
	Point cur=start;
	int success=0;
	path.Set(cur.x,cur.y,1); /* mark start position */
	DetectPath(path,cur,success);

}
void Maze::DetectPath(TwoDimensionArray & ta,Point & cur,int & success)
{
	if (cur.x==end.x&&cur.y==end.y)
	{
		success=1;
		return;
	}
	if (cur.x>0 && (maze.Get(cur.x-1,cur.y) & 0x2) && (ta.Get(cur.x-1,cur.y)==0)) /* west */
	{
		cur.x-=1;
		ta.Set(cur.x,cur.y,1);
		DetectPath(ta,cur,success);
		if (success) return;
		ta.Set(cur.x,cur.y,0);
		cur.x+=1;
	}
	if (cur.y>0 && (maze.Get(cur.x,cur.y-1) & 0x1) && (ta.Get(cur.x,cur.y-1)==0)) /* north */
	{
		cur.y-=1;
		ta.Set(cur.x,cur.y,1);
		DetectPath(ta,cur,success);
		if (success) return;
		ta.Set(cur.x,cur.y,0);
		cur.y+=1;
	}
	if ((maze.Get(cur.x,cur.y) & 0x2) && (ta.Get(cur.x+1,cur.y)==0)) /* east */
	{
		cur.x+=1;
		ta.Set(cur.x,cur.y,1);
		DetectPath(ta,cur,success);
		if (success) return;
		ta.Set(cur.x,cur.y,0);
		cur.x-=1;
	}
	if ((maze.Get(cur.x,cur.y) & 0x1) && (ta.Get(cur.x,cur.y+1)==0)) /* south */
	{
		cur.y+=1;
		ta.Set(cur.x,cur.y,1);
		DetectPath(ta,cur,success);
		if (success) return;
		ta.Set(cur.x,cur.y,0);
		cur.y-=1;
	}
}
void DrawSize(int width,int height)
{
	int left=textwidth(prompt2)+24;
	char w[]="Width:";
	char h[]=" Height:";
	char buffer[8];
	setfillstyle(SOLID_FILL,BGCOLOR);
	bar(left,472,left+textwidth(w)+textwidth(h)+textwidth(" ")*6,479);
	settextjustify(LEFT_TEXT,CENTER_TEXT);
	setcolor(GREEN);
	outtextxy(left,476,w);
	sprintf(buffer,"%3d",width);
	left+=textwidth(w);
	setcolor(BGCOLOR);
	outtextxy(left,476,"   ");
	setcolor(YELLOW);
	outtextxy(left,476,buffer);
	left+=textwidth(buffer);
	setcolor(GREEN);
	outtextxy(left,476,h);
	left+=textwidth(h);
	setcolor(BGCOLOR);
	outtextxy(left,476,"   ");
	sprintf(buffer,"%3d",height);
	setcolor(YELLOW);
	outtextxy(left,476,buffer);
}
void Draw()
{
	int style,size;
	settextjustify(CENTER_TEXT, CENTER_TEXT);
	cleardevice();
	size = 1;
	style=TRIPLEX_FONT;
	settextstyle(style, HORIZ_DIR, size);
	outtextxy(320,9,caption);
	style=DEFAULT_FONT;
	settextstyle(style, HORIZ_DIR, size);
	settextjustify(LEFT_TEXT, CENTER_TEXT);
	outtextxy(24,467,prompt1);
	outtextxy(24,476,prompt2);
}
void DrawMaze(const Maze & m)
{
	int style,size,i,j,border;
	int mw,mh,left,top;
	setfillstyle(SOLID_FILL,BGCOLOR);
	bar(0,24,639,456);
	mw=m.GetWidth();
	mh=m.GetHeight();
	left=LEFT;
	top=TOP;
	setcolor(MAZECOLOR);
	line(left,top,left+mw*MAZE_CELL_SIZE,top);
	line(left,top,left,top+mh*MAZE_CELL_SIZE);
	for (j=0;j<mh;j++)
		for (i=0;i<mw;i++)
		{
			border=m.GetMaze(i,j);
			border=~border;
			if ( border & 0x1) /* bottom */
				line(left+(i+0)*MAZE_CELL_SIZE,
					top+(j+1)*MAZE_CELL_SIZE,
					left+(i+1)*MAZE_CELL_SIZE,
					top+(j+1)*MAZE_CELL_SIZE);
			if ( border & 0x2) /* right */
				line(left+(i+1)*MAZE_CELL_SIZE,
					top+(j+0)*MAZE_CELL_SIZE,
					left+(i+1)*MAZE_CELL_SIZE,
					top+(j+1)*MAZE_CELL_SIZE);
		}
}

void DrawPath(const Maze & m)
{
	int i,j;
	int mw,mh,left,top;
	mw=m.GetWidth();
	mh=m.GetHeight();
	left=LEFT;
	top=TOP;

	setcolor(PATHCOLOR);
	for (j=0;j<mh;j++) /* horz */
		for (i=0;i<mw-1;i++)
		{
			if (m.GetPath(i,j)&&m.GetPath(i+1,j)&& (m.GetMaze(i,j) & 0x2 ) )
				line(left+(i+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					top+(j+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					left+(i+1)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					top+(j+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
		}
	for (j=0;j<mh-1;j++)
		for (i=0;i<mw;i++)
		{
			if (m.GetPath(i,j)&&m.GetPath(i,j+1)&& (m.GetMaze(i,j) & 0x1 ) )
				line(left+(i+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					top+(j+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					left+(i+0)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
					top+(j+1)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
		}
}

int TraceMaze(TwoDimensionArray & tr,Point & cur,const Maze & m,direction dir)
{
	int left,top;
	left=(639-m.GetWidth()*MAZE_CELL_SIZE)/2;
	top=(479-m.GetHeight()*MAZE_CELL_SIZE)/2+2;;
	switch(dir)
	{
	case west:
		if (cur.x>0 && (m.GetMaze(cur.x-1,cur.y) & 0x2))
		{
			if (tr.Get(cur.x-1,cur.y)==0)
			{
				tr.Set(cur.x-1,cur.y,1);
				setcolor(TRACECOLOR);
			}
			else
			{
				tr.Set(cur.x,cur.y,0);
				setcolor(BADCOLOR);
			}
			line(left+((cur.x-1))*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
			cur.x-=1;
		}
		break;
	case north:
		if (cur.y>0 && (m.GetMaze(cur.x,cur.y-1) & 0x1))
		{
			if (tr.Get(cur.x,cur.y-1)==0)
			{
				tr.Set(cur.x,cur.y-1,1);
				setcolor(TRACECOLOR);
			}
			else
			{
				tr.Set(cur.x,cur.y,0);
				setcolor(BADCOLOR);
			}
			line(left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+(cur.y-1)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
			cur.y-=1;
		}
		break;
	case east:
		if (cur.x<m.GetWidth() && (m.GetMaze(cur.x,cur.y) & 0x2))
		{
			if (tr.Get(cur.x+1,cur.y)==0)
			{
				tr.Set(cur.x+1,cur.y,1);
				setcolor(TRACECOLOR);
			}
			else
			{
				tr.Set(cur.x,cur.y,0);
				setcolor(BADCOLOR);
			}
			line(left+(cur.x+1)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
			cur.x+=1;
		}
		break;
	case south:
		if (cur.y<m.GetHeight() && (m.GetMaze(cur.x,cur.y) & 0x1))
		{
			if (tr.Get(cur.x,cur.y+1)==0)
			{
				tr.Set(cur.x,cur.y+1,1);
				setcolor(TRACECOLOR);
			}
			else
			{
				tr.Set(cur.x,cur.y,0);
				setcolor(BADCOLOR);
			}
			line(left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+(cur.y+1)*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				left+cur.x*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2,
				top+cur.y*MAZE_CELL_SIZE+MAZE_CELL_SIZE/2);
			cur.y+=1;
		}
		break;
	}
	if (cur.x==m.GetEnd().x&&cur.y==m.GetEnd().y)
	{
		sound(700);
		delay(100);
		nosound();
		return 1;
	}
	return 0;
}


int main(void)
{
	int mazewidth=8,mazeheight=6,success=0;
	int oldw,oldh;
	randomize();
	TwoDimensionArray trace(mazewidth,mazeheight);
	Point cur(0,0);
	Maze m(mazewidth,mazeheight);
	int i,j,key;



	trace.Set(0,0,1);

	Draw();
	DrawMaze(m);
	DrawSize(m.GetWidth(),m.GetHeight());
	for(;;)
	{
		oldw=mazewidth;
		oldh=mazeheight;
		while (bioskey(1)==0);
		key=bioskey(0);
		switch(key)
		{
		case ESC:
			goto exit;
		case F1:
			DrawPath(m);
			break;
		case F2:
			m.SetSize(mazewidth,mazeheight);
		case F3:
			DrawMaze(m);
			trace.SetSize(mazewidth,mazeheight);
			trace.Set(0,0,1);
			cur.x=0;
			cur.y=0;
			success=0;
			break;
		case HOME:
			if (mazewidth>2) mazewidth--;
			break;
		case END:
			if (mazewidth<MAZE_MAX_WIDTH) mazewidth++;
			break;
		case PAGEUP:
			if (mazeheight>2) mazeheight--;
			break;
		case PGDOWN:
			if (mazeheight<MAZE_MAX_HEIGHT) mazeheight++;
			break;
		case LEFTKEY:
			if (!success)
				success=TraceMaze(trace,cur,m,west);
			break;
		case UPKEY:
			if (!success)
				success=TraceMaze(trace,cur,m,north);
			break;
		case RIGHTKEY:
			if (!success)
				success=TraceMaze(trace,cur,m,east);
			break;
		case DOWNKEY:
			if (!success)
				success=TraceMaze(trace,cur,m,south);
			break;
		}
		if (oldw!=mazewidth||oldh!=mazeheight)
			DrawSize(mazewidth,mazeheight);
	}
	exit:

	return 0;
}