maze.cpp

迷宫探险算法

#include <graphics.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <bios.h>
#include <dos.h>

#define MAZE_MAX_WIDTH  48
#define MAZE_MAX_HEIGHT 36
#define MAZE_TOP        24
#define MAZE_CENTER    320
#define MAZE_CELL_SIZE  12
#define LEFT (639-mw*MAZE_CELL_SIZE)/2;
#define TOP	 (479-mh*MAZE_CELL_SIZE)/2+2;
#define BGCOLOR     BLACK
#define MAZECOLOR   WHITE
#define PATHCOLOR  YELLOW
#define TRACECOLOR  GREEN
#define BADCOLOR      RED

#define ESC      283
#define F1     15104
#define F2     15360
#define F3     15616
#define HOME   18176
#define END    20224
#define PAGEUP 18688
#define PGDOWN 20736
#define LEFTKEY  19200
#define UPKEY    18432
#define RIGHTKEY 19712
#define DOWNKEY  20480

char caption[]="Maze 2002  http://shchenchang.top263.net";
char prompt1[]="F1=Show Path  F2=New Maze  F3=Redraw Maze  ArrowKeys=Move  Esc=Exit";
char prompt2[]="Home/End=Change Width  PageUp/PageDown=Change Height  ";

enum direction {west,north,east,south};

class Point
{
public:
	int x,y;
	Point();
	~Point(){}
	Point(int,int);
	Point & operator=(const Point &);
};
Point::Point()
{
	x=y=0;
}
Point::Point(int ax,int ay)
{
	x=ax;
	y=ay;
}
Point & Point::operator=(const Point &p)
{
	x=p.x;
	y=p.y;
	return *this;
}

class TwoDimensionArray
{
private:
	int width,height;
	int **pM,*spM;
	void Clear();
public:
	TwoDimensionArray();
	TwoDimensionArray(int,int);
	~TwoDimensionArray();
	int SetSize(int,int);
	int Get(int,int) const ;
	int Set(int,int,int);
	int GetWidth() const {return width;}
	int GetHeight() const {return height;}
};
TwoDimensionArray::TwoDimensionArray()
{
	width=height=0;
	spM=NULL;
	pM=NULL;
}
TwoDimensionArray::~TwoDimensionArray()
{
	Clear();
}
int TwoDimensionArray::SetSize(int w,int h)
{
	int i,j;
	Clear();
	width=w;
	height=h;
	spM=new int[w*h];
	if (spM==NULL)
	{
		printf("Not enough memory!\n");
		exit(1);
		return 0;
	}
	pM=new int* [w];
	if (pM==NULL)
	{
		delete []spM;
		printf("Not enough memory!\n");
		exit(1);
		return 0;
	}
	for (j=0;j<w;j++)
		pM[j]=spM+j*h;
	for (i=0;i<w;i++)
		for (j=0;j<h;j++)
			pM[i][j]=0;

	return 1;
}
TwoDimensionArray::TwoDimensionArray(int w,int h):spM(NULL),pM(NULL)
{
	SetSize(w,h);
}
void TwoDimensionArray::Clear()
{
	if (pM!=NULL)
		delete []pM;
	if (spM!=NULL)
		delete []spM;
	width=height=0;
}
int TwoDimensionArray::Get (int x,int y) const
{
	return pM[x][y];
}
int TwoDimensionArray::Set(int x,int y,int v)
{
	pM[x][y]=v;
	return v;
}


class Graph
{
public:
	Graph();
	~Graph();
};
Graph G;
Graph::Graph()
{
	int gdriver = VGA, gmode=VGAHI, errorcode;

	errorcode = registerbgidriver(EGAVGA_driver);

	/* report any registration errors */
	if (errorcode < 0)
	{
		printf("Graphics error: %s\n", grapherrormsg(errorcode));
		printf("Press any key to halt:");
		getch();
		exit(1); /* terminate with an error code */
	}
	errorcode = registerbgifont(triplex_font);
	/* report any registration errors */
	if (errorcode < 0)
	{
		printf("Graphics error: %s\n", grapherrormsg(errorcode));
		printf("Press any key to halt:");
		getch();
		exit(1); /* terminate with an error code */
	}


   /* initialize graphics mode */
   initgraph(&gdriver, &gmode, "e:\\tc\\bgi");

   /* read result of initialization */
   errorcode = graphresult();

   if (errorcode != grOk)  /* an error occurred */
   {
	  printf("Graphics error: %s\n", grapherrormsg(errorcode));
	  printf("Press any key to halt:");
	  getch();
	  exit(1);             /* return with error code */
   }

}
Graph::~Graph()
{
	closegraph();
}

