#include"stdafx.h"
#include"CreateMap.h"
#include<stdlib.h>  
#include<time.h>  
//====================================================================================
int		g_MazeWidth;		//迷宮地圖寬度
int		g_MazeHeight;		//迷宮地圖高度
int		g_MazeMap[MAX_MAZE_WIDTH+1][MAX_MAZE_HEIGHT+1]={0};	//迷宮地圖數(shù)組
//=======================迷宮地圖的隨機(jī)創(chuàng)建模塊==========================================================
typedef struct 
{
	int tag;   						//在數(shù)組里標(biāo)記的數(shù)字
	int x,y;						//在數(shù)組中的位置g_MazeMap[x][y];
	int vx,vy;  					//x,y的移動方向
	int step;   					//在一個方向上連續(xù)挖地圖的長度
	int maxX;						//x的最大值
	int maxY;						//y的最大值
}SDigMap;
//====================================================================
void ClearMap(int w,int h)//將表示迷宮地圖的數(shù)組置零
{
	g_MazeWidth=w;
	g_MazeHeight=h;
	int i,j;
	for(i=0;i<=w;i++)
		for(j=0;j<=h;j++)
		{
			g_MazeMap[i][j]=0;
		}
		srand(time(0));
}
//=====================================================================================
void DigIt(SDigMap *p)//將該處挖掉，即打標(biāo)記
{
	g_MazeMap[	p->x  ][ p->y  ] = p->tag;
}
//=====================================================================================
void Walk(SDigMap *p)//挖地圖的坐標(biāo)前移
{
	    p->x	+=	p->vx;
    	p->y	+=	p->vy; 
}
//=====================================================================================
int  IsNextDigged(int x,int y,int vx,int vy,SDigMap *p)//判斷下一個坐標(biāo)是否被給該對象挖掉
{
	if( g_MazeMap[	x + vx  ][ y + vy ]	==	p->tag ) return 1;
	else 	return 0;
}
//==========================================================================================
void HitWall(SDigMap *p)//挖地圖的坐標(biāo)如撞墻，則反向
{
	    if( p->x + p->vx < 1 || p->x + p->vx > p->maxX) 
			p->vx = -p->vx;
    	if( p->y + p->vy < 1 || p->y + p->vy > p->maxY)  
    		p->vy = -p->vy;
}
//======================================================================================
int  CanNextBeDigged(SDigMap *p)//檢測下一個點是否可以挖
{
	   int x = p->x + p->vx;
	   int y = p->y + p->vy;             //下一點的坐標(biāo)
       int vx = p->vy;					//與原方向轉(zhuǎn)彎的方向
       int vy = p->vx;
	   //判斷當(dāng)前點的下一個點的三個鄰點是否被自己挖過,如果被自己挖過，下一點不能挖了，否則把自己挖通了
       if( IsNextDigged( x, y, p->vx, p->vy, p ) ) return 0;//前一點是否被挖 
       if( IsNextDigged( x, y, vx, vy, p ) ) return 0;//左一點是否被挖 
       if( IsNextDigged( x, y, -vx, -vy, p ) )	return 0;//右一點是否被挖  
       return 1;		//周圍都沒被挖,看來可以被挖
}
//====================================================================================
void Jump(SDigMap *p)//跳過下一點，跳到下一點的周圍三個點上
{
    	int vx=p->vy;
    	int vy=p->vx;	//與原方向轉(zhuǎn)彎的兩個方向
 	    Walk(p);		//先走到下一點上
        if( IsNextDigged( p->x, p->y, p->vx, p->vy, p ) )  //前一點被挖,走過去
        {
        	Walk(p);   
        }
        else if(IsNextDigged( p->x, p->y, vx, vy, p ))  //左一點被挖,走過去
        {
           	p->x += vx;    
        	p->y += vy;   
        }
        else if(IsNextDigged( p->x, p->y, -vx, -vy, p))  //右一點被挖,走過去
        {
           	p->x -= vx;
        	p->y -= vy;  
        }
}
//=====================================================================================
int  IsLinked(SDigMap *p)//檢查是否挖通
{
       	int vx=p->vy;
       	int vy=p->vx;//與原方向轉(zhuǎn)彎的兩個方向
       	//如果改點的三個鄰點，既不是自身標(biāo)記又不是0，則該點被別的SDigMap挖過,既已經(jīng)挖通了
    	if( g_MazeMap[ p->x+vy ][ p->y+vx ] != p->tag && g_MazeMap[ p->x+vy ][p->y+vx ] !=0 )  return 1;  //前一個點是否被別的挖
    	if( g_MazeMap[ p->x+vx ][ p->y+vy ] != p->tag && g_MazeMap[ p->x+vx ][ p->y+vy ] != 0 ) return 1; //左一個點是否被別的挖	 
    	if( g_MazeMap[ p->x-vx ][ p->y-vy ] != p->tag && g_MazeMap[ p->x-vx ][ p->y-vy ] != 0 ) return 1;//右一個點是否被別的挖
    	return 0; 
}
//=====================================================================================
void RandomVxy(SDigMap *p)//產(chǎn)生隨機(jī)方向
{
	    int vx=p->vy;
    	int vy=p->vx;
		int k=rand()%50;
    	//將隨機(jī)數(shù)3個空間，原方向必將改變
    	if( 0<=k && k<10 )// 反方向的概率為發(fā)生轉(zhuǎn)彎的概率一半
    	{    p->vx = -vx;
    		p->vy = -vy;
    	} 
    	if( 10<=k && k<30 )//右向
    	{
     		p->vx = -vy;
    		p->vy = -vx;
    	} 
    	if( 30<=k && k<50 )//向左    
    	{
    		p->vx = vy;
    		p->vy = vx;
    	}
}
//=====================================================================================
int  ContinuouslyDig( SDigMap *p )//連續(xù)挖
{
    	int i=0; 
    	RandomVxy( p );//產(chǎn)生一個隨機(jī)方向
 		p->step =1+rand()%2;//隨機(jī)產(chǎn)生在該方向上挖的連續(xù)步長
    	while( i<p->step )
    	{
			 HitWall( p );  //首先檢測是否撞墻，如果撞墻方向取反
			 //對于下一點的三種策略:1走過 2走過去挖掉 3跳過去
			if(IsNextDigged(p->x,p->y,p->vx,p->vy,p))//檢測下一點是否被自己挖過
				Walk(p);//已經(jīng)被挖，走過去
			 else if( CanNextBeDigged( p ) )//沒有被挖，是否可以挖
				{
					Walk( p );//可以挖，走過去，
        			DigIt( p );//挖掉
        			if( IsLinked( p ) ) return 1;//如果挖通，跳出循環(huán)，并返回	
				}
			 else Jump( p );//不可以挖，跳過去	
			i++;
    	}
    	 return 0;
}
//=====================================================================================
int bSeed(int x,int y)//是否可以作為種子
{	//改點和四個鄰點都沒被挖，則可以從該點開始挖地圖
	if( g_MazeMap[x][y] != 0 )		return 0;
	if( g_MazeMap[x-1][y] != 0 )	return 0;
	if( g_MazeMap[x][y-1] != 0 )	return 0;
	if( g_MazeMap[x+1][y] != 0 )	return 0;
	if( g_MazeMap[x][y+1] != 0 )	return 0;
	return 1;
}
//=====================================================================================
void ImproveMap(int w,int h)//改善迷宮
{
	int		i,j;
	int 	tag=3;
	int		bLink=0;       //判斷地圖是否挖通
	//SDigMap:	tag	x	y	vx	vy	step	maxX	maxY
	SDigMap m={ 3,	1,	1,	1,	0,	1,		w-2,	h-2};//標(biāo)號為1，從坐標(biāo)（1，1）開始挖
	for( i=1; i<w-1; i++ )
		for( j=1; j<h-1; j++ )
		{
             if(bSeed( i, j )==1)
			 {
				m.tag=tag;
				m.x=i;
				m.y=j;
				tag++;
				DigIt(&m);
				bLink=0;
				while( !bLink )
                     bLink=ContinuouslyDig( &m );
			 }
		}
}
//=====================================================================================
void RandomExit(SDigMap *p,int w,int h,POINT* pExit)//pExit返回迷宮出口
{	//設(shè)置隨即出口，隨機(jī)出口位置可為左上角，坐下角，右上角
	int k=rand()%60;
	if( 0<=k && k<30 )//出口在左上角,概率最大
	{
		p->x=1;
		p->y=1;
		pExit->x=0;
		pExit->y=1;		
	}
	else if( 30<=k && k<45 )//左下角
	{
		p->x=1;
		p->y=h-2;
		pExit->x=0;
		pExit->y=h-2;		
	}
	else if( 45<=k && k<60 )//右上角
	{
		p->x=w-2;
		p->y=1;
		pExit->x=w-2;
		pExit->y=0;
	}
	g_MazeMap[pExit->x][pExit->y]=1;//先將迷宮出口挖掉
}
//========================================================================================
void CreateMap(int w,int h,POINT* pExit)//創(chuàng)建迷宮地圖,地圖大小為w*h,pExit返回出口坐標(biāo)
{
	//SDigMap:		tag		x		y		vx		vy		step	maxX		maxY
	SDigMap m1={ 	1,		1,		1,		1,		0,		1,		w-2,		h-2};//標(biāo)號為1，從坐標(biāo)（1，1）開始挖
	SDigMap m2={ 	2,		w-2,	h-2,	-1,		0,		1,		w-2,		h-2};//標(biāo)號為2，從坐標(biāo)（N，N）開始挖
	int		bLink=0;       //判斷地圖是否挖通
	ClearMap(w,h);//首先，全部清零			
	RandomExit(&m1,w,h,pExit);//隨機(jī)設(shè)置老鼠出口
	DigIt( &m1 );  	//初始點先挖掉    
	DigIt( &m2 );//老鼠在右下角
	while( !bLink )//從兩邊同時挖，先挖出從開始處到出口的通路
	{  
		bLink	=	ContinuouslyDig( &m1 );//從入口開始的挖圖對象，隨機(jī)方向，隨機(jī)步長，返回是否挖通
		if(!bLink)	bLink=ContinuouslyDig( &m2 );//從迷宮最深處開始的挖圖對像
	}
	ImproveMap(w,h);//改進(jìn)地圖，將大片沒被挖的地方，多挖出一些通道，讓地圖更加迷人,嘿嘿!
}