class Maze
{
private:
	int width,height;
	Point start,end;
	TwoDimensionArray maze,path;
	int ExtendableInDir(const TwoDimensionArray &,const Point &,direction);
	int Extendable(const TwoDimensionArray &,const Point &);
	Point FindExtendablePosition(const TwoDimensionArray &);
	direction RandDirection(int,int,int,int);
	void GenerateMaze();
	void GeneratePath();
	void DetectPath(TwoDimensionArray &,Point &,int &);

public:
	Maze();
	Maze(int,int);
	int SetSize(int,int);
	void SetStart(const Point &);
	void SetEnd(const Point &);
	const Point & GetStart() const;
	const Point & GetEnd() const;

	int GetMaze(int,int) const;
	int GetPath(int,int) const;
	int GetWidth() const{return width;}
	int GetHeight()const{return height;}
};
Maze::Maze()
{
	width=height=0;
}
int Maze::GetMaze(int x,int y) const
{
	return maze.Get(x,y);
}
int Maze::GetPath(int x,int y) const
{
	return path.Get(x,y);
}
int Maze::SetSize(int w,int h)
{
	int i;
	if (w<=1||h<=1)
	{
		printf("Meanless size!");
		return 0;
	}
	if (w>MAZE_MAX_WIDTH)
	{
		printf("Width is too large!");
		return 0;
	}
	if (h>MAZE_MAX_HEIGHT)
	{
		printf("Height is too large!");
		return 0;
	}
	width=w;
	height=h;
	start.x=0;
	start.y=0;  /* entrance of the maze is at upper left corner */
	end.x=w-1;
	end.y=h-1;  /* exit of the maze is at lower right corner */
	maze.SetSize(w,h);
	path.SetSize(w,h);

	GenerateMaze();
	GeneratePath();


	return 1;
}
Maze::Maze(int w,int h)
{
	SetSize(w,h);
}

void Maze::SetStart(const Point &p)
{
	start=p;
}
void Maze::SetEnd(const Point &p)
{
	end=p;
}
const Point & Maze::GetStart() const
{
	return start;
}
const Point & Maze::GetEnd() const
{
	return end;
}

int Maze::ExtendableInDir(const TwoDimensionArray & ta,const Point & p,direction dir)
{
	switch (dir)
	{
	case west:
		if (p.x>0 && (ta.Get(p.x-1,p.y)==0))
			return 1;
		return 0;
	case north:
		if (p.y>0 && (ta.Get(p.x,p.y-1)==0))
			return 1;
		return 0;
	case east:
		if (p.x<(ta.GetWidth()-1) && (ta.Get(p.x+1,p.y)==0))
			return 1;
		return 0;
	default: /* south */
		if (p.y<(ta.GetHeight()-1) && (ta.Get(p.x,p.y+1)==0))
			return 1;
	}
	return 0;
}

int Maze::Extendable(const TwoDimensionArray & ta,const Point & p)
{
	if ( ((ExtendableInDir(ta,p, west)) ||
		(ExtendableInDir(ta,p,north)) ||
		(ExtendableInDir(ta,p, east)) ||
		(ExtendableInDir(ta,p,south))) && ta.Get(p.x,p.y) )
		return 1;
	return 0;
}
Point Maze::FindExtendablePosition(const TwoDimensionArray & ta)
{
	int i,j,w,h,select;
	Point *tp,rp;
	int count=0;

	w=ta.GetWidth();
	h=ta.GetHeight();

	tp=new Point[w*h];

	for (i=0;i<w;i++)
		for (j=0;j<h;j++)
		{
			if ( Extendable(ta,Point(i,j)) )
			{
				tp[count].x=i;
				tp[count].y=j;
				count++;
			}
		}
	if (count==0)
		rp.x=rp.y=-1;
	else
	{
		select=rand()%count;
		rp=tp[select];
	}
	delete []tp;

	return rp;
}

direction Maze::RandDirection(int w,int n,int e,int s)
{
	direction dir[4];
	int count=0,select;
	if (e)
	{
		dir[count]=east;
		count++;
	}
	if (w)
	{
		dir[count]=west;
		count++;
	}
	if (s)
	{
		dir[count]=south;
		count++;
	}
	if (n)
	{
		dir[count]=north;
		count++;
	}


	select=rand()%count;
	return dir[select];
}